C++——map|set介绍

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

关联式容器

set

关联式容器

在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、
forward_list(C++11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。

关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是<key, value>结构的键值对在数据检索时比序列式容器效率更高
map和set是关联式容器

vector/list/deque是序列式容器

set

set由二叉搜索树实现set是key模型。

有3个模板参数

1. set是按照一定次序存储元素的容器
2. 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。
set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。
3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行
排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对
子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。

6.set遍历时候数据是有序的因为是搜索二叉树按照中序遍历就是有序的
注意
1. 与map/multimap不同map/multimap中存储的是真正的键值对<key, value>set中只放
value但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时只需要插入value即可不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素时间复杂度为$log_2 n$
7. set中的元素不允许修改
8. set中的底层使用二叉搜索树(红黑树)来实现

set的构造

函数声明	功能介绍
set (const Compare& comp = Compare(), const Allocator& = Allocator() );	构造空的set
set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );	用[first, last)区间中的元素构造 set
set ( const set<Key,Compare,Allocator>& 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第一个元素的反向迭代器即end
reverse_iterator rend()	返回set最后一个元素下一个位置的反向迭代器即rbegin
const_reverse_iterator crbegin() const	返回set第一个元素的反向const迭代器即cend
const_reverse_iterator crend() const	返回set最后一个元素下一个位置的反向const迭代器即crbegin

set的容量

函数声明	功能介绍
bool empty ( ) const	检测set是否为空空返回true否则返回true
size_type size() const	返回set中有效元素的个数

set修改操作

函数声明	功能介绍
pair<iterator,bool> insert ( const value_type& x )	在set中插入元素x实际插入的是<x, x>构成的键值对如果插入成功返回<该元素在set中的位置true>,如果插入失败说明x在set中已经存在返回<x在set中的位置false>
void erase ( iterator position )	删除set中position位置上的元素
size_type erase ( const key_type& x )	删除set中值为x的元素返回删除的元素的个数
void erase ( iterator first, iterator last )	删除set中[first, last)区间中的元素
void swap ( set<Key,Compare,Allocator>& st );	交换set中的元素
void clear ( )	将set中的元素清空
iterator find ( const key_type& x ) const	返回set中值为x的元素的位置如果没找到返回end最后一个元素之后的位置
size_type count ( const key_type& x ) const	返回set中值为x的元素的个数因为是搜索二叉树所以只能返回0和1

iterator lower_bound (const value_type& val);	它返回一个迭代器指向容器中不被认为在 val 之前的第一个元素
iterator upper_bound (const value_type& val);	它返回一个迭代器该迭代器指向set容器中的值该值大于参数中传递的val。如果没有这样的元素则返回end()。

multiset支持数据重复冗余所以count一般用在这里进行统计个数

equal_range

该函数是找一段区间

pair:

multiset

1. multiset是按照特定顺序存储元素的容器其中元素是可以重复的。
2. 在multiset中元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成
的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器
中进行修改(因为元素总是const的)但可以从容器中插入或删除。
3. 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭
代器遍历时会得到一个有序序列。
5. multiset底层结构为二叉搜索树(红黑树)。

find(3)返回的是中序遍历的第一个3的位置即最左边的3

erase(3)删的是所有的3

注意
1. multiset中再底层中存储的是<value, value>的键值对
2. mtltiset的插入接口中只需要插入即可
3. 与set的区别是multiset中的元素可以重复set是中value是唯一的
4. 使用迭代器对multiset中的元素进行遍历可以得到有序的序列
5. multiset中的元素不能修改
6. 在multiset中找某个元素时间复杂度为$O(log_2 N)$
7. multiset的作用可以对元素进行排序

map

key: 键值对中key的类型
T 键值对中value的类型
Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比
较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户
自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的
空间配置器
注意在使用map时需要包含头文件

map的构造

函数声明	功能介绍
map()	构造一个空的map

map的迭代器

函数声明	功能介绍
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否则返回false
size_type size() const	返回map中有效元素的个数
mapped_type& operator[] (const key_type& k)	返回去key对应的value