12、【C++】关联式容器set、multiset、map、multimap

gamblerofdestinyR14

1997人浏览 · 2025-12-04 21:15:00

gamblerofdestinyR14 · 2025-12-04 21:15:00 发布

12、【C++】关联式容器set、multiset、map、multimap

一、关联式容器概述

1.1 关联式容器与序列式容器的对比

特性	关联式容器（set、map等）	序列式容器（vector、list等）
元素组织方式	按关键字有序存储	按插入顺序存储
查找效率	O(log n)（平衡树）/O(1)（哈希表）	O(n)（线性查找）
插入删除效率	O(log n)（平衡树）	O(1)（尾部）/O(n)（中间）
迭代器类型	双向迭代器（不支持随机访问）	随机访问/双向迭代器
键的特性	支持关键字查找	无关键字概念
典型应用	去重、统计、字典	动态数组、链表

1.2 关联式容器的分类

C++标准库的关联式容器分为有序关联式容器（基于平衡二叉搜索树，如红黑树）和无序关联式容器（基于哈希表，如unordered_set、unordered_map）。本文重点讨论有序关联式容器：

set：键集合，键唯一，有序。
multiset：键集合，键可重复，有序。
map：键值对集合，键唯一，有序。
multimap：键值对集合，键可重复，有序。

1.3 底层数据结构：红黑树

set、multiset、map、multimap的底层实现为红黑树（Red-Black Tree），一种自平衡的二叉搜索树，具有以下特性：

有序性：中序遍历可得到有序序列。
平衡性：通过颜色规则（红/黑节点）和旋转操作保持树高为O(log n)。
高效操作：插入、删除、查找的时间复杂度均为O(log n)。

红黑树的平衡规则（简化）：

每个节点非红即黑。
根节点为黑。
叶子节点（NIL）为黑。
红色节点的子节点必为黑。
从任一节点到其叶子节点的所有路径包含相同数量的黑节点。

1.4 关联式容器的核心特性

有序性：元素按关键字升序排列（默认），可通过自定义比较器修改排序规则。
键唯一性：set和map的键不可重复，multiset和multimap的键可重复。
高效查找：基于红黑树的O(log n)查找效率。
迭代器稳定性：插入删除操作不会导致迭代器失效（除非迭代器指向被删除元素）。

二、set容器

2.1 set的概念与特性（键唯一、有序）

set是有序的键集合容器，其特性：

键唯一：不允许插入重复键，重复插入会被忽略。
有序存储：元素按关键字升序排列（默认使用std::less<T>比较器）。
不可修改键：set的迭代器指向的元素为const，不允许修改键（会破坏有序性）。

2.2 set的常用接口

2.2.1 构造与析构

#include <set>
#include <vector>

// 默认构造
std::set<int> s1;

// 范围构造
std::vector<int> v = {3,1,2};
std::set<int> s2(v.begin(), v.end()); // {1,2,3}（自动排序）

// 拷贝构造
std::set<int> s3(s2);

// 自定义比较器（降序）
std::set<int, std::greater<int>> s4(v.begin(), v.end()); // {3,2,1}

2.2.2 插入与删除

接口	功能描述	返回值
`insert(const T& val)`	插入键val	`pair<iterator, bool>`（迭代器+插入是否成功）
`erase(iterator pos)`	删除pos位置元素	下一个有效迭代器
`erase(const T& val)`	删除键val	被删除的元素个数
`clear()`	清空所有元素	无

示例：

std::set<int> s;
// 插入
auto ret = s.insert(2); // ret.first指向2，ret.second=true（插入成功）
ret = s.insert(2); // ret.second=false（键已存在，插入失败）
s.insert(1);
s.insert(3); // s={1,2,3}

// 删除
s.erase(2); // 删除键2，s={1,3}
auto it = s.find(1);
s.erase(it); // 删除迭代器指向的元素，s={3}
s.clear(); // s为空

2.2.3 查找与统计

接口	功能描述	时间复杂度
`find(const T& val)`	查找键val，返回迭代器；不存在返回end()	O(log n)
`count(const T& val)`	统计键val的个数（set中只能是0或1）	O(log n)
`lower_bound(const T& val)`	返回第一个≥val的迭代器	O(log n)
`upper_bound(const T& val)`	返回第一个>val的迭代器	O(log n)
`equal_range(const T& val)`	返回键val的区间[lower_bound, upper_bound)	O(log n)

示例：

