1.2.1.3 contiguous or node

• Another classification of containter : contiguous-base and node-base.
  1. vector, string, and deque
  2. list and slist(linked list), set and map(balanced trees)
• Why we have this point of view.
  1. Because all the contiguous-base container has invalidation of iterator(pointer, reference) problem.
  2. All the node-base container only support bidirectional iterators.
  3. All the node-base container don’t have reserve() function and need to worry allocation problem. deque doesn’t have reserve() function either
• About the iterator invalidation problem, First, you need to know the invalidation rules below:

  Insertion

  • Sequence containers
    1. vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)
    2. deque: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected)
    3. list: all iterators and references unaffected
  • Associative containers: [multi]set,map all iterators and references unaffected
  • Container adaptors: stack, queue and priority_queue: inherited from underlying container.(Usually, we don’t use iterator in stack, queue and priority_queue. Maybe you don’t need to worry about it. )

  Erasure

  • Sequence containers
    1. vector: every iterator and reference after the point of erase is invalidated
    2. deque: all iterators and references are invalidated, unless the erased members are at an end (front or back) of the deque (in which case only iterators and references to the erased members are invalidated)
    3. list: only the iterators and references to the erased element is invalidated
  • Associative containers: [multi]set,map: only iterators and references to the erased elements are invalidated
  • Container adaptors: stack, queue and priority_queue: inherited from underlying container

  swap

  no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.

  Resizing

  vector, deque and list as per insert/erase