Sequential Containers

Container: A type that stores a collection of objects.

Sequential Container: A container whose elements are arranged according to their position in the sequence.

Container Adaptor: A type that provides a specialized interface on top of another container.

Common sequential containers include:

#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <string>
#include <vector>

9.1 Overview of the Sequential Containers

The sequential containers differ mainly in:

how elements are stored
how elements are accessed
where insertion and deletion are efficient

Container	Main Characteristic
`vector`	Dynamic array with fast random access
`deque`	Fast random access and insertion at both ends
`list`	Doubly linked list
`forward_list`	Singly linked list
`array`	Fixed-size array
`string`	Specialized character sequence

`vector`

vector: A variable-size sequence stored contiguously in memory.

std::vector<int> values{
    10,
    20,
    30
};

std::cout << values[1];

Output:

vector provides fast random access.

values[2] = 100;

Insertion at the end is efficient.

values.push_back(40);

Insertion in the middle may require moving later elements.

`deque`

deque: A double-ended queue supporting fast insertion and removal at both ends.

std::deque<int> values{
    20,
    30
};

values.push_front(10);
values.push_back(40);

Result:

10 20 30 40

Unlike vector, deque efficiently supports:

push_front()
pop_front()

while also providing random access.

`list`

list: A doubly linked list.

std::list<int> values{
    10,
    20,
    30
};

A list supports efficient insertion and deletion at arbitrary iterator positions.

auto iter = values.begin();

++iter;

values.insert(
    iter,
    15
);

Result:

10 15 20 30

A list does not provide random-access subscripting.

Invalid:

// values[2]

`forward_list`

forward_list: A singly linked list that supports only forward traversal.

std::forward_list<int> values{
    10,
    20,
    30
};

It uses less overhead than a doubly linked list, but traversal is only forward.

`array`

array: A fixed-size standard-library container.

std::array<int, 3> values{
    10,
    20,
    30
};

The size is part of the type:

std::array<int, 3>

and cannot change after construction.

Choosing a Sequential Container

Use vector by default unless another container has a clear advantage.

Typical choices:

Need fast random access
    -> vector

Need insertion at both ends
    -> deque

Need frequent middle insertion/deletion
    -> list / forward_list

Need fixed size
    -> array

Need character sequence
    -> string

Container choice should be based on the operations the program performs most often.

9.2 Container Library Overview

Containers are class templates.

std::vector<int> numbers;
std::vector<std::string> words;

The element type is supplied as a template argument.

A container can also store another container.

std::vector<
    std::vector<int>
> matrix;

Element Type Requirements

Not every container operation can be used with every possible element type.

An operation is valid only when the element type supports the operations required by that container operation.

For example, copying a container requires its elements to be copyable.

1) Iterators

Iterator: An object used to access and move through container elements.

std::vector<int> values{
    10,
    20,
    30
};

auto iter =
    values.begin();

std::cout << *iter;

Output:

Incrementing the iterator moves to the next element.

++iter;

std::cout << *iter;

Output:

Iterator Ranges

A range is normally represented by two iterators:

[begin, end)

This means:

begin is included
end is excluded

Example:

auto begin =
    values.begin();

auto end =
    values.end();

end() refers to one position past the last element.

It must not be dereferenced.

Wrong:

// std::cout << *values.end();

Traversing a Range

for (
    auto iter = values.begin();
    iter != values.end();
    ++iter)
{
    std::cout
        << *iter
        << '\n';
}

A valid range has the property that repeatedly incrementing the first iterator eventually reaches the second.

Empty Range

A range is empty when:

begin == end

For an empty container:

std::vector<int> values;

bool empty =
    values.begin()
    == values.end();

Random-Access Iterator Operations

Containers such as:

vector
deque
array
string

support iterator arithmetic.

std::vector<int> values{
    10,
    20,
    30,
    40
};

auto iter =
    values.begin() + 2;

std::cout << *iter;

Output:

