Sequential Containers

Characteristics of std::vector<>

std::vector<> is an efficient sequential container because …

  • Organization: contiguous memory ⟶ perfect utilization of processor caches

  • Appending is performs liek with strings (logarithmic time)

But …

  • Removal at arbitrary position is slow

  • Insertion at arbitrary position is slow

  • ⟶ Unwanted copies

std::vector<>: Modification at the Back

  • Appending at the back

    • There is room $to$ immediate

    • No room ⟶ allocate (double the space), copy over, and append

  • Removing from the back

    • Immediate

    • capacity() remains same

    • size() decremented by one

../../../../../../_images/40-35-00-vector-push-back.svg

std::vector<>: Insertion

Performance is miserable!

  • Insert at arbitrary position

    • All elements from there on have to be shifted (copied) toward the end by one position

    • Reallocation is also possible

  • Removal at arbitrary position

    • All elements from there have to be copied one down

../../../../../../_images/40-35-00-vector-insert.svg

std::list<>: Insertion and Deletion

  • Insertion at arbitrary position

    • Pointer rearrangement ⟶ constant time

  • Deletion at arbitrary position

    • Pointer rearrangement ⟶ constant time

../../../../../../_images/40-35-00-list.svg