Standard Sequence Containers Sequence Containers Sequ.Containers

`array<T,size>`	fixed-size contiguous array
`vector<T>`	dynamic contiguous array; amortized O(1) growth strategy; C++'s default container
`deque<T>`	double-ended queue; fast insert/erase at both ends
`list<T>`	doubly-linked list; O(1) insert, erase & splicing; in practice often slower than vector
`forward_list<T>`	singly-linked list; O(1) insert, erase & splicing; needs less memory than `list`; in practice often slower than vector

Common Features

Regularity: Copy, Assign, Compare

All standard sequence containers are regular types:

deeply copyable: copying creates a new container object and copies all contained values
deeply assignable: all contained objects are copied from source to assignment target
deeply comparable: comparing two containers compares the contained objects
deep ownership: destroying the container destroys all contained objects

std::vector<int> a {4,7,1,9};
std::vector<int> b {1,2,3};
bool equal1 = (a == b);  // false
b = a;  // copy assignment ⇒ b: 4
7
1
9
bool equal2 = (a == b);  // true
a[0] = 3;     // a: 3
7
1
9
 b: 4
7
1
9
bool equal3 = (a == b);  // false
// different ways of making exact copies,
// i.e., copy-constructing new containers:
std::vector<int> a2 {a};
std::vector<int> a3 (a);
std::vector<int> a4 = a;
auto a5 {a};
auto a6 (a);
auto a7 = a;

Type Argument Deduction C++17

As of C++17 the element type can be deduced from constructor calls.

std::vector v {1, 2, 3, 4};
std::vector v {1.f, 2.3f, 4.5f};
std::vector v {1., 2.3, 4.6};
struct p2 { int x; int y; };
std::vector v {p2{1,2}};

std::vector<int>
std::vector<float>
std::vector<double>

std::vector<p2>

Common Interface Parts

Iterators for Forward Traversal

can be obtained from all standard sequence containers either with member functions:

container.begin()→ @first_element
container.end()→ @one_behind_last_element

or with free-standing functions: C++11

std::begin(container)→ @first_element
std::end(container)→ @one_behind_last_element

If you are not familiar with what iterators are, please refer to this article .

Const Iterators for Forward Traversal

can be obtained from all standard sequence containers either with member functions:

container.cbegin()→ const@first_element
container.cend()→ const@one_behind_last_element

or with free-standing functions: C++11

std::cbegin(container)→ const@first_element
std::cend(container)→ const@one_behind_last_element

Emptiness Query

either with member function

container.empty()→ true, if container has no elements

or with free-standing function: C++11

std::empty(container)→ true, if container has no elements

Type Interface

container::value_type
container::size_type
container::iterator
container::const_iterator

using con_t = std::vector<double>;
con_t::size_type i = 0;         // std::size_t
auto x = con_t::value_type{0};  // double

`array<T,size>`

overhead-free random access
fast traversal; good for linear searches
size has to be a constant expression (= known at compile time)
does not support size-changing operations (resize, insert, erase, …)
potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)

#include <array>
#include <iostream>

int main () {std::array<int,6> a {4,8,15,16,23,42};
std::cout << a.size() << '\n';    // 6
std::cout << a[0] << '\n';        // 4
std::cout << a[3] << '\n';        // 16
std::cout << a.front() << '\n';   // 4
std::cout << a.back() << '\n';    // 42
std::array<int,3> b {7,8,9};
// a = b;  //  COMPILER ERROR: types don't match!
}

STACK


42
23
16
15
8
4
…

`vector<T>`

C++'s default container

overhead-free random access
fast traversal; good for linear searches
insertion at the end in amortized constant time
potentially slow if insert/erase operations at front and/or random positions dominate
potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)
all operations that can change capacity (insert, push_back, …) may invalidate references/pointers to any vector element
potentially long allocation times for very large amount of values (can be mitigated, see here )

Quick Recap

#include <vector>
#include <iostream>

int main () {
std::vector<int> v {2,4,5};
v.push_back(6);
v.pop_back();
v[1] = 3;
std::cout << v[2];
for (int x : v)   std::cout << x << ' ';
std::cout << '\n';
v.reserve(8);
v.resize(5, 0);
std::cout << v.capacity() << '\n';
std::cout << v.size() << '\n';
}


2
4
5
2
4
5
6
2
4
5
 
2
3
5
prints 5
prints 2 3 5
2
3
5
 
 
 
 
 
2
3
5
0
0
0
 
 
prints 8
prints 5

Iterator Ranges

= pair `p,q` of iterators

end-of-range iterator q points one behind the last element in the range

Making Vectors From Ranges

vector<int> u {0,1,2,3};
vector<int> v {begin(u),               begin(u)+2};

