目录

• 关联式容器
• 键值对
• set文档介绍
• • set的模板参数列表
  • set的使用
  • • set的构造
    • set的迭代器
    • set的容量
    • set修改操作
• multiset
• map的介绍
• • map的模板参数说明
  • map的构造
  • map的迭代器
  • map的容量与元素访问
  • map中元素的修改
• map容器的综合应用

关联式容器

我们已经接触过STL中的部分容器，比如：vector、list、deque、这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高

总结：
1、容器本身底层采用线性序列存储数据的结构叫做序列式容器，比如vector、list
2、容器本身底层采用键值对存储数据的结构叫做关联式容器，比如map、set

键值对

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

set文档介绍

1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. 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中查找某个元素，时间复杂度为：o(log n)
7. set中的元素不允许修改(为什么?)

8. set中的底层使用二叉搜索树(红黑树)来实现

set的模板参数列表

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。

Compare：set中元素默认按照小于来比较，less是一个仿函数类

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

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的拷贝构造

void functest01() 
{
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	int len = sizeof(arr) / sizeof(arr[0]);

	set<int> s1;//构造0个元素的set对象
	set<int> s2(arr, arr + len); //使用【arr,arr + len】区间构造set对象
	set<int> s3(s2); //调用set的拷贝构造函数创建set对象

	cout << s1.size() << endl;
	cout << s2.size() << endl;
	cout << s3.size() << endl;
}

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最后一个元素下一个位置的反向迭代器，即
const_reverse_iterator crbegin() const	返回set第一个元素的反向const迭代器，即cend
const_reverse_iterator crend() const	返回set最后一个元素下一个位置的反向const迭代器，即crbegin

