编辑“︁C++ 关联容器”︁

{{Note|本文是C++标准模板库(STL)容器系列的关联容器章节，适合具备基础C++知识的读者阅读。建议先掌握[[C++序列容器]]再学习本章内容。}}

= C++关联容器 =

'''关联容器'''（Associative Containers）是C++标准模板库(STL)中一类基于'''键值对'''（key-value）存储数据的容器，与序列容器不同，它们通过'''键'''（key）而非位置来访问元素。关联容器通常使用'''平衡二叉搜索树'''或'''哈希表'''实现，因此能提供高效的元素查找、插入和删除操作。

== 关联容器分类 ==

C++标准库提供以下关联容器，可分为两类：

=== 有序关联容器 ===
* {{code|std::set}}：唯一键的集合，按键排序
* {{code|std::multiset}}：键可重复的集合，按键排序
* {{code|std::map}}：键值对集合，键唯一且按键排序
* {{code|std::multimap}}：键值对集合，键可重复且按键排序

=== 无序关联容器（C++11引入） ===
* {{code|std::unordered_set}}：唯一键的集合，基于哈希表
* {{code|std::unordered_multiset}}：键可重复的集合，基于哈希表
* {{code|std::unordered_map}}：键值对集合，键唯一且基于哈希表
* {{code|std::unordered_multimap}}：键值对集合，键可重复且基于哈希表

<mermaid>
graph LR
    A[关联容器] --> B[有序]
    A --> C[无序]
    B --> D[set/multiset]
    B --> E[map/multimap]
    C --> F[unordered_set/unordered_multiset]
    C --> G[unordered_map/unordered_multimap]
</mermaid>

== 核心特性 ==

=== 共同特性 ===
* 通过键（而非位置）访问元素
* 提供高效的查找操作（通常O(log n)或O(1)）
* 支持自定义比较函数或哈希函数

=== 有序容器特性 ===
* 元素按键排序（默认升序）
* 通常用红黑树实现
* 支持范围查询（如"找出所有键在A到B之间的元素"）

=== 无序容器特性 ===
* 元素不按特定顺序存储
* 基于哈希表实现
* 平均情况O(1)时间复杂度访问

== 详细容器介绍 ==

=== std::set ===
存储唯一键的集合，自动排序。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <set>

int main() {
    std::set<int> numbers = {3, 1, 4, 1, 5, 9};  // 重复的1会被忽略
    
    // 插入元素
    numbers.insert(2);
    
    // 遍历集合（自动排序）
    for(int num : numbers) {
        std::cout << num << " ";  // 输出: 1 2 3 4 5 9
    }
    
    // 查找元素
    if(numbers.find(4) != numbers.end()) {
        std::cout << "\n4 found in set!";
    }
}
</syntaxhighlight>

=== std::map ===
存储键值对，键唯一且自动排序。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> ageMap = {
        {"Alice", 30},
        {"Bob", 25}
    };
    
    // 插入元素
    ageMap["Charlie"] = 28;
    ageMap.insert({"Dave", 22});
    
    // 访问元素
    std::cout << "Bob's age: " << ageMap["Bob"] << "\n";
    
    // 遍历map
    for(const auto& pair : ageMap) {
        std::cout << pair.first << " is " << pair.second << " years old\n";
    }
    
    /* 输出:
    Bob's age: 25
    Alice is 30 years old
    Bob is 25 years old
    Charlie is 28 years old
    Dave is 22 years old
    */
}
</syntaxhighlight>

=== std::unordered_map ===
哈希表实现的键值对容器，提供平均O(1)复杂度的查找。

<syntaxhighlight lang="cpp">
#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, std::string> capitalMap = {
        {"France", "Paris"},
        {"Italy", "Rome"}
    };
    
    // 插入元素
    capitalMap["Japan"] = "Tokyo";
    
    // 查找元素
    auto it = capitalMap.find("Italy");
    if(it != capitalMap.end()) {
        std::cout << "Capital of Italy is " << it->second << "\n";
    }
    
    // 遍历（无序）
    for(const auto& pair : capitalMap) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }
}
</syntaxhighlight>

== 性能比较 ==

下表比较主要操作的时间复杂度（n为元素数量）：

