14

Possible Duplicate:
When do you prefer using std::list<T> instead of std::vector<T>?

I just watched the recording of the GoingNative'12 talk by Bjarne Stroustrup. And I'm a bit confused.

In this talk he in particular discusses the vector vs list question and suggest that in many cases vector is faster even if you insert and remove intensively to/from the middle, as compilers can optimize a lot of things and like compact structures. And the conclusion(as I understand it) is: first use vector and later think whether you need something else. That sounds reasonable, but taking into account the first observation, what criteria I should take into account? I always thought that if you insert/remove intensively - use list. Similar things are suggested in some topics here. See

Relative performance of std::vector vs. std::list vs. std::slist?

and

vector vs. list in STL

And now according to Stroustrup I was wrong.

Of course I can write a couple of tests and try to figure out what to use in each particular situation, but is there a theoretical way?

Community
  • 1
  • 1
Shamdor
  • 3,019
  • 5
  • 22
  • 25
  • 6
    Actually, if `vector` is slow you should next try `deque` before `list`. – Pubby Nov 01 '12 at 09:48
  • 1
    +1 to Pubby. Unless I *need* continuity for all elements in the sequence (i.e. a big-ass buffer) I prefer deque anyway, which frankly has one of the slickest management algorithms in the entire std lib. – WhozCraig Nov 01 '12 at 09:51
  • 2
    Use a profiler to compare both versions with production data, then choose the one that performs better. – Axel Nov 01 '12 at 10:10
  • 2
    @WhozCraig Except that `deque` doesn't generally improve performance in such cases. In practice, the only reason I've found to use anything other than `std::vector` is iterator safety, and `std::deque` doesn't help there; you need `std::list`. – James Kanze Nov 01 '12 at 10:11

1 Answers1

18

The most important motivation for preferring std::list over std::vector is the validity of iterators, not performance. If at the time you're inserting or erasing, you have other iterators into the container, then you probably need std::list, since it insertion doesn't invalidate any iterators, and erasure only invalidates iterators to the element being erased. About the only time std::list will win on performance is when copy and assignment are extremely expensive, and in such cases, it's often a better choice to modify the contained class to reduce the cost of copy and assignment, rather than switching to std::list.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • 1
    If you just need stable iterators, you should consider something like [boost::container::stable_vector](http://www.boost.org/doc/libs/1_48_0/doc/html/boost/container/stable_vector.html). – Mankarse Nov 01 '12 at 10:37
  • 4
    @Mankarse if you're not already making use of boost, adding boost dependencies to a project to get stable iterators seems a little excessive, given that you could just use `std::list`. – Rook Nov 01 '12 at 10:40