Assigning Ranges To A Vector

vector<int> u {0, 1, 2, 3};
vector<int> w; …
w.assign(begin(u)+1,         end(u));

Insert Elements

Insert At The End (Fastest)

.push_back(element)

vector<int> v {1,2,3};
v.push_back(4);

Insert Anywhere (Potentially Slow)

insert positions are specified with iterators

.insert(@insert_pos, element)
.insert(@insert_pos, {elem1,elem2,…})

vector<int> v {1,2,3};

v.insert(begin(v)+1, 5);

v.insert(begin(v), {7,8}); 

v.insert(end(v), 9);

Insert From Iterator Range

.insert(@insert_pos, @first, @last)

vector<int> y {4,5,6,7,8};
vector<int> x {1,2};
x.insert(begin(x), 
         begin(y),          begin(y)+3);

Insert & Construct Elements In-Place Insert Elements In-Place Insert In-Place C++11

.emplace_back(arg1, arg2, …)
.emplace(@insert_pos, arg1, arg2, …)

makes a new element with forwarded constructor arguments

struct p2d {
  p2d(int x_, int y_):
    x{x_}, y{y_} {}
  int x, y;
};
vector<p2d> v { p2d{2,3} };
// insert copy
v.push_back( p2d{6,4} );
// construct in place with
// constructor ↓ ↓ arguments
v.emplace_back(9,7);
// iterator ↓ to first pos
v.emplace(begin(v), 5,8);

custom 
← constructor
necessary for
emplace(_back)

2
3

2
3
6
4


2
3
6
4
9
7

5
8
2
3
6
4
9
7

Erase Elements

Erase At The End (Fast)

vector<int> v {1,2,3,4,5,6};
v.pop_back();

Erase Everything (Fast)

vector<int> v {1,2,3,4,5,6};
v.clear();

Erase Anywhere (Potentially Slow)

which elements to erase is specified with iterators and iterator ranges

.erase(@position)
.erase(@range_begin, @range_end)

vector<int> v {1,2,3,4,5,6};
v.erase( begin(v)+2 );

vector<int> v {1,2,3,4,5,6};
v.erase( begin(v)+1,          begin(v)+4 );

Erasing does not affect the capacity, i.e., none of the vector's memory is freed.

Shrink The Capacity / Free Memory Shrinking

Erasing elements from a vector does never change the capacity and thus never frees any memory.

`.shrink_to_fit()` (May work)

ISO standard does not demand that it actually shrinks
standard library implementation might decide not to shrink

vector<int> v;
// add a lot of elements …
// erase elements …
v.shrink_to_fit(); C++11

Guaranteed to work:

make temporary copy ⇒ copy does exactly fit the elements
exchange memory buffers by swapping/moving
temporary gets automatically destroyed

vector<int> v;
// add a lot of elements …
// erase elements …
// shrink: make a new copy and
// replace v's content with it:
v = vector<int>(v);       C++11-20
// or:
v.swap( vector<int>(v) ); C++98-20

Attention After Insert/Erase! After Insert/Erase Attention!