list and forward_list iterators do not support this form of arithmetic.

2) Container Type Members

Containers define useful member types.

For:

std::vector<int> values;

examples include:

std::vector<int>::value_type
std::vector<int>::size_type
std::vector<int>::iterator
std::vector<int>::const_iterator

Important types:

Type	Meaning
`value_type`	Element type
`size_type`	Type used for sizes
`difference_type`	Signed iterator-distance type
`iterator`	Modifiable iterator
`const_iterator`	Read-only iterator
`reference`	Reference to element
`const_reference`	Reference to const element
`reverse_iterator`	Reverse iterator

Example:

std::vector<int>::size_type size =
    values.size();

Usually auto is simpler:

auto size =
    values.size();

`iterator` vs. `const_iterator`

A normal iterator can modify elements.

std::vector<int> values{
    1,
    2,
    3
};

std::vector<int>::iterator iter =
    values.begin();

*iter = 100;

A const_iterator cannot modify through the iterator.

std::vector<int>::const_iterator iter =
    values.cbegin();

std::cout << *iter;

But:

// *iter = 100;

is not allowed.

3) `begin` and `end` Members

Common iterator members include:

begin()
end()

cbegin()
cend()

rbegin()
rend()

crbegin()
crend()

`begin()` and `end()`

for (
    auto iter = values.begin();
    iter != values.end();
    ++iter)
{
    std::cout << *iter;
}

`cbegin()` and `cend()`

These always return const iterators.

for (
    auto iter = values.cbegin();
    iter != values.cend();
    ++iter)
{
    std::cout << *iter;
}

Use them when the loop should only read the elements.

Reverse Iterators

rbegin() starts at the last element.

rend() represents the position before the first element.

std::vector<int> values{
    10,
    20,
    30
};

for (
    auto iter = values.rbegin();
    iter != values.rend();
    ++iter)
{
    std::cout
        << *iter
        << ' ';
}

Output:

30 20 10

4) Defining and Initializing a Container

Containers can be initialized in several ways.

Default Construction

std::vector<int> values;

A variable-size container is initially empty.

values.empty();

returns true.

List Initialization

std::vector<int> values{
    1,
    2,
    3,
    4
};

The number of initializers determines the size.

Copy Construction

std::vector<int> source{
    1,
    2,
    3
};

std::vector<int> destination(
    source
);

destination contains copies of the elements in source.

Range Construction

A container can be constructed from an iterator range.

std::list<int> source{
    1,
    2,
    3
};

std::vector<int> destination(
    source.begin(),
    source.end()
);

Result:

1 2 3

Range construction can copy between different container types when the element types are compatible.

Size Constructor

std::vector<int> values(10);

Creates ten value-initialized ints.

Conceptually:

0 0 0 0 0 0 0 0 0 0

Size and Value Constructor

std::vector<int> values(
    5,
    10
);

Result:

10 10 10 10 10

`array` Has Fixed Size

std::array<int, 3> values{
    10,
    20,
    30
};

Its type includes the size.

These are different types:

std::array<int, 3>
std::array<int, 5>

Unlike a built-in array, library array objects can be copied and assigned when their types match.

std::array<int, 3> a{
    1,
    2,
    3
};

std::array<int, 3> b;

b = a;

5) Assignment and `swap`

Container assignment replaces the target container's elements.

std::vector<int> a{
    1,
    2,
    3
};

std::vector<int> b{
    10,
    20
};

a = b;

Now:

a = {10, 20}

List Assignment

a = {
    100,
    200,
    300
};

The old elements are replaced.

`assign()`

assign() replaces all existing elements.

std::vector<int> values;

values.assign(
    5,
    10
);

Result:

10 10 10 10 10

Assigning a Range

std::list<int> source{
    1,
    2,
    3
};

std::vector<int> destination;

destination.assign(
    source.begin(),
    source.end()
);

Result:

1 2 3

This allows assignment from a different compatible container type.

`swap()`

swap() exchanges container contents.

std::vector<int> a{
    1,
    2
};

std::vector<int> b{
    10,
    20,
    30
};

a.swap(b);

Afterward:

a = {10, 20, 30}
b = {1, 2}

The nonmember form is also available.

swap(a, b);

For most variable-size containers, swapping is efficient because internal container structures are exchanged rather than copying every element.

array differs because its elements must be exchanged.

6) Container Size Operations

Common size operations include:

values.size();
values.empty();
values.max_size();

`size()`

std::vector<int> values{
    10,
    20,
    30
};

std::cout
    << values.size();

Output:

`empty()`

if (values.empty())
{
    std::cout
        << "empty\n";
}

This is normally preferable to:

if (values.size() == 0)

when only emptiness is being checked.

`max_size()`

auto maximum =
    values.max_size();

This reports an upper bound on the number of elements the container can hold.

`forward_list`

forward_list does not provide a size() member.

Its design avoids storing the additional state required to provide constant-time size information.

7) Relational Operators

Containers of the same type can be compared.

std::vector<int> a{
    1,
    2,
    3
};

std::vector<int> b{
    1,
    2,
    3
};

bool same =
    a == b;

Result:

true

Two containers are equal when they contain equal elements in the same order.

Lexicographical Comparison

Container ordering works similarly to dictionary ordering.

std::vector<int> a{
    1,
    2
};

std::vector<int> b{
    1,
    3
};

bool result =
    a < b;

The comparison examines corresponding elements until a difference is found.

Here:

1 == 1
2 < 3

so:

a < b

is true.

Container comparisons rely on the comparison operations of their element types.

9.3 Sequential Container Operations

Sequential containers provide operations to:

add elements
access elements
remove elements
resize containers

1) Adding Elements to a Sequential Container

Important insertion operations include:

Operation	Meaning
`push_back(t)`	Add at back
`push_front(t)`	Add at front
`insert(p, t)`	Insert before `p`
`insert(p, n, t)`	Insert `n` copies before `p`
`insert(p, b, e)`	Insert range before `p`
`insert(p, il)`	Insert initializer list

Not every container supports every operation.

`push_back()`

std::vector<int> values{
    10,
    20
};

values.push_back(30);

Result:

10 20 30

`push_front()`

Containers such as deque and list support insertion at the front.

std::deque<int> values{
    20,
    30
};

values.push_front(10);

Result:

10 20 30

vector does not provide push_front().

`insert()`

insert() inserts before the supplied iterator.

std::vector<int> values{
    10,
    30
};

auto iter =
    values.begin() + 1;

values.insert(
    iter,
    20
);

Result:

10 20 30

Inserting at `end()`

Passing end() inserts at the back.

values.insert(
    values.end(),
    40
);

Equivalent in purpose to:

values.push_back(40);

Inserting Multiple Copies

std::vector<int> values{
    1,
    5
};

values.insert(
    values.begin() + 1,
    3,
    0
);

Result:

1 0 0 0 5

Inserting a Range

std::vector<int> source{
    2,
    3,
    4
};

std::vector<int> destination{
    1,
    5
};

destination.insert(
    destination.begin() + 1,
    source.begin(),
    source.end()
);

Result:

1 2 3 4 5

Return Value from `insert()`

insert() returns an iterator to an inserted element.

std::vector<int> values{
    10,
    30
};

auto iter =
    values.insert(
        values.begin() + 1,
        20
    );

std::cout << *iter;

Output:

The returned iterator is useful in loops that modify a container.

Emplace Operations

emplace constructs an element directly in the container from constructor arguments.

Suppose:

class Person
{
public:
    Person(
        std::string name,
        int age)
        : name(std::move(name)),
          age(age)
    {
    }

private:
    std::string name;
    int age;
};

Then:

std::vector<Person> people;

people.emplace_back(
    "Alice",
    20
);

The arguments are used to construct a Person directly at the end of the vector.

Related operations include:

emplace()
emplace_back()
emplace_front()

depending on the container.

2) Accessing Elements

Important access operations include:

Operation	Meaning
`front()`	First element
`back()`	Last element
`[]`	Indexed access without checking
`at()`	Indexed access with checking

`front()`

std::vector<int> values{
    10,
    20,
    30
};

std::cout
    << values.front();

Output:

`back()`

std::cout
    << values.back();

Output:

Element Access Returns References

These operations return references.

values.front() = 100;

Now:

100 20 30

Likewise:

values.back() = 300;

`operator[]`

std::cout
    << values[1];

Indexed access does not perform bounds checking.

An invalid index results in undefined behavior.

// Dangerous:
// values[100]

`at()`

at() performs bounds checking.

std::cout
    << values.at(1);

For an invalid index:

values.at(100);

the function throws:

std::out_of_range

Checking `at()`

try
{
    std::cout
        << values.at(100);
}
catch (
    const std::out_of_range& error)
{
    std::cerr
        << error.what()
        << '\n';
}

Empty Container Rule

Do not call:

front()
back()
pop_front()
pop_back()

when the required element does not exist.

Check first:

if (!values.empty())
{
    std::cout
        << values.front();
}

3) Erasing Elements

Common removal operations include:

Operation	Meaning
`pop_back()`	Remove last element
`pop_front()`	Remove first element
`erase(p)`	Remove element at `p`
`erase(b, e)`	Remove range
`clear()`	Remove all elements

`pop_back()`

std::vector<int> values{
    10,
    20,
    30
};

values.pop_back();

Result:

10 20

pop_back() removes the element but does not return it.

If the value is needed:

int value =
    values.back();

values.pop_back();

`pop_front()`

std::deque<int> values{
    10,
    20,
    30
};

values.pop_front();

Result:

20 30

`erase()`

std::vector<int> values{
    10,
    20,
    30
};

auto iter =
    values.begin() + 1;

values.erase(iter);

Result:

10 30

Return from `erase()`

erase() returns an iterator to the element following the erased element.

std::vector<int> values{
    10,
    20,
    30
};

auto iter =
    values.begin();

iter =
    values.erase(iter);

Now iter refers to:

This return value is important when erasing elements inside a loop.

Erasing a Range

std::vector<int> values{
    1,
    2,
    3,
    4,
    5
};

values.erase(
    values.begin() + 1,
    values.begin() + 4
);

The erased range is:

[1, 4)

which contains:

2 3 4

Result:

1 5

`clear()`

values.clear();

Afterward:

values.empty()

is true.

Erasing While Iterating

A common safe pattern is:

for (
    auto iter = values.begin();
    iter != values.end();)
{
    if (*iter % 2 == 0)
    {
        iter =
            values.erase(iter);
    }
    else
    {
        ++iter;
    }
}

If an element is erased, use the iterator returned by erase().

4) Specialized `forward_list` Operations

A forward_list stores only a link to the next element.

Therefore insertion and deletion are expressed relative to the element before the position being modified.

Important operations:

before_begin()
insert_after()
emplace_after()
erase_after()

`before_begin()`

before_begin() represents a special position before the first element.

std::forward_list<int> values{
    20,
    30
};

auto before =
    values.before_begin();

values.insert_after(
    before,
    10
);

Result:

10 20 30

`insert_after()`

auto iter =
    values.begin();

values.insert_after(
    iter,
    15
);

If iter refers to 10, the new sequence becomes:

10 15 20 30

`erase_after()`

auto iter =
    values.begin();

values.erase_after(iter);

This removes the element after iter.

Why `forward_list` Uses `after`

A singly linked node knows only where the next node is.

Conceptually:

node
 │
 ▼
next
 │
 ▼
next

To erase an element efficiently, the container needs access to the preceding node.

That is why the interface uses operations relative to the element before the target.

5) Resizing a Container

resize() changes the number of elements.

std::vector<int> values{
    1,
    2,
    3
};

