How do vectors work?

[HyperFlexed]

I realize my question totally abhors the black box model of programming, but I cannot deny my innate curiousity either. I can't seem to find the code to the vector class anywhere. I'm curious as to how it expands. I am trying to make a database engine for design practice, and I would like to apply the principle of expansion to my work. I figure learning how the Vector class works would allow me to emulate the behaviour without actually using the Vector class (because I have had a lot of trouble with the vector class ).

[wtd]

Perhaps you could expalain the problems you've had working with the Vector class.

The whole reason for Java's massive library is avoiding reinventing the wheel.

[HyperFlexed]

I don't want to reinvent the wheel, I'm just curious on how it works. DO you know where I can find the source to the Vector class?

The problem I was having was very odd. I was adding elements to my vector using add (), but when I would add an element the size would increase but all of the elements would be reassigned the pointer to the object I just put into the vector. I no longer have the source code though as I retrofitted the program to predict how many elements I would have in advance and make an appropriate array instead. This came at the cost of a much slower program (because my troubles with Vector brought my deadline too close to do a good job of the project)

[wtd]

I have no idea how you would determine that, but I suspect the mechanism is to reserve a certain amount of memory at the start, then expand it later if need be. The means by which this is done is not something the user is supposed to care about.

Are you certain you weren't just adding the same object to the vector?

Something like:

code:

SomeObjectType myVariable = new SomeObjectType(); Vector myVector = new Vector(); for each line in file {    myVariable.setSomething(doSomethingTo(line));    myVector.add(myVariable); }

[Hikaru79]

Here's the source to the java.util.Vector class. The whole Java standard library is distributed with the JDK, just look for a foldar named src.zip in the JDK directory.

I've attached the .java file Enjoy.

[HyperFlexed]

I think I figured out how it works.

code:

/**      * This implements the unsynchronized semantics of ensureCapacity.      * Synchronized methods in this class can internally call this      * method for ensuring capacity without incurring the cost of an      * extra synchronization.      *      * @see java.util.Vector#ensureCapacity(int)      */     private void ensureCapacityHelper(int minCapacity) {         int oldCapacity = elementData.length;         if (minCapacity > oldCapacity) {             Object[] oldData = elementData;             int newCapacity = (capacityIncrement > 0) ?                 (oldCapacity + capacityIncrement) : (oldCapacity * 2);             if (newCapacity < minCapacity) {                 newCapacity = minCapacity;             }             elementData = new Object[newCapacity];             System.arraycopy(oldData, 0, elementData, 0, elementCount);         }     }

It looks like it copies the old array to a larger one, and I guess the old array is freed from memory. Genius.

Also, I am curious about this part...

code:

public class Vector<E>     extends AbstractList<E>

what's with the E's in braces?

[Hikaru79]

HyperFlexed wrote:

Also, I am curious about this part...

code:

public class Vector<E>     extends AbstractList<E>

what's with the E's in braces?

Read up on Java generics at wtd's tutorial here.

[wtd]

It has to do with generics.

In Java 1.4, a Vector was simply "Vector", and held Objects. This means that you can add any type of Object to it. Since every class derives from Object, that basically means anything.

The problem with this arises when you want to get something out of the vector. You have to cast it back to the original type.

Java:

Vector myVector = new Vector(); myVector.add("hello"); System.out.println((String)myVector.elementAt(0));

That's all well and good, though perhaps the cast makes the syntax a bit clumsy. But... what happens if we add an Integer to the vector?

Java:

Vector myVector = new Vector(); myVector.add("hello"); myVector.add(new Integer(42)); System.out.println((String)myVector.elementAt(0)); System.out.println((String)myVector.elementAt(1));

Now we get a ClassCastException because we tried to cast an Integer to a String. If only the compiler had prevented us from including just any type of object.

That's what generics do.

Java:

Vector<String> myVector = new Vector<String>(); myVector.add("hello"); myVector.add(new Integer(42)); System.out.println(myVector.elementAt(0)); System.out.println(myVector.elementAt(1));

Now this fails to compile.

You'll also notice that I don't need a cast now.

[HyperFlexed]

So I guess this saves from repetative casting? I still don't quite grasp it... If it casts everything the object returns to the type you want I could have saved a lot of typing haha, I kept casting every time I took from the Vector.

[wtd]

It also protects you from inadvertantly adding an element of the wrong type.

And this is specific to 1.5. If you're using 1.4.2, then you're out of luck, and you have to do things the "old" way.