关联式容器

在初阶阶段，我们已经接触过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本身就是key，key就是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