C++ 关联容器

C++关联容器

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

关联容器分类

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

有序关联容器

• std::set
  

  ：唯一键的集合，按键排序

• std::multiset
  

  ：键可重复的集合，按键排序

• std::map
  

  ：键值对集合，键唯一且按键排序

• std::multimap
  

  ：键值对集合，键可重复且按键排序

无序关联容器（C++11引入）

• std::unordered_set
  

  ：唯一键的集合，基于哈希表

• std::unordered_multiset
  

  ：键可重复的集合，基于哈希表

• std::unordered_map
  

  ：键值对集合，键唯一且基于哈希表

• std::unordered_multimap
  

  ：键值对集合，键可重复且基于哈希表

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]

核心特性

共同特性

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

有序容器特性

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

无序容器特性

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

详细容器介绍

std::set

存储唯一键的集合，自动排序。

#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!";
    }
}

std::map

存储键值对，键唯一且自动排序。

#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
    */
}

std::unordered_map

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

#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";
    }
}

性能比较

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

操作	有序容器	无序容器
插入	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：单词计数器

使用

std::map

统计文本中单词出现频率：

#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
    */
}

案例2：电话簿快速查询

使用

std::unordered_map

实现高效电话簿：

#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";
}

高级主题

自定义比较函数

对于有序容器，可以自定义排序规则：

#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
    }
}

自定义哈希函数

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

#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";
}

最佳实践

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: 需要提供哈希函数和相等比较函数，可通过特化

std::hash

或传递自定义函数对象实现。