C++关联容器概述-平芜编程栈

文章目录

关联容器（Associative Containers）全面概述

一、关联容器的核心特性

1. 存储逻辑：键值对为核心

2. 底层实现与性能特征

3. 键的唯一性

二、C++ STL 中常见关联容器详解

1. 有序关联容器

（1）map：一对一有序键值对映射

（2）set：有序唯一键集合

（3）multimap/multiset：可重复键的有序容器

2. 无序关联容器

三、关联容器的适用场景

四、关联容器与顺序容器的核心区别

总结

关联容器（Associative Containers）全面概述

关联容器是 C++ 标准模板库（STL）中一类核心容器，与顺序容器（如vector、list）最大的区别在于：它不以元素的存储位置（下标）作为访问依据，而是通过「键（Key）」与「值（Value）」的关联关系来管理和访问数据。这种设计让关联容器在「查找、插入、删除」等操作上具备更高的效率，是处理映射、去重、快速检索类问题的首选工具。

一、关联容器的核心特性

1. 存储逻辑：键值对为核心

关联容器的底层存储围绕「键值对（Key-Value Pair）」展开：

键（Key）：作为元素的唯一标识（部分容器支持重复键），用于快速检索；
值（Value）：是实际需要存储和使用的数据，可以是任意类型（基本类型、自定义结构体、容器等）。
特例：set/unordered_set仅存储「键」，可理解为 “值等于键” 的特殊键值对，核心作用是存储不重复（或可重复）的有序 / 无序数据。

2. 底层实现与性能特征

关联容器分为「有序」和「无序」两大类，底层实现的差异直接决定了性能表现：

类型	底层实现	排序特性	查找时间复杂度	插入 / 删除复杂度
有序关联容器	红黑树（平衡二叉搜索树）	按键自动升序排序	O(logn)	O(logn)
无序关联容器	哈希表（Hash Table）	无序（按哈希值存储）	平均O(1)，最坏O(n)	平均O(1)，最坏O(n)

红黑树的优势是「稳定的对数级效率」，且能保证元素有序；哈希表则在平均情况下实现常数级效率，但无序且依赖哈希函数的设计（哈希冲突会导致性能退化）。

3. 键的唯一性

根据键是否允许重复，关联容器可进一步划分：

唯一键容器：map、set、unordered_map、unordered_set，插入重复键时操作会失败（或覆盖原有值）；
可重复键容器：multimap、multiset，允许多个元素共用同一个键，适用于 “一对多” 映射场景（如一个用户对应多个联系方式）。

二、C++ STL 中常见关联容器详解

1. 有序关联容器

（1）map：一对一有序键值对映射

map<K, V>存储<K, V>类型的键值对，键K唯一且自动升序排序，支持通过键快速访问值，是最常用的关联容器之一。核心用法示例：

#include <iostream> #include <map> #include <string> using namespace std; int main() { // 定义map：键为string（学生姓名），值为int（成绩） map<string, int> student_scores; // 方式1：直接赋值插入（键不存在则创建，存在则覆盖） student_scores["张三"] = 95; student_scores["李四"] = 88; // 方式2：insert插入（键重复时插入失败，不会覆盖） auto insert_result = student_scores.insert({"张三", 100}); if (!insert_result.second) { cout << "插入失败：张三的成绩已存在，当前值为" << insert_result.first->second << endl; } // 访问元素：通过键查找 cout << "李四的成绩：" << student_scores["李四"] << endl; // 输出88 // 安全查找：避免访问不存在的键（会自动插入默认值） auto it = student_scores.find("王五"); if (it != student_scores.end()) { cout << "王五的成绩：" << it->second << endl; } else { cout << "未找到王五的成绩" << endl; } // 遍历map（自动按姓名升序排列） cout << "\n所有学生成绩：" << endl; for (const auto& pair : student_scores) { // pair.first是键，pair.second是值 cout << pair.first << "：" << pair.second << endl; } // 删除元素 student_scores.erase("李四"); // 按键删除 cout << "\n删除李四后，剩余学生数：" << student_scores.size() << endl; // 输出1 return 0; }

