一、容器分类
- 序列式容器:vector list
- 关联式容器: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
set的insert
single element (1) pair<iterator,bool> insert (const value_type& val);
with hint (2) iterator insert (iterator position, const value_type& val);
range (3) template </class InputIterator>
void insert (InputIterator first, InputIterator last);
void testset1()
{
set<int> s;
s.insert(10);
s.insert(0);
s.insert(3);
s.insert(7);
s.insert(5);
s.insert(5);
s.insert(5);
// 搜索树默认遍历是中序
// 排序+去重
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
}
set的erase
void erase (iterator position);
size_type erase (const value_type& val);
void erase (iterator first, iterator last);
void testset2()
{
set<int> s;
s.insert(10);
s.insert(0);
s.insert(3);
s.insert(7);
s.insert(5);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
set<int>::iterator pos = s.find(5);
if (pos != s.end())
{
s.erase(pos);
}
for (auto e : s)
{
cout << e << " ";
}
}
四、multiset
multiset允许键值重复,其余操作与set几乎相同
multiset的insert
void testmultiset1()
{
// 最大区别就是允许插入同样的值
multiset<int> s;
s.insert(10);
s.insert(0);
s.insert(3);
s.insert(7);
s.insert(5);
s.insert(5);
s.insert(5);
s.insert(5);
s.insert(5);
multiset<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
multiset的find
void testmultiset2()
{
multiset<int> s;
s.insert(10);
s.insert(0);
s.insert(3);
s.insert(7);
s.insert(5);
s.insert(5);
s.insert(5);
s.insert(5);
s.insert(5);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
multiset<int>::iterator pos = s.find(5);
// 这里找到是中序的第一个5
/*if (pos != s.end()) { s.erase(pos); }*/
while (pos != s.end())
{
cout << *pos << " ";
++pos;
}
}
multiset的erase
void testmultiset3()
{
multiset<int> s;
s.insert(10);
s.insert(0);
s.insert(3);
s.insert(7);
s.insert(5);
s.insert(5);
s.insert(5);
s.insert(5);
s.insert(5);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
multiset<int>::iterator pos = s.find(5);
// 这里找到是中序的第一个5
// 第一种就是删除所有的5迭代器
//while (pos != s.end()&&*pos==5)
//{
// // 如果直接删除,就会导致迭代器失效
// auto next = pos;
// next++;
// s.erase(pos);
// pos = next;
//}
// 第二种就是直接删除值
cout << s.erase(5) <<endl;
for (auto e : s)
{
cout << e << " ";
}
}
五、map
map的insert
single element (1) pair<iterator,bool> insert (const value_type& val);
with hint (2) iterator insert (iterator position, const value_type& val);
range (3) template <class InputIterator>
void insert (InputIterator first, InputIterator last);
数据类型:
key_type | The first template parameter (Key)
mapped_type | The second template parameter (T)
value_type | pair<const key_type,mapped_type>
pair的构造函数:
default (1) pair();
copy (2) template<class U, class V> pair (const pair<U,V>& pr);
initialization (3) pair (const first_type& a, const second_type& b);
make_pair较于pair的优势就是它是一个函数模板,可以自动推导参数的类型
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}
void testmap1()
{
// 字典
map<string, string> dict;
// 1、直接构造对象
pair<string, string> kv1("sort", "排序");
dict.insert(kv1);
// 2、匿名对象进行构造
dict.insert(pair<string, string>("study", "学习"));
// 3、make_pair是一个函数模板,本质也是\ 返回一个pair的匿名对象,可以自动推导类型
dict.insert(make_pair("test", "测试"));
auto it = dict.begin();
while (it != dict.end())
{
cout << it->first << ": " << it->second << endl;
//cout << (*it).first << ": " << (*it).second << endl;
++it;
}
}
重点operator[ ]
统计水果出现的次数
// 第一种:通过查找的方式统计
void testmap2()
{
string fruits[] = {
"香蕉","香蕉",
"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
//key是水果名称,value是该水果出现的次数
map<string, int> countMap;
for (auto& str : fruits)
{
auto ret = countMap.find(str);
if (ret == countMap.end())
{
// 没找到,说明要插入
countMap.insert(make_pair(str, 1));
}
else
{
ret->second++;
}
}
//范围for相当于 kv=*it 这个操作
for (auto& kv : countMap)
{
cout << kv.first <<" : " << kv.second << endl;
}
cout << endl;
}
这种方法的统计有缺陷,就是第一次会查找该值在不在map中,如果在直接value++,如果不在会进行插入操作,插入时又会进行一次查找操作,不免效率会低一点
改进
利用如下insert函数
pair<iterator,bool> insert (const value_type& val);
利用这个insert,它会返回一个pair对象,其成员pair::first设置为一个迭代器,指向新插入的元素或映射中具有等效键的元素。如果插入了新元素,则对键值对中的pair::second元素设置为true ,如果已存在等效键,则设置为false 。
如果不存在,则返回新插入位置的迭代器,second设置为true
如果已存在,则返回已经存在位置的迭代器,second设置为false
// 第二种:改进第一种
void testmap3()
{
string fruits[] = {
"香蕉","香蕉",\
"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
//key是水果名称,value是该水果出现的次数
map<string, int> countMap;
for (auto& str : fruits)
{
//pair<iterator, bool> insert(const value_type & val);
auto pair = countMap.insert(make_pair(str,1));
if (pair.second == false)
{
pair.first->second++;
}
}
//范围for相当于 kv=*it 这个操作
for (auto& kv : countMap)
{
cout << kv.first << " : " << kv.second << endl;
}
cout << endl;
}
使用operator[ ]
mapped_type& operator[] (const key_type& k);
// 第三种:operator[]
void testmap4()
{
string fruits[] = {
"香蕉","香蕉",\
"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
map<string, int> countMap;
for (auto& str : fruits)
{
countMap[str]++;//一句代码即可统计
}
for (auto& kv : countMap)
{
cout << kv.first << " : " << kv.second << endl;
}
cout << endl;
}
以前的[ ]都是数组行为,这里的[ ]的传入的是key,返回的是value的引用,进一步看看[ ]的调用等价于:
mapped_type& operator[] (const key_type& k)
{
return (*((this->insert(make_pair(k,mapped_type()))).first)).second;
}
//简化一下
mapped_type& operator[] (const key_type& k)
{
pair<iterator,bool> ret =insert(make_pair(k,mapped_type()));
return ret.first->second;
}
这里统计次数second给的模板参数是int( ),为0,++过后变为1了,所以虽然刚开始新插入的int为0,返回值是value的引用,所以可以统计次数了。
1、水果第一次出现,插入+修改
2、水果不是第一次出现,查找+修改
总结一下[ ]的作用
- 插入
- 查找
- 修改
void testmap5()
{
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("test", "测试"));
dict.insert(make_pair("left", "左边"));
dict["left"] = "剩余";// 修改left
dict["hello"];// 没有此key,充当插入的作用
cout << dict["sort"] << endl;// 有这个key,充当查找
dict["C++"] = "C加加";// 充当插入+修改
}
六、multimap
与map使用几乎相同,它允许key冗余,但是没有operator[ ]
multimap的insert
void testmultimap()
{
// 允许key冗余
multimap<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("test", "测试"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("left", "留下"));
for (auto& kv : dict)
{
cout << kv.first << " : " << kv.second << endl;
}
cout << endl;
// 计数
cout << dict.count("left") << endl;
}
七、OJ题
- 本公司现在要给公司员工发波福利,在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多,但是却又不知道哪种水果比较受欢迎,然后公司就让每个员工报告了自己最爱吃的k种水果,并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数,并且求出大家最喜欢吃的
前k种水果
。
第一种:
//OJ题
//统计最相爱的前k个水果
struct CountVal
{
bool operator()(const pair<string,int>& l, const pair<string, int>& r)
{
return l.second > r.second;
}
};
void GetFavoriteFruit1(const vector<string>& fruits,size_t k)
{
map<string, int> countMap;
// 统计次数
for (auto& str : fruits)
{
countMap[str]++;
}
// 找前k个——topk问题
//1、数据量不大,我们可以排序
// 首先我们想要使用sort,必须传入随机迭代器的容器\ 所以我们把数据插入到vector<pair<string, int>>中
vector<pair<string, int>> sortV;
for (auto& kv : countMap)
{
sortV.push_back(kv);
}
sort(sortV. begin(), sortV.end(),CountVal());
for (int i = 0; i < k; i++)
{
cout << sortV[i].first << ":" << sortV[i].second << endl;
}
}
void test1()
{
vector<string> fruits = {
"香蕉","香蕉","梨",\
"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
GetFavoriteFruit1(fruits,3);
}
第一种改进的版本:
struct CountIterator
{
bool operator()(const map<string, int>::iterator& l, map<string, int>::iterator& r)
{
return l->second > r->second;
}
};
void GetFavoriteFruit1(const vector<string>& fruits,size_t k)
{
map<string, int> countMap;
// 统计次数
for (auto& str : fruits)
{
countMap[str]++;
}
// 找前k个——topk问题
// 改进:在vector中存map的迭代器,迭代器比pair小,更加节省空间
vector <map<string, int>::iterator> sortV;
auto it = countMap.begin();
while (it != countMap.end())
{
sortV.push_back(it);
it++;
}
sort(sortV.begin(), sortV.end(), CountIterator());
for (int i = 0; i < k; i++)
{
cout << sortV[i]->first << ":" << sortV[i]->second << endl;
}
}
void test1()
{
vector<string> fruits = {
"香蕉","香蕉","梨","香蕉",
"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
GetFavoriteFruit1(fruits,3);
}
第二种:
//2、可以使用multimap
void GetFavoriteFruit2(const vector<string>& fruits, size_t k)
{
map<string, int> countMap;
// 统计次数
for (auto& str : fruits)
{
countMap[str]++;
}
multimap<int, string,greater<int>> sortMap;
for (auto& kv : countMap)
{
sortMap.insert(make_pair(kv.second, kv.first));
}
auto it = sortMap.begin();
while (it != sortMap.end())
{
cout << it->second << " : " << it->first << endl;
it++;
}
}
void test1()
{
vector<string> fruits = {
"香蕉","香蕉","梨","香蕉",
"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
GetFavoriteFruit2(fruits,3);
}
第三种:
struct CountVal
{
bool operator()(const pair<string,int>& l, const pair<string, int>& r)
{
return l.second < r.second;
}
};
void GetFavoriteFruit3(const vector<string>& fruits, size_t k)
{
map<string, int> countMap;
// 统计次数
for (auto& str : fruits)
{
countMap[str]++;
}
//3、可以使用priority_queue
priority_queue<pair<string, int>, vector<pair<string, int>>, CountVal> qp;
for (auto& kv : countMap)
{
qp.push(kv);
}
while (k--)
{
cout << qp.top().first << ":" << qp.top().second << endl;
qp.pop();
}
}
void test1()
{
vector<string> fruits = {
"香蕉","香蕉","梨","香蕉",
"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
GetFavoriteFruit3(fruits,3);
}
第三种改进版本:
struct CountIterator
{
bool operator()(const map<string, int>::iterator& l, map<string, int>::iterator& r)
{
//return l->second > r->second;
return l->second < r->second;
}
};
void GetFavoriteFruit3(const vector<string>& fruits, size_t k)
{
map<string, int> countMap;
// 统计次数
for (auto& str : fruits)
{
countMap[str]++;
}
priority_queue<map<string, int>::iterator, vector<map<string, int>::iterator>, CountIterator> pq;
auto it = countMap.begin();
while (it != countMap.end())
{
pq.push(it);
++it;
}
while (k--)
{
cout << pq.top()->first << ":" << pq.top()->second << endl;
pq.pop();
}
}
void test1()
{
vector<string> fruits = {
"香蕉","香蕉","梨","香蕉",
"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
GetFavoriteFruit3(fruits,3);
}
- 前K个高频单词
给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字典顺序排序。
示例 1:
输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”] 解析: “i” 和 “love” 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 “i” 在 “love” 之前。
sort的底层是快速排序,它是不稳定的一个排序,可能OJ过不了。
我们可以选择一个稳定的排序:std::stable_sort
,下面所使用的的是multimap来进行排序操作的,也可以完成。
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
map<string,int> countMap;
// 统计次数
for(auto &str: words)
{
countMap[str]++;
}
// 排序操作
// 按照value来排序,排降序传入greater
multimap<int,string,greater<int>> sortMap;
for(auto & kv: countMap)
{
sortMap.insert(make_pair(kv.second,kv.first));
}
// 拿到前k个
vector<string> v;
auto it=sortMap.begin();
while(k--)
{
v.push_back(it->second);
++it;
}
return v;
}
};
今天的文章map和set的使用分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/67614.html