C++

Containere asociative: hartă, set, hartă_neordonată

Aflați despre containerele asociative ordonate și neordonate — hărți, seturi și variantele lor multiple și neordonate. Înțelegeți când să alegeți arbori vs tabelele hash.

Containere asociative comandate vs necomandate

STL oferă două familii de containere asociative:

Comandat (implementat ca arbori roșu-negru):
-std::map— perechi cheie-valoare sortate, chei unice
-std::set— chei unice sortate
-std::multimap— perechi cheie-valoare sortate, chei duplicate permise
-std::multiset— chei sortate, duplicate permise

Neordonat (implementat ca tabele hash):
-std::unordered_map— chei-valoare bazate pe hash, chei unice
-std::unordered_set— chei unice bazate pe hash
-std::unordered_multimap— chei duplicate bazate pe hash
-std::unordered_multiset— bazate pe hash, duplicate

Containerele comandate păstrează elementele sortate și oferă căutarea, inserarea și ștergerea O(log n). Containerele neordonate folosesc hashing pentru operațiuni cu cazuri medii O(1), dar O(n) caz mai rău dacă au loc multe coliziuni.

Folosind harta și set

std::mapstores key-value pairs sorted by key.std::setstores unique sorted values. Both are implemented as self-balancing red-black trees, guaranteeing O(log n) operations.

map_set.cpp
#include <map>
#include <set>
#include <string>
#include <iostream>

int main() {
    // std::map — sorted key-value pairs
    std::map<std::string, int> ages;
    ages["Alice"] = 30;              // insert or update
    ages["Bob"]   = 25;
    ages.insert({"Charlie", 35});    // insert only if key absent
    ages.emplace("Diana", 28);       // construct in-place

    // Lookup
    if (auto it = ages.find("Bob"); it != ages.end()) {
        std::cout << it->first << " is " << it->second << '\n';
    }

    // C++17 structured bindings — elegant map iteration
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << '\n';
    }
    // Output is sorted by key: Alice, Bob, Charlie, Diana

    // std::set — sorted unique values
    std::set<int> primes = {2, 3, 5, 7, 11, 13};
    primes.insert(5);                // no effect — 5 already present
    primes.insert(17);               // inserted

    if (primes.contains(7)) {        // C++20
        std::cout << "7 is prime\n";
    }

    // count() — returns 0 or 1 for set (useful pre-C++20)
    if (primes.count(4) == 0) {
        std::cout << "4 is not prime\n";
    }

    // lower_bound / upper_bound — range queries
    auto lo = primes.lower_bound(5);
    auto hi = primes.upper_bound(11);
    for (auto it = lo; it != hi; ++it) {
        std::cout << *it << ' ';     // 5 7 11
    }
    std::cout << '\n';
}

Unordered Containers and Custom Hash Functions

Unordered containers use hash tables for O(1) average-case lookup. For custom key types, you must provide a hash function and an equality operator.

unordered_custom.cpp
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <iostream>

// Custom type as key
struct Point {
    int x, y;
    bool operator==(const Point&) const = default;  // C++20
};

// Custom hash function
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // Combine hashes — a common pattern
        auto h1 = std::hash<int>{}(p.x);
        auto h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);  // simple combine (consider better hashes in production)
    }
};

int main() {
    // Basic unordered_map — O(1) average lookup
    std::unordered_map<std::string, double> prices;
    prices["apple"]  = 1.50;
    prices["banana"] = 0.75;
    prices["cherry"] = 3.00;

    // try_emplace (C++17) — only constructs value if key is absent
    prices.try_emplace("apple", 9.99);   // no-op, "apple" exists
    prices.try_emplace("date", 4.50);    // inserted

    // extract and insert (C++17 node API)
    auto node = prices.extract("banana");
    if (!node.empty()) {
        node.key() = "plantain";          // rename key without copy
        prices.insert(std::move(node));
    }

    for (const auto& [fruit, price] : prices) {
        std::cout << fruit << ": $" << price << '\n';
    }

    // Custom type as key
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2});   // duplicate — not inserted
    std::cout << "Unique points: " << points.size() << '\n';  // 2
}