All iterators into a vector are invalidated if its capacity is changed or elements are moved by insert, push_back, emplace, emplace_back, erase, =, assign, resize, reserve. (Swapping two vector's contents does not invalidate iterators, except for the end iterator.)

vector<int> v {0,1,2,3,5,6};
auto i = begin(v) + 3;

Dangerous

use of iterator after insert/erase:

v.insert(i,8);
cout << *i; //

v.erase(i);
cout << *i; //

Correct

use new valid iterator returned by insert/erase
the returned iterator refers to the original position

i = v.insert(i,8);
cout << *i;

i = v.erase(i);  
cout << *i;

Overview: Iterator Invalidating Operations Iterator Invalidating Operations Invalidation

Operations	Invalidated Iterators
`const` (read only) operations	none
`swap`, `std::swap`	only `end()`
`reserve`, `shrink_to_fit`	if capacity changed: all else: none
`push_back`, `emplace_back`	if capacity changed: all else: only `end()`
`insert`, `emplace`	if capacity changed: all else: only at or after insertion point (incl. `end()`)
`resize`	if capacity changed: all else: only `end()` and iterators to erased elements
`pop_back`	iterators to erased element and `end()`
`erase`	iterators to erased elements and all after them (incl. `end()`)
`clear`, `operator=`, `assign`	all

`std::vector` Interface Overview

(click for fullscreen view)

`deque<T>`

Double Ended Queue

constant-time random access (extremely small overhead)
fast traversal; good for linear searches
good insertion and deletion performance at both ends
insertion does not invalidate references/pointers to elements
potentially slow if insert/erase operations at random positions dominate
potentially slow if element type has high copy/assignment cost (reordering elements requires copying/moving them)
potentially long allocation times for very large amount of values (can be mitigated, see here )

#include <deque>
std::deque<int> d {0, 0, 0};
d.push_back(1);
d.push_front(2);
vector<int>   v {3, 4, 5, 6};
d.insert(begin(d),
         begin(v), end(v));
d.pop_front();

d.erase(begin(d)+2, begin(d)+5);

`std::deque` Interface Overview

(click for fullscreen view)

`list<T>`

Doubly-linked List

restructuring operations don't require elements to be moved/copied (good for storing large objects with high copy/assignment cost)
constant-time splicing (of complete lists)
random access only in linear time
slow traversal due to bad memory locality

#include <list>
std::list<int> l {3};
l.push_back(2);
l.push_front(4);
l.splice(begin(l)+1,
           list<int>{8, 4, 7});
l.reverse();
l.sort();
l.unique();


3
3 ⇄ 2
4 ⇄ 3 ⇄ 2

4 ⇄ 8 ⇄ 4 ⇄ 7 ⇄ 3 ⇄ 2
2 ⇄ 3 ⇄ 8 ⇄ 4 ⇄ 7 ⇄ 4
2 ⇄ 3 ⇄ 4 ⇄ 4 ⇄ 7 ⇄ 8
2 ⇄ 3 ⇄ 4 ⇄ 7⇄ 8

`std::list` Interface Overview

(click for fullscreen view)

`forward_list<T>`

Singly-linked List

uses less memory than list
restructuring operations don't require elements to be moved/copied (good for storing large objects with high copy/assignment cost)
constant-time splicing (of complete lists)
random access only in linear time
slow traversal due to bad memory locality
only forward traversal possible
somewhat cumbersome interface due to forward-only links
- no: size(), back(), push_back(), pop_back(), insert()
- instead: insert_after(), splice_after(), before_begin()

#include <forward_list>
std::forward_list<int> l {23,42,4};
l.insert_after(begin(l), 5);
l.insert_after(  before_begin(l), 88);
l.erase_after(begin(l));


23 → 42 → 4
23 → 5 → 42 → 4
88 → 23 → 5 → 42 → 4
88 → 5 → 42 → 4

`std::forward_list` Interface Overview

std::forward_list interface visual overview

(click for fullscreen view)

Guidelines

Which Sequence Container Should I Use? Which Sequence Container? Which?

Default choice: `std::vector`!

flowchart for selecting an appropriate standard library container

Iterators

Beginner's Guide / Std.Library 1

Views

Related …

std::vector

Overview Sheet "Sequence Containers"

Last updated: 2022-06-01

First Steps

Input & Output

Custom Types – Part 1

Diagnostics

Standard Library – Part 1

Function Objects

Standard Library – Part 2

Code Organization

Custom Types – Part 2

Generic Programming

Memory Management

Software Design Basics

Common Features

Regularity: Copy, Assign, Compare

All standard sequence containers are regular types:

Type Argument Deduction C++17

Common Interface Parts

Iterators for Forward Traversal

Const Iterators for Forward Traversal

Emptiness Query

Type Interface

array<T,size>

vector<T>

C++'s default container

Quick Recap

Iterator Ranges

= pair p,q of iterators

Making Vectors From Ranges

Assigning Ranges To A Vector

Insert Elements

Insert At The End (Fastest)

Insert Anywhere (Potentially Slow)

Insert From Iterator Range

Insert & Construct Elements In-Place Insert Elements In-Place Insert In-Place C++11

Erase Elements

Erase At The End (Fast)

Erase Everything (Fast)

Erase Anywhere (Potentially Slow)

Shrink The Capacity / Free Memory Shrinking

.shrink_to_fit() (May work)

Guaranteed to work:

Attention After Insert/Erase! After Insert/Erase Attention!

Dangerous

Correct

Overview: Iterator Invalidating Operations Iterator Invalidating Operations Invalidation

std::vector Interface Overview

deque<T>

Double Ended Queue

std::deque Interface Overview

list<T>

Doubly-linked List

std::list Interface Overview

forward_list<T>

Singly-linked List

std::forward_list Interface Overview

Guidelines

Which Sequence Container Should I Use? Which Sequence Container? Which?

Default choice: std::vector!

Related …

Comments…

`array<T,size>`

`vector<T>`

= pair `p,q` of iterators

`.shrink_to_fit()` (May work)

`std::vector` Interface Overview

`deque<T>`

`std::deque` Interface Overview

`list<T>`

`std::list` Interface Overview

`forward_list<T>`

`std::forward_list` Interface Overview

Default choice: `std::vector`!