Vector vs ArrayList

[rick.huby]

I have used Vectors extensively in the past but recently came across
ArrayList on my travels.

Both seem to do pretty much the same thing. In the API's it says that
ArrayLists are not synchronised but Vectors are - what does this mean?
Also when would you use each one over the other?

 

[Ulf_N]

(e-mail address removed) skrev:

I have used Vectors extensively in the past but recently came across
ArrayList on my travels.

Both seem to do pretty much the same thing. In the API's it says that
ArrayLists are not synchronised but Vectors are - what does this mean?
Also when would you use each one over the other?

Good question. I too would like to know. I do know that Vector is thread
safe while ArrayList is not, and that Vector therefore is slightly
slower. But is it really that much slower? I seem to remember someone
from Sun saying (at a conference) that the difference is very slight
indeed... So, are there any *other* good reasons for using ArrayList
instead of Vector?
/ulf

 

[Paul Tomblin]

Both seem to do pretty much the same thing. In the API's it says that
ArrayLists are not synchronised but Vectors are - what does this mean?
Also when would you use each one over the other?

It means you should probably use Vector if your object might be operated
on by two threads at the same time. Otherwise, ArrayList is probably
(marginally) more efficient.

 

[Tor Iver Wilhelmsen]

It means you should probably use Vector if your object might be operated
on by two threads at the same time. Otherwise, ArrayList is probably
(marginally) more efficient.

But keep in mind Vector predates the Collection API that ArrayList is
part of, and has been "retrofitted" into it. For synchronized versions
of the collections, lokk at the relevant factory methods in the class
java.util.Collections.

 

[Paul Tomblin]

But keep in mind Vector predates the Collection API that ArrayList is
part of, and has been "retrofitted" into it. For synchronized versions

That was a concern when ArrayLists and the new Collection API first
appeared, because (if memory serves me correctly) Vector didn't have
iterator() and other Collection and List methods. But now it does, so I
don't see the harm in using a Vector rather than
Collections.synchronizedList(new ArrayList(...)) when you want a
synchronized list.

 

[Alun Harford]

(e-mail address removed) skrev:

Good question. I too would like to know. I do know that Vector is thread
safe while ArrayList is not, and that Vector therefore is slightly
slower. But is it really that much slower? I seem to remember someone
from Sun saying (at a conference) that the difference is very slight
indeed... So, are there any *other* good reasons for using ArrayList
instead of Vector?

public class Tester {
public static void main(String[] args) {
java.util.Random random = new java.util.Random();
long beginTime;
long endTime;

beginTime = System.currentTimeMillis();
java.util.ArrayList arrayList = new java.util.ArrayList();
for(int i=0;i<1<<20;i++) arrayList.add(new
Integer(random.nextInt()));
java.util.Collections.sort(arrayList);
endTime = System.currentTimeMillis();
long totalTimeArrayList= endTime-beginTime;


beginTime = System.currentTimeMillis();
java.util.Vector vector = new java.util.Vector();
for(int i=0;i<1<<20;i++) vector.add(new Integer(random.nextInt()));
java.util.Collections.sort(vector);
endTime = System.currentTimeMillis();
long totalTimeVector = endTime-beginTime;

System.out.println(totalTimeArrayList); //3219
System.out.println(totalTimeVector); //3765
}
}

ArrayList is almost 20% faster for that on my machine (running Sun JVM
1.4.2)
It's probably a typical figure for other (more sensible) programs.

Alun Harford

 

[Tony Morris]

I have used Vectors extensively in the past but recently came across
ArrayList on my travels.

Both seem to do pretty much the same thing. In the API's it says that
ArrayLists are not synchronised but Vectors are - what does this mean?
Also when would you use each one over the other?

You should never use Vector unless you are using a core API that depends on
it or you are supporting a <1.2 runtime environment.
Vector cannot be formally deprecated because core APIs depend on it.
http://www.xdweb.net/~dibblego/java/faq/answers.html#q35
http://java.sun.com/tutorial/collections

Be aware that there is a lot of fallacy with respect to this issue, and so
you will probably be thrown a few red herrings.

 

[Dimitri Maziuk]

Paul Tomblin sez:

That was a concern when ArrayLists and the new Collection API first
appeared, because (if memory serves me correctly) Vector didn't have
iterator() and other Collection and List methods.