void functest02() 
{
	int arr[] = { 1,1,2,3,3,4,5,6,7,7,8,9,11,20,32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	set<int> s(arr, arr + len);
	//使用正向迭代器
	for (auto it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
}

void functest03()
{
	int arr[] = { 1,1,2,3,3,4,5,6,7,7,8,9,11,20,32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	set<int> s(arr, arr + len);
	//使用反向迭代器
	for (auto it = s.rbegin(); it != s.rend(); it++)
	{
		cout << *it << " ";
	}
}

void functest04()
{
	int arr[] = { 1,1,2,3,3,4,5,6,7,7,8,9,11,20,32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	set<int> s(arr, arr + len);
	//使用返回const类型的反向迭代器
	for (auto it = s.crbegin(); it != s.crend(); it++)
	{
		cout << *it << " ";
	}
}

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的元素的位置
size_type count ( const key_type& x ) const	返回set中值为x的元素的个数

//erase函数的对比
void functest05()
{
	int arr[] = { 1,1,2,3,3,4,5,6,7,7,8,9,11,20,32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	set<int> s(arr, arr + len);
	auto it = s.find(30);
	s.erase(it);  
	//如果set集合中并不存在该元素，使用void erase ( iterator position )函数删除不存在的元素会报错
	s.erase(30); 
	//即使set集合并不存在30这个元素，使用size_type erase ( const key_type& x )删除这个不存在的元素也不会报错
}

multiset

我们知道set是不允许的键值冗余的，而multiset是允许键值冗余的

//multiset与set的对比
void functest06() 
{
	int arr[] = { 1,1,2,3,3,4,5,6,7,7,8,9,11,20,32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	multiset<int> ms(arr, arr + len);
	set<int> s(arr, arr + len);
	
	//从打印的结果来看multiset是可以存放重复的key的，而set却不允许存在重复的key
	for (auto& ref : ms) cout<< ref <<" "; //1 1 2 3 3 4 5 6 7 7 8 9 11 20 32
	cout << endl;
	for (auto& ref : s) cout << ref << " ";//1 2 3 4 5 6 7 8 9 11 20 32
}

//multiset的其他接口函数
void functest07() 
{
	int arr[] = { 1,1,2,3,3,4,5,6,7,7,8,9,11,20,32 };
	int len = sizeof(arr) / sizeof(arr[0]);
	multiset<int> ms(arr, arr + len);

	for (auto& ref : ms) cout<< ref <<" "; //1,1,2,3,3,4,5,6,7,7,8,9,11,20,32
	cout << endl;
	
	//multiset容器统计key为val的元素个数
	cout << ms.count(3) << endl;  // 2
	cout << ms.count(7) << endl;  // 2
	
	ms.erase(3); //使用erase函数会将所有的key为3的元素全部删除
	for (auto& ref : ms) cout << ref << " "; //1 1 2 4 5 6 7 7 8 9 11 20 32
	cout << endl;
	
}

multiset的成员接口函数大部分和set是一样的，而他的find函数需要注意一下，find查找到后返回的是在容器中第一次出现的元素

map的介绍

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair: typedef pair value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

map的模板参数说明

key: 键值对中key的类型

T： 键值对中value的类型

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况
下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则
(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
注意：在使用map时，需要包含头文件。

map的构造

函数声明	功能介绍
explicit map (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type())	构造一个没有元素的空容器。
map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());	用[first, last)区间中的元素构造set
map (const map& x)	拷贝构造一个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

map中元素的修改

函数声明	功能简介
pair<iterator,bool> insert ( const value_type& x )	在map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功
void erase ( iterator position )	删除position位置上的元素
size_type erase ( const key_type& x )	删除键值为x的元素
void erase ( iterator first, iterator last )	删除[first, last)区间中的元素
void swap ( map<Key,T,Compare,Allocator>& mp )	交换两个map中的元素
void clear ( )	将map中的元素清空
iterator find ( const key_type& x )	在map中插入key为x的元素，找到返回该元素的位置的迭代器，否则返回end
const_iterator find ( const key_type& x ) const	在map中插入key为x的元素，找到返回该元素的位置的const迭代器，否则返回cend
size_type count ( const key_type& x ) const	返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中

接口测试：

//map对象的两种插入方式
void func() 
{
	map<int, double> m;
	//调用pair的构造函数，构造一个匿名对象并插入至map容器
	m.insert(pair<int, double> (1,1.1));
	m.insert(pair<int, double>(2, 2.2));
	m.insert(pair<int, double>(3, 3.3));
	m.insert(pair<int, double>(4, 4.4));
	//调用函数模板，让函数模板自己去推断类型最终返回已经构造的pair对象
	m.insert(make_pair(1, 1.1));
	
	//访问每一个map容器中元素的first和second的值
	for (map<int, double>::iterator it = m.begin(); it != m.end(); it++)
		cout << it->first << ": " << it->second << endl;
		//map是一个天然的有序容器，也就是说元素存在进map后就会是有序的
}

对于这两种插入元素的方式如果觉得不能理解的话这里博主准备了两份源码，可以帮助读者理解

make_pair源码

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
 {
   return ( pair<T1,T2>(x,y) );
 }

pair源码

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

考察map成员函数使用，将每一种水果存放到map容器后将水果用“{}”打包起来，最后再把容器中的水果吃掉

void func() 
{
	map<int, string> m;
	m.insert(pair<int, string>(4, "黄皮"));
	m.insert(pair<int, string>(2, "西瓜"));
	m.insert(pair<int, string>(1, "香蕉"));
	m.insert(make_pair(3, "苹果"));
	//使用迭代器遍历map容器
	for (map<int, string>::iterator it = m.begin(); it != m.end(); it++)
		cout << it->first << "： "  << it->second<<endl;
	
	cout << endl;

	//修改map元素结点中second的值
	for (auto it = m.begin(); it != m.end(); it++)  
	{
		it->second.insert(0,"{");
		it->second += "}";
	}

	for (auto& ref : m) cout << ref.first << ": " << ref.second << endl;
	cout << endl;
	//通过key值找到该结点，将key所对应的节点值的second修改
	for (auto & ref : m) 
	{
		auto ret = m.find(ref.first);
		if (ret != m.end())
		{
			string& s = ret->second;
			s.insert(s.size() - 1, "被吃掉");
		}
	}
	for (auto& ref : m) cout << ref.first << ": " << ref.second << endl;
	
}

insert细节谈

//insert 的返回值pair在这里有什么作用呢？
pair<iterator,bool> insert (const value_type& val);

结合官方文档细读

总结：
insert接口函数会返回一个pair对象，其成员pair::first被设为指向新插入元素的迭代器，如果使用insert向map容器中插入一个key值的元素，如果这个key已经存在于容器中，那么pair::second将被设置为false，如果容器中并不存在和新插入元素相同的key值那么pair::second将被设置为true

举例应用场景体现pair对象的作用

统计每一种水果出现的次数

void func2() 
{
	string arr[] = { "西瓜","葡萄","西瓜","西瓜","葡萄","橘子","西瓜" };
	map<string, int> m;
	for (auto &ref : arr) 
	{
		auto ret = m.insert(make_pair(ref, 1));
		//insert无论是否能够插入成功都会返回一个pair，而pair对象中的成
		//员pair::first指向的就是这个结点的指针，如果插入成功则
		//pair::second会被设置为true，如果插入失败pair::second设置为false
		
		if (ret.second == false) ret.first->second++;
		//插入失败代表容器中已经存在该元素，那么就对已经存在的水果计数++
	}
	for (auto& ref : m) cout << ref.first << "：" << ref.second << endl;
}	

map::operator[]的理解是在建立在理解pair之后的，既然我们已经理解了pair后那么就再来理解operator[ ]，让我们对map的理解更全一步

map::operator[]细节谈

mapped_type& operator[] (const key_type& k)
{
   return (*((this->insert(make_pair(k,mapped_type()))).first)).second
}

insert(make_pair(k,mapped_type()) 会返回一个pair对象，pair::first存放的是结点的迭代器，*((this->insert(make_pair(k,mapped_type())) 会对pair::first解引用，最后访问结点中的second成员

operator[]扩展学习

看了operator[]的源码后我们知道他会在内部调用insert函数，会返回一个pair::first成员存放的是结点的迭代器，最后会返回second的引用使其可以被修改，那么我们可以看看这种写法

void func3()
{
	char ch = '0';
	string arr[] = { "西瓜","葡萄","西瓜","西瓜","葡萄","橘子","西瓜" };
	map<string, string> m;  //创建一个空容器，
	for (auto &ref : arr) 
	{
		m[ref] = "";   //使用operator[]相当于插入一个key值元素并修改second的值
	}
	for (auto& ref : m) cout << ref.first << "：" << ref.second << endl;
}

map容器的综合应用

通过统计每一种水果出现的次数，再比较水果出现的次数排降序

//使用vector容器 + sort函数  
struct MapitComper
{
	//比较实际传递的迭代器指向的second值
	bool operator()(map<string, int>::iterator x, map<string, int>::iterator y) 
	{
		return x->second > y->second;
	}
	
};

//对map中的值排序使用vector + sort
void func4() 
{
	string arr[] = { "西瓜","葡萄","西瓜","西瓜","葡萄","橘子","西瓜" };
	//创建一个空容器
	map<string, int> m;  
	//统计每一种水果出现的次数
	for (auto& ref : arr) m[ref]++; 

	//创建vector容器，容器中存放的元素类型是map<string, int>::iterator
	vector<map<string, int>::iterator> v; 
	map<string, int>::iterator it = m.begin();
	while (it != m.end()) 
	{
		v.push_back(it); //将map容器中的每一个元素的迭代器存放进vector中
		it++;
	}
	//将vector容器中的值根据second排降序
	sort(v.begin(), v.end(), MapitComper());
	for (auto& ref : v) cout << ref->first << "：" << ref->second << endl;
}

利用map排序

//利用map排序，由于map底层是一颗红黑树所以他是天然的有序
void func5()
{
	string arr[] = { "西瓜","葡萄","西瓜","西瓜","葡萄","橘子","西瓜" };
	//创建一个空容器
	map<string, int> m;
	for (auto& ref : arr) m[ref]++;  //统计水果出现的次数

	map<int, string, greater<int>> sortmap;
	//遍历map容器将second的位置放置再key的位置，将first值放在second的位置，达到以second值排成降序的目的
	for (auto& ref : m) sortmap.insert(make_pair(ref.second, ref.first));  
	//遍历sortmap
	for (auto& ref : sortmap) cout << ref.first << "：" << ref.second << endl;
}

sortmap.insert(make_pair(ref.second, ref.first)); 先看这段插入代码，我们都知道make_pair会返回一个临时对象，是一种拷贝行为，为了减少拷贝这种我们还是往容器中插入迭代器吧，那么既然是只根据key来排序，我们下一步就是要set容器

使用set容器排序

struct MapItCompare
{
	//比较实际传递的迭代器中的second值，值得一提的是如果是再vs2019自己写仿函数的话需要加上const，因为2019下会对这块检查
	bool operator()( map<string, int>::iterator x,  map<string, int>::iterator y)const 
	{
		return x->second < y->second;
	}

};

//利用set排序
void func6()
{
	string arr[] = { "西瓜","葡萄","西瓜","西瓜","葡萄","橘子","西瓜" };
	//创建一个空容器
	map<string, int> m;
	for (auto& ref : arr) m[ref]++; //统计水果出现的次数
	set<map<string, int>::iterator, MapItCompare> sortset;
	map<string, int>::iterator it = m.begin();
	while (it != m.end())
	{
		sortset.insert(it);
		//set同样也是一个天然的有序容器，插入过程种会根据key值大大小放到合适的位置
		it++;
	}
	//遍历set容器
	for (auto& ref : sortset) cout << ref->first << "：" << ref->second << endl;
}

使用优先级队列逆序输出达到有序目的

利用优先级队列建大堆依次取堆顶数据，达到倒序输出目的

void func7() 
{
	string arr[] = { "西瓜","葡萄","西瓜","西瓜","葡萄","橘子","西瓜" };
	map<string, int> m;
	for (auto& ref : arr) m[ref]++; //统计水果出现的次数

	typedef map<string, int>::iterator M_IT; //typdef
	
	priority_queue<M_IT, vector<M_IT>, MapItCompare> pq;
	M_IT it = m.begin();
	while (it != m.end()) //循环将指向map元素的迭代器存放进优先级队列
	{
		pq.push(it);
		it++;
	}
	while (!pq.empty()) //将优先级队列的堆顶迭代器取出，读取该迭代器所指向元素的成员值
	{
		cout << pq.top()->first << "：" << pq.top()->second << endl;
		pq.pop();
	}
}