C++set关联式容器

C++set

1. 关联式容器

vector、list、deque、forward_list(C++11)等STL容器，其底层为线性序列的数据结构，里面存储的是元素本身，这样的容器被统称为序列式容器。而map、set是一种关联式容器，关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。map和set的键是唯一的，但是mutimap和multiset支持多个同名且有不同映射的键共存。

2. 键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value, key代表键值，value表示与key对应的信息。比如：学生的姓名和他的学号是一一对应的，那么就可以通过查找学生的姓名来查找到对应的学号。set容器是Key结构。set不允许存在相同的key（multiset除外），且key不可修改（因为会破坏内部的红黑树结构）。

3.set容器

形参含义：

T：键值对应value的类型
Compare:比较器的类型，缺省情况下按照小于来比较，一般情况下（内置类型元索）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显式传递比较规则（一般情况下按照函数指针或者仿函数来传递）
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

4.set的成员函数

4.1 map的成员函数介绍

set的构造：

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

set的迭代器：

函数声明	功能介绍
begin()和end()	begin:首元素的位置；end：下一个元素的位置
cbegin()和cend()	c指const，cbegin和cend指向的内容不能修改
rbegin()和rend()	反向迭代器，rbegin从end开始，rend从begin开始，其++和–的方向相反
crbegin()和crend()	与前一个功能相同，但指向的内容不能修改

set的容量与元素访问：

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

set的修改：

函数名	函数声明	功能介绍
insert	pair<iterator,bool> insert (const value_type& val)	在set中插入键值对x，注意x是一个键值对，返回值也是键值对；iterator代表新插入元素的位置，bool代表插入成功
erase	void erase (iterator position)	删除position位置上的元素
	size_type erase (const value_type& val)	删除键值为x的元素
	void erase (iterator first, iterator last)	删除**[first,last)**区间中的元素
swap	void swap (set& x)	交换两个set中的元素
clear	void clear()	删除set里所有的元素

set的比较:

函数名	函数声明	功能介绍
key_comp
value_comp

set的操作：

函数名	函数声明	功能介绍
find	iterator find (const value_type& val) const	搜索set里键等于k的元素，如果找到返回一个映射的迭代器，找不到返回end的迭代器,find函数默认查找中序的第一个相等的值
count	size_type count (const value_type& val) const	搜索set里键等于k的元素，找到返回1，找不到返回0
lower_bound	iterator lower_bound (const value_type& val) const	在set里找>=k的元素，返回符合情况的最小键的迭代器
upper_bound	iterator upper_bound (const value_type& val) const	在set里找>k的元素，返回符合情况的最小键的迭代器
equal_range	pair<iterator,iterator> equal_range (const value_type& val) const

5. multimap和multiset

mutiset(map)相等的值可以在左孩子也可以在右孩子（会调整树的结构，无所谓插在哪里）。