Containers and Their Costs

The right container for the job

The Standard Template Library (STL) provides generic containers. std::vector<T> is a dynamic array: contiguous, cache-friendly, O(1) indexing and amortised O(1) push_back, O(n) insertion in the middle; it should be your default container. std::array<T, N> is a fixed-size array with value semantics, replacing C arrays. std::string is a vector-like container of characters. std::deque supports fast insertion at both ends. std::list is a doubly linked list; it is rarely the best choice because of poor memory locality. Ordered associative containers, std::map and std::set (usually red-black trees), keep keys sorted with O(log n) operations. Unordered containers, std::unordered_map and std::unordered_set (hash tables), give average O(1) lookups without ordering. Adaptors include std::stack, std::queue and std::priority_queue (a max-heap by default). Remember that operations on a container can invalidate iterators, pointers and references: a vector reallocation invalidates all of them.

Container families

Sequence containers keep order of insertion; associative containers organise by key.

Common containers in use

vector by default; map when you need order; unordered_map for fast lookup.

#include <map>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<int> marks{72, 45, 90};
    marks.push_back(66);                         // amortised O(1)
    marks.reserve(1000);                         // avoid repeated reallocations

    std::map<std::string, int> ranked{{"Ravi", 2}, {"Asha", 1}};   // sorted by key
    for (const auto& [name, rank] : ranked) { /* Asha, then Ravi */ }

    std::unordered_map<std::string, int> stock;
    stock["pen"] += 10;                          // operator[] inserts 0 if missing
    if (auto it = stock.find("pad"); it == stock.end()) { /* not found */ }
    bool has_pen = stock.contains("pen");        // C++20

    std::priority_queue<int> pq;                 // max-heap
    pq.push(5); pq.push(42); pq.push(17);
    int top = pq.top();                          // 42

    std::priority_queue<int, std::vector<int>, std::greater<>> min_pq;   // min-heap
}

operator[] on a map inserts

if (counts[key] > 0) silently inserts key with value 0 when it is missing, growing the map and breaking const-correctness. Use find, contains or at (which throws if missing) for lookups.

त्वरित जाँच: Which container should be your default choice for a sequence of elements in C++?

• std::vector
• std::list
• std::map
• std::deque