输出结果：

plaintext

插入失败：张三的成绩已存在，当前值为95 李四的成绩：88 未找到王五的成绩 所有学生成绩： 李四：88 张三：95 删除李四后，剩余学生数：1

（2）`set`：有序唯一键集合

set<T>仅存储类型为T的键，且键唯一、自动升序，核心作用是 “去重 + 有序存储”。核心用法示例：

#include <iostream> #include <set> using namespace std; int main() { set<int> nums; // 插入元素（重复元素自动忽略） nums.insert(3); nums.insert(1); nums.insert(2); nums.insert(2); // 重复，插入无效 // 遍历（自动升序） cout << "set中的元素："; for (int num : nums) { cout << num << " "; // 输出：1 2 3 } cout << endl; // 查找元素 if (nums.count(2)) { // count返回1（存在）或0（不存在） cout << "元素2存在" << endl; } // 删除元素 nums.erase(1); cout << "删除1后，元素数量：" << nums.size() << endl; // 输出2 return 0; }

输出结果：

plaintext

set中的元素：1 2 3 元素2存在 删除1后，元素数量：2

（3）`multimap`/`multiset`：可重复键的有序容器

multimap允许同一个键对应多个值，multiset允许存储重复的键，用法与map/set基本一致，核心差异是 “键可重复”。multimap示例：

#include <iostream> #include <map> #include <string> using namespace std; int main() { // 一个联系人对应多个电话号码 multimap<string, string> contact_phones; contact_phones.insert({"张三", "13800138000"}); contact_phones.insert({"张三", "13900139000"}); contact_phones.insert({"李四", "13700137000"}); // 查找张三的所有电话号码 cout << "张三的电话号码：" << endl; // equal_range返回键对应的迭代器范围 auto range = contact_phones.equal_range("张三"); for (auto it = range.first; it != range.second; ++it) { cout << " " << it->second << endl; } return 0; }

输出结果：

plaintext

张三的电话号码： 13800138000 13900139000

2. 无序关联容器

无序关联容器（unordered_map/unordered_set）底层基于哈希表实现，元素无序但查找效率更高，用法与有序容器几乎一致，仅 “排序特性” 不同。unordered_map示例：

#include <iostream> #include <unordered_map> #include <string> using namespace std; int main() { unordered_map<string, string> city_code; city_code["北京"] = "010"; city_code["上海"] = "021"; city_code["广州"] = "020"; // 遍历（无序，输出顺序不固定） cout << "城市区号（无序）：" << endl; for (const auto& pair : city_code) { cout << pair.first << "：" << pair.second << endl; } // 查找效率更高（平均O(1)） auto it = city_code.find("上海"); if (it != city_code.end()) { cout << "\n上海的区号：" << it->second << endl; } return 0; }

输出结果（顺序不固定）：

plaintext

城市区号（无序）： 广州：020 上海：021 北京：010 上海的区号：021

三、关联容器的适用场景

map/unordered_map：适用于 “一对一” 映射场景，如配置表（键：配置项名称，值：配置值）、缓存（键：数据 ID，值：数据内容）、字典（键：单词，值：释义）；
set/unordered_set：适用于去重 + 快速查找场景，如存储用户 ID（避免重复）、过滤重复数据、判断元素是否存在；
multimap/multiset：适用于 “一对多” 映射场景，如通讯录（一个姓名对应多个电话）、日志分类（一个分类对应多条日志）。

四、关联容器与顺序容器的核心区别

维度	关联容器	顺序容器（vector/list/deque）
访问方式	按键访问（find/[]）	按位置访问（下标 / 迭代器）
排序特性	有序容器自动排序，无序容器无排序	按插入顺序存储，无自动排序
查找效率	高（O(logn)/O(1)）	低（O(n)）
核心优势	快速查找、去重、映射	快速遍历、随机访问（vector）、灵活插入删除（list）