开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> C++STL之map和set的使用 -> 正文阅读

[数据结构与算法]C++STL之map和set的使用

map和set

set

set的使用

set的插入

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

void test_set1()
{
	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(7);
}
int main()
{
	test_set1();
	return 0;
}

set的遍历

//遍历：排序+去重
set<int>::iterator it = s.begin();
while (it != s.end())
{
    cout << *it << " ";
    ++it;
}
cout << endl;
//范围for遍历
for (auto e : s)
{
    cout << e << " ";
}
cout << endl;
set<int> copy(s);//拷贝构造
for (auto e : s)
{
    cout << e << " ";
}

set的find接口

#include<set>
void test_set()
{
    set<int> s;
    s.insert(4);
    s.insert(2);
    s.insert(3);
    s.insert(6);
    s.insert(1);
    s.insert(8); 
    set<int>::iterator ret = s.find(4);//  O(logN)
    //这两个有效率的区别
    auto ret = find(s.begin(),s.end(),4);//这个是暴力查找，在一段迭代器区间里进行查找 O(N)
}

find我们可以用算法里面的find接口，也可以用set提供的find接口：

set<int>::iterator ret = s.find(4);//O(logN)
    //这两个有效率的区别
auto ret = find(s.begin(),s.end(),4);//这个是暴力查找，在一段迭代器区间里进行查找 O(N)

但是这两个有效率的区别：set的底层是二叉搜索树的性质，时间复杂度为O(logN)，而算法当中的find是在一段迭代器区间暴力查找，在一段迭代器区间里进行查找，时间复杂度O(N)

set的erase接口

删除接口可以传迭代器撒谎才能胡，也可以传val，也可以传迭代器区间