Of course, iterator() isn't particularly useful in ArrayList/Vector
context since they're random access lists -- unlike sequential-access
generic List. (So all you're getting with iterator is a new object
instead of an int counter.)

Dima

 

[Bent C Dalager]

I have used Vectors extensively in the past but recently came across
ArrayList on my travels.

Both seem to do pretty much the same thing. In the API's it says that
ArrayLists are not synchronised but Vectors are - what does this mean?
Also when would you use each one over the other?

If you use anything that is synchronized, you need to do so with the
utmost care or it will come back and bite you at some inopportune time
later. Vector, as an example, is prone to deadlock in some rather
trivial two-thread use cases in which an unsynchronized ArrayList
would perform perfectly.

If you do not desperately _need_ a synchronized list, you should
always go for an unsynchronized ArrayList. If you do need one that is
synchronized, you may want to used a Collections.synchronizedList()
although on 1.4.2 that synchronization seems slightly buggy (not sure
if it's fixed in 5.0). Vector might be more functional.

Cheers
Bent D

 

[Tilman Bohn]

In message <[email protected]>,
Bent C Dalager wrote on Wed, 2 Mar 2005 11:44:27 +0000 (UTC):

[...]

If you use anything that is synchronized, you need to do so with the
utmost care or it will come back and bite you at some inopportune time
later. Vector, as an example, is prone to deadlock in some rather
trivial two-thread use cases in which an unsynchronized ArrayList
would perform perfectly.

That's a very dangerous statement. It will only `come back and bite
you' in a multi-threaded setting. But in that case, the same is of
course true of using non-thread-safe objects unthinkingly. True, Vector
(or synchronized Collection objects) might deadlock if you don't pay
attention to what you're doing. Unsynchronized versions OTOH might
corrupt state if you don't pay attention. Choose your poison. Or better,
do pay attention and get a live _and_ safe application. You _always_
have to be careful in concurrent programming, because you're constantly
walking that fine line between liveness and safety.

 

[Thomas G. Marshall]

Dimitri Maziuk coughed up:

Paul Tomblin sez:

Of course, iterator() isn't particularly useful in ArrayList/Vector
context since they're random access lists -- unlike sequential-access
generic List. (So all you're getting with iterator is a new object
instead of an int counter.)

No, that's not right at all. First, they are plenty useful. Secondly, what
do you mean "sequential access generic List". You capitalized the List, so
are you referring to the List interface? If so, go look: List has get(int
index) and similar methods which are random access.

Regarding the first point again: the fact that you are provided random
access has nothing to do with whether or not you wish to access the thing
serially. Arrays, for example, are often looped through. HashMaps are
excellent examples of what you're talking about: random access, but
sequential access not all that interesting.

*Besides*, in my analysis of craploads of code over the years, the most
exploited benefit of a List/Vector is that they can grow essentially without
predetermined bounds. Not that they are random access.

 

[Thomas G. Marshall]

Tilman Bohn coughed up:

In message <[email protected]>,
Bent C Dalager wrote on Wed, 2 Mar 2005 11:44:27 +0000 (UTC):

[...]

If you use anything that is synchronized, you need to do so with the
utmost care or it will come back and bite you at some inopportune
time later. Vector, as an example, is prone to deadlock in some
rather trivial two-thread use cases in which an unsynchronized
ArrayList would perform perfectly.

That's a very dangerous statement.

It sure is!

It will only `come back and bite
you' in a multi-threaded setting. But in that case, the same is of
course true of using non-thread-safe objects unthinkingly. True,
Vector (or synchronized Collection objects) might deadlock if you
don't pay attention to what you're doing. Unsynchronized versions
OTOH might corrupt state if you don't pay attention. Choose your
poison. Or better, do pay attention and get a live _and_ safe
application. You _always_ have to be careful in concurrent
programming, because you're constantly walking that fine line between
liveness and safety.

Yes. I'll go further with this.

Having a "thread safe" synchronized ArrayList doesn't mean squat if you're
not paying attention to what compound series of operations you are
performming on it.

For example, take a look at this seemingly innocuous access on a fully
synchronized [made up] Thing object that maintains an internal integer:

thing.set(thing.get() + 1); // bring thing up by one

It does *not* matter if both set() and get() are synchronized methods, this
line of code is going to produce very unpredictable results if two threads
execute it without further synchronization around the entirety of all three
operations. If you don't readily see why, you had better go get a book on
the subject.

*The same thing applies to the synchronized*
*collections you retrieve from the Collections*
*class.*

 

[Dimitri Maziuk]

Thomas G. Marshall sez:

Dimitri Maziuk coughed up: ....

No, that's not right at all. First, they are plenty useful. Secondly, what
do you mean "sequential access generic List". You capitalized the List, so
are you referring to the List interface? If so, go look: List has get(int
index) and similar methods which are random access.

Read the fine API docs.

Index-based access in List is potentially O(n) (that's what "sequential"
means, you have to traverse the whole n nodes from the start to get to
n-th node) so use of iterator is preferred over get()/set().
IOW, if you iterate over a java.util.List in a for( int i = 0; ... ) loop
you may get O(n^2) time whereas the iterator will give you O(n).

Index-based access in an array/Vector is O(1), that's what makes it
"random access". Both iterator and for loop will give you O(n) time,
the only difference is that iterator is a new object that has some
extra cruft for iterating backwards and the lame concurrent modification
check for people who write multi-threaded programs while knowing nothing
about "synchronized". (See src.zip.)

Regarding the first point again: the fact that you are provided random
access has nothing to do with whether or not you wish to access the thing
serially. Arrays, for example, are often looped through. HashMaps are
excellent examples of what you're talking about: random access, but
sequential access not all that interesting.

You got it backwards: the problem is not accessing an array serially, it's
accessing a List randomly.

*Besides*, in my analysis of craploads of code over the years, the most
exploited benefit of a List/Vector is that they can grow essentially without
predetermined bounds. Not that they are random access.

You've never seen a

java.util.List mylist = OtherPeople'sCode.getSomeList();
for( int i = 0; i < mylist.size(); i++ )
mylist.get( i )...

?

Dima

 

[Thomas G. Marshall]

Dimitri Maziuk coughed up:

Thomas G. Marshall sez:

Read the fine API docs.

I do, quite a bit actually, and I spend even more time in the java source.

However it's fairly clear that I missed what you were saying, so lets just
chat this through quickly.

Index-based access in List is potentially O(n) (that's what
"sequential" means, you have to traverse the whole n nodes from the
start to get to n-th node) so use of iterator is preferred over
get()/set().
IOW, if you iterate over a java.util.List in a for( int i = 0; ... )
loop you may get O(n^2) time whereas the iterator will give you O(n).
Right.


Index-based access in an array/Vector is O(1), that's what makes it
"random access". Both iterator and for loop will give you O(n) time,
the only difference is that iterator is a new object that has some
extra cruft for iterating backwards and the lame concurrent
modification check for people who write multi-threaded programs while
knowing nothing about "synchronized". (See src.zip.)

It is still /useful/, which is counter to your statement that it is not.
The reason to use iterators is to keep the implementation details out of the
loop access. You want to uncouple the thing that needs to traverse the list
from the details of getting each cell from it. Using iterators allows you
to change the underlying object later. You know this. So it certainly
isn't the case that "all you're getting with iterator is a new object
instead of an int counter". I suppose that was what I was reacting to: the
devaluation of the iteration idiom.

You got it backwards: the problem is not accessing an array serially,
it's accessing a List randomly.

Yes. I think I misread your original point. You didn't answer this
specifically when I asked, but I can see now what you meant by
"sequential-access generic List". That generic list you talk about would be
like a linked list is: sequential only, unless provisions are made for
indexing.

You've never seen a

java.util.List mylist = OtherPeople'sCode.getSomeList();
for( int i = 0; i < mylist.size(); i++ )
mylist.get( i )...

Of /course/ I have. It's called bad design if the index is only used for
grabbing the data and nothing else. Iterators provide the perfect
abstraction for this: it allows you to have the underlying object manage the
access for you, allowing you to change it from a List to some other object.
And in 1.5 they give you an abbreviated way of indicating the exact same
iterator.

 

[Chris Uppal]

[...] the lame concurrent modification
check for people who write multi-threaded programs while knowing nothing
about "synchronized". (See src.zip.)

I agree that the concurrent modification check is prety lame, but you are wrong
to associate it with threaded programming. It is there to try to protect
against incorrect modifications /from the same thread/ whilst an iteration is
active.

In the standard implementations the modification counter is not even
thread-safe itself.

-- chris

 

[Tilman Bohn]

In message <4asVd.48010$t46.23749@trndny04>,
Thomas G. Marshall wrote on Wed, 02 Mar 2005 23:40:48 GMT:

[...]

Yes. I'll go further with this.

Having a "thread safe" synchronized ArrayList doesn't mean squat if you're
not paying attention to what compound series of operations you are
performming on it.

For example, take a look at this seemingly innocuous access on a fully
synchronized [made up] Thing object that maintains an internal integer:

thing.set(thing.get() + 1); // bring thing up by one

Of course this is broken. I didn't mean to imply that declaring methods
synchronized automatically made client code safe. I was only refuting the
claim that you should stay away from synchronized classes because of the
danger of deadlock.

[...]

operations. If you don't readily see why, you had better go get a book on
the subject.

[...]

I don't know why you think I wouldn't see this. ;-)

 

[Tilman Bohn]

In message <4asVd.48010$t46.23749@trndny04>,
Thomas G. Marshall wrote on Wed, 02 Mar 2005 23:40:48 GMT:

[...]

For example, take a look at this seemingly innocuous access on a fully
synchronized [made up] Thing object that maintains an internal integer:

thing.set(thing.get() + 1); // bring thing up by one

Another thing that occurred to me over lunch. The above is just broken
client code. What's worse is if the designer of the Thing class thought
of this and `helpfully' added a method incByOne() -- and thought just
because all it does is value++ they can dispense with synchronization.

 

[Dimitri Maziuk]

Chris Uppal sez:

[...] the lame concurrent modification
check for people who write multi-threaded programs while knowing nothing
about "synchronized". (See src.zip.)

I agree that the concurrent modification check is prety lame, but you are wrong
to associate it with threaded programming. It is there to try to protect
against incorrect modifications /from the same thread/ whilst an iteration is
active.

In the standard implementations the modification counter is not even
thread-safe itself.

True. I still don't quite see the point -- but then I'm biased by STL
containers where effects of concurrent modification atually make sense.

Dima

 

[Dimitri Maziuk]

Thomas G. Marshall sez:

Dimitri Maziuk coughed up: ....

Yes. I think I misread your original point. You didn't answer this
specifically when I asked, but I can see now what you meant by
"sequential-access generic List". That generic list you talk about would be
like a linked list is: sequential only, unless provisions are made for
indexing.

That's why I RTFM'ed you: by "generic List" I meant specifically
"inteface java.util.List" whose API docs say: "assume O(n) for
get()/set() and use iterators instead". Of course, there's only
two implementations: array and linked list, so efectively every
List is presumed to be a linked list.

Which is fine -- as long as you don't need frequent random access
you should use java.util.List.

If you do need frequent random access, better make sure you use
java.util.ArrayList everywhere. Because if you don't, that nice
abstraction will turn around and bite you in the ass when you
least expect it. I.e. someone *will* replace the array with linked
list while you're not looking and your code *will* slow down to a
crawl while you're demoing it to important customer.
Murphy says so.

Dima

 

[Thomas G. Marshall]

Dimitri Maziuk coughed up:

Thomas G. Marshall sez:

That's why I RTFM'ed you: by "generic List" I meant specifically
"inteface java.util.List" whose API docs say: "assume O(n) for
get()/set() and use iterators instead". Of course, there's only
two implementations: array and linked list, so efectively every
List is presumed to be a linked list.

Which is fine -- as long as you don't need frequent random access
you should use java.util.List.

If you do need frequent random access, better make sure you use
java.util.ArrayList everywhere. Because if you don't, that nice
abstraction will turn around and bite you in the ass when you
least expect it. I.e. someone *will* replace the array with linked
list while you're not looking and your code *will* slow down to a
crawl while you're demoing it to important customer.
Murphy says so.

Precisely right. However, this is also the reason to always use iterators
when possible, which is what caused me to enter this sub-thread. Someone
swapping out an ArrayList with a LinkedList, and all of a sudden the get()'s
don't seem too nifty. So /use/ the iterator if you can, even when you
currently have something you are *sure* is just fine with random access.

Sound like that particular shark swam up and bit me in the ass before? In
one particular instance I was modifying a very large project. There were
many loops (not written by me) through various parts of what were once
ArrayList's. When the ArrayLists were all converted to LinkedLists, the
code all worked ok, but things got slower when everyone expected it to get
faster.