91

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++?

interstar
  • 26,048
  • 36
  • 112
  • 180

3 Answers3

106

Use the std::vector class from the standard library.

SLaks
  • 868,454
  • 176
  • 1,908
  • 1,964
  • 3
    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 Oct 19 '10 at 19:53
  • 5
    @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 MyList`. – Steve Townsend Oct 19 '10 at 19:57
  • 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 Oct 19 '10 at 23:14
  • 3
    @interstar, `ArrayList`, as you might be able to guess from the name, isn't implemented as a linked list, either. You might be thinking of `LinkedList`. Also, even if you have a fairly high turnover of objects added and removed from the list, `vector` might still be faster than `list` as long as you allocate enough space for it initially that it doesn't need to re-allocate (i.e., give it the maximum space it should ever need). – Kyle Strand Apr 23 '13 at 19:31
  • @KyleStrand That's interesting. I always assumed that ArrayList meant "an arraylike thing that's implemented as a linked-list", rather than a "linked-list like thing that's implemented as an array". – interstar Feb 22 '15 at 17:40
  • 1
    @interstar I've now learned that even when you *do* need reallocation, array-like storage is *still* almost always faster than linked lists. Linked lists are a nice programming concept, but in practice they're essentially pointless. – Kyle Strand Feb 23 '15 at 17:45
  • @Kyle: Linked lists are far from pointless! It totally depends on your use-case. They're fastest when doing lots of insertions/deletions. Try that with an array and you're stuck iterating through half of the elements (on average) to re-pack, for every insert operation. Arrays are ideal if your data sets are relatively fixed, pre-sorted, or easily indexed... or if you're using a hashing function. Learn your data structures, what they're best for, and avoid "golden hammers!" – electromaggot Dec 22 '15 at 07:15
  • @electromaggot Do you have any benchmarks to support those claims? Of course a good software engineer must understand data structures, but the C++ standard actually recommends `vector` as the go-to data-structure for most things. Linked lists are not "fastest when doing lots of insertions/deletions," even from the middle of the list, unless you're *directly* storing objects (rather than pointers) and the objects are either fairly large or have nontrivial constructors/destructors. This is largely because the theoretical algorithmic operation-order matters less than data locality due to caching. – Kyle Strand Dec 22 '15 at 19:10
  • @electromaggot See [Herb Sutter](http://www.gotw.ca/gotw/054.htm) and [Baptiste Wicht](http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html) on the issue. (I don't know Wicht by name, but the article seems pretty good.) Note that both Sutter and Wicht do come to the conclusion that `deque` is often better than `vector`, but `deque` is still array-based. – Kyle Strand Dec 22 '15 at 19:24
  • By "theoretical algorithmic operation-order" I meant "algorithmic complexity." – Kyle Strand Dec 22 '15 at 19:31
  • @Kyle Strand: Good links. Both compare the different data structures given various use cases. The Wicht article concludes that in three of six such cases, std::list may be best fit, so I think even he would disagree that lists are pointless. General statements may misguide those who are here to learn! – electromaggot Dec 22 '15 at 21:43
  • @electromaggot Since those cases are entirely due to the size of the contained element, the correct approach (in my opinion) probably *isn't* "use a `list`," but "use pointers instead of direct containment." That said, my "essentially pointless" comment was largely inspired by an ex-coworker with nearly two decades of experience whose opinions I used to rely upon perhaps a *liiiiiiiiiittle* too much. – Kyle Strand Dec 22 '15 at 21:57
67

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
  • 53,498
  • 9
  • 91
  • 140
1

Like other answers the closest one is std::vector.

But there is one important thing to consider, space complexity.

The C++ vector has compiler dependent calculation when current capacity is full. When capacity is full some compilers grow the vector capacity exponentially and some loosely exponential.

For Java arraylist, there are no exact details specified by standards for recalculating the capacity when it is full. Some have a rough calculation of 150% plus one. But not sure if that is the exact calculation.

Pavan Chandaka
  • 11,671
  • 5
  • 26
  • 34