C++

Associative Containers: map, set, unordered_map

Μάθετε για τα διατεταγμένα και μη ταξινομημένα συσχετιστικά κοντέινερ — χάρτες, σύνολα και τις πολλαπλές και μη ταξινομημένες παραλλαγές τους. Κατανοήστε πότε να επιλέξετε δέντρα έναντι πίνακες κατακερματισμού.

Ordered vs Unordered Associative Containers

Το STL παρέχει δύο οικογένειες συσχετιστικών εμπορευματοκιβωτίων:

Παραγγελία (εφαρμόστηκε ως κοκκινόμαυρα δέντρα):
-std::map— ταξινομημένα ζεύγη κλειδιών-τιμών, μοναδικά κλειδιά
-std::set— ταξινομημένα μοναδικά κλειδιά
-std::multimap— ταξινομημένα ζεύγη κλειδιών-τιμών, επιτρέπονται τα διπλά κλειδιά
-std::multiset— ταξινομημένα κλειδιά, επιτρέπονται διπλότυπα

Χωρίς σειρά (εφαρμόζεται ως πίνακες κατακερματισμού):
-std::unordered_map— κλειδί-τιμή βασισμένη σε κατακερματισμό, μοναδικά κλειδιά
-std::unordered_set— μοναδικά κλειδιά που βασίζονται σε κατακερματισμό
-std::unordered_multimap— διπλότυπα κλειδιά βασισμένα σε κατακερματισμό
-std::unordered_multiset— με βάση κατακερματισμό, διπλότυπα

Τα παραγγελθέντα κοντέινερ διατηρούν τα στοιχεία ταξινομημένα και παρέχουν αναζήτηση, εισαγωγή και διαγραφή O(log n). Τα μη παραγγελθέντα κοντέινερ χρησιμοποιούν κατακερματισμό για λειτουργίες μέσης περίπτωσης O(1) αλλά το O(n) στη χειρότερη περίπτωση εάν συμβούν πολλές συγκρούσεις.

Χρήση χάρτη και σετ

Τοstd::mapαποθηκεύει ζεύγη κλειδιού-τιμής ταξινομημένα κατά κλειδί. Τοstd::setαποθηκεύει μοναδικές ταξινομημένες τιμές. Και τα δύο υλοποιούνται ως αυτοεξισορροπούμενα κόκκινα-μαύρα δέντρα, που εγγυώνται λειτουργίες O(log n).

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';
}

Μη διατεταγμένα κοντέινερ και προσαρμοσμένες λειτουργίες κατακερματισμού

Τα μη ταξινομημένα κοντέινερ χρησιμοποιούν πίνακες κατακερματισμού για αναζήτηση μέσης περίπτωσης O(1). Για προσαρμοσμένους τύπους κλειδιών, πρέπει να παρέχετε μια συνάρτηση κατακερματισμού και έναν τελεστή ισότητας.

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 και Multiset

Ταstd::multimapκαιstd::multisetεπιτρέπουν διπλότυπα κλειδιά. Χρησιμοποιήστε τοequal_range()για να βρείτε όλες τις καταχωρήσεις με ένα δεδομένο κλειδί.

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
}

Προσαρμοσμένοι συγκριτές για παραγγελθέντα κοντέινερ

Τα παραγγελθέντα κοντέινερ από προεπιλογή είναιstd::less(αύξουσα σειρά). Μπορείτε να παρέχετε έναν προσαρμοσμένο συγκριτή ως το τρίτο όρισμα προτύπου:

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<=>) για αυτόματη δημιουργία όλων των τελεστών σύγκρισης.

Παγίδα

Η χρήσηoperator[]σεstd::mapήstd::unordered_mapεισάγεται μια προεπιλεγμένη τιμή εάν το κλειδί δεν υπάρχει. Αυτή είναι μια κοινή πηγή ανεπαίσθητων σφαλμάτων:

Το ``cpp
std::map m;
int val = m["missing"]; // inserts {"missing", 0} into the map!
``

Use find(), count(), or περιέχει() (C++20) for lookup without modification. Use at() εάν θέλετε μια εξαίρεση στα κλειδιά που λείπουν.

Βέλτιστη πρακτική

Χρησιμοποιήστεunordered_map/unordered_set όταν χρειάζεστε μόνο αναζήτηση, εισαγωγή και διαγραφή — η μέση περίπτωση O(1) ξεπερνά το O(log n) για μεγάλες συλλογές.

Χρησιμοποιήστεmap/set όταν χρειάζεστε:
- Ταξινομημένη σειρά επανάληψης
- Ερωτήματα εύρους (lower_bound,upper_bound,equal_range)
- Εγγυημένη O(log n) στη χειρότερη περίπτωση (χωρίς παθολογικές συγκρούσεις κατακερματισμού)

Για μικρές συλλογές (λιγότερα από ~100 στοιχεία), ένα ταξινομημένοstd::vectorμεstd::lower_boundμπορεί να έχει καλύτερη απόδοση και στα δύο λόγω της τοποθεσίας της κρυφής μνήμης.

Βασικά συμπεράσματα
  • Ταstd::mapκαιstd::setχρησιμοποιούν κόκκινα-μαύρα δέντρα — λειτουργίες O(log n) με ταξινομημένη σειρά
  • Ταstd::unordered_mapκαιstd::unordered_setχρησιμοποιούν πίνακες κατακερματισμού — Ο(1) μέσος όρος αλλά απαιτεί συνάρτηση κατακερματισμού
  • Χρησιμοποιήστε δομημένες συνδέσεις C++17 (auto& [key, val]) για καθαρή επανάληψη χάρτη
  • Τοoperator[]στους χάρτες εισάγει αθόρυβα τις προεπιλεγμένες τιμές — χρησιμοποιήστεfind()ήcontains()για ασφαλή αναζήτηση
  • Οι προσαρμοσμένοι τύποι ως κλειδιά απαιτούνoperator<(παραγγελία) ή συνάρτηση κατακερματισμού +operator==(μη παραγγελία)
  • Τοtry_emplace(C++17) αποφεύγει την κατασκευή της τιμής εάν το κλειδί υπάρχει ήδη

Κουίζ — Δοκιμάστε τις γνώσεις σας

(15 XP)

1. Ποια είναι η μέση χρονική πολυπλοκότητα της αναζήτησης στο`std::unordered_map`;

2. Τι συμβαίνει όταν χρησιμοποιείτε το`operator[]`με ένα κλειδί που δεν υπάρχει σε ένα`std::map`;

3. Ποιο κοντέινερ πρέπει να επιλέξετε εάν χρειάζεστε ερωτήματα ταξινομημένης επανάληψης ΚΑΙ εύρους (lower_bound/upper_bound);

Προηγούμενο
Sequence Containers: vector, deque, list, array
Επόμενο
Προσαρμογείς Εμπορευματοκιβωτίων & Ειδικά Εμπορευματοκιβώτια