C++ STL Containers: vector, map, set, unordered_map & Adaptors Masterclass
📌 Covered in this in-depth guide:
vector & deque · list & forward_list · map & set · unordered_map & set · stack/queue/priority_queue · pair & tuple · optional & variant · Container Complexity
Welcome to Phase 14: STL Containers! The C++ Standard Template Library provides production-grade, generic, battle-tested data structures. Each container makes different trade-offs between time complexity, memory layout, and ordering guarantees. Choosing the right container is a key skill.
1Container Comparison Master Table
| Container | Ordered? | Access | Insert/Erase (avg) | Memory |
|---|---|---|---|---|
std::vector<T> | No (insertion) | O(1) random | O(1) back / O(n) middle | Contiguous heap |
std::deque<T> | No | O(1) random | O(1) front & back | Chunked |
std::list<T> | No | O(n) | O(1) any position | Node-based |
std::set<T> | Sorted | O(log n) | O(log n) | Red-Black tree |
std::map<K,V> | Sorted by key | O(log n) | O(log n) | Red-Black tree |
std::unordered_set<T> | No | O(1) avg | O(1) avg | Hash table |
std::unordered_map<K,V> | No | O(1) avg | O(1) avg | Hash table |
std::stack<T> | LIFO | top only | O(1) | Adaptor over deque |
std::queue<T> | FIFO | front only | O(1) | Adaptor over deque |
std::priority_queue<T> | Max heap | top = max | O(log n) | Heap over vector |
2Sequence Containers in Depth
C++ — vector, deque, list▶ Run in Compiler
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
int main() {
// ─── std::vector ─────────────────────────────────────
std::vector<int> vec{10, 20, 30};
vec.reserve(10); // pre-allocate capacity
vec.push_back(40);
vec.emplace_back(50); // construct in-place
vec.erase(vec.begin() + 1); // remove element at index 1
std::cout << "vector: ";
for (int v : vec) std::cout << v << " ";
std::cout << "| size=" << vec.size() << " cap=" << vec.capacity() << "
";
// ─── std::deque ─────────────────────────────────────
std::deque<int> dq{20, 30};
dq.push_front(10); // O(1) front insert
dq.push_back(40); // O(1) back insert
std::cout << "deque: ";
for (int d : dq) std::cout << d << " ";
std::cout << "
";
// ─── std::list (doubly-linked) ───────────────────────
std::list<int> lst{10, 30, 20, 40};
lst.sort(); // O(n log n) in-place
lst.unique(); // remove consecutive duplicates
std::cout << "list sorted: ";
for (int l : lst) std::cout << l << " ";
std::cout << "
";
return 0;
}3Associative & Unordered Containers
C++ — map, set, unordered_map▶ Run in Compiler
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <string>
int main() {
// ─── std::map (sorted by key, unique keys) ───────────
std::map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 87;
scores.emplace("Charlie", 92);
scores["Bob"] = 90; // update
std::cout << "Sorted scores:
";
for (const auto& [name, score] : scores) { // structured binding C++17
std::cout << " " << name << ": " << score << "
";
}
auto it = scores.find("Alice");
if (it != scores.end()) std::cout << "Found Alice: " << it->second << "
";
// ─── std::set (sorted, unique elements) ─────────────
std::set<int> primes{2, 3, 5, 7, 11};
primes.insert(13);
primes.insert(3); // duplicate ignored
std::cout << "Primes: ";
for (int p : primes) std::cout << p << " ";
std::cout << "
";
// ─── std::unordered_map (O(1) average) ──────────────
std::unordered_map<std::string, int> wordCount;
for (const std::string& word : {"the", "cat", "sat", "the", "cat", "the"})
wordCount[word]++;
std::cout << "Word counts:
";
for (const auto& [w, c] : wordCount)
std::cout << " " << w << ": " << c << "
";
return 0;
}4Utility Types: pair, tuple, optional, variant
C++ — pair, tuple, optional, variant▶ Run in Compiler
#include <iostream>
#include <tuple>
#include <optional>
#include <variant>
#include <string>
// optional: a value that might not exist
std::optional<int> findIndex(const std::vector<int>& v, int target) {
for (int i = 0; i < (int)v.size(); ++i)
if (v[i] == target) return i;
return std::nullopt; // explicitly "no value"
}
int main() {
// pair
auto p = std::make_pair(42, std::string("hello"));
std::cout << p.first << ", " << p.second << "
";
// tuple
auto t = std::make_tuple(1, 3.14, std::string("C++20"));
std::cout << std::get<0>(t) << " " << std::get<1>(t) << " " << std::get<2>(t) << "
";
// optional
std::vector<int> nums{10, 20, 30, 40};
if (auto idx = findIndex(nums, 30))
std::cout << "Found at index: " << *idx << "
";
else
std::cout << "Not found
";
// variant: type-safe union
std::variant<int, double, std::string> v;
v = 42;
std::cout << "variant int: " << std::get<int>(v) << "
";
v = std::string("hello variant");
std::cout << "variant str: " << std::get<std::string>(v) << "
";
return 0;
}5Technical FAQs
Q1: When to use vector vs list?
Use vector by default — cache-friendly contiguous memory wins in practice. Use list only when you need O(1) insert/erase at arbitrary positions with stable iterators.
Q2: What is emplace_back vs push_back?
emplace_back(args...) constructs the element in-place — avoids a copy/move. push_back(obj) copies or moves an already-constructed object. Prefer emplace_back.
Q3: When does unordered_map degrade to O(n)?
In worst-case hash collisions, all keys land in the same bucket — O(n) lookup. Prevent this with a good hash function or by using reserve() to avoid rehashing.
Q4: What is std::optional used for?
Return std::optional<T> from functions that may fail to produce a value — instead of using sentinel values (-1, nullptr, or throwing exceptions for ordinary "not found" cases).
Q5: Difference between std::set and std::unordered_set?
std::set keeps elements sorted (O(log n) ops) using a Red-Black tree. std::unordered_set uses hashing for O(1) average ops but has no ordering guarantee.