企业官网建设流程全解析

🏆浮世尘弦：个人主页

⭐个人专栏：《C语言》、《数据结构与算法》、《C++》

💎：非淡薄无以明志，非宁静无以致远

前言

容器是 C++ 标准库中最常用的基础设施之一，而按存储和组织方式划分，容器大致可以分为序列式容器与关联式容器。本文将依次介绍set、multiset、map和multimap：从基本概念、构造方式与迭代器，到插入、删除、查找等常见操作，再到map中的pair类型与operator[]函数，逐步梳理关联式容器的使用方法。希望读完之后，你不仅能够熟练使用set与map，也能理解它们为何这样设计，从而在实际问题中做出更清晰、更可靠的容器选择。让我开始今天的学习吧！

目录

前言

一，序列式容器和关联式容器

二，set容器

1，介绍set容器

2，set容器的使用

1，set的构造和迭代器

2，set的插入

3，set的删除和查找

3，multiset的使用

三，map容器

1，介绍map容器和pair类型

2，map容器的使用

1，map容器的构造和迭代器

2，map的插入，删除和查找

3,operator[]函数⭐

3，multimap的使用

一，序列式容器和关联式容器

在 C++ STL 中，容器整体分为两大类：序列式容器和关联式容器。

我们之前学习的STL中的部分容器：string，vector，list，deque，array这些容器都可以称为序列式容器。序列式容器的核心特点：元素按插入的顺序线性排列，不自动排序，允许存在重复元素，元素的位置由插入的时机和位置决定。

关联式容器的结构通常是非线性的，常见的容器有：set/multiset，map/multimap.关联式容器的核心特点：通过键”key“存储和访问元素，而不是通过位置。底层一般是红黑树/哈希表。查找效率远高于序列式容器。

set和map的底层容器都是红黑树。红黑树是一个平衡二叉搜索树。set使用的是二叉搜索树key搜索场景的结构。map使用的是key/map场景的结构。

如果想要理解二叉搜索树，具体可以看一看我的上一篇文章：

【C++】《手撕二叉搜索树：删除才是真正的分水岭》

二，set容器

1，介绍set容器

set官方文档：

set容器

基本介绍：set容器的核心功能是自动去重和自动排序。

底层结构：底层是一个红黑树（平衡二叉搜索树）。

自动排序：在插入元素时，会自动进行排序，默认使用less：升序。容器中不允许存在相同key值的元素，会自动去重。

不可直接修改：不能直接修改元素，会破坏红黑树的结构。如果要修改元素，必须先删除旧元素，再插入新的元素。

时间复杂度：插入，删除，查找的时间复杂度都为O(logN)

参数解释：

第一个参数T为底层关键字的类型。

第二个参数Compare为仿函数，默认是小于比较（升序）。如果需要特殊的排序可以自己实现一个仿函数。

第三个参数的内存是从空间配置器中申请的，一般不需要手动传入。使用默认的即可。

2，set容器的使用🌟

1，set的构造和迭代器

set的构造我们主要看四个部分：

empty中的explicit关键字的作用是：禁止构造函数的隐式类型转换。

// 假设没有 explicit 时的荒谬写法： // 编译器会试图把 std::greater<int>() 隐式转换成一个 map 对象！ std::map<int, int> myMap = std::greater<int>();

加上这个关键字可以避免一些错误的类型转换，要使用map类型必须显式调用构造函数。

set使用的是：双向迭代器

set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

2，set的插入

第一种single element为：插入单个元素 。直接传入具体的数据。

返回值：返回一个std::pair<iterator, bool>

pair.first(iterator)：指向插入成功的那个元素，如果元素已存在，则指向已存在的那个元素。

pair.second(bool)：表示插入是否真正发生。true表示插入成功（原先没有）；false表示插入失败（原先已有该元素）。

第二种with hint为:在某个位置附近插入元素。

这样做的好处是减少了插入时的查找位置时的查找次数。如果给的位置完全不对，时间复杂度依旧会退化成：O(logN)

返回值：返回一个迭代器，指向被插入的元素（或者如果元素已存在，则指向已有的元素）。不像1有bool，因为带提示的情况下无法简单判断是否发生插入。

第三种range为:将迭代器区间[first,last)中的所有元素都插入到set容器中。

应用场景：合并两个容器，或者从另一个容器（如vector、list）批量导入数据。

第四种initializer list为：接受一个花括号{...}形式的初始化列表，将里面的元素依次插入。元素会自动去重。

使用代码演示：

