ansaurus

Question

What is the preferred STL collection when that's all you need?

Answer 1

+1 A:

std::vector. Doesn't require an operator<.

dan04 2010-07-20 00:31:09

Answer 2

+5 A:

vector probably has the lowest overhead of all the containers. As long as you are not adding or removing things in the middle.

deinst 2010-07-20 00:31:40

For what usage profile? </rhetorical> I guess that leads to the question of if someone has tool that estimates the overhead of using each collection type for an assumed profile of adds/iterates/removes/etc.

BCS 2010-07-20 00:35:00

Vector's only weakness is middle insertion and removal, so if you don't care about anything other than that the elements are in a container, you can always just add to the end and avoid that pathological case.

Tyler McHenry 2010-07-20 00:39:07

I don't know about that ... `push_back()` isn't exactly what I would call _fast_ as the collection becomes large.

D.Shawley 2010-07-20 01:41:58

`push_back()` is supposed to run in constant amortized time. That means that some calls may cause large allocations and take a long time, but the average time is constant. This does not take into problems with paging and virtual memory, but any collection will suffer from those, and sooner than vector.

deinst 2010-07-20 01:54:57

The problem with `std::vector` and `push_back()` is that the amount of contiguous space required increases as the number of elements grows. Since `std::allocator` does not expose a resize, the implementation is forced to allocate a larger chunk, copy construct each element in turn, and then deallocate the current chunk. This causes problems with memory fragmentation due to the shuffle on every resize and performance hits when you have a non-trivial copy constructor.

D.Shawley 2010-07-20 22:56:23

Answer 3

+4 A:

By default, use a vector... But then, if possible, don't forget to use a type indirection!

The reason for that is that if you only need to iterate, then you should be able to use any one of the available STL containers, and choose it once through a typedef indirection.

For example, let's say you'll initially choose a vector (which is the default choice) :

typedef std::vector<MyThing> MyThingContainer ;

And then use the container as usual :

void foo(MyThingContainer & things)
{
    for(MyThingContainer::iterator it = things.begin(),
        itEnd = things.end() ;
        it != itEnd ;
        ++it)
   {
      MyThing & thing = *it ;
      // Do something with that thing
   }
}

This way, the day you find a list, or a deque, or whatever is a better container than a vector, just by changing the typedef and recompiling, you'll change the true type of the container.

paercebal 2010-07-20 09:46:11

+1 for type indirection.

Fred Larson 2010-07-20 13:04:41

@Fred Larson: Fact is, this is the only reason I answered. After all, all the answers were already quite enough (your answers made me pause, though), so there was no need to add another one, but for this indirection thing... ^_^ ...

paercebal 2010-07-20 13:22:57

Answer 4

+7 A:

The standard recommends using vector as your default container. But Herb Sutter actually makes a case for using deque as your first choice.

Fred Larson 2010-07-20 13:04:10

+1 for the link. I believed I remembered Sutter prefering the vector, but your link cleared all that : Standard goes for vector by default, and Sutter goes for Deque by default.

paercebal 2010-07-20 13:24:28

Check Neil's blog about it: http://punchlet.wordpress.com/2009/12/27/letter-the-fourth/ . Unless you need C-compatibility, `deque` is the one-fits-them-all component.

Matthieu M. 2010-07-20 14:50:15

+1 ... I was trying to remember who recommended `deque` as a good default choice

D.Shawley 2010-07-20 22:57:47

Answer 5

A:

std::vector is a good default choice. It's a simple data structure, implemented as a dynamic array. The elements are packed next to each other which is good locality of reference (beneficial for caching)

seand 2010-07-20 13:11:58

ansaurus

tags:

views:

answers:

What is the preferred STL collection when that's all you need?

related questions