The C++ Standard Template Library (STL) provides crucial components like containers,

algorithms, iterators, and functors (function objects) that enhance the coding experience, save
time, and are frequently used in practical coding, placements, and internships.

Here are the notes on the major STL containers and algorithms, including the time complexity
tables for key operations.

I. Sequential Containers
Sequential containers store data in a continuous or sequential manner.

1. Vector

A vector is very similar to a C++ array but is dynamic, allowing it to resize (increase or
decrease size) at runtime. It is implemented internally as a dynamic array.

●​ Key Properties:
○​ Size: The number of elements currently stored in the vector.
○​ Capacity: The number of elements the vector can currently hold.
○​ Resizing: When a vector is full and needs more space, it creates a new vector of
double the previous capacity, copies the old data, and then inserts the new data.
●​ Access: Supports random access (like arrays, using square bracket notation or the
.at() function).
●​ Insertion/Deletion:
○​ push_back() / emplace_back(): Insert data at the end. emplace_back()
creates the object in place, while push_back() assumes the object is already
created.
○​ pop_back(): Deletes the last element.
○​ front() / back(): Accesses the first or last element.
○​ insert() / erase(): Inserts or erases an element or a range of elements at an
arbitrary position using iterators. These are generally costly operations.
○​ clear(): Deletes all elements; the size becomes zero, but the internal capacity
remains the same.

Vector Operations Time Complexity Sourc

e

push_back, pop_back, emplace_back Big O(1) (Constant Time)

 front, back, size, capacity, empty, Index Big O(1) (Constant Time)
Access ([], .at())

erase, insert Big O(N) (Linear Time, worst

case)

2. List

A list is a sequential container internally implemented as a doubly linked list.

●​ Key Features:
○​ It allows operations (push/pop/emplace) from both the front and the back.
○​ Functions include push_front, pop_front, emplace_front, in addition to
the back-end operations.
○​ Does not support random access (cannot use square bracket notation like
list).
●​ Common Functions: size, erase, clear, begin, rbegin, rend, insert, front,
back all exist, similar to vectors.

List Operations Time Complexity Sourc

e

push_front, push_back, pop_front, Big O(1) (Constant Time)

pop_back

3. Deque (Double-Ended Queue)

A Deque is a sequential container implemented as a double-ended queue.

●​ Key Features:
○​ It behaves very similarly to a List, allowing operations from both ends
(push_front, pop_front, push_back, pop_back).
○​ Internally, a Deque is implemented using dynamic arrays.
○​ Supports random access.

Deque Operations Time Complexity Sourc

e

push_front, push_back, pop_front, Big O(1) (Constant Time)

pop_back
II. Adaptors and Specialized Containers
4. Pair

A pair is used to group any two values (Value 1 and Value 2), which may be of the same or
different types.

●​ Access: Values are accessed using .first and .second.

●​ Usage: Pairs can be nested (Pair of Pairs) or used within other containers (Vector of
Pairs).
●​ push_back vs. emplace_back (in Vector of Pairs):
○​ push_back requires a pre-constructed pair object to be passed.
○​ emplace_back takes the values individually (separated by commas) and
automatically creates the pair object in place at the time of insertion.

5. Stack

A Stack is a LIFO (Last In, First Out) data structure. Elements are added and removed only from
the top.

●​ Key Functions: push (or emplace), pop (removes the top element), top (accesses
the top element), empty, size, and swap.
●​ Order: Elements are popped in the reverse order of insertion.

Stack Time Complexity Sourc

Operations e

push, top, pop Big O(1) (Constant Time)

6. Queue

A Queue is a FIFO (First In, First Out) data structure. Elements are inserted from the back (or
rear) and removed from the front.

●​ Key Functions: push, pop, front (accesses the front element), back (accesses the
last element), size, empty, and swap.
●​ Order: Elements are popped in the same order they were inserted.

Queue Time Complexity Sourc

Operations e

push, front, pop Big O(1) (Constant Time)

7. Priority Queue

A Priority Queue is a special data structure that internally uses a Max Heap or Min Heap (binary
tree structure).

●​ High Priority: The element with the highest priority is always at the top.
●​ Default Behavior (Max Heap): By default, the largest value has the highest priority and
sits at the top. Elements pop out in sorted order (largest first).
●​ Min Heap (Reverse Order): To achieve a Min Heap (where the smallest element is at
the top), a custom syntax must be used, including a vector of the data type and a
comparator/functor (std::greater<int>).

Priority Queue Operations Time Complexity Sourc

e

push, pop Big O(log N) (Logarithmic Time)

