std::list

The std::list container implements a doubly linked list. Memory allocation is non-contiguous, with nodes linked internally via pointers. It provides dynamic sizing and constant-time insertion or deletion of elements at known positions. Traversal is typically handled using iterators. For scenarios requiring frequent random access, std::vector or std::deque are significantly more efficient choices.

std::list<int> numbers;
numbers.push_back(10);
numbers.push_back(20);
numbers.push_front(5);
for (int val : numbers) {
    std::cout << val << " ";
}

std::stack

Defined in <stack>, this container adaptor enforces a Last-In-First-Out (LIFO) paradigm. Elements can only be added to or removed from the top of the stack. Pushing an array onto a stack and popping it sequentially will yield the reversed array.

• push(x): Adds element x to the top.
• pop(): Removes the top element.
• top(): Accesses the top element.
• empty(): Checks if the stack is empty.
• size(): Returns the current element count.

std::stack<int> s;
s.push(100);
s.pop();

Associative Sets

std::set

A sorted associative container that stores unique keys. Duplicate insertions are automatically ignored. By default, elements are sorted in ascending order using operator<; custom structs must overload this operator. The underlying Red-Black Tree ensures O(log n) complexity for insertions, deletions, and searches.

• insert(), erase(), find()
• lower_bound(): Iterator to the first element not less than the given value.
• upper_bound(): Iterator to the first element greater than the given value.
• size(), empty(), clear(), iterator methods (begin(), end(), etc.)

Custom sorting can be applied using functors:

struct DescendingSort {
    bool operator()(const int& lhs, const int& rhs) const {
        return lhs > rhs;
    }
};
std::set<int, DescendingSort> customSet;

std::multiset

Similar to std::set but permits duplicate elements. Calling erase(x) removes all instances of x. To remove a single instance, use erase(find(x)) to delete only the first matched iterator.

std::unordered_set

Implemented via a hash table, storing unique elements without any specific order. It lacks lower_bound() and upper_bound(). While offering average O(1) complexity, worst-case scenarios degrade to O(n), making performance unstable.

Associative Maps

std::map

Stores key-value pairs with unique keys, sorted by key using a Red-Black Tree. Operations like insertion, deletion, and search execute in O(log n) time.

• insert() / erase(): Modify contents.
• find(): Returns an iterator to the element.
• count(): Returns 0 or 1, frequently used to verify key existence.
• lower_bound(): Finds the first element with a key not less than the specified value.

std::map<int, std::string> dict = {{1, "Alpha"}, {2, "Beta"}};
dict.insert({3, "Gamma"});
dict[2] = "Delta";
for (const auto& entry : dict) {
    std::cout << entry.first << ": " << entry.second << "\n";
}
if (dict.count(4) == 0) {
    std::cout << "Key 4 is absent\n";
}

std::multimap

Allows multiple entries with identical keys. Calling erase(key) removes all matching entries. The equal_range(key) function returns a pair of iterators defining the range of elements sharing the specified key.

auto bounds = mmap.equal_range(2);
for (auto it = bounds.first; it != bounds.second; ++it) {
    std::cout << it->second << "\n";
}

std::unordered_map

Hash-based key-value storage. It does not maintain order and lacks lower_bound(). It provides rapid average O(1) access, though worst-case complexity is O(n).

std::pair

Defined in <utility>, this template binds two heterogeneous values together, accessible via .first and .second. Pairs can be nested and are frequently used for multi-value returns or map iterations.

std::pair<int, double> p1(5, 3.14);
std::pair<int, std::pair<int, int>> nested(1, {2, 3});
std::cout << nested.second.first << "\n";

When utilized in sorting algorithms, std::pair defaults to sorting by .first; if equal, it sorts by .second.

std::vector<std::pair<int, int>> vec = {{3, 1}, {1, 5}, {1, 2}};
std::sort(vec.begin(), vec.end()); // Result: {1,2}, {1,5}, {3,1}

Queue Adaptors

std::queue

Implements a First-In-First-Out (FIFO) structure. Core methods include push(x), pop(), front(), back(), empty(), and size().

std::priority_queue

Organizes elements by priority, defaulting to a max-heap where the largest element sits at the top. push() and pop() operate in O(log n), while top(), empty(), and size() run in O(1).

To create a min-heap, supply the std::greater functor (requires <functional>). Ensure a space between consecutive angle brackets to avoid parsing as the right-shift operator.

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

Custom comparators can be implemented via structs:

struct CustomCompare {
    bool operator()(int a, int b) {
        return a > b;
    }
};
std::priority_queue<int, std::vector<int>, CustomCompare> customPQ;

std::deque

A double-ended queue allowing efficient O(1) insertions and deletions at both the front and back. Key methods include push_back(), push_front(), pop_back(), pop_front(), front(), back(), empty(), and clear().

std::vector

A dynamic array managing contiguous memory. Elements are accessed via zero-indexed [] operators. Because size() returns an unsigned integer, evaluating i <= vec.size() - 1 can trigger underflow if the vector is empty; prefer i < vec.size().

Common operations include push_back(), pop_back(), insert(), erase(), size(), empty(), and resize(). Iterators are provided via begin() and end().

for (auto it = data.begin(); it != data.end(); ++it) {
    std::cout << *it << "\n";
}

Removing duplicates requires sorting first, followed by std::unique which shifts duplicates to the end, and finally erase to resize the container.

std::sort(data.begin(), data.end());
data.erase(std::unique(data.begin(), data.end()), data.end());
data.erase(data.begin() + 2); // Removes the 3rd element