Are vector a special case of linked lists?

Question

When talking about the STL, I have several schoolmates telling me that "vectors are linked lists".

I have another one arguing that if you call the erase() method with an iterator, it breaks the vector, since it's a linked list.

They also tend to don't understand why I'm always arguing that vector are contiguous, just like any other array, and don't seem to understand what random access means. Are vector stricly contiguous just like regular arrays, or just at most contiguous ? (for example it will allocate several contiguous segments if the whole array doesn't fit).

Answer 1

I'm sorry to say that your schoolmates are completely wrong. If your schoolmates can honestly say that "vectors are linked lists" then you need to respectfully tell them that they need to pick up a good C++ book (or any decent computer science book) and read it. Or perhaps even the Wikipedia articles for vectors and lists. (Also see the articles for dynamic arrays and linked lists.)

---

Vectors (as in std::vector) are not linked lists. (Note that std::vector do not derive from std::list). While they both can store a collection of data, how a vector does it is completely different from how a linked list does it. Therefore, they have different performance characteristics in different situations.

For example, insertions are a constant-time operation on linked lists, while it is a linear-time operation on vectors if it is inserted in somewhere other than the end. (However, it is amortized constant-time if you insert at the end of a vector.)

The std::vector class in C++ are required to be contiguous by the C++ standard:

23.2.4/1 Class template vector

A vector is a kind of sequence 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. Storage management is handled automatically, though hints can be given to improve efficienty. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

Compare that to std::list:

23.2.2/1 Class template list

A list is a kind of sequence that supports bidirectional iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. Unlike vectors (23.2.4) and deques (23.2.1), fast random access to list elements is not supported, but many algorithms only need sequential access anyway.

Clearly, the C++ standard stipulates that a vector and a list are two different containers that do things differently.

You can't "break" a vector (at least not intentionally) by simply calling erase() with a valid iterator. That would make std::vectors rather useless since the point of its existence is to manage memory for you!

Answer 2

vector will hold all of it's storage in a single place. A vector is not even remotely like a linked list. Infact, if I had to pick two data structures that were most unlike each other, it would be vector and list. "At most contiguous" is how a deque operates.

Vector:

1. Guaranteed contiguous storage for all elements - will copy or move elements.
2. O(1) access time.
3. O(n) for insert or remove.
4. Iterators invalidated upon insertion or removal of any element.

List:

1. No contiguous storage at all - never copies or moves elements.
2. O(n) access time- plus all the nasty cache misses you're gonna get.
3. O(1) insert or remove.
4. Iterators valid as long as that specific element is not removed.

As you can see, they behave differently in every data structure use case.