C++——map和set的基本使用

一，关联式容器

二，键值对

三，set的使用

3.1 set介绍

3.2 set的插入和删除

3.3 set的pair

3.4 multiset

四，map的使用

4.1 map介绍

4.2 map实现简易字典

4.3 map实现统计次数

4.4 map的[]

五，使用map或set解决部分OJ题

5.1 复杂链表的复制

5.2 前K个高频单词

5.2.1 解法一：使用sort算法排序

5.2.2 使用multimap解决

5.2.3 使用set的特性加仿函数解决

5.3 两个数组的交集

一，关联式容器

在前面的文章里，我们以及接触过STL的部分容器，包括：vector，list，deque等，这些容器同称为序列式容器，因为其底层为线性序列的数据结构，里面存的是元素本身。

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

二，键值对

键值对是用来表示居于一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value。key代表监事，value表示与key对应的信息。比如建一个英汉互译的字典，所以这个字典中，英语单词与其含义是一一对应的关系，即通过该单词可以在字典中找到对应的中文含义

下面是STL中关于键值对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){}
};

三，set的使用

3.1 set介绍

①set是按照一定次序存储元素的容器

②在set中，元素的value也标识它（value就是key，类型为T），并且每个value必须是唯一的

③在内部，set中的元素总是按照其内部比较对象所指示的特点排序准则进行排序

④set在底层是用红黑树实现的

3.2 set的插入和删除

void test_set1()
{//set<int> s = {1,2,1,6,3,8,5};//列表初始化int a[] = { 1,2,1,6,3,8,5 };set<int> s(a, a + sizeof(a) / sizeof(int));//set支持通过迭代器区间初始化//set<int,greater<int>> s(a, a + sizeof(a) / sizeof(int));可以自行控制这颗树//set间接完成了  排序+去重，因为set底层是一个搜索二叉树set<int>::iterator it = s.begin();while (it != s.end()){//搜索树不允许修改key，可能会破坏搜索的规则//*it += 1;cout << *it << " ";it++;}cout << endl;//删除//方法1s.erase(1);for (auto e : s){cout << e << " ";}cout << endl;//方法2set<int>::iterator pos = s.find(2);if (pos != s.end())//判断有没有找到{s.erase(pos);}for (auto e : s){cout << e << " ";}cout << endl;//count()返回数据个数，但由于set默认去重只能返回0或1，所以一般用作判断该数是否存在cout << s.count(3) << endl;  //判断在不在，并且返回个数cout << s.count(30) << endl;
}

void test_set2()
{set<int> myset;set<int>::iterator itlow, itup;for (int i = 0; i < 10; i++)myset.insert(i * 10);  //10 20 30 40 50 60 70 80 90itlow = myset.lower_bound(25);//返回的是>=val的第一个值，此处返回30itup = myset.upper_bound(60);//返回的是>val的第一个值，此处返回70cout << "[" << *itlow << "," << *itup << "]" << endl;myset.erase(itlow, itup);//删除这两个值所代表的范围之间的数
}

3.3 set的pair

void test_set3()//pair用来记录一对数据
{set<int> myset;for (int i = 1; i <= 5; i++)myset.insert(i * 10);//10 20 30 40 50 pair<set<int>::const_iterator, set<int>::const_iterator> ret;ret = myset.equal_range(40);cout << "the lower bound points to : " << *ret.first << endl;cout << "the upper bound points to : " << *ret.second << endl;
}

3.4 multiset

void test_multiset()//multiset与set不一样的是，multiset允许有重复值
{int a[] = { 3,1,2,1,6,3,8,3,5,3,1 };multiset<int> s(a, a + sizeof(a) / sizeof(int));for (auto e : s){cout << e << " ";}cout << endl;cout << s.count(1) << endl;//这里的count就是记录个数了auto pos = s.find(3);//find时如果有多个值，返回中序的第一个位置,如果想找第二个3，把迭代器++一下就是第二个3while (pos != s.end()){cout << *pos << " ";++pos;}cout << endl;s.erase(3);//如果要删除的值有多个，删除所有的值for (auto e : s){cout << e << " ";}
}

四，map的使用

4.1 map介绍

①map是关联容器，它按照特点的次序（按照key来比较）存储由简直key和value组合而成的元素

②在map中，键值key通常用于排序和唯一的标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair

③在内部，map中的元素总是按照键值key进行比较排序的

④map支持下标访问符，即在[]中放入key，就可以找到与key对应的value