@[TOC](Comprehensive Explanation of the C++ Standard Template Library (STL) – Everything You Need to Learn About STL)

1. Concept of STL

1. 1. STL (Standard Template Library) is a generic term for the “containers + algorithms + iterators” in the C++ standard library, implemented using templates for generic programming. It evolved from HP’s STL and was standardized in C++98. Today, when people refer to STL, they usually mean these core components:

• • Containers: Structures for storing data
• • Algorithms: Such as sort, find, accumulate, transform, lower_bound, etc. (header files , )
• • Iterators: “Pointer-style” objects that decouple algorithms from containers (categories include input/output/forward/double-ended/random access, etc.)
• • Function Objects/Predicates: Comparators, custom rules (today often using lambda for direct customization)
• • Adapters: Wrappers for containers/iterators/functions (e.g., back_inserter, std::not_fn)
• • Allocators: Memory allocation strategies (usually the default is sufficient)

2. Common Container Classifications in STL:

1. Sequence Class

Container	Underlying Data Structure (Implementation Habit)	Main Features/Complexity Points
<span>std::array<T, N></span>	Fixed lengthContinuous memory	Compile-time fixed length; random access O(1); almost never invalidated (except for object destruction).
<span>std::vector<T></span>	Dynamic array (continuous memory), geometric expansion	<span>push_back</span> amortized O(1); insertion/deletion in the middle O(n);expansion invalidates all iterators/references.
<span>std::deque<T></span>	Segmented array (block list + central index)	Insertion/deletion at head/tail O(1); random access O(1); overall non-continuous; operations at both ends often invalidate iterators.
<span>std::list<T></span>	Doubly linked list (node storage)	Insertion/deletion/concatenation at known positions <span>splice</span> O(1); no random access; iterators/references stable (except for the deleted one).
<span>std::forward_list<T></span>	Singly linked list	Lighter; only provides forward iteration; insertion/deletion at head/known predecessor O(1); no <span>size()</span>.
<span>std::basic_string<charT></span> (<span>std::string</span>)	Dynamic array (continuous memory); most implementations have SSO (small string optimization)	Semantics similar to <span>vector</span> (by character); expansion rules similar; whether SSO is enforced is not mandatory, but common.

2. Ordered Associative

Container	Underlying Data Structure	Main Features/Complexity Points
<span>std::set</span> / <span>std::multiset</span>	Balanced binary search tree (usually red-black tree)	Ordered, unique/repeatable; search/insert/delete O(log n); iterators stable (except for deleted elements).
<span>std::map</span> / <span>std::multimap</span>	Balanced BST (usually red-black tree)	Ordered key-value pairs; operations O(log n); supports custom comparators.

3. Unordered Associative (Hash)

Container	Underlying Data Structure	Main Features/Complexity Points
<span>std::unordered_set</span> / <span>std::unordered_multiset</span>	Hash table: bucket array + chaining (node linked list)	Average search/insert/delete O(1), worst O(n);<span>rehash</span> willinvalidate iterators (references usually remain valid).
<span>std::unordered_map</span> / <span>std::unordered_multimap</span>	Same as above	Same as above; adjustable load factor <span>max_load_factor</span>, rehash/reserve as needed.

4. Adapters (Containers wrapped based on other containers)

Container Adapter	Typical Underlying	Main Features/Complexity Points
<span>std::stack</span>	Default <span>deque</span> (can also use <span>vector</span>/<span>list</span>)	LIFO; <span>push/pop/top</span> O(1) (depends on the underlying structure).
<span>std::queue</span>	Default <span>deque</span>	FIFO; <span>push</span> tail/<span>pop</span> head O(1).
<span>std::priority_queue</span>	<span>vector</span> based binary heap (max heap)	<span>top</span> O(1); <span>push/pop</span> O(log n); unstable sorting.

5. C++23 Extensions

Container	Underlying Data Structure	Key Points
<span>std::flat_set</span> / <span>std::flat_map</span> (and multi versions)	Sorted continuous storage (commonly <span>vector</span> + binary search)	Search O(log n), insert/delete O(n); cache-friendly, very appealing for small/medium-sized data. Implementation support depends on the compiler.

3. Operations on Containers

1. General (almost all containers have)

