Thursday, August 16, 2007

java.util.ArrayList != std::list

When using "lists" in Java, ArrayList is usally the choice. When using list contructs in C++, using std::list is usually not a good idea, as it is implemented as linked list, and therefore all indexed acesses (list[i]) take linear time, and an iteration such as

for (int i=0; i<list.size(); i++) {...}
takes O(n^2)! (Of course, one should not do this in StdC++/STL anyway, but use the iterators.) Thus, std::vector should be used in most cases. Only exception: regularly adding elements somewhere inside the list, which is far more efficient in a (doubly) linked list.

No comments: