Ch9.2: Common Operations

Overview

All sequential containers share a large set of common operations. This section presents comprehensive tables showing what each operation does, how to use it, and which containers support it. A ✓ means supported; — means not available; a note means the operation exists but with different semantics.

1. Type Aliases

Every container exposes a standard set of nested type aliases. These let you write generic code that adapts to the container’s element type, size type, and iterator category.

Type Alias Description Example vector deque list forward_list array bitvec span string_view
value_type The type of elements stored in the container. ::std::vector<T>::value_type x; ✓✓✓✓ ✓bool✓char_type
size_type Unsigned integer type for sizes and indices. Always ::std::size_t. using Sz = C::size_type; size_tsize_t size_tsize_t size_tsize_t size_tsize_t
difference_type Signed integer type for iterator differences. Always ::std::ptrdiff_t. auto d = it2 - it1; ptrdiff_tptrdiff_t ptrdiff_tptrdiff_t ptrdiff_tptrdiff_t ptrdiff_tptrdiff_t
reference Type returned when dereferencing an iterator. For bitvec this is a proxy, not a real reference. T& r = v[0]; T&T&T&T& T&—T&ch const&
const_reference A const-qualified reference to an element. T const& r = v[0]; T const&T const&T const&T const& T const&—T const&ch const&
pointer Pointer to value_type. For bitvec this is a proxy iterator, not a raw pointer. T* p = v.data(); T*T*T*T* T*—T*ch const*
iterator category The iterator concept the container supports. Determines which algorithms can be used. using ItCat = typename C::iterator_category; ContiguousRandom access BidirectionalForward Contiguous— ContiguousContiguous (const)
reverse_iterator Whether the container supports reverse iteration via rbegin() / rend(). for (auto it = v.rbegin(); it != v.rend(); ++it) ✓✓✓ —✓— ✓✓

2. Capacity Operations

These operations query or adjust the number of elements a container can hold without reallocating.

Operation Description Example vector deque list forward_list array bitvec span string_view
empty() / is_empty() Returns true if the container has no elements. if (v.is_empty()) { ... } ✓✓✓✓ ✓✓✓✓
size() Returns the number of elements currently stored. auto n = v.size(); ✓✓— — (see note) ✓ (static)✓ ✓✓
size_bytes() Returns the total number of bytes occupied by the elements (size() * sizeof(T)). auto bytes = v.size_bytes(); ✓✓✓✓ ✓✓✓✓
max_size() Returns the maximum number of elements the container could theoretically hold. auto m = v.max_size(); ✓✓✓— ✓✓✓✓
capacity() Returns the number of elements that can be stored before a reallocation is needed. auto c = v.capacity(); ✓✓—— —✓——
reserve() Requests that capacity be at least n elements. Does not change size(). v.reserve(100zu); ✓ — (see reserve_back) ———✓ ——
shrink_to_fit() Requests removal of unused capacity, reducing memory usage. May invalidate iterators. v.shrink_to_fit(); ✓✓—— —✓——

Note: Neither list nor forward_list provides size(). Counting elements in a linked list requires Θ(n) traversal, so the size is intentionally omitted to avoid hiding the cost. Use ::std::ranges::distance() if you need it.

deque note: Instead of reserve(), a deque provides reserve_back(n) and reserve_front(n) for reserving capacity at each end independently. It also provides front_capacity() and back_capacity().

3. Element Access

These operations provide direct access to individual elements by index or position.

Operation Description Example vector deque list forward_list array span string_view
operator[] Access element at index. Bounds-checked: calls fast_terminate() if out of range. auto x = v[2zu]; ✓✓—— ✓✓✓
index_unchecked() Access element at index without bounds checking. Faster but undefined behaviour if out of range. auto x = v.index_unchecked(2zu); ✓✓—— ✓✓✓
front() Returns a reference to the first element. Undefined behaviour if empty. auto x = v.front(); ✓✓✓✓ ✓✓✓
back() Returns a reference to the last element. Undefined behaviour if empty. auto x = v.back(); ✓✓✓— ✓✓✓
data() Returns a raw pointer to the underlying contiguous storage. T* p = v.data(); ✓——— ✓✓✓
front_unchecked() Returns a reference to the first element without checking if the container is empty. auto x = v.front_unchecked(); ✓✓✓✓ ✓✓✓
back_unchecked() Returns a reference to the last element without checking if the container is empty. auto x = v.back_unchecked(); ✓✓✓— ✓✓✓

4. Iterator Operations

These operations return iterators that delimit the elements of the container. All iterators follow the left-inclusive convention: the range [begin(), end()) includes the first element but excludes the past-the-end element.

Operation Description Example vector deque list forward_list array span string_view
begin() / end() Returns an iterator to the first element / to the position past the last element. for (auto it = v.begin(); it != v.end(); ++it) ✓✓✓✓ ✓✓✓
cbegin() / cend() Returns a const iterator. The elements cannot be modified through this iterator. for (auto it = v.cbegin(); it != v.cend(); ++it) ✓✓✓✓ ✓✓✓
rbegin() / rend() Returns a reverse iterator. Iterates from last element to first. for (auto it = v.rbegin(); it != v.rend(); ++it) ✓✓✓✓ ✓✓✓
before_begin() Returns an iterator to the position before the first element. Only forward_list provides this, for insertion at the front. fl.insert_after(fl.before_begin(), val); ———✓ ———

5. Modifiers

These operations add, remove, or replace elements in the container.

Operation Description Example vector deque list forward_list bitvec
clear() Removes all elements. Memory is not deallocated; capacity is preserved for reuse. v.clear(); ✓✓✓✓ ✓
clear_destroy() Removes all elements and deallocates all memory. Equivalent to clear() followed by shrink_to_fit(). v.clear_destroy(); ✓✓✓✓ ✓
push_back() Adds a copy of val to the end of the container. v.push_back(42zu); ✓✓✓— ✓
push_front() Adds a copy of val to the front of the container. v.push_front(42zu); —✓✓✓ —
pop_back() Removes the last element. Undefined behaviour if the container is empty. v.pop_back(); ✓✓✓— ✓
pop_front() Removes the first element. Undefined behaviour if the container is empty. v.pop_front(); —✓✓✓ —
emplace_back() Constructs an element in-place at the end, forwarding args... to the constructor. v.emplace_back(1zu, 2zu); ✓✓✓— —
emplace_front() Constructs an element in-place at the front, forwarding args... to the constructor. v.emplace_front(42zu); —✓✓✓ —
resize() Changes the number of elements. If growing, new elements are value-initialised. If shrinking, elements at the end are removed. v.resize(10zu); ✓✓—— ✓
assign() Replaces the entire contents. Overloads: assign(count, val) or assign(first, last). v.assign(5zu, 42zu); ✓✓—— —
append_range() Appends all elements from a range [first, last) to the end of the container. v.append_range(other.begin(), other.end()); ✓✓—— ✓
swap() Exchanges the contents of two containers of the same type. Θ(1) for most containers. v.swap(w); ✓✓✓✓ ✓

Key takeaways

← Ch9.1: Overview ↑ Main Page Ch9.3: Insert/Erase by Index →