• • begin()/end()/cbegin()/cend(): Iteration start and end (traversal)
• • rbegin()/rend(): Reverse iteration
• • size(): Number of elements
• • empty(): Is it empty
• • clear(): Clear (many iterators become invalid)
• • swap(other) / std::swap(a,b): Constant time swap
• • Assignment/Construction: Copy/move construction, operator=

2. Common Operations for Sequence Containers (vector/deque/list/forward_list/array/string)

Element Access

• • front() / back(): First/last element
• • operator: Random access (no boundary check)
• • at(i): Access with boundary check
• • data(): Underlying pointer (for continuous storage types)

Insertion/Construction

• • insert(pos, x) / emplace(pos, args…): Insert at any position
• • push_back(x) / emplace_back(…): Insert at the tail
• • push_front(x) / emplace_front(…): Insert at the head (deque/list/forward_list)
• • assign(n, x) / assign(first,last): Reset content

Deletion/Adjustment

• • erase(pos) / erase(first,last): Delete range
• • pop_back() / pop_front(): Pop tail/head
• • resize(n): Change size (fill if insufficient, truncate if exceeded)

Specific to vector (Dynamic Array)

• • capacity(): Capacity
• • reserve(n): Reserve capacity (reduce expansions)
• • shrink_to_fit(): Reclaim excess capacity
• • <span>Note: When the size reaches capacity, vector will expand, which will invalidate all iterators/references; random access O(1).</span>

For deque (Segmented Array)

• • <span>Note: No capacity/reserve; insertion/deletion at both ends O(1), random access O(1).</span>

For list (Doubly Linked List)

• • splice(pos, other[, it|first,last]): Constant time concatenation
• • remove(val) / remove_if(pred): Delete matches
• • unique(): Remove adjacent duplicates
• • merge(other[, comp]): Merge ordered lists
• • sort([comp]) / reverse(): Sort/reverse within the list
• • <span>Note: Iterators are stable (except for deleted elements), no random access.</span>

For forward_list (Singly Linked List)

• • before_begin(): Iterator before the head
• • insert_after(pos, x) / emplace_after(…)
• • erase_after(pos) / erase_after(first,last)
• • Note: Only forward iteration; no size().

For array

• • fill(x): Fill
• • Other functions like size()/data()/front()/back() are the same as above
• • <span>Note: Fixed length, cannot insert/delete elements.</span>

3. Ordered Associative Containers (set/multiset/map/multimap, red-black trees, etc.)

Search/Range:

• • find(key): Locate iterator (O(log n))
• • count(key): Count (set/map is 0/1; multi* can be >1)
• • lower_bound(key) / upper_bound(key) / equal_range(key): Range query
• • contains(key) (C++20): Check existence

Insertion/Deletion:

• • insert(x) / emplace(args…) / erase(key|it|first,last)

Only for map/multimap:

• • operator: If not present, insert default value and return reference
• • at(key): Access with check
• • insert_or_assign(k,v) / try_emplace(k, args…) (C++17)

Node Operations (C++17):

extract(k|it) → insert(node) / merge(other)

4. Unordered Associative Containers (unordered_set/map and multi variants, hash tables)

Search/Existence:

• • find / count / contains (all average O(1))

Insertion/Deletion/Access:

• • insert / emplace / erase
• • operator[] / at (only for unordered_map)

Buckets and Load Factor (Hash Specific):

• • bucket_count() / bucket(key) / bucket_size(i)
• • load_factor() / max_load_factor(f)
• • rehash(n) / reserve(n): Control expansion
• • <span>Note: rehash/reserve will invalidate all iterators (references usually remain valid).</span>

5. Container Adapters

stack

• • push/emplace, pop, top, size, empty

queue

• • push/emplace, pop, front, back, size, empty

priority_queue

• • push/emplace (O(log n)), pop (O(log n)), top (O(1)), size, empty

6. Common Considerations

• • map::operator[] will insert a default value; for read-only use find/at/contains.
• • In vector, middle insert/erase or expansion will invalidate many iterators/references.
• • rehash/reserve of unordered_* will invalidate all iterators.
• • List member algorithms (list::splice/merge/sort/unique) are member functions, not free functions in .

4. Links to Individual STL Container Discussions

• • Reserved, article addresses will be filled in after updates

1. 1. vector:
2. 2. list:
3. 3. deque:
4. 4. set/multiset/unordered_set:
5. 5. map/multimap/unordered_map:
6. 6. stack/queue/priority_queue: