1. 关联式容器

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的

键值对，在数据检索时比序列式容器效率更高

2. 键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代

表键值，value表示与key对应的信息

代码

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)
{}
};

3. 树形结构的关联式容器

根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构

树型结构的关联式容器主要有四种：map、set、multimap、multiset

这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列

4. 标准库里面的 set类 和 map类

set 类的介绍：

1. set 类的实现底层就是红黑树，该容器可以进行双向迭代，且它是有序的
2. 与哈希不同，它 和 map 都是树形结构

a. set 类的使用

1. set 类的模板参数

    2. set 类的构造

     3.  set 类的修改

函数声明

pair<iterator,bool> insert

( const value_type& x )

功能介绍

在set中插入元素x，实际插入的是<x, x>构成的

键值对，如果插入成功，返回<该元素在set中的

位置，true>,如果插入失败，说明x在set中已经

存在，返回<x在set中的位置，false>

注意：

返回类型

是一个键值对

iterator代表新插入元素的位置，bool代表释放插入成功

函数声明

void erase ( iterator position )

void erase ( const value_type& x )

功能介绍

删除set中position位置上的元素

删除set中元素 x

函数声明                                                                                   

iterator find                                                                   

( const key_type& x ) const

功能介绍

返回set中值为x的元素的位置

函数声明

void erase

( iterator first, iterator last )

功能介绍

删除set中[ first, last ) 位置上的元素

1. set 类的容量

函数声明

bool empty ( ) const

功能介绍

检查 set 是否为空

函数声明

size_type size() const

功能介绍

返回set中有效元素的个数

b. map 类的使用

1. map 的构造

• map()
• map(InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator())

1. map 的修改

函数声明

pair<iterator,bool> insert

( const value_type& x )

功能介绍

在map中插入键值对x，注意x是一个键值

对，返回值也是键值对：iterator代表新插入

元素的位置，bool代表释放插入成功

代码举例

#include<iostream>
using namespace std;
#include<map>
int main()
{
	map<int, int> s;
	s.insert(make_pair(10, 2)); //make_pair 是模板函数
  // s.insert(pair<int,int>(10,2))  也是对的
	auto it = s.begin(); //it 是迭代器
	while (it != s.end())
	{
		cout << it->first << ":" << (*it).second << endl; //*it 是键值对 
		++it;
	}
}

真正写法是 it->->first (省略了一个->,这里用法提过一次，具体看底层实现)

函数声明

size_type erase ( const key_type& x )

void erase ( iterator position )

void erase ( iterator first, iterator last )

功能介绍

删除键值为x的元素

删除position位置上的元素

删除[first, last)区间中的元素

1. map 的容量和访问

这里明显用了运算符重载了[] , 传的参数是key_vaule 模型里面的 key ，返回得到的是 vaule 本身（既可被访问也可被修改）

代码举例

#include<iostream>
using namespace std;
#include<map>
int main()
{
	string arr[] = { "苹果", "香蕉" ,"苹果" ,"梨" ,"葡萄" };
	map<string, int> s;
	for (auto i : arr)
	{
		s[i]++;
	}
	auto it = s.begin();
	while (it != s.end())
	{
		cout << it->first << "：" << it->second << endl;
		++it;
	}
}

运行结果：

实现原理

不看后置++，单看[] ， 实际上里层是调用了 insert 函数 , 返回

这个类型的，再用 .first(iterator 类型) ，返回 它的 ->second (就是 value 了)

c. multiset类 的使用

与 set 类的不同的是：multiset 类 不会去重

d. multimap类 的使用

与 map 类的不同的是：multimap类 不会去重