set和map的使用"/>
C++：set和map的使用
set和map的使用
- 1.关联式容器
- 2.key模型和key_value模型
- 3.set
- 3.1一些注意点
- 3.2set的使用
- 3.3习题
- 4.multiset
- 5.map
- 5.1一些注意点
- 5.2map的使用
- 5.3习题
- 6.multimap
1.关联式容器
序列式容器：比如我们之前讲的vector、string、list等均为序列式容器，特点是按元素顺序来保存和访问。
关联式容器：比如本次讲的map和set，和序列式容器不同，其依靠键值来保存和访问，数据检索效率闭序列式容器高。
PS：本文只讲使用，set和map底层是一颗平衡二叉搜索树。
2.key模型和key_value模型
（1）key模型：主要解决在不在的问题？比如现在录入人脸信息，用户登录的判断就可以采用key模型，set其实就是一个key模型。
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;int main() {set<string> s;vector<string> v = {"张三", "李四", "王五", "赵六"};for (auto e : v) s.insert(e); //还没讲接口，这里的作用是录入信息string input;while (cin >> input){if (s.count(input)) //这里的作用是在set中查找input是否存在{cout << "存在，查找成功" << endl;}else{cout << "不存在" << endl;}}return 0;
}
（2）key_value模型：和key模型最大的不同就是存储，key模型只存一个键值，而key_value模型存储的是一个键值对。除了可以解决在不在的问题，还可以通过键值找到对应信息，map其实就是一个key_value模型。
键值对：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量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){}
};int main() {//还没讲接口，知道大概意思就行map<string, string> mapTranslation; //就以英汉翻译词典为例子//录入词典的信息mapTranslation.insert(make_pair("left", "左边"));mapTranslation.insert(make_pair("right", "右边"));mapTranslation.insert(make_pair("sort", "排序"));mapTranslation.insert(make_pair("father", "父亲"));string input;while (cin >> input){if (mapTranslation.count(input)) //这里也是查找在不在{cout << "中文为: " << mapTranslation[input] << endl; //这里拿到value}else{cout << "词典无记录" << endl;}}return 0;
}
3.set
3.1一些注意点
- set不允许键值冗余，比如插入3后不能再插入3。拒绝键值冗余，本就是二叉搜索树的定义。故set中不会有重复的元素，可以利用这一点对数据进行去重。
- set利用迭代器遍历元素，可以得到一个有序序列，可利用这一点对数据进行排序。原理是中序遍历二叉搜索树可以得到有序序列。
- set元素默认按小于比较，即默认升序。
- set不允许修改元素，如果支持修改会无法维护搜索二叉树的结构。
- set中查找某个元素，时间复杂度为：logN
3.2set的使用
（1）模板参数
（2）构造
| 函数声明 | 功能 |
|---|---|
| set (const Compare& comp = Compare(), const Allocator& = Allocator()) | 空构造 |
| set (InputIterator first, InputIterator last, 后面和空构造一样) | 迭代器区间构造 |
| set (const set& x) | 拷贝构造 |
（3）迭代器
| 函数声明 | 功能 |
|---|---|
| iterator begin() | 返回set中起始位置元素的迭代器 |
| iterator end() | 返回set中最后一个元素后面的迭代器 |
| reverse_iterator rbegin() | 反向迭代器，返回end() |
| reverse_iterator rend() | 反向迭代器，返回begin()的前一个位置 |
（4）容量
| 函数声明 | 功能 |
|---|---|
| bool empty ( ) const | 检测set是否为空，空返回true，否则返回false |
| size_type size() const | 返回set中有效元素的个数 |
（5）增加、删除、查找
| 函数声明 | 功能 |
|---|---|
| pair<iterator,bool> insert ( const value_type& x ) | 在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>；如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false> |
| void erase ( iterator position) | 删除对应position位置的元素 |
| size_type erase ( const key_type& x ) | 删除set中值为x的元素，返回删除的元素的个数 |
| void erase ( iterator first, iterator last ) | 删除set中[first, last)区间中的元素 |
| iterator find ( const key_type& x ) const | 返回set中值为x的元素的迭代器，不存在返回end() |
| size_type count ( const key_type& x ) const | 返回set中值为x的元素的个数 |
| void swap (set& sp ) | 交换两个set中的元素 |
| void clear ( ) | 将set中的元素清空 |
几个注意点：
- insert的返回值希望大家记一下，方便大家理解map的核心接口。
- 判断键值在不在set中有两种方法：
第一种是find(key)，依据返回值判断，是end()代表不在，否则存在。
第二种是count(key)，如果存在返回非0，不存在返回0，也可以进行判断。
选择习惯的方式即可。
3.3习题
链接：两个数组交集
题目要求：
代码加解析：
//主要思想是利用set进行去重
//（1）先用set1存储nums1的值，比如[1,2,2,1]->[1,2]（set去重）
//（2）定义一个set2,如果nums2的值在set1中可以找到，就插入set2中
//注意：因为nums2中可能存在多个相同值，故用set可以进行去重
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> set_exist;set<int> result;for(auto e : nums1){set_exist.insert(e);}for(auto e : nums2){if(set_exist.find(e) != set_exist.end()) //如果存在{result.insert(e);}}return vector<int>(result.begin(), result.end());}
};//这个题也可以先去重加排序
//交集：（1）不相等小的加加；（2）相等是交集，同时加加
//差集：（1）不相等小的是差集，小的加加；（2）相等都不是差集，同时加加 （3）一方走完，剩下的都是差集
4.multiset
multiset和set使用几乎一致，唯一的不同就是允许键值冗余。
- 迭代器遍历依然可以得到有序序列
- count()接口对multiset非常重要
- multiset的find()查找返回的是中序遍历的第一个元素。
- multiset可以对存在重复元素的序列排序。
5.map
5.1一些注意点
- 在内部，map中的元素总是按照键值key进行比较排序的，和value无关。
- map不允许键值冗余，map中的键值对是唯一的。
- 利用迭代器遍历可以得到有序序列，不过是按key来排序。
- map不允许修改key，但可以修改value。支持修改键值会无法维护二叉搜索树结构。
- map中查找某个元素，时间复杂度为：logN
5.2map的使用
（1）模板参数
（2）构造
| 函数声明 | 功能 |
|---|---|
| map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()) | 空构造 |
| map (InputIterator first, InputIterator last, 后面和空构造一样) | 迭代器区间构造 |
| map (const map& x) | 拷贝构造 |
（3）迭代器
| 函数声明 | 功能 |
|---|---|
| iterator begin() | 返回set中起始位置元素的迭代器 |
| iterator end() | 返回set中最后一个元素后面的迭代器 |
| reverse_iterator rbegin() | 反向迭代器，返回end() |
| reverse_iterator rend() | 反向迭代器，返回begin()的前一个位置 |
（4）容量
| 函数声明 | 功能 |
|---|---|
| bool empty ( ) const | 检测set是否为空，空返回true，否则返回false |
| size_type size() const | 返回set中有效元素的个数 |
（5）增加、删除、修改、查找
| 函数声明 | 功能 |
|---|---|
| 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 ) | 删除map中键值为x的元素，返回删除的元素的个数 |
| void erase ( iterator first, iterator last ) | 删除map中[first, last)区间中的元素 |
| iterator find ( const key_type& x ) const | 返回map中键值为x的元素的迭代器，不存在返回end() |
| size_type count ( const key_type& x ) const | 返回map中键值为x的元素的个数 |
| mapped_type& operator[] (const key_type& k) （非常重要） | 返回key对应的value |
| void swap ( map& mp ) | 交换两个map中的元素 |
| void clear ( ) | 将map中的元素清空 |
几个注意点：
- 这里的接口中最重要的就是operator[]，因为[]不仅可以访问value，还可以进行插入。
operator[]的原理是： 用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中如果key已经存在，插入失败，如果不存在就进行插入。insert返回的键值对第一个元素就是元素对应的迭代器，operator[]函数通过迭代器最后返回键值对中的value的引用。 - 对map的迭代器解引用得到是键值对结构体，设迭代器为x，拿value的方式有两种。(*x).second或x->second。
- map判断键值对在不在的方式和前面set一致。
5.3习题
链接：前k个高频单词
题目要求：
代码加解析：
//这里的核心思路：
//（1）用map统计每个字符串出现次数
//（2）对键值对进行排序，出现次数相同的要按字典序来排
// 因为键值对自带的比较规则是只按key排序的，所以我们需要自定义排序（比较方法）
//其实只是访问的话unordered_map更加快速，但unordered_map迭代器遍历无法保证有序
class compare
{
public:bool operator()(pair<string,int> p1, pair<string,int> p2) const{if(p1.second == p2.second){//出现次数相同，按字典序排return p1.first < p2.first;}else{//要排降序，按大于排return p1.second > p2.second;}}
};
class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> count_map; //用map统计for(int i = 0; i < words.size(); i++){count_map[words[i]] ++;}//排序（降序）vector<pair<string,int>> result(count_map.begin(), count_map.end());;sort(result.begin(),result.end(),compare());vector<string> ret;for(int i = 0; i < k; i++)ret.push_back(result[i].first);return ret;}
};
//也可以利用set进行排序
// set<pair<string, int>, compare> sort_set(count_map.begin(), count_map.end());
// vector<string> ret;
// auto it = sort_set.begin();
// while(k--)
// {
// ret.push_back(it->first);
// it++;
// }
// return ret;
6.multimap
multimap和map使用几乎一致，最大的不同就是允许键值冗余。
- multimap没有支持operator[]。
原因是存在多个同键值的键值对，不知道取谁的value。 - 迭代器遍历依然可以得到有序序列。
- count()接口对multimap非常重要。
- multimap的find()查找返回的是中序遍历的第一个元素。
- multimap可以对存在重复元素的序列排序。
更多推荐
C++：set和map的使用
发布评论