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

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

std::list<>: Insertion and Deletion

Insertion at arbitrary position Pointer rearrangement ⟶ constant time Deletion at arbitrary position Pointer rearrangement ⟶ constant time