std::set<int> s = {1,2,3,4};
auto it = s.find(3); // 指向3的迭代器
int cnt = s.count(3); // 1（存在）
auto lb = s.lower_bound(2); // 指向2的迭代器
auto ub = s.upper_bound(2); // 指向3的迭代器
auto range = s.equal_range(2); // pair<lb, ub>

2.2.4 迭代器与遍历

set的迭代器为双向迭代器，支持++、--操作，但不支持+n、-n：

std::set<int> s = {1,2,3};

// 正向遍历
for (std::set<int>::iterator it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " "; // 1 2 3
}

// 反向遍历
for (std::set<int>::reverse_iterator rit = s.rbegin(); rit != s.rend(); ++rit) {
    std::cout << *rit << " "; // 3 2 1
}

// C++11范围for
for (int x : s) {
    std::cout << x << " "; // 1 2 3
}

2.3 set的键唯一性验证

set插入重复键时，insert返回的pair.second为false，表示插入失败：

std::set<int> s;
auto ret1 = s.insert(1); // ret1.second = true
auto ret2 = s.insert(1); // ret2.second = false，ret2.first指向已存在的1

2.4 set与函数对象（自定义排序）

set默认使用std::less<T>（升序），可通过函数对象自定义排序规则：

// 函数对象：降序比较器
struct Greater {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

std::set<int, Greater> s = {3,1,2}; // {3,2,1}

// 使用lambda表达式（C++11+，需用function包装）
#include <functional>
std::set<int, std::function<bool(int, int)>> s2(
    [](int a, int b) { return a > b; }
);
s2.insert({3,1,2}); // {3,2,1}

三、multiset容器

3.1 multiset的概念与特性（键可重复、有序）

multiset与set的唯一区别是键可重复，其他特性（有序、不可修改键）相同。

3.2 multiset与set的接口差异

接口	set行为	multiset行为
`insert(const T& val)`	返回`pair<iterator, bool>`	返回迭代器（始终插入成功）
`count(const T& val)`	返回0或1	返回键val的实际个数
`erase(const T& val)`	删除所有键为val的元素（set中最多1个）	删除所有键为val的元素

3.3 multiset的插入与查找

示例：

std::multiset<int> ms;
ms.insert(2);
ms.insert(2); // 允许重复插入，ms={2,2}
ms.insert(1); // ms={1,2,2}

// 查找所有键为2的元素
auto it = ms.find(2); // 指向第一个2
int cnt = ms.count(2); // 2（键2出现2次）

// 遍历所有键为2的元素
for (int i = 0; i < cnt; ++i) {
    std::cout << *it << " ";
    ++it; // 指向下一个2
}

3.4 案例：统计元素出现次数

#include <string>
#include <vector>
#include <multiset>
#include <iostream>

int main() {
    std::vector<std::string> words = {"apple", "banana", "apple", "orange", "banana", "apple"};
    std::multiset<std::string> ms(words.begin(), words.end());

    // 统计每个单词出现次数
    auto it = ms.begin();
    while (it != ms.end()) {
        std::string word = *it;
        int cnt = ms.count(word);
        std::cout << word << ": " << cnt << "次" << std::endl;
        std::advance(it, cnt); // 跳过已统计的单词
    }
    return 0;
}

输出：

apple: 3次
banana: 2次
orange: 1次

四、map容器

4.1 map的概念与特性（键值对、键唯一、有序）

map是有序的键值对（key-value）集合，其特性：

键值对：每个元素是std::pair<const K, V>类型（键不可修改，值可修改）。
键唯一：键不允许重复，重复插入会被忽略。
有序存储：按键升序排列（默认）。

4.2 map的键值对（pair类型）

std::pair是存储两个元素的结构体，常用于表示键值对：

#include <utility> // pair所在头文件

// pair构造
std::pair<int, std::string> p1(1, "one");
auto p2 = std::make_pair(2, "two"); // 自动推导类型

// 访问成员
std::cout << p1.first << ": " << p1.second << std::endl; // 1: one

map的元素类型为pair<const key_type, mapped_type>，因此迭代器解引用得到pair对象。

4.3 map的常用接口

4.3.1 构造与析构

// 默认构造
std::map<int, std::string> m1;

// 初始化列表构造（C++11）
std::map<int, std::string> m2{{1, "one"}, {2, "two"}, {3, "three"}};

// 范围构造
std::map<int, std::string> m3(m2.begin(), m2.end());

// 自定义比较器（降序）
std::map<int, std::string, std::greater<int>> m4(m2.begin(), m2.end()); // {3,2,1}

4.3.2 插入与删除

接口	功能描述	返回值
`insert(const pair<K,V>& val)`	插入键值对val	`pair<iterator, bool>`（迭代器+插入是否成功）
`emplace(K key, V val)`	原地构造键值对（效率高于insert）	`pair<iterator, bool>`
`erase(iterator pos)`	删除pos位置元素	下一个有效迭代器
`erase(const K& key)`	删除键key	被删除的元素个数

示例：

std::map<int, std::string> m;
// 插入方式1：insert(pair)
m.insert(std::make_pair(1, "one"));
// 插入方式2：emplace（直接传参）
m.emplace(2, "two");
// 插入方式3：operator[]（不存在则插入默认值）
m[3] = "three"; // 等价于m.insert({3, "three"})

// 删除
m.erase(2); // 删除键2
auto it = m.find(1);
m.erase(it); // 删除键1

4.3.3 元素访问

接口	功能描述	特点
`operator[](const K& key)`	访问键key对应的值，不存在则插入默认值	可能触发插入，非const对象可用
`at(const K& key)`	访问键key对应的值，不存在则抛出out_of_range	不触发插入，const对象可用

示例：

std::map<int, std::string> m{{1, "one"}};
std::cout << m[1] << std::endl; // "one"
m[2] = "two"; // 插入{2, "two"}
// m[3]; // 插入{3, ""}（默认值为空字符串）

try {
    m.at(4); // 抛出out_of_range异常
} catch (const std::exception& e) {
    std::cout << e.what() << std::endl;
}

4.3.4 查找与统计

与set接口类似，但find返回指向键值对的迭代器：

std::map<int, std::string> m{{1, "one"}, {2, "two"}};
auto it = m.find(2); // 指向{2, "two"}的迭代器
if (it != m.end()) {
    std::cout << it->first << ": " << it->second << std::endl; // 2: two
}
int cnt = m.count(1); // 1（键唯一）

4.4 map的迭代器遍历

std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};

