Just getting back into using C++ and trying to convert a simple Java program I wrote recently.
What's the preferred equivalent to the Java ArrayList in C++?
Hmmm ... from the other answer, it sounds like vector isn't implemented as a linked list? Am I right? I'm using this list as a collection which will have a fairly high turnover of objects added and removed from it. Is this array actually the best implementation? Or is there a linked-list version?
interstar
2010-10-19 19:53:22
@interstar - absolutely correct. If you really want linked-list semantics, then use `std::list`, though then you lose the indexability (no `operator[]`) so it's not really an array. `list` that has its own idiosyncracies such that `vector` is often a better choice. In Standard C++ containers, you are going to have to compromise one way or the other. Look at `deque`, that may offer better perf for you. It's (relatively) easy to measure `vector` vs `deque` vs `list` as they are largely interchangeable in the code - just use a typedef for your container e.g. `typedef vector<MyObj> MyList`.
Steve Townsend
2010-10-19 19:57:24
well, I'll try the vector first. Because index is useful. If it's too slow I may move to the linked-list. Thanks
interstar
2010-10-19 23:14:57
@interstar: Linked lists are the slowest data structure there is, except in extremely situational cases.
GMan
2010-10-19 23:38:27
+3
A:
A couple of additional points re use of vector here.
Unlike ArrayList and Array in Java, you don't need to do anything special to treat a vector as an array - the underlying storage in C++ is guaranteed to be contiguous and efficiently indexable.
Unlike ArrayList, a vector can efficiently hold primitive types without encapsulation as a full-fledged object.
When removing items from a vector, be aware that the items above the removed item have to be moved down to preserve contiguous storage. This can get expensive for large containers.
Make sure if you store complex objects in the vector that their copy constructor and assignment operators are efficient. Under the covers, C++ STL uses these during container housekeeping.
Advice about reserve()ing storage upfront (ie. at vector construction or initialilzation time) to minimize memory reallocation on later extension carries over from Java to C++.
Steve Townsend
2010-10-19 19:11:50