Vectors and Maps

Vector or Map: Decide from Meaning

std::vector<T> represents an ordered sequence of values in contiguous storage. std::map<Key, T> represents key-value associations ordered by unique keys. They are not interchangeable performance switches; they model different questions:

• “What is the third score?” suggests a sequence and possibly a vector.
• “What score belongs to Sara?” suggests a key-value association and possibly a map.
• “Preserve insertion order and look up names” may need a vector plus an index, or another deliberately designed structure.

Vector Deep Dive: Size, Capacity and Safe Access

#include <vector>

std::vector<int> scores;
scores.reserve(100);       // capacity at least 100; size is still 0
scores.push_back(78);      // size becomes 1
scores.emplace_back(91);   // constructs an element at the end

int first = scores[0];     // no bounds check
int checked = scores.at(1); // throws std::out_of_range if invalid

Vector supports constant-time indexing and amortized constant-time insertion at the end. “Amortized” means occasional growth may allocate a larger block and move/copy existing elements, while a sequence of push-backs has constant average cost per insertion under the guarantee.

reserve(n) requests capacity for at least n elements but creates none. resize(n) changes the size and creates/removes elements. This is invalid:

std::vector<int> values;
values.reserve(10);
// values[0] = 7;  // error: size is still zero

Use push_back, emplace_back or resize before indexing. Read the dedicated C++ vector tutorial for construction and member functions.

Map Deep Dive: Ordered Keys and Lookup

#include <map>
#include <string>

std::map<std::string, int> marks{
    {"Sara", 91}, {"Aman", 78}
};

marks.insert_or_assign("Aman", 83);

if (auto it = marks.find("Sara"); it != marks.end()) {
    std::cout << it->second;
}

if (marks.contains("Kabir")) { /* C++20 */ }

A map maintains elements in the order defined by its comparator (ascending std::less by default). Search, insertion and erasure are logarithmic. The standard specifies behavior and complexity, not a mandatory tree implementation.

Be precise with access:

• m[key] returns the value and inserts a value-initialized entry when the key is absent.
• m.at(key) does not insert and throws std::out_of_range when missing.
• m.find(key) returns an iterator; it works before C++20.
• m.contains(key) returns a boolean since C++20.
• try_emplace avoids constructing the mapped value when the key already exists.

For sets and associative fundamentals, see C++ set and map.

Combined Vector-and-Map Program with Output

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

int main() {
    std::vector<int> scores{78, 91, 84, 91};
    std::sort(scores.begin(), scores.end());

    std::cout << "Sorted scores:";
    for (int score : scores) std::cout << ' ' << score;

    std::map<std::string, int> by_name{
        {"Sara", 91}, {"Aman", 78}, {"Kabir", 84}
    };
    by_name.at("Aman") += 5;

    std::cout << "\nBy name:";
    for (const auto& [name, score] : by_name) {
        std::cout << ' ' << name << ':' << score;
    }
}

The vector preserves duplicate scores and is sorted by value. The map produces key order, not insertion order: Aman, Kabir, Sara. The structured binding binds each pair as name and score; const auto& avoids copying.

Complexity Comparison and Alternatives

A sorted vector can be excellent for read-heavy small or medium data: compact storage, binary search and fast traversal. Its insertion remains O(n). A map is valuable when ordered keyed updates are frequent and stable element handles matter.

If ordering is irrelevant, consider unordered_map: expected average constant lookup, but worst-case linear behavior, hash requirements, rehashing and no stable sorted iteration. Big-O alone does not decide real speed; benchmark representative data.

Iteration, Mutation and Invalidation

Vector rules that matter

• If an operation changes capacity, all iterators, pointers and references to elements are invalidated.
• Without reallocation, inserting invalidates handles at or after the insertion position; erase invalidates the erased position and everything after it.
• reserve can reduce repeated reallocations, but calling a later larger reserve can itself reallocate.

Map rules that matter

• Insertion/emplacement does not invalidate existing iterators and references.
• Erasure invalidates only iterators/references to erased elements.
• Do not dereference end(); after erase, use the returned next iterator where appropriate.

for (auto it = by_name.begin(); it != by_name.end(); ) {
    if (it->second < 40) it = by_name.erase(it);
    else ++it;
}

In range-for loops, use const auto& for read-only access and auto& when modifying mapped values. A map key is const through its iterator; changing it in place would violate ordering. Erase and insert under the new key instead.

Real Design Patterns

1. Sorted report plus keyed lookup

If an application needs both insertion order and name lookup, a map alone cannot preserve insertion order. One design stores records in a vector and keeps a separate map from key to stable identifier/index. Define how erasure and vector relocation affect the index.

2. Frequency table

std::map<std::string, int> frequency;
for (const std::string& word : words) {
    ++frequency[word]; // insertion is intentional here
}

Here operator[] is ideal because a missing count should begin at zero.

3. Read-mostly flat data

std::vector<std::pair<std::string, int>> records;
std::sort(records.begin(), records.end());
auto it = std::lower_bound(records.begin(), records.end(),
                           std::pair{std::string{"Sara"}, 0});

This can be compact and cache-friendly, but duplicates, comparator semantics and update cost must be designed deliberately. Prefer clear standard containers until profiling demonstrates a need for a more complex dual structure.

Common Mistakes and Review Checklist

1. Is identity positional or keyed?
2. Must iteration be sorted, insertion-ordered or arbitrary?
3. Are duplicate keys allowed?
4. What are the dominant operations?
5. Must pointers/references stay valid?
6. Can a lookup modify the structure?
7. Are empty and missing-key cases tested?
8. Are warnings and sanitizers used in development?

Authoritative References

• C++ Working Draft: vector
• C++ Working Draft: map
• C++ Working Draft: Container Requirements

Complexity, access and invalidation claims were checked against the current working draft. These guarantees matter more than a particular vendor's internal implementation.