C++

关联容器：map、set、unordered_map

学习有序和无序关联容器──映射、集合及其 multi- 和 unordered 变体。了解何时选择树结构还是哈希表。

有序与无序关联容器

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)。

使用 map 和 set

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

对于自定义类型，你可以在类中定义 operator<，或传递一个比较器函数对象或 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);

在 C++20 中，你可以使用太空飞船运算符（operator<=>）自动生成所有比较运算符。

常见陷阱

在 std::map 或 std::unordered_map 上使用 operator[] 会在键不存在时插入一个默认构造的值。这是一种常见的隐蔽 bug 来源：

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

使用 find()、count() 或 contains()（C++20）进行不修改的查找。如果希望在键缺失时抛出异常，使用 at()。

最佳实践

使用 unordered_map/unordered_set 当你只需要查找、插入和删除时──对于大型集合，O(1) 平均情况优于 O(log n)。

使用 map/set 当你需要：
- 排序的迭代顺序
- 范围查询（lower_bound、upper_bound、equal_range）
- 保证 O(log n) 最坏情况（无病态哈希冲突）

对于小型集合（少于约 100 个元素），使用 std::lower_bound 的排序 std::vector 由于缓存局部性可能优于两者。

关键要点
  • std::map 和 std::set 使用红黑树──O(log n) 操作，带排序顺序
  • std::unordered_map 和 std::unordered_set 使用哈希表──平均 O(1)，但需要哈希函数
  • 使用 C++17 结构化绑定（auto& [key, val]）实现简洁的 map 迭代
  • map 上的 operator[] 会静默插入默认值──使用 find() 或 contains() 进行安全查找
  • 自定义类型作为键需要 operator<（有序）或哈希函数 + operator==（无序）
  • try_emplace（C++17）在键已存在时避免构造值

测验 — 检验你的知识

(15 经验值)

1. `std::unordered_map` 中查找的平均时间复杂度是多少？

2. 在 `std::map` 中使用不存在的键调用 `operator[]` 会发生什么？

3. 如果你需要排序迭代和范围查询（lower_bound/upper_bound），应该选择哪种容器？

上一课
顺序容器：vector、deque、list、array
下一课
容器适配器与特殊容器