Vector Vs. List in Stl

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?

Difference between vector and list

A vector is a resizable array. It's elements are stored next to each other in a contiguous block of memory, so that the position of each can be calculated quickly; this is known as random access. Inserting and removing elements from the middle requires moving all the later elements, so can be rather slow.

A list is a linked list. The elements are scattered around memory, and each has pointers to the next and previous element. You can only find an element by following the chain of pointers, which might be rather slow; this is known as sequential access. But elements can be inserted and removed just by modifying a few pointers, so that can be quite fast.

STL Containers - difference between vector, list and deque

Use deque if you need efficient insertion/removal at the beginning and end of the sequence and random access; use list if you need efficient insertion anywhere, at the sacrifice of random access. Iterators and references to list elements are very stable under almost any mutation of the container, while deque has very peculiar iterator and reference invalidation rules (so check them out carefully).

Also, list is a node-based container, while a deque uses chunks of contiguous memory, so memory locality may have performance effects that cannot be captured by asymptotic complexity estimates.

deque can serve as a replacement for vector almost everywhere and should probably have been considered the "default" container in C++ (on account of its more flexible memory requirements); the only reason to prefer vector is when you must have a guaranteed contiguous memory layout of your sequence.

When do you prefer using std::listT instead of std::vectorT?

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.

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

As usual the best answer to performance questions is to profile both implementations for your use case and see which is faster.

In general if you have insertions into the data-structure (other than at the end) then vector may be slower, otherwise in most cases vector is expected to perform better than list if only for data locality issues, this means that if two elements that are adjacent in the data-set are adjacent in memory then the next element will already be in the processor's cache and will not have to page fault the memory into the cache.

Also keep in mind that the space overhead for a vector is constant (3 pointers) while the space overhead for a list is paid for each element, this also reduces the number of full elements (data plus overhead) that can reside in the cache at any one time.

STL vector vs list: Most efficient for graph adjacency lists?

I don't think this can be answered with absolute certainty. Nonetheless, I'd estimate that there's at least a 90% chance that a vector will do better. An adjacency list actually tends to favor a vector more than many applications, because the order of elements in the adjacency list doesn't normally matter. This means when you add elements, it's normally to the end of the container, and when you delete an element, you can swap it to the end of the container first, so you only ever add or delete at the end.

Yes, a vector has to copy or move elements when it expands, but in reality this is almost never a substantial concern. In particular, the exponential expansion rate of a vector means that the average number of times elements get copied/moved tends toward a constant -- and in a typical implementation, that constant is about 3.

If you're in a situation where the copying honestly is a real problem (e.g., copying elements is extremely expensive), my next choice after vector still wouldn't be list. Instead, I'd probably consider using std::deque instead¹. It's basically a vector of pointers to blocks of objects. It rarely has to copy anything to do an expansion, and on the rare occasion that it does, all it has to copy is the pointers, not the objects. Unless you need the other unique capabilities of a deque (insert/delete in constant time at either end), a vector is usually a better choice, but even so a deque is almost always a better choice than a list (i.e., vector is generally the first choice, deque a fairly close second, and list quite a distant last).

---

^{1. One minor aside though: at least in the past, Microsoft's implementation of `std::deque` had what I'd consider sort of a defect. If the size of an element in the `deque` is greater than 16, it ends up storing pointers to "blocks" of only a single element apiece, which tends to negate much of the advantage of using `deque` in the first place. This generally won't have much effect on its use for an adjacency list though.}

array vs vector vs list

Use STL vector. It provides an equally rich interface as list and removes the pain of managing memory that arrays require.

You will have to try very hard to expose the performance cost of operator[] - it usually gets inlined.

I do not have any number to give you, but I remember reading performance analysis that described how vector<int> was faster than list<int> even for inserts and deletes (under a certain size of course). The truth of the matter is that these processors we use are very fast - and if your vector fits in L2 cache, then it's going to go really really fast. Lists on the other hand have to manage heap objects that will kill your L2.

std::list and std::vector - Best of both worlds?

There's a theoretical result that says that any data structure representing an ordered list cannot have all of insert, lookup by index, remove, and update take time better than O(log n / log log n), so no such data structure exists.

There are data structures that get pretty close to this, though. For example, an order statistics tree lets you do insertions, deletions, lookups, and updates anywhere in the list in time O(log n) apiece. These are reasonably good in practice, and you may be able to find an implementation online.

Depending on your specific application, there may be alternative data structures that are more tailored toward your needs. For example, if you only care about finding the smallest/biggest element at each point in time, then a data structure like a Fibonacci heap might fit the bill. (Fibonacci heaps are usually slower in practice than a regular binary heap, but the related pairing heap tends to run extremely quickly.) If you're frequently updating ranges of elements by adding or subtracting from them, then a Fenwick tree might be a better call.

Hope this helps!

---

Related Topics