当前位置：首页 > news >正文

STL的map和set（关联式容器深度解析）

news 2025/5/26 8:33:24

本节目标

1.关联式容器

2.键值对

3.树形结构的关联式容器

4.底层结构

关联式容器

序列式容器和关联式容器是 C++ 标准模板库（STL）中的两种基本容器类型，它们的主要区别在于元素的存储方式和访问方式。

序列式容器按照元素插入的顺序存储元素，每个元素都有固定的位置，除非被显式删除或移动。例如我们前面学的vector / list / deque / forward_list /array等，其底层为线性序列的数据结构，里面存储的是元素本身

关联式容器按照键（key）来存储和访问元素，键通常是唯一的，并且会根据特定的排序准则自动排序，在数据检索时比序列式容器效率更高，常见的容器有map/set/multiset/multimap

键值对：key-value

用来表示具有一一对应的结构，该结构中一般包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如用身份证号码存储一个人的基本信息，你通过身份证号码和信息对应，把它存储起来，查一个人时只需要查找它的身份证号码，后续在把号码对应的信息查出来

这是STL对于pair的底层实现

可以发现就是封装了一个pair类，类里面有两个成员变量，也就是键值对，一般第一个是key，第二个是value

这是STL头文件<utility>中的pair，看它的构造函数，与底层实现的一样

也就是有三种构造方式，第一个是构造空的，第二个是拷贝构造函数，第三个是传参构造

树形结构的关联式容器

根据应用场景不同，STL总共实现了两种不同结构的管理式容器：树型结构和哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树（即红黑树）作为底层结构，容器中的元素是一个有序的序列。下面依次介绍每个容器的使用方法。

set

set的介绍

集合（Set）是一种按照特定顺序存储唯一元素的容器。

在集合中，元素的值本身即作为其标识（每个元素的值就是键，类型为 T），且每个值必须唯一。一旦元素被放入集合，其值不能被修改（元素在容器中始终为常量），但可以插入新元素或移除已有元素。

从内部实现来看，集合中的元素始终按照其内部比较对象（类型为 Compare）所定义的严格弱序准则进行排序。

与无序集合（unordered_set）相比，集合容器通过键访问单个元素的速度通常较慢，但它们允许基于元素顺序直接对子集进行迭代。

集合通常以二叉搜索树（红黑树）的形式实现。

注意：

1.与map/multimap不同，map/multimap中存储的是真正的键值对<key,value>，在set中只放value，但在底层实际存放的是由<value,value>的键值对，也就是它以value为标识，所以每个值必须唯一，并且不能修改

2.在set中插入元素时，只需要插入value即可，不需要构造键值对

3.set的元素不可以重复(因此可以使用set去重)

4.使用set的迭代器遍历set中的元素，可以得到有序序列

5.set中的元素默认按照小于来比较

6.set中查找某个元素，时间复杂度时log以2为底的N次

7.set中的元素不允许被修改（为什么？因为它底层是一颗红黑树，如果你进行了修改就改变了本来树的结构，元素值就是红黑树的键，修改键会破坏树的有序性和平衡性）

8.set中的底层使用二叉搜索树（红黑树）来实现

set的使用

T:set中存放的元素的类型，实际在底层存储<value,value>的键值对

Compare：set中元素默认按照小于来比较

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

set的构造：

第一个构造空的set