// 正向遍历
for (auto it = m.begin(); it != m.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

// C++11结构化绑定（推荐）
for (const auto& [key, value] : m) {
    std::cout << key << ": " << value << std::endl;
}

4.5 案例：字典存储与查询

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

int main() {
    // 构建字典
    std::map<std::string, std::string> dict{
        {"apple", "苹果"},
        {"banana", "香蕉"},
        {"orange", "橙子"}
    };

    // 查询单词
    std::string word;
    std::cout << "请输入单词：";
    std::cin >> word;

    auto it = dict.find(word);
    if (it != dict.end()) {
        std::cout << "翻译：" << it->second << std::endl;
    } else {
        std::cout << "单词未找到" << std::endl;
    }
    return 0;
}

五、multimap容器

5.1 multimap的概念与特性（键值对、键可重复、有序）

multimap与map的唯一区别是键可重复，其他特性（键值对、有序）相同。

5.2 multimap与map的接口差异

无operator[]和at接口：因为键可重复，无法确定返回哪个值。
insert返回迭代器：而非pair<iterator, bool>（始终插入成功）。
count返回实际个数：而非0或1。

5.3 multimap的插入与查找

示例：

#include <multimap>
std::multimap<int, std::string> mm;
mm.insert({1, "one"});
mm.insert({1, "first"}); // 键1可重复插入
mm.emplace(2, "two");

// 查找所有键为1的元素
auto range = mm.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

输出：

1: one
1: first

5.4 案例：一对多映射（如学生-课程）

#include <multimap>
#include <string>
#include <iostream>

int main() {
    // 学生-课程映射（一个学生可选多门课）
    std::multimap<std::string, std::string> student_courses;
    student_courses.insert({"张三", "数学"});
    student_courses.insert({"张三", "英语"});
    student_courses.insert({"李四", "语文"});
    student_courses.insert({"李四", "数学"});

    // 打印某个学生的所有课程
    std::string name = "张三";
    auto range = student_courses.equal_range(name);
    std::cout << name << "的课程：" << std::endl;
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "- " << it->second << std::endl;
    }
    return 0;
}

输出：

张三的课程：
- 数学
- 英语

六、关联式容器的迭代器

6.1 迭代器的类型与特性

有序关联式容器的迭代器为双向迭代器，支持：

++/--：前后移动。
*/->：访问元素。
不支持+n/-n（随机访问）。

