C++: STL, Standard Template Library Basics

Learn the three pillars of the STL, master the vector container, and apply common algorithms to sort, search, and analyze data.

What is the STL?

The Standard Template Library is a collection of ready-made, generic components built into C++. Instead of implementing your own dynamic array, sorting routine, or search function from scratch, you use battle-tested STL components that work with any data type through templates. The STL divides into three tightly connected pillars: containers, iterators, and algorithms.

`Three Pillars of the STL`

Containers store data. Iterators navigate it. Algorithms operate on it. The three are designed to plug together seamlessly.

Containers: data structures that manage a collection of objects (vector, list, map, set, ...)
Iterators: pointer-like objects that point into a container and can be advanced element by element
Algorithms: generic functions (sort, find, count, ...) that operate on any range defined by two iterators
Because algorithms work through iterators, the same sort() call works on a vector, a deque, or a plain array

Container Overview

STL containers fall into three categories. Sequence containers store elements in a linear order. Associative containers store elements sorted by key for fast lookup. Unordered associative containers use hash tables for near-constant-time access.

`Common Containers`

vector is the default choice for most tasks. Switch to another container only when you have a concrete reason, for example, map when you need key-value lookup.

vector: dynamic array, fast random access, amortized O(1) push_back
list: doubly linked list, O(1) insert/remove anywhere, no random access
deque: double-ended queue, fast push/pop at both ends
map: sorted key-value pairs, O(log n) lookup by key
set: sorted unique values, O(log n) membership test
unordered_map / unordered_set: hash-based, average O(1) lookup

Container	Header	Access	Best for
vector	<vector>	Random O(1)	General-purpose dynamic list
list	<list>	Sequential O(n)	Frequent mid-list inserts/removes
map	<map>	Key O(log n)	Key-value storage, sorted
unordered_map	<unordered_map>	Key O(1) avg	Fast key-value lookup
set	<set>	Key O(log n)	Unique sorted values

Vector: Declaration and Basic Operations

A vector is a resizable array. It stores elements contiguously in memory like a plain array, but grows automatically when more space is needed. Include <vector> and declare with the element type in angle brackets.

`vector declaration`

vector<int> v; creates an empty vector of ints. You can also provide an initial size or a brace-initializer list.

Empty: vector<int> v;
With size: vector<int> v(5); five elements, all zero
With values: vector<int> v = {10, 20, 30};
Access by index: v[0] or v.at(0), at() throws on out-of-range, [] does not

Vector Basics

C++

Create, push, access, and pop. push_back grows the vector; pop_back shrinks it.

size() and capacity()

A vector tracks two numbers: its size (how many elements are currently stored) and its capacity (how many elements the current allocation can hold before a reallocation is needed). When the size reaches the capacity, the vector allocates a larger block, copies the elements, and frees the old block.

`size vs capacity`

size() is what you use for logic. capacity() is an implementation detail, the vector manages it automatically. Use reserve() to pre-allocate when you know the final size in advance.

size(): current number of elements
capacity(): allocated slots, always greater than or equal to size
reserve(n): pre-allocate space for n elements to avoid repeated reallocations
shrink_to_fit(): request that excess capacity be released back to the system

size() vs capacity()

C++

reserve() sets the capacity without adding elements. clear() removes elements but keeps the allocation.

Iterators

An iterator is a pointer-like object that refers to an element inside a container. v.begin() points to the first element; v.end() points one past the last. Incrementing the iterator with ++it advances it to the next element. All STL algorithms accept a begin/end pair and work with any container.

`begin() and end()`

The half-open range [begin, end) is the universal convention. begin points to the first element; end points one past the last, it is never dereferenced.

Declare: vector<int>::iterator it = v.begin();
Dereference: *it gives the element value
Advance: ++it moves to the next element
Loop: for (auto it = v.begin(); it != v.end(); ++it) cout << *it;
Range-based for is cleaner for simple traversal: for (int x : v) cout << x;

Iterator vs Range-based For

C++

Both loops visit every element. Range-based for is shorter and preferred for simple traversal.

sort() and reverse()

std::sort rearranges elements between two iterators in ascending order by default. Pass greater<int>() as the third argument for descending order. std::reverse flips the order of elements in place.

`sort() and reverse()`

Both live in <algorithm>. sort() uses an introsort hybrid with average O(n log n) time. reverse() is O(n).

Ascending: sort(v.begin(), v.end());
Descending: sort(v.begin(), v.end(), greater<int>());
Reverse in place: reverse(v.begin(), v.end());
Custom comparator: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

sort() Ascending, Descending, and reverse()

C++

Three calls, three different orderings. greater<int>() flips the default comparison.

min_element() and max_element()

std::min_element and std::max_element return iterators to the smallest and largest element in a range. Dereference the iterator with * to get the value, or subtract v.begin() to get the index.

`min_element and max_element`

Both return iterators. Dereference to get the value; subtract v.begin() to get the position.

auto it = min_element(v.begin(), v.end()); *it = minimum value
auto it = max_element(v.begin(), v.end()); *it = maximum value
Index of minimum: min_element(v.begin(), v.end()) - v.begin()
Both run in O(n), they scan the entire range once

min_element and max_element

C++

Dereference the returned iterator for the value; subtract begin() for the position.

find() and count()

std::find searches for the first occurrence of a value and returns an iterator to it, or v.end() if not found. std::count returns how many times a value appears in the range.

`find() and count()`

Check find's result against v.end() before dereferencing. count() is safe to call regardless, it returns 0 if the value is absent.

find: auto it = find(v.begin(), v.end(), target);
Check: if (it != v.end()) { found; } else { not found; }
Index: it - v.begin() gives the zero-based position
count: int n = count(v.begin(), v.end(), target);

find() and count()

C++

find returns the iterator to the first match or end(). count tallies all occurrences.

Dynamic Student Marks Storage

Putting the concepts together: a vector that grows as marks are entered, combined with sort, min/max, and a simple average calculation. This pattern covers the majority of real-world vector usage in one compact example.

`Combining Vector and Algorithms`

Collect data with push_back, analyze it with STL algorithms, and present the results, all without managing any raw memory.

push_back adds each mark dynamically, no need to know the count upfront
accumulate (from <numeric>) sums all elements in one line
sort + front/back gives min and max after sorting
The same code works for any number of students with no changes

Student Marks Analysis

C++

Sort once, then front() and back() are the min and max. accumulate sums the whole vector.

Knowledge Check

1. What are the three main components of the STL?

2. Which method adds an element to the end of a vector?

3. What does pop_back() do to a vector?

4. What is the difference between size() and capacity() on a vector?

5. Which header must you include to use std::sort?

6. How do you sort a vector v in descending order using std::sort?

7. What does std::find return if the element is not found?

8. Which iterator method returns a pointer-like object to the first element of a vector?

9. What does std::count(v.begin(), v.end(), x) return?