top, size, empty Big O(1) (Constant Time)

III. Non-Sequential (Associative) Containers

These containers store data based on specialized structures, often relying on keys for
organization.

8. Map

A Map stores key-value pairs.

●​ Properties of Standard Map (Sorted Map):

○​ Keys must be unique (cannot be duplicated).
○​ Data is automatically sorted in ascending order based on the key.
○​ Internally implemented as a self-balancing tree.
●​ Insertion/Access: Achieved using square bracket notation (m[key] = value), or
insert / emplace functions.
●​ Functions: count, erase, find, size, empty.

Map Variations

Map Type Description Key Time Complexity Sourc

Characteristic (Insert, Erase, Count) e
 Normal Data sorted by Sorted; Unique Big O(log N)
Map unique keys. Keys

Multi Map Allows storage of Sorted; Duplicate Big O(log N)

multiple, duplicate Keys
keys.

Cannot use square N/A

bracket notation

Unordered Data stored in a Unordered; Unique Big O(1)

Map random, Keys (Amortized/Average)
unordered manner.

Implemented using Big O(N) (Worst case,

hashing. rare)

9. Set

A Set stores only unique values. It is analogous to a mathematical set.

●​ Properties of Standard Set (Sorted Set):

○​ Values are stored in a sorted order (ascending by default).
○​ Inserting duplicate values is ignored.
○​ Internally uses a self-balancing tree.
●​ Key Functions: insert / emplace, count, erase, find, size, empty.
●​ Boundary Functions (for Sorted Data):
○​ lower_bound(key): Returns an iterator to the element which is not less than
the key.
○​ upper_bound(key): Returns an iterator to the element which is greater than
the key.

Set Variations

Set Type Description Key Time Complexity Sourc

Characteristic (Insert, Count, Erase) e

Normal Set Stores unique values in Sorted; Unique Big O(log N)

a sorted order. Values

Multi Set Allows storage of Sorted; Big O(log N)

duplicate elements. Duplicate Values
 Unordered Stores unique values in Unordered; Big O(1)
Set a random, unordered Unique Values (Amortized/Average)
manner.

Implemented using Big O(N) (Worst case,

hashing. rare)

Note: lower_bound N/A N/A

and upper_bound are
not applicable to
Unordered Sets.

IV. Iterators
Iterators simplify looping over containers and allow access to direct memory locations, behaving
like generalized pointers.

●​ begin(): Returns an iterator pointing to the beginning (index 0) of the container.

Dereferencing it returns the first value.
●​ end(): Returns an iterator pointing to the memory location just after the last element. It
does not point to the last element itself.
●​ Reverse Iterators:
○​ rbegin() (Reverse Begin): Points to the last index.
○​ rend() (Reverse End): Points to the memory location just before the first index.
●​ Custom Iterators: Iterators can be created and incremented (++) to move sequentially
through a container.
●​ auto Keyword: In modern C++, the auto keyword automatically determines the type of
the iterator (e.g., vector<int>::iterator or reverse_iterator), simplifying
syntax.

V. Algorithms
Algorithms are frequently used functions often associated with the <algorithm> header.

1. Sort

The sort function arranges elements within a specified range.

 ●​ Usage: Requires passing the starting iterator/pointer and the ending iterator/pointer (the
position after the last element to be included).
●​ Default: Sorts in ascending order.
●​ Custom/Reverse Sorting: To sort in descending order or apply a custom logic, a
comparator (or functor) must be passed as the third argument.
○​ The std::greater<T> comparator is used for reverse/descending order
sorting.
○​ A custom comparator is a boolean function that defines the comparison logic
(e.g., sorting pairs based on the second value).

2. Reverse

The reverse function reverses the order of elements within a specified range (start and end
iterators).

3. Permutations

●​ next_permutation(): Returns the lexicographically next permutation of the elements

in the range.
●​ prev_permutation(): Returns the lexicographically previous permutation.

4. Search and Utility

●​ min() / max(): Returns the minimum or maximum of two individual values.

●​ min_element() / max_element(): Returns an iterator to the minimum or maximum
element within a given range.
●​ swap(): Used to swap the values of two variables.
●​ binary_search(): Searches for a target value within a sorted range and returns a
boolean value (true or false) indicating existence.

5. Bitwise Functions

●​ __builtin_popcount(N): Counts the number of set bits (bits equal to 1) in an

integer N.
●​ Data Type Variation: Different trailing letters are used based on the integer data type:
__builtin_popcountl for long int and __builtin_popcountll for long long
int.