C++ 关联容器

什么是关联容器？

关联容器是C++ STL(标准模板库)中的一类重要容器，与顺序容器不同，关联容器中的元素是通过键(key)来组织和访问的，而不是通过位置。关联容器在内部通常使用红黑树等平衡树结构实现，这使得它们在查找、插入和删除操作上具有较高的效率（通常为对数时间复杂度）。

C++ STL提供了四种基本的关联容器：

1. set：存储唯一键的集合，按照键排序
2. map：存储键-值对的集合，按照键排序，键唯一
3. multiset：允许重复键的集合，按照键排序
4. multimap：允许重复键的键-值对集合，按照键排序

备注

C++11之后，还引入了基于哈希表实现的无序关联容器：unordered_set、unordered_map、unordered_multiset和unordered_multimap，它们提供了平均常数时间复杂度的操作。本文将重点介绍基于平衡树的关联容器。

set容器

set是一个只包含唯一键的集合，它按照键的值自动排序。

基本操作

#include <iostream>
#include <set>

int main() {
    // 创建一个set容器
    std::set<int> numbers;
    
    // 插入元素
    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(10); // 重复元素不会被插入
    
    // 遍历输出set中的元素
    std::cout << "Set elements: ";
    for(const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 检查元素是否存在
    if(numbers.find(10) != numbers.end()) {
        std::cout << "Element 10 found in the set" << std::endl;
    }
    
    // 删除元素
    numbers.erase(20);
    
    // 再次遍历
    std::cout << "After erasing 20: ";
    for(const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 获取set的大小
    std::cout << "Size of set: " << numbers.size() << std::endl;
    
    return 0;
}

输出结果：

Set elements: 10 20 30
Element 10 found in the set
After erasing 20: 10 30
Size of set: 2

重要成员函数

• insert(val)：插入元素
• erase(val)：删除指定值的元素
• find(val)：查找元素，返回迭代器
• count(val)：返回指定值元素的数量（对于set通常为0或1）
• clear()：清空容器
• size()：返回容器中元素的数量
• empty()：检查容器是否为空

map容器

map容器存储键值对（pair类型），并按照键自动排序。每个键在map中只能出现一次。

基本操作

#include <iostream>
#include <map>
#include <string>

int main() {
    // 创建一个map容器，键类型为string，值类型为int
    std::map<std::string, int> studentScores;
    
    // 插入元素的几种方式
    studentScores["Alice"] = 95;
    studentScores.insert(std::make_pair("Bob", 89));
    studentScores.insert({"Charlie", 78});
    
    // 访问元素
    std::cout << "Alice's score: " << studentScores["Alice"] << std::endl;
    
    // 遍历map
    std::cout << "Student scores:" << std::endl;
    for(const auto& pair : studentScores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 检查键是否存在
    if(studentScores.find("David") == studentScores.end()) {
        std::cout << "David is not in the map" << std::endl;
    }
    
    // 修改值
    studentScores["Bob"] = 92;
    
    // 删除元素
    studentScores.erase("Charlie");
    
    // 再次遍历
    std::cout << "After modifications:" << std::endl;
    for(const auto& pair : studentScores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

输出结果：

Alice's score: 95
Student scores:
Alice: 95
Bob: 89
Charlie: 78
David is not in the map
After modifications:
Alice: 95
Bob: 92

重要成员函数

• operator[]：访问或插入元素（如果键不存在）
• insert(pair)：插入键值对
• erase(key)：删除特定键的元素
• find(key)：查找特定键，返回迭代器
• count(key)：返回特定键的元素数量（对于map通常为0或1）
• clear()：清空容器
• size()：返回容器中元素的数量
• empty()：检查容器是否为空

警告

使用operator[]访问不存在的键会创建一个新的键值对，值为默认构造的值。如果只想查询元素而不想插入，请使用find()或count()。

multiset容器

multiset是set的变体，允许存储重复的键。

基本操作

#include <iostream>
#include <set>

int main() {
    // 创建一个multiset容器
    std::multiset<int> numbers;
    
    // 插入元素，包括重复元素
    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(10); // 可以插入重复元素
    
    // 遍历输出
    std::cout << "Multiset elements: ";
    for(const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 计算特定值的元素数量
    std::cout << "Count of 10: " << numbers.count(10) << std::endl;
    
    // 删除所有特定值的元素
    numbers.erase(10);
    
    // 再次遍历
    std::cout << "After erasing 10: ";
    for(const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

Multiset elements: 10 10 20 30
Count of 10: 2
After erasing 10: 20 30

multimap容器

multimap是map的变体，允许一个键对应多个值。

基本操作

#include <iostream>
#include <map>
#include <string>

int main() {
    // 创建一个multimap容器
    std::multimap<std::string, std::string> dictionary;
    
    // 插入元素，允许同一个键对应多个值
    dictionary.insert({"apple", "a fruit"});
    dictionary.insert({"apple", "a tech company"});
    dictionary.insert({"book", "a collection of pages"});
    
    // 遍历输出所有元素
    std::cout << "Dictionary entries:" << std::endl;
    for(const auto& entry : dictionary) {
        std::cout << entry.first << ": " << entry.second << std::endl;
    }
    
    // 查找特定键的所有值
    std::string key = "apple";
    auto range = dictionary.equal_range(key);
    
    std::cout << "\nAll definitions of '" << key << "':" << std::endl;
    for(auto it = range.first; it != range.second; ++it) {
        std::cout << " - " << it->second << std::endl;
    }
    
    return 0;
}

输出结果：

Dictionary entries:
apple: a fruit
apple: a tech company
book: a collection of pages

All definitions of 'apple':
 - a fruit
 - a tech company

关联容器的常见应用场景

1. 字典和映射：存储键值对的查找表，如单词和定义、ID和用户信息等。

2. 计数和统计：使用map或multimap统计元素出现次数。

3. 去重：使用set去除重复元素。

4. 排序集合：存储需要保持有序的元素集合。

5. 符号表：在编译器或解释器中实现符号表。

实例：单词频率统计

#include <iostream>
#include <map>
#include <string>
#include <sstream>

int main() {
    std::string text = "this is a sample text this is just an example text for word counting example";
    std::map<std::string, int> wordFrequency;
    
    // 将文本拆分为单词并计数
    std::stringstream ss(text);
    std::string word;
    
    while(ss >> word) {
        // 当单词不存在时，会创建一个计数为0的新条目，然后增加计数
        wordFrequency[word]++;
    }
    
    // 输出每个单词的频率
    std::cout << "Word frequencies:" << std::endl;
    for(const auto& pair : wordFrequency) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

输出结果：

Word frequencies:
a: 1
an: 1
counting: 1
example: 2
for: 1
is: 2
just: 1
sample: 1
text: 2
this: 2
word: 1

自定义类型作为关联容器的键

要使用自定义类型作为关联容器的键，需要提供比较运算符或比较函数对象，以便容器能够正确排序和查找元素。

#include <iostream>
#include <set>
#include <string>

// 自定义类型
class Person {
public:
    std::string name;
    int age;
    
    Person(const std::string& n, int a) : name(n), age(a) {}
    
    // 定义 < 运算符，用于set的排序
    bool operator<(const Person& other) const {
        if(name != other.name)
            return name < other.name;
        return age < other.age;
    }
};

int main() {
    std::set<Person> people;
    
    people.insert(Person("Alice", 25));
    people.insert(Person("Bob", 30));
    people.insert(Person("Alice", 30));  // 不同的人，因为年龄不同
    
    std::cout << "People in the set:" << std::endl;
    for(const auto& person : people) {
        std::cout << person.name << ", " << person.age << std::endl;
    }
    
    return 0;
}

输出结果：

People in the set:
Alice, 25
Alice, 30
Bob, 30

关联容器的性能特点

关联容器使用平衡树（通常是红黑树）实现，提供以下性能特点：

1. 查找操作：O(log n) 时间复杂度
2. 插入操作：O(log n) 时间复杂度
3. 删除操作：O(log n) 时间复杂度
4. 元素始终有序：让按键遍历变得简单高效

提示

如果不需要元素排序，但需要更快的查找、插入和删除操作，可以考虑使用C++11引入的无序关联容器（如unordered_map和unordered_set），它们基于哈希表实现，提供平均常数时间复杂度的操作。

总结

C++的关联容器是STL中非常强大的工具，它们提供了高效的键值存储和检索机制：

• set：存储唯一的已排序元素
• map：存储唯一键和对应值的已排序集合
• multiset：允许重复键的已排序集合
• multimap：允许一个键对应多个值的已排序集合

关联容器适用于需要快速查找、插入和删除操作的场景，尤其是当数据需要保持有序时。它们在许多实际应用中都非常有用，如字典、符号表、频率计数等。

练习题

1. 创建一个程序，使用map存储学生姓名和成绩，然后按成绩从高到低排序输出。
2. 使用multimap实现一个简单的电话簿，其中一个人可以有多个电话号码。
3. 利用set统计一个文本文件中不重复单词的数量。
4. 创建一个自定义类Product，包含产品名称和价格，使其能作为set的键。

进一步学习资源

• C++ Reference: Set
• C++ Reference: Map
• C++ Reference: Multiset
• C++ Reference: Multimap