【C++ map和set】

文章目录

- map和set
- - 序列式容器和关联式容器
  - 键值对
  - set
  - - set的主要操作
  - map
  - - map主要操作
  - multiset和multimap

map和set

序列式容器和关联式容器

之前我们接触的vector,list,deque等，这些容器统称为序列式容器，其底层为线性序列的的数据结构，里面存储的是元素本身。
关联式容器也是用来存储数据的，只不过存储的是<key, value>结构的键值对，在查找时比序列式容器效率更高。

键值对

用来表示具有对应关系的一种结构，该结构中一般只包含两个成员变量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)
{}
};

pair所在头文件：#include < utility >
C++标准库中提供了四种主要的树形结构关联式容器:map,set,multiset,multimap

set

在这里插入图片描述
set是按照一定次序存储元素的容器
在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。
set中的元素不可以重复(因此可以使用set进行去重)。
使用set的迭代器遍历set中的元素，可以得到有序序列
set中的元素默认按照小于来比较
set中查找某个元素，时间复杂度为： $log_2 n$

set的主要操作

在这里插入图片描述
在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>

删除set中position位置上的元素

返回set中值等于val的节点个数
在这里插入图片描述
lower_bound返回set中第一个大于等于val的迭代器
upper_bound返回set中第一个大于val的迭代器

map

在这里插入图片描述
key: 键值对中key的类型
T：键值对中value的类型

map主要操作

在这里插入图片描述
和set一样，insert返回一个pair<iterator, bool>, iterator 指向成功创建的节点或者已经存在的节点，bool代表插入是否成功
同时map的其他操作如erase,count等和set类似，这里就不一一列举了
map和set操作最大的不同就是map重载了operator[]
在这里插入图片描述