目录

pair 对组

set/multiset 容器

set 的特性：

树：

二叉搜索树的放置规则：

set 常用api：

构造、大小、插入

 查找

 set 容器存放类

map/multimap 容器

基本概念：

 map 常用api：

插入操作

 删除、查找

---

pair 对组

pair 对组是一个类，类中有两个公有的成员变量。

pair 将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用 pair 的两个公有属性 first 和 second 访问。

pairint> mp("sun",18);

set/multiset 容器

set 的特性：

所有元素都会根据元素的键值自动被排序；

set 的元素不像 map 那样可以同时拥有实值和键值，set 的元素既是键值又是实值，set 不允许两个元素有相同的键值；

不可以通过 set 的迭代器改变 set 元素的值，set 的 iterator 是一种 const_iterator。

multiset 的特性及用法与set完全相同，唯一区别在于允许键值重复。

set 和 multiset 的底层实现是红黑树（平衡二叉树的一种）。

树：

二叉树就是任何节点最多只允许有两个子节点，分别为左子节点和右子节点。

 

二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。

二叉搜索树的放置规则：

任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。

平衡二叉树：

红黑树：

set 常用api：

构造、大小、插入

set st;          //set默认构造函数：
mulitset mst;    //multiset默认构造函数: 
set(const set &st); //拷贝构造函数
 
set& operator=(const set& st);  //重载等号操作符
swap(st);           //交换两个集合容器
 
size();   //返回容器中元素的数目
empty();  //判断容器是否为空
 
insert(elem);      //在容器中插入元素
clear();           //清除所有元素
erase(pos);        //删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(begin,end);  //删除区间[begin,end)的所有元素 ，返回下一个元素的迭代器
erase(elem);       //删除容器中值为elem的元素

 可以看出，set 根据自身规则进行排序，从小到大。

 

set 容器不允许有两个相同的元素，但是插入相同的元素，编译不会报错，运算也不报错，只是不把数据插入容器。
我们来验证一下：

首先来看 insert 的定义：

 可以看出，它的返回值是一个 pair，所以需要定义一个 pair 类型的变量接它的返回值，eg：

pairint>::iterator,bool> ret = s.insert(4);

 不能通过算法进行排序：

 查找

find(key);  //查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
1.	count(key);           //查找键key的元素个数
2.	lower_bound(keyElem); //返回第一个key>=keyElem元素的迭代器
3.	upper_bound(keyElem); //返回第一个key>keyElem元素的迭代器
equal_range(keyElem);   //返回容器中key与keyElem相等的上下限的两个迭代器

 

 set 容器存放类

 上面的例子都是往 set 容器中存放 int类型的元素，下面存储一个类对象试下。

set 容器存储对象时，需要告诉 set 容器规则，即告诉 set 容器该如何对对象元素进行排序。

 注意：

当对仿函数中的()进行重载，希望得到指定的排序方式时，提示如下错误：

 解决方法：

在运算符重载函数后面加上 const 。

map/multimap 容器

基本概念：

map/multimap 也是关联式容器，容器自身有规则，根据元素的键值自动排序；

map 的所有元素都是 pair，同时拥有实值和键值，pair 的第一元素为键值，第二元素为实值；

map 不允许两个元素有相同的键值；

不能通过 map 的迭代器改变 map 的键值，因为 map 的键值关系到 map 元素的排列规则，但是可以修改元素的实值；

multimap 和 map 的操作类似，唯一区别是 multimap 键值可重复；

map 和 multimap 都是以红黑树为底层实现机制。

 map 常用api：

map mp;      //map默认构造函数: 
map(const map &mp);  //拷贝构造函数
 
map&operator=(const map& mp);  //重载等号运算符
swap(mp);   //交换两个集合容器
 
size();     //返回容器中元素的数目
empty();    //判断容器是否为空

插入操作

map.insert(...); //往容器插入元素，返回pair
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";

 

 改变排序规则：

 注意：

当使用 [] 方式插入数据时，如果没有实值，那么键值也是存在的。

 删除、查找

clear();           //删除所有元素
erase(pos);        //删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(begin,end);  //删除区间[begin,end)的所有元素 ，返回下一个元素的迭代器
erase(keyElem);    //删除容器中key为keyElem的对组
 
find(key);      //查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回map.end();
count(key);     //返回容器中键值为key的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
lower_bound(keyElem);  //返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);  //返回第一个key>keyElem元素的迭代器。	
equal_range(keyElem);  //返回容器中key与keyElem相等的上下限的两个迭代器。