vector vs list

      No Comments on vector vs list

vector:

  • Contiguous memory.
  • Pre-allocates space for future elements, so extra space required beyond what’s necessary for the elements themselves.
  • Each element only requires the space for the element type itself (no extra pointers).
  • Can re-allocate memory for the entire vector any time that you add an element.
  • Insertions at the end are constant, amortized time, but insertions elsewhere are a costly O(n).
  • Erasures at the end of the vector are constant time, but for the rest it’s O(n).
  • You can randomly access its elements.
  • Iterators are invalidated if you add or remove elements to or from the vector.
  • You can easily get at the underlying array if you need an array of the elements.

list:

  • Non-contiguous memory.
  • No pre-allocated memory. The memory overhead for the list itself is constant.
  • Each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
  • Never has to re-allocate memory for the whole list just because you add an element.
  • Insertions and erasures are cheap no matter where in the list they occur.
  • It’s cheap to combine lists with splicing.
  • You cannot randomly access elements, so getting at a particular element in the list can be expensive.
  • Iterators remain valid even when you add or remove elements from the list.
  • If you need an array of the elements, you’ll have to create a new one and add them all to it, since there is no underlying array.

Leave a Reply

Your email address will not be published. Required fields are marked *