ToB企服应用市场:ToB评测及商务社交产业平台

标题: STL map、set、multi_map、multi_set 基本概念与用法 [打印本页]

作者: 泉缘泉 时间: 2024-8-23 16:35
标题: STL map、set、multi_map、multi_set 基本概念与用法
目录

基本概念

关联式容器

在初阶阶段，我们已经接触过STL中的部门容器，比如：vector、list、deque、
forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面
存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的
键值对，在数据检索时比序列式容器服从更高。

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包罗两个成员变量key和value，key代
表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中一定
有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应
该单词，在词典中就可以找到与其对应的中文含义。
SGI-STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

复制代码

树形结构的关联式容器

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

set

描述

set文档

翻译

set是按照一定次序存储元素的容器

在set中，元素的value也标识它(value就是key，类型为T)，而且每个value必须是唯一的。
set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。

在内部，set中的元素总是按照其内部比力对象(类型比力)所指示的特定严格弱排序准则进行
排序。

set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们答应根据次序对
子集进行直接迭代。

set在底层是用二叉搜索树(红黑树)实现的。

注意：

与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放
value，但在底层实际存放的是由构成的键值对。

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

set中的元素不可以重复(因此可以使用set进行去重)。

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

set中的元素默认按照小于来比力

set中查找某个元素，时间复杂度为：$log_2 n$

set中的元素不答应修改(为什么?)

set中的底层使用二叉搜索树(红黑树)来实现。

set的使用

模板参数列表

参数:
key_typeKeyvalue_typeKeykey_compareComparevalue_compareCompare

set中只有key,以是value_type也是key;同理value_compare等于key_compare
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

基本构造函数
函数声明功能介绍set (const Compare& comp = Compare(), const Allocator& = Allocator() );构造空的setset (InputIterator ﬁrst, InputIterator last, const Compare& comp = Compare(), const Allocator&= Allocator() );用[ﬁrst, last)区间中的元素构造 setset ( const set& x);set的拷贝构造...set的迭代器
函数声明功能介绍iterator begin()返回set中起始位置元素的迭代器iterator end()返回set中最后一个元素后面的迭代器const_iterator cbegin() const返回set中起始位置元素的const迭代器const_iterator cend() const返回set中最后一个元素后面的const迭代器reverse_iterator rbegin()返回set第一个元素的反向迭代器，即endreverse_iterator rend()返回set最后一个元素下一个位置的反向迭代器，即rbeginconst_reverse_iterator crbegin() const返回set第一个元素的反向const迭代器，即cendconst_reverse_iterator crend() const返回set最后一个元素下一个位置的反向const迭代器，即crbegin

set支持正向迭代器与反向迭代器

set的容量
函数声明功能介绍bool empty ( ) const检测set是否为空，空返回true，否则返回truesize_type size() const返回set中有效元素的个数set的通例操作
函数声明功能介绍pair insert ( const value_type& x )在set中插入元素x，实际插入的是构成的键值对，如果插入成功，返回,如果插入失败，说明x在set中已经存在，返回void erase ( iterator position )删除set中position位置上的元素size_type erase ( const key_type& x )删除set中值为x的元素，返回删除的元素的个数void erase ( iterator ﬁrst, iterator last )删除set中[ﬁrst, last)区间中的元素void swap ( set& s );交换两个set中的元素void clear ( )将set中的元素清空iterator ﬁnd ( const key_type& x ) const返回set中值为x的元素的位置size_type count ( const key_type& x ) const返回set中值为x的元素的个数(set.count()只等于0或1)map

map文档
描述

翻译：

map是关联容器，它按照特定的次序(按照key来比力)存储由键值key和值value组合而成的元素。

在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，而且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair:
typedef pair value_type;

在内部，map中的元素总是按照键值key进行比力排序的。

map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map答应根据次序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。

map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

map通常被实现为二叉搜索树(更正确的说：均衡二叉搜索树(红黑树))。

map的使用

模板参数列表

key键值对中key的类型T键值对中value的类型Compare:较器的类型，map中的元素是按照key来比力的，缺省情况下按照小于来比力，一般情况下(内置类型元素)该参数不需要通报，如果无法比力时(自定义类型)，需要用户本身显式通报比力规则(一般情况下按照函数指针或者仿函数来通报)Alloc通过空间配置器来申请底层空间，不需要用户通报，除非用户不想使用尺度库提供的空间配置器构造函数

迭代器
函数声明功能介绍begin()和end()begin:首元素的位置，end最后一个元素的下一个位置cbegin()和cend()与begin和end意义相同，但cbegin和cend所指向的元素不能修改rbegin()和rend()反向迭代器，rbegin在end位置，rend在begin位置，其++和--操作与begin和end操作移动相反crbegin()和crend()与rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改map的容量与元素访问
函数声明功能介绍bool empty ( ) const检测map中的元素是否为空，是返回true，否则返回falsesize_type size() const返回map中有效元素的个数mapped_type& operator[] (const key_type& k)返回去key对应的value,不存在则默认构造后插入mapped_type& at (const key_type& k);返回去key对应的value,不存在则抛异常

在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value,at()函数则是直接抛异常。

map中元素的操作
函数声明功能介绍pair insert ( const value_type& x )在map中插入键值对x注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功void erase ( iterator position )删除position位置上的元素size_type erase ( const key_type& x )删除键值为x的元素void erase ( iterator ﬁrst, iterator last )删除[ﬁrst, last)区间中的元素void swap ( map& mp )交换两个map中的元素void clear ( )将map中的元素清空iterator ﬁnd ( const key_type& x )在map中插入key为x的元素，找到返回该元素的位置的迭代器，否则返回endconst_iterator ﬁnd ( const key_type& x ) const在map中插入key为x的元素，找到返回该元素的位置的const迭代器，否则返回cendsize_type count ( const key_type& x ) const返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中

当key已存在时，insert插入失败
[] 支持查找，插入，修改

【总结】

map中的的元素是键值对

map中的key是唯一的，而且不能修改

默认按照小于的方式对key进行比力

map中的元素如果用迭代器去遍历，可以得到一个有序的序列

map的底层为均衡搜索树(红黑树)，查找服从比力高$O(log_2 N)$

支持[]操作符，operator[]中实际进行插入查找。

multiset

描述

multiset文档

[翻译]：

multiset是按照特定次序存储元素的容器，其中元素是可以重复的。

在multiset中，元素的value也会识别它(因为multiset中本身存储的就是组成
的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器
中进行修改(因为元素总是const的)，但可以从容器中插入或删除。

在内部，multiset中的元素总是按照其内部比力规则(类型比力)所指示的特定严格弱排序准则
进行排序。

multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭
代器遍历时会得到一个有序序列。

multiset底层结构为二叉搜索树(红黑树)。

增补：

multiset中再底层中存储的是的键值对

mtltiset的插入接口中只需要插入即可

与set的区别是，multiset中的元素可以重复，set是中value是唯一的

使用迭代器对multiset中的元素进行遍历，可以得到有序的序列

multiset中的元素不能修改

在multiset中找某个元素，时间复杂度为$O(log_2 N)$

multiset的作用：可以对元素进行排序

multiset简朴使用

[code]#include void TestSet(){ int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 }; // 注意：multiset在底层实际存储的是的键值对 multiset s(array, array + sizeof(array)/sizeof(array[0])); for (auto& e : s) cout

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)