第二个用[first，last）区间中的原色构成set

第三个拷贝构造

set的迭代器

这与我们之前学的一样

set的容量

学会empty和size即可，跟之前一样的

empty()：是空就返回true，非空返回false

size():返回set中有效元素的个数

set修改操作

第一个插入可以插入任意元素，只要和set里面存的元素的类型一样即可

注意：这里的返回值，返回一个键值对，键值对的第一个元素是迭代器类型，第二个是布尔类型

为什么？？？

因为可能你插入重复的元素，如果你插入重复的元素就返回那个元素的位置，并且返回false，用那个元素的位置和false创建一个键值对类，然后在返出去

第二个插入是给一个位置，在这个位置后插入一个元素，如果这个位置正确就不调整，否则还要进行调整，因为你底层是一颗红黑树

第三个插入时给一段区间，把区间的元素进行插入

最常用的是第一种

第一个删除pos位置的元素

第二个如果你知道元素是什么，可以直接指定，返回值是无符号整形，返回0表示未找到，返回1表示成功删除

第三个删除，删除一段区间

交换两个set对象

清空里面的元素

操作函数：

这里重点学习find即可

查找某个元素，找到返回它所在的迭代器位置，找不到返回end()位置

map

map的介绍

映射（Maps）属于关联式容器，其存储的元素由键值（key value）和映射值（mapped value）组合而成，并且这些元素会按照特定顺序排列。

在映射里，键值的主要作用是对元素进行排序以及唯一标识元素，而映射值则用于存储与该键相关联的内容。键和映射值的类型可以不一样，它们被组合在成员类型 value_type 中，这是一种将两者结合起来的 pair 类型：

typedef pair<const Key, T> value_type;

从内部实现来看，映射中的元素始终依据键，按照特定的严格弱序准则（由其内部比较对象（类型为 Compare）来确定）进行排序。

和无序映射（unordered_map）容器相比，映射容器通过键来访问单个元素的速度通常要慢一些。不过，映射容器能够基于元素的顺序直接对子集进行迭代。

映射中的映射值可以利用方括号运算符（operator[]），通过其对应的键直接进行访问。

映射一般是用二叉搜索树（红黑树）来实现的。

map的使用

map的模板参数说明

template < class Key,                        // map::key_type           
class T,                                     // map::mapped_type          
class Compare = less<Key>,                   // map::key_compare          
class Alloc = allocator<pair<const Key,T> >  // map::allocator_type

key：键值对中key的类型

T：键值对中value的类型

Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下（内置类型元素）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显示传递比较规则（一般情况下按照函数指针或者仿函数来传递）

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不选使用标准库提供的空间配置器

map的构造


empty (1)	
explicit map (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
range (2)	
template <class InputIterator>  
map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(),       const allocator_type& alloc = allocator_type());
copy (3)	
map (const map& x);

第一个在使用缺省的情况下可以直接map<int,int>m：构造一个空的map

第二个也就是区间构造

第三个就是map的拷贝构造函数

map的迭代器

跟之前的学习一样

map的容量

empty()：判空

size()：大小

map中的元素的修改

这里对swap和clear不讲解，只针对insert和erase

于set一样的，就是三个，一般常用第一个，其中value_type是下面的typedef过的

value_type

pair<const key_type,mapped_type>

与set一样三个，第一个pos位置删除，第二个删除某个key，第三个删除一段区间

find函数：

就是查找某个key，然后返回它的迭代器位置即可

make_pair()

它是一个全局的函数，作用就是用来构造pair这个类的

以后构造pair的时候可以不要pair<int,int>(1,2)

可以直接make_pair(1,2)

重点学习operator[]：

与之前的set对比，map支持[]，而set不支持

如果k与容器中的某个元素的键匹配，则该函数返回对其映射值的引用。

如果k与容器中任何元素的键都不匹配，则函数会插入一个带有该键的新元素，并返回对其映射值的引用。请注意，这总会使容器大小增加 1，即使没有为该元素分配映射值（元素会使用其默认构造函数进行构造）。

类似的成员函数map::at在键存在的元素上具有相同的行为，但在键不存在时会抛出异常。

这个函数就等价于在调用

(*((this->insert(make_pair(k,mapped_type()))).first)).second

总结：就是如果这个key在就返回对其映射值得引用，如果不在就会插入

 _Tp& operator[](const key_type& __k) {iterator __i = lower_bound(__k);// __i->first is greater than or equivalent to __k.if (__i == end() || key_comp()(__k, (*__i).first))__i = insert(__i, value_type(__k, _Tp()));return (*__i).second;}

这个是源码，不好看，所以我们看它的等价式，就等价于调用

(*((this->insert(make_pair(k,mapped_type()))).first)).second

可以自行看一下括号的分配情况

讲解：

这里的mapped_type()是value的typedef过的，也就是value的类型，为什么是有个括号呢？因为如果不存在的话要调用它的构造函数，其实内置类型也可以看作类，也就是int()，它会调int的默认构造函数，也就会是0，一般这种都是0，如果你是自定义类型，就会调自定义类型的默认构造函数

第二个是make_pair(k,mapped_type())，k就是你传入的参数，构造一个pair对象

第三个insert(make_pair(k,mapped_type()))

第四个就是this->insert(make_pair(k,mapped_type())) ,this就是你的对象的地址嘛，->找到insert在进行插入

第五个((this->insert(make_pair(k,mapped_type()))).first))，当你调完你this的insert后，根据上面对insert的学习，会返回一个pair对象嘛，pair里面第一个存的是迭代器类型，第二个存的是bool类型，相当于pair.first，那就会拿到迭代器位置

然后对迭代器位置进行解引用，也就是你那个真实存的的pair，然后.second拿到value，返回它的引用，外部就可以进行更改。（迭代器解引用就是pair对象）

为什么operator[]不用find实现

用find，我们回去找到find的返回值，是迭代器类型，对比一下insert的返回，是pair对象

如果用find，map中没有k，如何返回？

用insert，如果k不在map中，则插入，在返回对value的引用

如果k在map中，则插入失败，返回k所在结点中的映射对象的引用

返回引用外部就可以修改，反观find，find的返回是iterator，k不在就返回end()，k在才返回

map的operator[]的应用场景

1.查找

2.修改

3.统计次数：比如你可以每次插入时，如果相同，对应得value就++，因为你不能插入相同得元素，你返回value的引用了就可以++

总结