22

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).

jokoon
  • 6,207
  • 11
  • 48
  • 85

4 Answers4

39

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!

Community
  • 1
  • 1
In silico
  • 51,091
  • 10
  • 150
  • 143
  • @In silico: regarding the "break", calling `erase` will invalidate the iterators to elements beyond the erased point (and 'end'). – Matthieu M. Jan 15 '11 at 15:38
  • @Matthieu M.: Right, calling `erase()` will invalidate some iterators, but it won't break or corrupt the vector itself. I was addressing the claim that `erase()` will "break the vector, since it's a linked list," which is nonsense. – In silico Jan 15 '11 at 22:57
  • @In silico: yes I understand what you mean, but I think that the OP (and his friends) used "break" because they didn't understand what invalidation meant, since erasing an element from a list doesn't invalidate any other iterator. – Matthieu M. Jan 16 '11 at 12:36
  • they also think that each vector element has a next and a previous element pointer – jokoon Jan 17 '11 at 09:56
  • @gokoon: Only doubly-linked list elements have next and previous pointers. Vector elements are contiguous, and therefore doesn't require next nor previous pointers. Again, if your schoolmates can seriously say that, you should tell them (respectfully!) to pick up [a C++ book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – In silico Jan 17 '11 at 20:24
  • I just wanted to be sure for myself first, I don't really care what they think, because I don't really like the way they tell it to me, all laughing and shit. I'll just link them this question/answer next time they bug me with that. – jokoon Jan 18 '11 at 08:02
13

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.

Puppy
  • 144,682
  • 38
  • 256
  • 465
3

By definition, vectors are contiguous blocks of memory like C arrays. See: http://en.wikipedia.org/wiki/Vector_(C%2B%2B)

Vectors allow random access; that is, an element of a vector may be referenced in the same manner as elements of arrays (by array indices). Linked-lists and sets, on the other hand, do not support random access or pointer arithmetic.

Daniel A. White
  • 187,200
  • 47
  • 362
  • 445
1

Vectors are not linked linked list, they provide random access and are contiguous just like arrays. In order to achieve this they re-allocate memory under the hood.

List is designed to allow quick insertions and deletions, while not invalidating any references or iterators except the ones to the deleted element.

Neera
  • 1,577
  • 8
  • 10