values.resize(5);

New elements are added at the end.

Result:

1 2 3 0 0

Resize with a Value

values.resize(
    7,
    10
);

New elements are initialized to 10.

Shrinking

values.resize(2);

Elements after the second are removed.

`resize()` vs. `reserve()`

These operations are different.

resize() changes:

number of elements

reserve() changes:

available storage capacity

6) Container Operations May Invalidate Iterators

Modifying a container can invalidate:

iterators
references
pointers

Iterator Invalidation: An iterator no longer refers to a valid position or element after a container modification.

`vector` Reallocation

Suppose:

std::vector<int> values{
    1,
    2,
    3
};

auto iter =
    values.begin();

Then:

values.push_back(4);

may cause the vector to allocate new storage.

If reallocation occurs:

old storage
    ↓
new larger storage
    ↓
elements moved

The old iterator is no longer valid.

Do not assume:

// potentially invalid:
// std::cout << *iter;

`list` Stability

Insertion into list normally does not invalidate iterators or references to existing elements.

std::list<int> values{
    1,
    3
};

auto iter =
    values.begin();

values.insert(
    std::next(iter),
    2
);

The iterator to the existing first element remains valid.

Erasing Invalidates the Erased Element

Even for containers with stable iterators, an iterator referring to an erased element becomes invalid.

auto iter =
    values.begin();

values.erase(iter);

// iter is invalid

Loops That Modify Containers

Use returned iterators from modification operations.

for (
    auto iter = values.begin();
    iter != values.end();)
{
    if (should_remove(*iter))
    {
        iter =
            values.erase(iter);
    }
    else
    {
        ++iter;
    }
}

Do Not Store `end()` When Modifying the Container

Avoid:

auto end =
    values.end();

for (
    auto iter = values.begin();
    iter != end;
    ++iter)
{
    // operations that modify values
}

A modification may invalidate the saved end.

Prefer evaluating the current end() when necessary.

9.4 How a `vector` Grows

A vector stores its elements contiguously.

Conceptually:

[10][20][30][40]

This makes random access efficient.

However, the vector needs contiguous space to grow.

Reallocation

Suppose the current allocation is full.

capacity = 4
size     = 4

[10][20][30][40]

Adding another element may require new storage.

Conceptually:

allocate larger block

old:
[10][20][30][40]

new:
[10][20][30][40][ ][ ][ ][ ]

The existing elements are transferred to the new storage.

This process is called reallocation.

Why Extra Capacity Is Allocated

If a vector allocated exactly one additional slot for every push_back(), growing repeatedly would require many reallocations.

Instead, vectors usually allocate extra unused capacity.

size     = elements currently present
capacity = elements possible before reallocation

`size()` vs. `capacity()`

std::vector<int> values;

std::cout
    << values.size()
    << '\n';

std::cout
    << values.capacity()
    << '\n';

size() reports the number of constructed elements.

capacity() reports available element storage before another allocation is needed.

Always:

capacity >= size

`reserve()`

reserve() requests storage for at least a given number of elements.

std::vector<int> values;

values.reserve(100);

This does not create 100 elements.

values.size();

is still:

but the vector may now hold at least 100 elements before requiring another reallocation.

Why Use `reserve()`

If the approximate number of elements is known:

std::vector<int> values;

values.reserve(1000);

for (int i = 0;
     i != 1000;
     ++i)
{
    values.push_back(i);
}

reserving storage may reduce the number of reallocations.

`reserve()` vs. `resize()`

std::vector<int> a;

a.reserve(10);

Afterward:

size     = 0
capacity >= 10

By contrast:

std::vector<int> b;

b.resize(10);

Afterward:

size     = 10
capacity >= 10

resize() creates elements.

reserve() does not.

`shrink_to_fit()`

values.shrink_to_fit();

requests that unused capacity be reduced.

It is a request to the implementation rather than a guarantee that capacity will change.

9.5 Additional `string` Operations

string provides operations beyond the common sequential-container interface.

These include:

substring construction
substr
insertion and replacement
searching
comparison
numeric conversion

1) Other Ways to Construct `string`s

A string can be built from part of another character sequence.

Character Pointer and Count

const char text[] =
    "Hello World";

std::string s(
    text,
    5
);

Result:

Hello

The constructor copies five characters beginning at text.

Substring Constructor

std::string source =
    "Hello World";

std::string result(
    source,
    6
);

Result:

World

The second argument is the starting position.

Position and Length

std::string source =
    "Hello World";

std::string result(
    source,
    6,
    3
);

Result:

Wor

`substr()`

substr() returns a new string containing part of the original.

std::string text =
    "Hello World";

std::string result =
    text.substr(
        6,
        5
    );

Result:

World

From Position to End

std::string result =
    text.substr(6);

Result:

World

2) Other Ways to Change a `string`

Important modification operations include:

assign()
insert()
erase()
append()
replace()

`assign()`

Replaces the entire string.

std::string text =
    "Hello";

text.assign(
    "World"
);

Result:

World

`insert()`

std::string text =
    "HelloWorld";

text.insert(
    5,
    " "
);

Result:

Hello World

`erase()`

std::string text =
    "Hello World";

text.erase(
    5,
    1
);

Result:

HelloWorld

`append()`

std::string text =
    "Hello";

text.append(
    " World"
);

Result:

Hello World

Similar to:

text += " World";

`replace()`

std::string text =
    "Hello C++";

text.replace(
    6,
    3,
    "World"
);

Result:

Hello World

The selected range is removed and replaced with new characters.

Multiple Overloads

String modification functions support many input forms.

The inserted or replacement characters may come from:

another string
a character array
an iterator range
repeated characters

This allows the most convenient interface to be selected for the data available.

3) `string` Search Operations

The major search operations are:

Operation	Meaning
`find()`	First occurrence
`rfind()`	Last occurrence
`find_first_of()`	First character in search set
`find_last_of()`	Last character in search set
`find_first_not_of()`	First character not in set
`find_last_not_of()`	Last character not in set

`find()`

std::string text =
    "hello world";

auto position =
    text.find("world");

Result:

Match Not Found

When no match exists:

auto position =
    text.find("C++");

the result is:

std::string::npos

Therefore:

if (
    position
    != std::string::npos)
{
    std::cout
        << "found\n";
}

`string::npos`

string::npos is a special value of type:

std::string::size_type

representing no valid position.

Do not usually store search results in a signed int.

Prefer:

auto position =
    text.find("world");

Starting Search Position

Search can begin from a specified position.

std::string text =
    "one two one";

auto first =
    text.find("one");

auto second =
    text.find(
        "one",
        first + 1
    );

Results:

first  = 0
second = 8

`rfind()`

Search from the end.

std::string text =
    "one two one";

auto position =
    text.rfind("one");

Result:

`find_first_of()`

Find the first occurrence of any character in a search set.

std::string text =
    "abc123";

auto position =
    text.find_first_of(
        "0123456789"
    );

Result:

The first digit occurs at position 3.

`find_first_not_of()`

Find the first character not contained in a specified set.

std::string text =
    "   hello";

auto position =
    text.find_first_not_of(
        " \t"
    );

This can be useful when locating the first non-whitespace character.

4) The `compare` Functions

compare() compares strings.

std::string a =
    "apple";

std::string b =
    "banana";

int result =
    a.compare(b);

Interpretation:

result < 0
    a < b

result == 0
    a == b

result > 0
    a > b

The exact nonzero value is less important than its sign.

Equal Strings

std::string a =
    "hello";

std::string b =
    "hello";

if (a.compare(b) == 0)
{
    std::cout
        << "equal\n";
}

5) Numeric Conversions

C++ provides functions for converting between strings and numeric values.

`to_string()`

Converts arithmetic values into strings.

int value = 42;

std::string text =
    std::to_string(value);

Result:

"42"

Floating-point example:

double value = 3.14;

std::string text =
    std::to_string(value);

`stoi()`

Converts a string to int.

std::string text =
    "123";

int value =
    std::stoi(text);

Result:

Other Integer Conversions

stoi   -> int
stol   -> long
stoul  -> unsigned long
stoll  -> long long
stoull -> unsigned long long

Floating-Point Conversions

stof  -> float
stod  -> double
stold -> long double

Example:

std::string text =
    "3.14159";

double value =
    std::stod(text);

Invalid Conversion

std::string text =
    "hello";

int value =
    std::stoi(text);

cannot produce an integer.

The function throws:

std::invalid_argument

Out-of-Range Conversion

A numeric string may represent a value too large for the target type.

The conversion can then throw:

std::out_of_range

Handling Conversion Errors

try
{
    int value =
        std::stoi(text);

    std::cout << value;
}
catch (
    const std::invalid_argument&)
{
    std::cerr
        << "not a number\n";
}
catch (
    const std::out_of_range&)
{
    std::cerr
        << "number too large\n";
}

9.6 Container Adaptors

Adaptor: A mechanism that provides a different interface over an existing type.

The standard container adaptors are:

stack
queue
priority_queue

They use an underlying sequential container to store their elements.

Required headers include:

#include <queue>
#include <stack>

Defining an Adaptor

Basic stack:

std::stack<int> values;

Basic queue:

std::queue<int> values;

Priority queue:

std::priority_queue<int> values;

Default Underlying Containers

The default underlying containers are:

stack
    -> deque

queue
    -> deque

priority_queue
    -> vector

Custom Underlying Container

An adaptor can specify a different compatible container.

Example:

std::stack<
    int,
    std::vector<int>
> values;

This stack uses a vector<int> internally.

Stack Adaptor

stack: A last-in, first-out container adaptor.

LIFO

Last In
First Out

Conceptually:

push 10

top
 ↓
[10]

push 20

top
 ↓
[20]
[10]

push 30

top
 ↓
[30]
[20]
[10]

`stack::push()`

std::stack<int> values;

values.push(10);
values.push(20);
values.push(30);

`stack::top()`

std::cout
    << values.top();

Output:

The value is not removed.

`stack::pop()`

values.pop();

The top element is removed.

Now:

values.top();

returns:

pop() does not return the removed value.

If needed:

int value =
    values.top();

values.pop();

`stack::emplace()`

Constructs an object directly at the top.

std::stack<std::string> values;

values.emplace(
    5,
    'A'
);

The new string is:

AAAAA

Queue Adaptor

queue: A first-in, first-out container adaptor.

FIFO

First In
First Out

Conceptually:

push 10
push 20
push 30

front       back
  ↓           ↓
[10][20][30]

`queue::push()`

std::queue<int> values;

values.push(10);
values.push(20);
values.push(30);

`queue::front()`

std::cout
    << values.front();

Output:

`queue::back()`

std::cout
    << values.back();

Output:

`queue::pop()`

values.pop();

Removes the front element.

Now:

front = 20

Priority Queue

priority_queue: A container adaptor that gives access to the highest-priority element.

std::priority_queue<int> values;

values.push(10);
values.push(30);
values.push(20);

The top is:

values.top();

Result:

The element inserted first is not necessarily removed first.

Priority determines the order.

Priority Queue Ordering

By default, priority is determined using the element type's ordering.

For integers:

std::priority_queue<int> values;

the largest value is normally at the top.

values.push(5);
values.push(100);
values.push(20);

std::cout
    << values.top();

Output:

Removing from a Priority Queue

while (!values.empty())
{
    std::cout
        << values.top()
        << ' ';

    values.pop();
}

For:

5 100 20

the output is ordered by priority:

100 20 5

Container vs. Container Adaptor

A sequential container exposes its stored sequence directly through operations such as:

begin()
end()
insert()
erase()