//set的使用 int main() { //插入+去重+排序 set<int> s1; s1.insert(1); s1.insert(3); s1.insert(14); s1.insert(12); s1.insert(3); s1.insert(1); //默认升序 //set<int>::iterator a1 = s1.begin(); auto a1 = s1.begin(); while (a1 != s1.end()) { cout << *a1 << " "; a1++; } cout << endl; //插入一个列表initializer_list遍历里面的数据 //再一个一个插入数据 s1.insert({ 2,3,4,5,6 }); for (auto ch : s1) { cout << ch << " "; } cout << endl; set<string> arr = { "apple","new","string","arr"}; //比较ASCII码值排序，从小到大 for (auto& e : arr) { cout << e << " "; } cout << endl; return 0; }

运行结果：

3，set的删除和查找

删除：

第一种：按照迭代器删除下一个元素

返回值：返回被删除元素之后的那个元素的迭代器。

第二种：删除集合中所有值为val的元素

返回值：返回被删除元素的个数。

• 对于std::set：因为元素是唯一的，返回值只能是 0 或 1（0 表示没找到，1 表示删除成功）。

• 对于std::multiset：返回值可能大于 1（会删除所有相等的元素）。

第三种：删除迭代器范围[first,last)中的所有元素

返回值：返回被删除的最后一个元素之后那个元素的迭代器。

使用场景：批量删除某个区间内的数据。结合lower_bound和upper_bound使用

lower_bound(x)返回的是第一个大于等于x的元素的迭代器

upper_bound(x)返回的是第一个大于x的元素的迭代器

查找：

通过值找到该位置的迭代器。

count也可以用来测试元素是否在集合当中

代码展示1：

////测试删除和查找 int main() { set<int> st = { 1,2,4,5,5,6,7 }; st.erase(st.begin());//通过迭代器进行删除 for (auto ch : st) { cout << ch << " "; } cout << endl; ////删除指定值 int x = 0; //cin >> x; //int num = st.erase(x); //if (num == 1) //{ // cout << "删除成功" << endl; //} //else //{ // cout << "不存在，删除失败" << endl; //} cin >> x; auto a1 = st.find(x); if (a1 != st.end()) { st.erase(x);//迭代器失效 //cout << *a1 << endl;//无法打印 } else { cout << "不存在，删除失败" << endl; } for (auto ch : st) { cout << ch << " "; } cout << endl; //可以利用算法库的查找，通过迭代器遍历，时间复杂度为O(N) auto fd = find(st.begin(), st.end(), x); //使用set自己的查找，时间复杂度为O(logN) auto fd2 = st.find(x); //count可以返回某个值x在set中的个数 //利用count快速实现查找 cin >> x; if (st.count(x)) { cout << "存在" << endl; } else { cout << "不存在" << endl; } return 0; }

运行测试：

代码展示2：

