Sekvenční kontejnery: vektor, deque, seznam, pole
Explore the sequence containers in the STL — vector, deque, list, forward_list, and array. Learn their performance trade-offs, memory layouts, and iterator invalidation rules.
What Are Sequence Containers?
Sequence containers store elements in a strict linear order. The STL provides five sequence containers, each optimized for different access and mutation patterns:
- std::vector — dynamic array, contiguous memory
- std::deque — double-ended queue, fast insertion at both ends
- std::list — doubly-linked list
- std::forward_list — singly-linked list
- std::array — fixed-size array, stack-allocated
Choosing the right container is one of the most impactful performance decisions you will make in C++. The key factors are access pattern, insertion/deletion pattern, and cache locality.
std::vector — Výchozí volba
std::vectoris the most commonly used container. It stores elements in a single contiguous block of memory, giving it excellent cache performance and O(1) random access. Appending elements withpush_backis amortized O(1) because the vector doubles its capacity when full.
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums; // empty vector
nums.reserve(100); // pre-allocate for 100 elements (no reallocation)
for (int i = 0; i < 10; ++i) {
nums.push_back(i * i); // amortized O(1)
}
// Size vs capacity
std::cout << "Size: " << nums.size() << '\n'; // 10
std::cout << "Capacity: " << nums.capacity() << '\n'; // >= 100
// Random access — O(1)
std::cout << "Element 3: " << nums[3] << '\n'; // 9
std::cout << "Element 3: " << nums.at(3) << '\n'; // 9 (bounds-checked)
// Erase-remove idiom (pre-C++20)
nums.erase(std::remove_if(nums.begin(), nums.end(),
[](int x) { return x > 50; }),
nums.end());
// C++20: std::erase_if (cleaner)
std::erase_if(nums, [](int x) { return x > 30; });
// Range-based for loop
for (int n : nums) {
std::cout << n << ' ';
}
std::cout << '\n';
}deque, list, and forward_list
std::dequeprovides O(1) insertion and deletion at both the front and back, but uses a segmented memory layout (array of fixed-size blocks) rather than a single contiguous allocation.std::listis a doubly-linked list offering O(1) insertion/deletion anywhere given an iterator, at the cost of poor cache locality.std::forward_listis a singly-linked list that uses less memory per node but only supports forward traversal.
#include <deque>
#include <list>
#include <forward_list>
#include <iostream>
int main() {
// deque — O(1) push_front and push_back
std::deque<int> dq;
dq.push_front(1); // O(1) — vector cannot do this efficiently
dq.push_back(2); // O(1)
dq.push_front(0); // O(1)
// dq: {0, 1, 2}
// list — O(1) insert/erase at any position with iterator
std::list<std::string> names = {"Alice", "Charlie", "Eve"};
auto it = std::next(names.begin()); // points to "Charlie"
names.insert(it, "Bob"); // O(1) insert before "Charlie"
names.erase(it); // O(1) erase "Charlie"
// names: {"Alice", "Bob", "Eve"}
// list has splice — O(1) move of entire sublists
std::list<std::string> more = {"Frank", "Grace"};
names.splice(names.end(), more); // moves all of 'more' into 'names'
// names: {"Alice", "Bob", "Eve", "Frank", "Grace"}
// more is now empty
// forward_list — singly linked, no size(), push_front only
std::forward_list<int> fl = {3, 1, 4, 1, 5};
fl.push_front(0);
fl.sort(); // member sort — O(n log n), stable
fl.unique(); // remove consecutive duplicates
// fl: {0, 1, 3, 4, 5}
for (int v : fl) std::cout << v << ' ';
std::cout << '\n';
}std::array — Fixed-Size, Zero Overhead
std::arraywraps a C-style array in a proper class, providing.size(),.at(), iterators, and compatibility with all STL algorithms — with zero overhead compared to a rawT[N].
#include <array>
#include <algorithm>
#include <iostream>
int main() {
std::array<int, 5> arr = {5, 2, 8, 1, 9};
std::sort(arr.begin(), arr.end()); // works with STL algorithms
std::cout << "Size: " << arr.size() << '\n'; // constexpr — known at compile time
std::cout << "Front: " << arr.front() << '\n'; // 1
std::cout << "Back: " << arr.back() << '\n'; // 9
// Bounds-checked access
try {
arr.at(10); // throws std::out_of_range
} catch (const std::out_of_range& e) {
std::cout << "Out of range: " << e.what() << '\n';
}
// Compile-time size via std::tuple_size
constexpr std::size_t n = std::tuple_size_v<decltype(arr)>; // 5
static_assert(n == 5);
}Choosing the Right Sequence Container
Použijte tento průvodce rozhodováním:
Použijtestd::vector (výchozí), když potřebujete náhodný přístup, iteraci přátelskou k mezipaměti nebo push/pop na zadní straně. Naprostá většina kódu by měla používatvector.
Použijtestd::deque, když potřebujete časté vkládání/vyjímání zepředu i zezadu (např. posuvné okno, fronta BFS).
Použijtestd::list, když potřebujete O(1) vložení/odebírání uprostřed daného iterátoru, nebo když potřebujetesplice()k přesouvání podseznamů mezi seznamy bez kopírování.
Použijtestd::forward_list, když záleží na paměti na uzel a potřebujete pouze procházení vpřed.
Použijtestd::array, když je velikost známá v době kompilace a nikdy se nezmění.
Poznámka k výkonu: Kvůli efektům mezipaměti procesorustd::vectorčasto překonávástd::listi pro střední vložení na moderním hardwaru až do překvapivě velkých velikostí (tisíce prvků). Před výběrem propojeného seznamu vždy změřte.
Each container has different rules for when iterators, pointers, and references become invalid:
vector — Insertion that triggers reallocation invalidates all iterators. Insertion without reallocation invalidates iterators at or after the insertion point. Erasure invalidates iterators at or after the erasure point.
deque — Insertion at the front or back invalidates all iterators but not references/pointers to existing elements. Insertion in the middle invalidates everything. Erasure at front/back only invalidates the erased element's iterator.
list/forward_list — Insertion and erasure never invalidate iterators, references, or pointers to other elements. Only the erased element's iterator is invalidated.
array — Iterators are never invalidated (the array cannot change size).
A common bug is modifying avectorinside a range-based for loop. If apush_backtriggers reallocation, the loop's hidden iterators become dangling.
If you know (or can estimate) how many elements avectorwill hold, callreserve()before filling it. This pre-allocates memory and avoids costly reallocations:
-reserve(n)changes capacity but not size — no elements are added.
-resize(n)changes size — it actually default-constructs elements.
-shrink_to_fit()is a non-binding request to reduce capacity to match size.
For hot loops that build vectors, a singlereserve()call can cut allocation overhead dramatically. Measure with large data sets to see the difference.
std::vectoris the default choice — contiguous memory means cache-friendly iteration and O(1) random access- Use
reserve()to pre-allocate vector memory when the approximate size is known std::dequeprovides O(1) push/pop at both front and back, but is not contiguousstd::listnabízí O(1) vložení/vymazání s iterátorem a nikdy neruší platnost ostatních iterátorůstd::arrayis a zero-overhead wrapper around C arrays with full STL compatibility- Iterator invalidation rules differ per container — know them to avoid dangling iterator bugs
Kvíz — Otestujte své znalosti
(15 XP)1. Which sequence container provides O(1) amortized`push_back`and contiguous memory layout?
2. What happens to all vector iterators when a`push_back`triggers reallocation?
3. What is the difference between`reserve(n)`and`resize(n)`on a vector?