关联式容器

我们已经学了 string，vector，list，deque，forward_list，这些统称序列性容器，是线性序列结构，他们存的是元素本身，那什么是关联式容器呢？他们与序列容器有何区别？
关联式容器：也是用来存数据的，与序列容器不同的是存的是<key,value>键值对，检索数据效率更高。

键值对

🚩表示一种对应关系的结构，包含两个成员变量 key和value，key代表键值，value代表key对应的信息。
例如：英汉互译字典，英语对应key值，查到key就可以看value (中文)。
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)
	{ } 
};

用法示例：

int main()
{
	pair<int, double> p1;
	std::cout << p1.first << p1.second << std::endl;
	pair<std::string, int> p2("hello", 3);
	std::cout << p2.first << p2.second << std::endl;
	return 0;
}

树形结构的关联式容器

STL实现了两种不同结构的管理式容器，树形和哈希型，树形管理式容器主要有4种，set，map，multiset，multimap，他们底层都是红黑树，（以后讲），容器元素是有序的序列

set

set文档
介绍：
1，set是按一定次序存储数据的容器，默认是升序
2，与map不同，map存储的是真正的键值对<key,value>,set只存value，但底层实现是<value,value>,
所以set插入元素时不用构造键值对，只插入value就行
3，set的值不能修改，里面存储的元素都是const，但是可以插入删除
4，set存储的元素不能重复。可以用来去重
5，查找元素的时间复杂度 log2n
🚩使用：
构造：

函数	说明
❤set(const Compare& comp=Compare(),Allocator& alloc =Alloccator())	空构造
❤set(InputIterator first,InputIterator second,Compare& comp=Compare(),Allocator& alloc=Alloctor())	(first,last)区间构造
❤set(const set<key,Compare,Allocator>& x)	拷贝构造

iterator	说明
⭐iterator begin()/end()	分别获得第一个数据位置，最后一个数据下一个位置的 iterator
⭐reverse_iterator rbegin()/rend()	分别获得最后一个，第一个前面一个位置的迭代器
const_iterator cbegin()/cend() const	第一个位置和最后一个数据下一个位置的迭代器
const_reverse_iterator crbegin()/crend() const	最后一个，第一个前面一个位置的迭代器

函数	说明
bool empty() const	判断set是否为空
size_type size() const	判断set元素个数
💪pair<iterator,bool> insert (const value_type x)	set插入x，实际插入的是<x,x>构成的键值对，如果插入成功返回<插入元素位置，true>，如果元素已存在则失败 <x在set位置，false>
void erase(iterator position)	删除position位置上的元素
💪size_type erase(const key_type& x)	删除x元素，返回删除元素个数
void erase(iterator first,iterator last)	删除 (first,last) 区间元素
void swap(set<Key,Compare,Allocator>& st)	两个set交换
void clear()	清空set
iterator find(const key_type& x) const	找x元素，返回x元素位置
size_type count(const key_type& x) const	返回set中x元素数量

使用样例：

#include <iostream>
#include <set>
using namespace std;

int main()
{

	set<int> st;
	int a[] = { 5,2,1,1,1,3,3,7,6 };
	for (auto& e : a)
	{
		st.insert(e);
	}
	cout << "st: ";
	for (auto& e : st)
	{
		cout << e << " ";
	}
	cout << endl;
	set<int> stt(st);
	stt.erase(1);
	stt.erase(2);
	stt.swap(st);
	cout << "st: ";
	for (auto e : st)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "stt：";
	for (auto e : stt)
	{
		cout << e << " ";
	}
	return 0;
}

st: 1 2 3 5 6 7
st: 3 5 6 7
stt：1 2 3 5 6 7

map

map文档
介绍：
1，map是关联容器，按照一定次序（key决定）存储<key,value>组合元素。
2，map通过键值查找一般比unordered_map慢，但是可以直接迭代得到有序序列
3，map可以通过下标查找value
4，map次序只由key值决定，默认升序
5，map中key值唯一
6，查找效率log2_N
map函数大多都与set类似，除了下标访问

mapped_type& operator[](const key_type& k)	返回key值对应的value

有个不常用函数at() , 和[]函数一样，不过当key值不存在时，访问key时会默认构造key和value键值对然后插入，at直接抛异常

用法示例：

#include <iostream>
#include <map>
using namespace std;
int main()
{
	map<string, string> mp;
	mp.insert(pair<string, string>("apple", "苹果"));
	mp.insert(make_pair("peach","桃子"));
	mp["banana"] = "香蕉";
	//mp.at("pear")="pear";
	for (auto& e : mp)
	{
		cout << e.first <<" "<< e.second<<endl;
	}
	cout << mp.count("watermelon")<<endl;
	return 0;
}

apple 苹果
banana 香蕉
peach 桃子
0

两种插入方式，一般用函数make_pair()，
banana mp中没有，直接插入了，

multiset，multimap

multiset与set唯一区别就是可以重复，可以用来排序，
multimap与map区别也是可以重复，另外下标不能用了

例题：

前k个高频单词

class Solution {
public:
struct greater
{
    bool operator()(const pair<string,int>& a,const pair<string,int>& b)
    {
        if(a.second!=b.second)
        return a.second>b.second;
        else
        {
            return a.first<b.first;
        }
    }
};
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> mp;
        for(auto& e: words)
        {
            mp[e]++;
        }
        vector<pair<string,int>> vc;
        for(auto& e:mp)
        {
            vc.push_back(e);
        }
        sort(vc.begin(),vc.end(),greater());
        vector<string> v;
        for(int i=0;i<k;i++)
        {
            v.push_back(vc[i].first);
        }
        return v;
    }
};

单词识别

#include <functional>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct compare
{
    bool operator()(const pair<string,int>& a,const pair<string,int>& b)
    {
        if(a.second!=b.second)
        return a.second>b.second;
        else 
        {
            return a.first<b.first;
        }
    }
};
int main()
{
    string s;
    map<string,int> mp;
    while(cin>>s)
    {
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='.')s.pop_back();
            s[i]=tolower(s[i]);
        }
        mp[s]++;
    }
    vector<pair<string,int>> vc;
    for(auto& e:mp)
    {
        vc.push_back(e);
    }
    sort(vc.begin(),vc.end(),compare());
    for(auto& it:vc)
    {
        cout<<it.first<<":"<<it.second<<endl;
    }
    return 0;
}