6.2 迭代器的有效性

插入操作：所有迭代器仍有效（红黑树结构调整不影响迭代器指向）。
删除操作：指向被删除元素的迭代器失效，其他迭代器仍有效。

示例：

std::set<int> s = {1,2,3,4};
auto it = s.begin();
++it; // it指向2
s.erase(it); // 删除2，it失效
// *it = 5; // 未定义行为

6.3 反向迭代器与const迭代器

反向迭代器：rbegin()/rend()，从尾到头遍历。
const迭代器：cbegin()/cend()，用于const对象，不可修改元素。

const std::set<int> s = {1,2,3};
for (auto it = s.cbegin(); it != s.cend(); ++it) {
    // *it = 4; // 错误：const迭代器不可修改
}

for (auto rit = s.rbegin(); rit != s.rend(); ++rit) {
    std::cout << *rit << " "; // 3 2 1
}

七、查找与统计接口深度剖析

7.1 find接口（查找键）

find(key)返回指向键key的迭代器，不存在则返回end()。时间复杂度O(log n)。

std::set<int> s = {1,2,3};
auto it = s.find(2);
if (it != s.end()) {
    std::cout << "找到：" << *it << std::endl;
}

7.2 count接口（统计键出现次数）

count(key)返回键key的出现次数，set中为0或1，multiset中为实际个数。时间复杂度O(log n + count)。

std::multiset<int> ms = {1,2,2,3};
int cnt = ms.count(2); // 2

7.3 lower_bound与upper_bound接口

lower_bound(key)：返回第一个≥key的迭代器。
upper_bound(key)：返回第一个**>key**的迭代器。
时间复杂度均为O(log n)。

示例：

std::set<int> s = {1,3,5,7};
auto lb = s.lower_bound(4); // 指向5（第一个≥4）
auto ub = s.upper_bound(5); // 指向7（第一个>5）

7.4 equal_range接口（返回键的区间）

equal_range(key)返回pair<lower_bound, upper_bound>，表示键key的所有元素区间。时间复杂度O(log n)。

std::multiset<int> ms = {2,2,2};
auto range = ms.equal_range(2);
int cnt = std::distance(range.first, range.second); // 3（元素个数）

八、自定义比较器

8.1 函数对象作为比较器

定义一个重载operator()的结构体作为比较器：

// 按字符串长度排序
struct StrLenCmp {
    bool operator()(const std::string& a, const std::string& b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b; // 长度相同则按字典序
    }
};

std::set<std::string, StrLenCmp> s = {"apple", "banana", "pear"};
// 排序结果："pear"（4）, "apple"（5）, "banana"（6）

8.2 lambda表达式作为比较器（C++11+）

使用lambda表达式作为比较器（需用std::function包装）：

#include <functional>
// 降序比较器
auto cmp = [](int a, int b) { return a > b; };
std::set<int, std::function<bool(int, int)>> s(cmp);
s.insert({3,1,2}); // {3,2,1}

8.3 案例：按结构体成员排序

struct Person {
    std::string name;
    int age;
};

// 按年龄升序，年龄相同按姓名升序
struct PersonCmp {
    bool operator()(const Person& a, const Person& b) const {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    }
};

std::set<Person, PersonCmp> s = {{"张三", 20}, {"李四", 18}, {"王五", 20}};
// 排序结果：李四(18), 张三(20), 王五(20)

九、关联式容器的性能分析与应用场景

9.1 时间复杂度对比（插入、删除、查找）

操作	set/map（红黑树）	multiset/multimap（红黑树）	vector（序列式）	list（序列式）
插入（中间）	O(log n)	O(log n)	O(n)	O(1)
删除（中间）	O(log n)	O(log n)	O(n)	O(1)
查找	O(log n)	O(log n)	O(n)	O(n)

9.2 去重与排序场景（set vs vector）

set：自动去重排序，适合数据量大且需频繁查找的场景。
vector+sort+unique：适合数据量小或插入后无需频繁修改的场景。

// set去重排序
std::set<int> s(v.begin(), v.end());
// vector去重排序
std::sort(v.begin(), v.end());
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end());

9.3 字典与映射场景（map的应用）

map适合存储键值对数据，如配置表、缓存、索引等：

// 配置表
std::map<std::string, std::string> config = {
    {"ip", "127.0.0.1"},
    {"port", "8080"},
    {"timeout", "30"}
};

9.4 区间查询场景（lower_bound/upper_bound）