Multimap and Multiset

std::multimapandstd::multisetallow duplicate keys. Useequal_range()to find all entries with a given key.

multimap_multiset.cpp
#include <map>
#include <set>
#include <iostream>
#include <string>

int main() {
    // multimap — multiple values per key
    std::multimap<std::string, std::string> phone_book;
    phone_book.insert({"Alice", "555-0100"});
    phone_book.insert({"Alice", "555-0101"});  // duplicate key OK
    phone_book.insert({"Bob",   "555-0200"});

    // equal_range returns a pair of iterators [first, last)
    auto [begin, end] = phone_book.equal_range("Alice");
    std::cout << "Alice's numbers:\n";
    for (auto it = begin; it != end; ++it) {
        std::cout << "  " << it->second << '\n';
    }

    // multiset — count duplicates
    std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
    std::cout << "Count of 3: " << ms.count(3) << '\n';  // 3
}

Custom Comparators for Ordered Containers

Ordered containers default tostd::less(ascending order). You can supply a custom comparator as the third template argument:

std::set<int, std::greater<int>> descending = {1, 5, 3};
// iteration order: 5, 3, 1

For custom types, you can either define operator< in your class or pass a comparator functor or lambda:

auto cmp = [](const Point& a, const Point& b) {
 return a.x < b.x || (a.x == b.x && a.y < b.y);
};
std::set<Point, decltype(cmp)> point_set(cmp);

In C++20, you can use the spaceship operator (operator<=>) to automatically generate all comparison operators.

Capcană

Utilizareaoperator[]pe unstd::mapsaustd::unordered_mapinseră o valoare construită implicit dacă cheia nu există. Aceasta este o sursă comună de erori subtile:

std::map<std::string, int> m;
int val = m["missing"]; // inserts {"missing", 0} into the map!

Use find(), count(), or contains() (C++20) for lookup without modification. Use at() dacă doriți o excepție pentru cheile lipsă.

Bună practică

Folosițiunordered_map/unordered_set atunci când aveți nevoie doar de căutare, inserare și ștergere — litera medie O(1) bate O(log n) pentru colecții mari.

Folosițimap/set când aveți nevoie de:
- Ordine de iterație sortată
- Interogări de interval (lower_bound,upper_bound,equal_range)
- O(log n) garantat în cel mai rău caz (fără coliziuni hash patologice)

Pentru colecțiile mici (mai puțin de ~ 100 de elemente), unstd::vectorsortat custd::lower_boundle poate depăși pe ambele datorită localității cache-ului.

Idei cheie
  • std::mapșistd::setfolosesc arbori roșu-negru — operațiuni O(log n) cu ordine sortată
  • std::unordered_mapșistd::unordered_setfolosesc tabele hash - medie O(1), dar necesită o funcție hash
  • Utilizați legături structurate C++17 (auto& [key, val]) pentru o iterație curată a hărții
  • operator[]pe hărți inserează în tăcere valorile implicite - utilizațifind()saucontains()pentru o căutare sigură
  • Tipurile personalizate ca chei necesităoperator<(comandat) sau o funcție hash +operator==(neordonat)
  • try_emplace(C++17) evită construirea valorii dacă cheia există deja

Test — Verifică-ți cunoștințele

(15 XP)

1. Care este complexitatea medie de timp a căutării în`std::unordered_map`?

2. Ce se întâmplă când utilizați`operator[]`cu o cheie care nu există într-un`std::map`?

3. Ce container ar trebui să alegeți dacă aveți nevoie de iterații sortate ȘI de interogări de interval (lower_bound/upper_bound)?

Anterior
Sequence Containers: vector, deque, list, array
Următor
Container Adaptors & Special Containers