```cpp
#include
void test_set()
{
set s;
s.insert(4);
s.insert(2);
s.insert(3);
s.insert(6);
s.insert(1);
s.insert(8);
set::iterator it = s.begin();
while(it!=s.end())
{
cout<<*it<<" “;
++it;
}
cout<<endl;
set::iterator ret = s.find(4);// O(logN)
if(ret != s.end())
{
s.erase(ret);
}
//也可以这样删除
s.erase(6);
s.erase(60);
for(auto e:s)
{
cout<< e <<” ";
}
cout<<endl;
}
int main()
{
test_set();
return 0;
}

map的介绍

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

键值对

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

map

map的使用

map的模板参数

key: 键值对中key的类型
T：键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
注意：在使用map时，需要包含头文件。

map的插入

void test_map1
{
    map<int,int> m;
    m.insert(pair<int,int>(1,1));
    m.insert(pair<int,int>(2,2));
    m.insert(pair<int,int>(3,3));
}

我们在插入时需要这样插入，为什么呢？

我们可以看到insert函数有一个参数，类型是value_type，value_type被typedef成了pair，用键值对来存储数据，我们也可以这样：

m.insert(make_pair(4,4));//函数模板去构造匿名对象返回，这个不需要写模板参数，自动去推

make_pair的实现：

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

那么为什么要将key和value封装起来呢？我们看下面的代码进行解释：

void test_map1
{
    map<int,int> m;
    m.insert(pair<int,int>(1,1));
    m.insert(pair<int,int>(2,2));
    m.insert(pair<int,int>(3,3));
    
    map<int,int>::iterator it = m.begin();
    while(it != m.end())
    {
        cout<<*it<<" ";//这里编译不过，这里如果这样的话需要返回两个值key和value，而C++不支持返回两个值，要返回两个值就需要构成一个结构来返回
        ++it;
    }
    cout<<endl;
}

*cout<<it<<endl；这里编译不过，这里如果这样的话需要返回两个值key和value，而C++不支持返回两个值，要返回两个值就需要构成一个结构来返回

所以需要这样用：

void test_map1()
{
    map<int,int> m;
    m.insert(pair<int,int>(1,1));
    m.insert(pair<int,int>(2,2));
    m.insert(pair<int,int>(3,3));
    
    map<int,int>::iterator it = m.begin();
    while(it != m.end())
    {
        //cout<<(*it).first << ":" << (*it).second << endl;
        //operator* 返回的是节点中值的引用
        cout<<it->first<<":"<<it->second<<endl;//这里为了可读性省略了一个箭头
        //operator-> 返回的是节点中值的指针，也就是pair<k,v>*
        ++it;
    }
    cout<<endl;
}

也支持范围for遍历：

void test_map1()
{
    map<int,int> m;
    m.insert(pair<int,int>(1,1));
    m.insert(pair<int,int>(2,2));
    m.insert(pair<int,int>(3,3));
  	for(auto& e:m)
    {
        cout<<e.first<<":"<<e.second<<endl;
    }
    cout<<endl;
}

简单英文翻译字典

#include<map>
void test_map2()
{
    map<string,string> dict;
    dict.insert(pair<string,string>("sort","排序"));
    dict.insert(make_pair("left","左边"));
    dict.insert(make_pair("string","字符串"));
    dict.insert(make_pair("right","右边"));
    dict.insert(make_pair("bed","床"));
    map<string,string>::iterator it = dict.begin();
    while(it !=dict.end())
    {
        //it.operator*()，不能返回两个值，这里返回的是类对象
        //cout<<(*it).first<<" "<<(*it).second<<endl;//报错
        //it.operator->()，返回类对象指针
        cout<<it->first<<" "<<it->second<<endl;
        ++it;
    }
    
}
int main()
{
    test_map2();
    return 0;
}

统计字符串个数

void test_map3()
{
    string str[] = {"sort","sort","tree","insert","sort","tree","sort","test"};
    map<string,int> countMap;//统计字符串个数
    for(auto& e:str)
    {
        auto ret = countMap.fin1d(e);//返回一个迭代器
        if(ret == countMap.end())
        {
            //如果不存在，则插入
        	countMap.insert(make_pair(e,1));
            //countMap.insert(pair<>(e,1));
        }
        else
        {
            //如果存在，则次数++
            //(*ret).second++;
            ret->second++;
        }
    }
    
    for(auto& kv:countMap)
    {
        cout<<kv.first<<" "<<kv.second<<endl;
    }
}

可以看到次数已经成功统计出来

统计次数的方式二：

正常来说如果insert插入成功了返回true，已经存在此时插入失败了返回false，但是我们可以看到insert的返回值是一个pair：

返回值是pair，其成员pair::first被设为一个迭代器，指向新插入的元素否则指向map中具有相等key的元素，如果插入了新元素，则将该对中的第二个元素pair::second设置为true;否则如果已经存在相等的key，则将其设置为false。

void test_map4()
{
    string str[] = { "sort","sort","tree","insert","sort","tree","sort","test" };
    map<string, int> countMap;
    for (const auto& e : str)
    {
        //先插入，如果str在map中，insert会返回str所在的节点的迭代器，++次数即可
        pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(e, 1));
        //auto ret = countMap.insert(make_pair(e, 1));
        if (ret.second == false)
        {
            //说明插入失败了，之前已经插入过了
            ret.first->second++;//ret.first是指向相同key的那个元素的迭代器,ret是insert返回的pair
        }
    }
    map<string, int>::iterator it = countMap.begin();
    while (it != countMap.end())
    {
        cout << it->first << " " << it->second << endl;
        ++it;
    }
}

operator[]的使用

统计次数的方式三(operator[])：

operator[]的实现：

mapped_type& operator[](const key_type& k)
{
	return (*((this->insert(make_pair(k,mapped_type()))).first)).second;//插入时的匿名对象默认值为0
}

operator[]的实现进行简化，也可以这样实现：

mapped_type& operator[](const key_type& k)
{
    pair<iterator,bool> ret = insert(make_pair(k,mapped_type()));//插入时的匿名对象默认值为0
	return ret.first->second;
}

这里也分两种情况：

k在map中，insert插入失败，因为k已经有了，insert返回的pair会带出k在map中存储节点的迭代器，通过这个迭代器，我们可以拿到k对应的value值，进行返回。
k不在map中，insert进行插入，插入的值是pair<k,value()>，insert返回新插入值节点的迭代器，通过这个迭代器，我们可以拿到k对应的value值，进行返回。

总结map的operator[]特征：

k不存在时，插入默认构造函数生成缺省值的value的pair<k,v()>
k存在时，返回k对应的value值

void test_map5()
{
    string str[] = { "sort","sort","tree","insert","sort","tree","sort","test" };
    map<string,int> countMap;
    //[]的用法
    for(const auto& e:str)
    {
        countMap[e]++;//countMap[]返回的是value
    }
    for(const auto& kv:countMap)
    {
        cout<<kv.first<<" "<<kv.second<<endl;
    }
}

1、如果k不在map中，先插入<k,V()>，返回新插入节点中V对象的引用

2、如果k已经在map中，返回k所在节点中对应V对象的引用

关于[]的一些扩展学习：

void test_map6()
{
    map<string,string> dict;
    dict.insert(make_pair("sort","排序"));
    dict["left"] = "左边";//插入+修改
    dict["insert"];//插入
    dict["insert"] = "插入";//已经存在所以只是修改
    dict["left"] = "左边、剩余";//已经存在所以只是修改
}

第一个是插入+修改，因为刚开始没有则插入，[]返回的是value，所以赋值相当于将他修改了，第二个只是插入，第三个只是修改，因为insert已经存在了就没有再插入只是修改，第四个也已经存在，所以只是修改

注意：

key不能被修改，但是value是可以被修改的：

#include<map>
void test_map()
{
    map<string,string> dict;
    dict.insert(pair<string,string>("sort","排序"));
    dict.insert(make_pair("left","左边"));
    dict.insert(make_pair("string","字符串"));
    dict.insert(make_pair("right","右边"));
    dict.insert(make_pair("bed","床"));
    map<string,string>::iterator it = dict.begin();
    while(it !=dict.end())
    {
        //it->first = "aaa";//error，key不能修改
        it->second.insert(0, "{");
        it->second += "}";
        cout<<it->first<<" "<<it->second<<endl;
        ++it;
    }
    
}
int main()
{
    test_map();
    return 0;
}

可以看到key值是不能修改的

value值是可以修改的：

比如left除了左边的意思还有剩余的意思，我们就可以将left的值修改：

auto ret = dict.find("left");
if(ret != dict.end())
{
    //ret->second.insert(ret->second.size()-1,"、剩余");
    //可读性优化技巧
    string& str = ret->second;
    str.insert(str.size()-1,"、剩余");
}
it = dict.begin();
while(it !=dict.end())
{
    cout<<it->first<<" "<<it->second<<endl;
    ++it;
}
cout<<endl;

我们下面给定一个字符串数组，统计每个单词的次数，然后找出出现次数最频繁的三个单词：

1、统计次数 2、找出出现次数最频繁的三个单词

void test_map7()
{
    //1、统计次数  2、找出出现次数最频繁的三个单词
    string str[] = { "sort","sort","tree","insert","sort","tree","sort","test" };
    map<string, int> countMap;
    //[]的用法
    for (const auto& e : str)
    {
        countMap[e]++;//countMap返回的是value
    }
    
}

这里有四种排序方法：

利用vector排序：

struct MapItCompare
{
    bool operator()(map<string, int>::iterator x, map<string, int>::iterator y)
    {
        return x->second > y->second;
    }
};
//对所有单词次数排序的思路
//vector<pair<string,int>> v;
vector<map<string, int>::iterator> v;
map<string, int>::iterator countMapIt = countMap.begin();//countMapIt是一个指向pair的迭代器
while (countMapIt != countMap.end())
{
    v.push_back(countMapIt);
    countMapIt++;
}
sort(v.begin(), v.end(), MapItCompare());//函数传对象

利用map排序：

//利用map排序 -- 拷贝了pair数据
//map<int,string> sortMap;
map<int, string, greater<int>> sortMap;//降序
for (auto e : countMap)
{
    sortMap.insert(make_pair(e.second, e.first));
}

利用set排序：

//利用set排序 -- 不拷贝pair数据
set<map<string, int>::iterator, MapItCompare> sortSet;//模板传类型
countMapIt = countMap.begin();//countMapIt是一个指向pair的迭代器
while (countMapIt != countMap.end())
{
    sortSet.insert(countMapIt);
    countMapIt++;
}

利用优先级队列排序：

//优先级队列
typedef map<string, int>::iterator M_IT;
priority_queue<M_IT, vector<M_IT>, MapItCompare> pq;
countMapIt = countMap.begin();//countMapIt是一个指向pair的迭代器
while (countMapIt != countMap.end())
{
    pq.push(countMapIt);
    countMapIt++;
}

erase的使用

erase是可以通过key进行删除的：

size_type erase (const key_type& k);

也可以传迭代器进行删除：

void erase (iterator position) ;

也可以传一段迭代器区间进行删除：

void erase (iterator first, iterator last) ;

map和multimap的对比

关于map和multimap的区别：

允许键值冗余与否，map不允许键值冗余，multimap允许键值冗余
multimap不支持[]

在multiset中查找一个值的实现：比如4，找到4以后，不能停止，要查找中序的第一个4，即找到4以后，要继续看4的左孩子是不是4，不是，就返回当前这个4，如果是，继续取左边的4，继续刚才的判断不断往后走

auto pos = s.find(4);//返回中序的第一个4
while(pos!=s.end() && *pos == 4)
{
    //找出所有的4
    cout<<*pos<<" ";
    ++pos;
}

如果想看4有几个，有对应的接口：

cout<<s.count(4)<<endl;
cout<<s.count(8 )<<endl;

下面我们看一下map和multimap插入的区别：

void test_map8()
{
    map<string,string> dict;
    dict.insert(make_pair("left","左边"));
    
    multimap<string,string> mdict;
    mdict.insert(make_pair("left","左边"));
    mdict.insert(make_pair("left","剩余"));
    mdict.insert(make_pair("left","左边"));
}

multimap在value相同时也会插入

在OJ中的使用

前k个高频单词

题目描述

给一非空的单词列表，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

示例 2：

输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

错误代码写法

class Solution {
public:
    struct MapItCompare
    {
        bool operator()(map<string,int>::iterator x,map<string,int>::iterator y)
        {
            return x->second > y->second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k)
    {
		map<string,int> countMap;//map的key时string，按照key进行排序，插入数据时中序就是字典序
    	//统计次数
    	for(auto& e : words)
    	{
    	    countMap[e]++;
    	}
        
        //存储到vector中进行排序
        //vector<pair<string,int>> v;//可以存pair
        vector<map<string,int>::iterator> v;//也可以存map的迭代器,节省存储空间
        map<string,int>::iterator countMapIt = countMap.begin();//countMapIt是一个指向pair的迭代器
        while(countMapIt!=countMap.end())
        {
            v.push_back(countMapIt);
            countMapIt++;
        }
        //排序
        //sort底层是快排,快排是不稳定的，sort排序后,字典序被打乱了,所以不能使用sort排序
        sort(v.begin(),v.end(),MapItCompare());//函数传对象
        
        //取出次数最多的前k个放入vector
        vector<string> retV;
        for(int i = 0;i < k;i++)
        {
            retV.push_back(v[i]->first);
        }
        
        return retV;
	}
};

sort底层是快排,快排是不稳定的，sort排序后,字典序被打乱了,所以不能使用sort排序

正确代码写法

第一步统计次数，string就按字典序进行排序了
第二步按次数排序(利用multimap，因为次数可能相同，相同时也可以进行插入)，相同次数的单词相对顺序不会发生改变，相当于是稳定的

class Solution {
public:
    struct MapItCompare
    {
        bool operator()(map<string,int>::iterator x,map<string,int>::iterator y)
        {
            return x->second > y->second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k)
    {
		map<string,int> countMap;
    	//统计次数
    	for(auto& e : words)
    	{
    	    countMap[e]++;
    	}
        
        //使用map/multimap特性进行排序是稳定的
        multimap<int,string,greater<int>> sortMap;//以int排序，降序
        for(auto pr : countMap)
        {
            sortMap.insert(make_pair(pr.second,pr.first));
        }//插入后就排好了
        
        vector<string> retV;
        auto it = sortMap.begin();
        while(k--)
        {
            retV.push_back(it->second);
            it++;
        }
        return retV;
	}
};