Standard Containers & Adaptors

Choose from operations

Start with the default std::vector. Move away only when a measured or structural requirement demands stable node addresses, cheap insertion at both ends, key-based lookup, or ordered traversal. Big-O describes growth, but locality, allocation count, and constants still shape real performance.

Sequence containers

Sequence containers arrange elements by position. vector and arrayare contiguous; deque is segmented; list andforward_list are node-based. All own their elements and clean them up automatically.

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> work;
    work.push_back("render");
    work.push_front("parse");
    work.emplace_back("publish");

    while (!work.empty()) {
        std::cout << work.front() << '\n';
        work.pop_front();
    }
}

• vector provides constant-time random access and amortized constant push_back
• deque provides constant-time access plus efficient insertion at both ends
• list provides stable iterators except to erased elements and constant-time splice
• forward_list is a minimal singly linked list without size()

Ordered associative containers

map stores key-value pairs and set stores keys. Their elements are ordered by a strict weak ordering, with logarithmic lookup and insertion. Themulti variants permit equivalent keys. A map's key is const inside each element because changing it in place would break ordering.

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> words{"map", "vector", "map", "set"};
    std::map<std::string, int> counts;
    for (const auto& word : words) ++counts[word];

    for (const auto& [word, count] : counts) {
        std::cout << word << ": " << count << '\n';
    }
}

Unordered containers and hashing

Unordered containers place elements into buckets based on a hash. Average lookup is constant time, but worst-case lookup is linear. If two keys compare equal, their hash values must match. Iteration order is unspecified and may change after rehashing.

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> stock{
        {"keyboard", 8}, {"mouse", 12}
    };

    if (auto found{stock.find("mouse")}; found != stock.end()) {
        found->second -= 1;
    }
    std::cout << stock.at("mouse") << '\n';
}

Container adaptors

An adaptor restricts an underlying container to a focused interface. stackexposes last-in-first-out operations, queue exposes first-in-first-out operations, and priority_queue exposes the greatest element according to its comparison.

#include <iostream>
#include <queue>
#include <string>

struct Job { int priority; std::string name; };
struct LowerPriority {
    bool operator()(const Job& left, const Job& right) const {
        return left.priority < right.priority;
    }
};

int main() {
    std::priority_queue<Job, std::vector<Job>, LowerPriority> jobs;
    jobs.push({2, "index"});
    jobs.push({5, "restore"});
    jobs.push({1, "cleanup"});
    std::cout << jobs.top().name << '\n';
}

Complexity and invalidation

Complexity guarantees describe how operations scale. Invalidation rules describe whether existing iterators, references, and pointers remain usable after mutation. These are part of correctness, not merely optimization, and differ across container families.