When Do You Prefer Using Std::List<T> Instead of Std::Vector<T>

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

Lists are better for inserting or deleting anywhere in the middle, vectors are better for inserting at the end.

Vectors are also better for accessing elements.

This is an artefact of the way they're implemented.

So, if a collection changes very little (compared to accesses) or the changes are concentrated at the end, I'd use a vector.

If the number of changes is substantial (compared to accesses) and they're not at the ends, I'd use a list.

By way of example, reading in a collection at program start-up and hardly ever changing it (or if the changes are only adding to the end), this would be a good candidate for a vector.

On the other hand, a phone book application for a particularly popular and fickle rock star, I'd be looking towards a list. Actually I'd be looking toward a database connection but that was the best example I could come up with at short notice :-)

As to references, the latest C++0x draft (at the time of this answer) states in part (23.3.4, lists):

A list is a sequence container that supports bidirectional iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. Unlike vectors and deques, fast random access to list elements is not supported.

Section 23.3.5 (on vectors):

A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time.

vector vs. list in STL

Situations where you want to insert a lot of items into anywhere but the end of a sequence repeatedly.

Check out the complexity guarantees for each different type of container:

What are the complexity guarantees of the standard containers?

Vector vs list according to Stroustrup

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.

What is the difference between std::array and std::vector? When do you use one over other?

std::array is just a class version of the classic C array. That means its size is fixed at compile time and it will be allocated as a single chunk (e.g. taking space on the stack). The advantage it has is slightly better performance because there is no indirection between the object and the arrayed data.

std::vector is a small class containing pointers into the heap. (So when you allocate a std::vector, it always calls new.) They are slightly slower to access because those pointers have to be chased to get to the arrayed data... But in exchange for that, they can be resized and they only take a trivial amount of stack space no matter how large they are.

[edit]

As for when to use one over the other, honestly std::vector is almost always what you want. Creating large objects on the stack is generally frowned upon, and the extra level of indirection is usually irrelevant. (For example, if you iterate through all of the elements, the extra memory access only happens once at the start of the loop.)

The vector's elements are guaranteed to be contiguous, so you can pass &vec[0] to any function expecting a pointer to an array; e.g., C library routines. (As an aside, std::vector<char> buf(8192); is a great way to allocate a local buffer for calls to read/write or similar without directly invoking new.)

That said, the lack of that extra level of indirection, plus the compile-time constant size, can make std::array significantly faster for a very small array that gets created/destroyed/accessed a lot.

So my advice would be: Use std::vector unless (a) your profiler tells you that you have a problem and (b) the array is tiny.

Advantages of using arrays instead of std::vector?

In general, I strongly prefer using a vector over an array for non-trivial work; however, there are some advantages of arrays:

• Arrays are slightly more compact: the size is implicit.
• Arrays are non-resizable; sometimes this is desirable.
• Arrays don't require parsing extra STL headers (compile time).
• It can be easier to interact with straight-C code with an array (e.g. if C is allocating and C++ is using).
• Fixed-size arrays can be embedded directly into a struct or object, which can improve memory locality and reducing the number of heap allocations needed.

When to use std::begin and std::end instead of container specific versions

If you look at, say, the definition of std::begin:

template< class C > 
auto begin( C& c ) -> decltype(c.begin());

You see that all it does is reference the begin() anyway. I suppose a decent compiler will make the difference nil, so I guess it comes down to preference. Personally, I'd use cont.begin() and cont.end() just so that I wouldn't have to explain it to anybody :)

As Mooing Duck points out, however, std::begin also works on arrays:

template< class T, size_t N > 
T* begin( T (&array)[N] );

... so there is that to consider. If you are not using arrays, I'd go with my suggestion. However if you are unsure if what is passed is going to be an STL container, or an array of <T>, then std::begin() is the way to go.

How to use list<T*> as method's parameter?

May be template would do the trick ?

#include <iostream>
#include <list>

template <class T>
void foo (const std::list<T*>& v)
{
       std::cout << __PRETTY_FUNCTION__ << std::endl;
}
int main()
{
   std::list<int*> v { nullptr, nullptr };

    foo(v);
}

How to choose between `std::vector<char>` and `std::string`?

What aspects need to be considered when making such a choice?

What is the input data and what is it going to be used for in the future? That would be a big consideration.

If the input data is not going to be used as a string in the future, it may be clearer in the future if you used a container as specified in the comments e.g. std::vector<std::byte>.

Why would I prefer using vector to deque

Elements in a deque are not contiguous in memory; vector elements are guaranteed to be. So if you need to interact with a plain C library that needs contiguous arrays, or if you care (a lot) about spatial locality, then you might prefer vector. In addition, since there is some extra bookkeeping, other ops are probably (slightly) more expensive than their equivalent vector operations. On the other hand, using many/large instances of vector may lead to unnecessary heap fragmentation (slowing down calls to new).

Also, as pointed out elsewhere on StackOverflow, there is more good discussion here: http://www.gotw.ca/gotw/054.htm .

why not implement c++ std::vector::pop_front() by shifting the pointer to vector[0]?

The vector wouldn't be able to free its memory if it did this.

Generally, you want the overhead per vector object to be small. That means you only store three items: the pointer to the first element, the capacity, and the length.

In order to implement what you suggest, every vector ever (all of them) would need an additional member variable: the offset from the start pointer at which the zeroth element resides. Otherwise, the memory could not be freed, since the original handle to it would have been lost.

It's a tradeoff, but generally the memory consumption of an object which may have millions of instances is more valuable than the corner case of doing the absolute worst thing you can do performance-wise to the vector.

---

Related Topics