An adaptor intentionally exposes a smaller specialized interface.

For example, stack provides:

push()
pop()
top()

9.1 Overview of the Sequential Containers
9.2 Container Library Overview
9.3 Sequential Container Operations
9.4 How a vector Grows
9.5 Additional string Operations
9.6 Container Adaptors

9.1 Overview of the Sequential Containers​

vector​

deque​

list​

forward_list​

array​

Choosing a Sequential Container​

9.2 Container Library Overview​

Element Type Requirements​

1) Iterators​

Iterator Ranges​

Traversing a Range​

Empty Range​

Random-Access Iterator Operations​

2) Container Type Members​

iterator vs. const_iterator​

3) begin and end Members​

begin() and end()​

cbegin() and cend()​

Reverse Iterators​

4) Defining and Initializing a Container​

Default Construction​

List Initialization​

Copy Construction​

Range Construction​

Size Constructor​

Size and Value Constructor​

array Has Fixed Size​

5) Assignment and swap​

List Assignment​

assign()​

Assigning a Range​

swap()​

6) Container Size Operations​

size()​

empty()​

max_size()​

forward_list​

7) Relational Operators​

Lexicographical Comparison​

9.3 Sequential Container Operations​

1) Adding Elements to a Sequential Container​

push_back()​

push_front()​

insert()​

Inserting at end()​

Inserting Multiple Copies​

Inserting a Range​

Return Value from insert()​

Emplace Operations​

2) Accessing Elements​

front()​

back()​

Element Access Returns References​

operator[]​

at()​

Checking at()​

Empty Container Rule​

3) Erasing Elements​

pop_back()​

pop_front()​

erase()​

Return from erase()​

Erasing a Range​

clear()​

Erasing While Iterating​

4) Specialized forward_list Operations​

before_begin()​

insert_after()​

erase_after()​

Why forward_list Uses after​

5) Resizing a Container​

Resize with a Value​

Shrinking​

resize() vs. reserve()​

6) Container Operations May Invalidate Iterators​

vector Reallocation​

list Stability​

Erasing Invalidates the Erased Element​

Loops That Modify Containers​

9.1 Overview of the Sequential Containers

`vector`

`deque`

`list`

`forward_list`

`array`

Choosing a Sequential Container

9.2 Container Library Overview

Element Type Requirements

1) Iterators

Iterator Ranges

Traversing a Range

Empty Range

Random-Access Iterator Operations

2) Container Type Members

`iterator` vs. `const_iterator`

3) `begin` and `end` Members

`begin()` and `end()`

`cbegin()` and `cend()`

Reverse Iterators

4) Defining and Initializing a Container

Default Construction

List Initialization

Copy Construction

Range Construction

Size Constructor

Size and Value Constructor

`array` Has Fixed Size

5) Assignment and `swap`

List Assignment

`assign()`

Assigning a Range

`swap()`

6) Container Size Operations

`size()`

`empty()`

`max_size()`

`forward_list`

7) Relational Operators

Lexicographical Comparison

9.3 Sequential Container Operations

1) Adding Elements to a Sequential Container

`push_back()`

`push_front()`

`insert()`

Inserting at `end()`

Inserting Multiple Copies

Inserting a Range

Return Value from `insert()`

Emplace Operations

2) Accessing Elements

`front()`

`back()`

Element Access Returns References

`operator[]`

`at()`

Checking `at()`

Empty Container Rule

3) Erasing Elements

`pop_back()`

`pop_front()`

`erase()`

Return from `erase()`

Erasing a Range

`clear()`

Erasing While Iterating

4) Specialized `forward_list` Operations

`before_begin()`

`insert_after()`

`erase_after()`

Why `forward_list` Uses `after`

5) Resizing a Container

Resize with a Value

Shrinking

`resize()` vs. `reserve()`

6) Container Operations May Invalidate Iterators

`vector` Reallocation

`list` Stability

Erasing Invalidates the Erased Element

Loops That Modify Containers