关联式容器的区间查询效率高于序列式容器：

// 查询成绩在[60, 80]的学生
std::map<int, std::string> scores = {{59,"F"}, {60,"D"}, {70,"C"}, {80,"B"}, {90,"A"}};
auto lb = scores.lower_bound(60);
auto ub = scores.upper_bound(80);
for (auto it = lb; it != ub; ++it) {
    std::cout << it->second << std::endl; // D, C
}

十、关联式容器的常见问题与最佳实践

10.1 迭代器失效问题

插入操作：所有迭代器仍有效（红黑树结构调整不影响迭代器指向）。
删除操作：仅指向被删除元素的迭代器失效，其他迭代器有效。

最佳实践：删除元素后，使用erase返回的迭代器继续遍历：

auto it = s.begin();
while (it != s.end()) {
    if (*it % 2 == 0) {
        it = s.erase(it); // 接收返回的下一个迭代器
    } else {
        ++it;
    }
}

10.2 避免键的修改

关联式容器的键是有序的，修改键会破坏容器结构，导致未定义行为。如需修改键，应先删除旧键，再插入新键：

// 错误：直接修改键
auto it = m.find(1);
it->first = 2; // 未定义行为

// 正确：删除旧键，插入新键
m.emplace(2, it->second);
m.erase(it);

10.3 map的operator[]与at的选择

operator[]：适合非const对象，需要插入新键值对的场景。
at：适合const对象或不希望意外插入的场景（如查找可能不存在的键）。

10.4 何时选择multiset/multimap而非set/map

键需要重复存储（如一对多关系）。
需统计键的出现次数。
无需通过operator[]访问元素。

通过以上内容，已经全面覆盖了set、multiset、map、multimap的核心知识点，包括特性、接口、实现原理及应用场景。合理选择关联式容器可显著提升程序的性能和可读性。

亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责

亚马逊云科技技术品牌专区

所有评论(0)

查看更多评论

gamblerofdestinyR14

@gamblerofdestinyR14

已为社区贡献4条内容

12、【C++】关联式容器set、multiset、map、multimap

gamblerofdestinyR14

12、【C++】关联式容器set、multiset、map、multimap

目录

一、关联式容器概述

1.1 关联式容器与序列式容器的对比

1.2 关联式容器的分类

1.3 底层数据结构：红黑树

1.4 关联式容器的核心特性

二、set容器

2.1 set的概念与特性（键唯一、有序）

2.2 set的常用接口

2.2.1 构造与析构

2.2.2 插入与删除

2.2.3 查找与统计

2.2.4 迭代器与遍历

2.3 set的键唯一性验证

2.4 set与函数对象（自定义排序）

三、multiset容器

3.1 multiset的概念与特性（键可重复、有序）

3.2 multiset与set的接口差异

3.3 multiset的插入与查找

3.4 案例：统计元素出现次数

四、map容器

4.1 map的概念与特性（键值对、键唯一、有序）

4.2 map的键值对（pair类型）

4.3 map的常用接口

4.3.1 构造与析构

4.3.2 插入与删除

4.3.3 元素访问

4.3.4 查找与统计

4.4 map的迭代器遍历

4.5 案例：字典存储与查询

五、multimap容器

5.1 multimap的概念与特性（键值对、键可重复、有序）

5.2 multimap与map的接口差异

5.3 multimap的插入与查找

5.4 案例：一对多映射（如学生-课程）

六、关联式容器的迭代器

6.1 迭代器的类型与特性

6.2 迭代器的有效性

6.3 反向迭代器与const迭代器

七、查找与统计接口深度剖析

7.1 find接口（查找键）

7.2 count接口（统计键出现次数）

7.3 lower_bound与upper_bound接口

7.4 equal_range接口（返回键的区间）

八、自定义比较器

8.1 函数对象作为比较器

8.2 lambda表达式作为比较器（C++11+）

8.3 案例：按结构体成员排序

九、关联式容器的性能分析与应用场景

9.1 时间复杂度对比（插入、删除、查找）

9.2 去重与排序场景（set vs vector）

9.3 字典与映射场景（map的应用）

9.4 区间查询场景（lower_bound/upper_bound）

十、关联式容器的常见问题与最佳实践

10.1 迭代器失效问题

10.2 避免键的修改

10.3 map的operator[]与at的选择

10.4 何时选择multiset/multimap而非set/map

所有评论(0)

温馨提示：您尚未绑定手机号

gamblerofdestinyR14