{| class="wikitable"
|-
! 操作 !! 有序容器 !! 无序容器
|-
| 插入 || O(log n) || 平均O(1)，最差O(n)
|-
| 删除 || O(log n) || 平均O(1)，最差O(n)
|-
| 查找 || O(log n) || 平均O(1)，最差O(n)
|-
| 遍历 || O(n) || O(n)
|-
| 范围查询 || O(log n + k) || 不支持
|}

== 实际应用案例 ==

=== 案例1：单词计数器 ===
使用{{code|std::map}}统计文本中单词出现频率：

<syntaxhighlight lang="cpp">
#include <iostream>
#include <map>
#include <string>
#include <sstream>

void wordCounter(const std::string& text) {
    std::map<std::string, int> freqMap;
    std::istringstream iss(text);
    std::string word;
    
    while(iss >> word) {
        ++freqMap[word];  // 自动初始化不存在的键为0
    }
    
    for(const auto& pair : freqMap) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }
}

int main() {
    wordCounter("hello world hello cpp world cpp cpp");
    /* 输出:
    cpp: 2
    cpp: 1
    hello: 2
    world: 2
    */
}
</syntaxhighlight>

=== 案例2：电话簿快速查询 ===
使用{{code|std::unordered_map}}实现高效电话簿：

<syntaxhighlight lang="cpp">
#include <iostream>
#include <unordered_map>
#include <string>

class PhoneBook {
    std::unordered_map<std::string, std::string> contacts;
    
public:
    void addContact(const std::string& name, const std::string& number) {
        contacts[name] = number;
    }
    
    std::string findNumber(const std::string& name) {
        auto it = contacts.find(name);
        return (it != contacts.end()) ? it->second : "Not found";
    }
};

int main() {
    PhoneBook pb;
    pb.addContact("Alice", "123-456-789");
    pb.addContact("Bob", "987-654-321");
    
    std::cout << "Alice's number: " << pb.findNumber("Alice") << "\n";
    std::cout << "Charlie's number: " << pb.findNumber("Charlie") << "\n";
}
</syntaxhighlight>

== 高级主题 ==

=== 自定义比较函数 ===
对于有序容器，可以自定义排序规则：

<syntaxhighlight lang="cpp">
#include <iostream>
#include <set>

// 自定义比较函数：按字符串长度排序
struct LengthCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

int main() {
    std::set<std::string, LengthCompare> words;
    
    words.insert("apple");
    words.insert("banana");
    words.insert("kiwi");
    
    for(const auto& word : words) {
        std::cout << word << " ";  // 输出: kiwi apple banana
    }
}
</syntaxhighlight>

=== 自定义哈希函数 ===
对于无序容器，可以自定义哈希函数：

<syntaxhighlight lang="cpp">
#include <iostream>
#include <unordered_set>
#include <functional>

struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 自定义哈希函数
struct PersonHash {
    std::size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);
    }
};

int main() {
    std::unordered_set<Person, PersonHash> people;
    
    people.insert({"Alice", 30});
    people.insert({"Bob", 25});
    
    std::cout << "Bucket count: " << people.bucket_count() << "\n";
}
</syntaxhighlight>

== 最佳实践 ==

1. '''选择合适容器'''：
   * 需要排序或范围查询 → 有序容器
   * 需要最高性能查找 → 无序容器
   * 键可重复 → multiset/multimap版本

2. '''考虑内存使用'''：
   * 有序容器通常内存占用更小
   * 无序容器可能有哈希表开销

3. '''键设计原则'''：
   * 有序容器：键必须定义严格弱序
   * 无序容器：键必须可哈希且支持相等比较

4. '''迭代器稳定性'''：
   * 有序容器：插入删除通常不使迭代器失效（被删除元素除外）
   * 无序容器：rehash可能使所有迭代器失效

== 常见问题 ==

'''Q: 何时选择map而非unordered_map？'''
A: 当需要有序遍历、范围查询或内存受限时选择map；当需要最高查找性能且不关心顺序时选择unordered_map。

'''Q: 如何选择set和map？'''
A: 当只需要存储键时用set，需要存储键值对时用map。

'''Q: 为什么我的自定义类型不能直接用作unordered_map的键？'''
A: 需要提供哈希函数和相等比较函数，可通过特化{{code|std::hash}}或传递自定义函数对象实现。

{{Tip|使用C++17的结构化绑定可以简化map遍历：
<syntaxhighlight lang="cpp">
for(const auto& [key, value] : myMap) {
    // 直接使用key和value
}
</syntaxhighlight>
}}

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 容器]]