int main() { set<int> st; for (int i = 0;i < 10;i++) { st.insert(i * 10); } for (auto ch : st) { cout << ch << " "; } cout << endl; //找到迭代器区间上界和下界 auto low = st.lower_bound(20); auto upper = st.upper_bound(60); //删除指定区间中的数据[] st.erase(low, upper); for (auto ch : st) { cout << ch << " "; } return 0; }

运行展示：

3，multiset的使用

官方文档：

multiset文档

multiset和set类似，唯一的区别在于：是否支持重复元素。

区别对比：

代码测试：

//测试multiset int main() { //相较于set，multiset只会排序，不去重 //multiset允许键值冗余 multiset<int> st = { 1,3,4,5,6,4,5,7,8,2,5 }; auto it = st.begin(); while (it != st.end()) { cout << *it << " "; it++; } cout << endl; //multiset可能有多个相同的x，find找的是中序的第一个 int x; cin >> x; auto ch = st.find(x); //打印里面的所有x值 while (ch != st.end() && *ch == x) { cout << *ch << " "; ch++; } cout << endl; //count会直接返回x的个数 cout << st.count(x) << endl; //直接删除里面所有的x值 st.erase(x); auto it1 = st.begin(); while (it1 != st.end()) { cout << *it1 << " "; it1++; } cout << endl; return 0; }

运行结果：

三，map容器

1，介绍map容器和pair类型

map容器：

map容器官方文档：

map容器

map容器是STL中的一种关联式容器。用来存储键值对（key-Value），其中键（Key）是唯一的不可修改的（析构会破坏底层红黑树结构），且底层会根据键自动进行排序,迭代器走中序遍历（有序）。map就相当于在set的基础上加上value对应来对应Key。

1. 底层结构：与set一样，通常基于红黑树（自平衡二叉搜索树）实现。

2. 键值对存储：存储的元素类型是std::pair<const Key, T>。first是键（只读，不能修改），second是值（可修改）。

3. 键唯一：每个键只能出现一次。如果插入已存在的键，插入操作会被忽略（不会覆盖原有的值）。

4. 自动排序：元素会根据键的大小自动升序排序（默认使用std::less）。

5. 时间复杂度：插入、删除、查找的时间复杂度稳定在O(log n)。

参数解释：

容器中的第一个参数Key为关键字类型。

第二个参数T是value的类型，和Key相对应。

第三个参数Compare为仿函数，默认是小于比较（升序）。如果需要特殊的排序可以自己实现一个仿函数。

第四个参数的内存是从空间配置器中申请的，一般不需要手动传入。使用默认的即可。

pair类型

由于一些函数的返回值需要返回两个关联数据，但是一般函数只能返回一个返回值，此时就要设计一个结构体，接收这两个数据。达到返回两个关联数据的效果。就是下面要讲的pair类型。

pair是一个结构体，里面的成员默认为public，可以直接访问。

T1和T2用来接收两个不同类型的数据。

可以使用first和second访问pair中的T1和T2

map底层中红黑树节点中的的数据就使用的是pair<key，T>存储键值对数据。

2，map容器的使用

1，map容器的构造和迭代器

map和set一样使用的是双向迭代器：

2，map的插入，删除和查找

插入成功返回：pair<新插入元素的迭代器，true>

插入失败返回：pair<已有元素的迭代器，false>

map插入，删除和查找的这几个函数和set插入的函数几乎一样。

find不仅可以查找元素，也可以通过迭代器返回的

// 单个数据插入，如果key已经存在则插入失败（即使value不相等也会插入失败） pair<iterator, bool> insert (const value_type& val); // 列表插入，已经在容器中存在的值不会插入 void insert (initializer_list<value_type> il); // 迭代器区间插入，已经在容器中存在的值不会插入 template <class InputIterator> void insert (InputIterator first, InputIterator last); // 查找k，返回k所在的迭代器，没有找到返回end() iterator find (const key_type& k); // 查找k，返回k的个数 size_type count (const key_type& k) const; // 删除一个迭代器位置的值 iterator erase (const_iterator position); // 删除k(k不存在返回0，存在返回1) size_type erase (const key_type& k); // 删除一段迭代器区间的值 iterator erase (const_iterator first, const_iterator last); // 返回大于等于k位置的迭代器 iterator lower_bound (const key_type& k); // 返回大于等于k位置的迭代器，这是 const 版本，逻辑同上 const_iterator lower_bound (const key_type& k) const;

find返回的是一个指向std::pair<const Key, T>对象的迭代器，可以通过返回值改变节点存储的value值。

3,operator[]函数⭐

先来看一个案例：

int main() { //统计单词的出现次数 string arr[] = {"wing","except","deed","except","wing","hope","except","hope","deed"}; map<string, int> countmap; for (const auto& ch : arr) { //auto tmp = countmap.find(ch); //if (tmp == countmap.end())//没找到,插入并把value赋为1 //{ // countmap.insert({ch,1}); //} //else//找到了就在原有value上+1 //{ // tmp->second++; //} //下面一行代码可以代替上面的部分 countmap[ch]++; } //统计出现次数 for (const auto& c1 : countmap) { cout << c1.first << ":" << c1.second << endl; } cout << endl; return 0; }

运行结果：

那么operator[]是如何起到上面的作用的呢？

接下来介绍一下operator[]:

operator[]函数可以实现三大功能：插入，查找，修改

下面看一下operator[]的底层实现来理解：

下面来实际测试一下operator[]的各种功能:

3，multimap的使用

官方文档：

multimap官方文档

multimap和map的主要差别在于：multimap支持健值冗余，insert/find/count/erase都有所差异，和set与multiset的关系一样。

差异对比：

测试案例：

结尾

本篇文章中所涉及到的代码：

gitee链接：map和set的使用

以上就是本文的全部内容了，如果对你有所帮助的话，请大佬不妨给博主来个“一键三连”，这对我是大大的支持，也能让博主产出更优质的内容。

往期回顾：

【C++】《手撕二叉搜索树：删除才是真正的分水岭》

总结：本文系统讲解C++ STL中set、multiset、map、multimap四种关联式容器的原理与使用。基于红黑树实现，具备自动排序与去重特性，支持高效插入、删除、查找（时间复杂度O(logN)）。重点介绍其构造、迭代器、插入/删除/查找操作及operator[]的三大功能。

⚡把上面的内容吃透就休息一下吧⚡