C++学习笔记---021
- C++之map的应用
- 1、map的简单介绍
- 1.1、基本概念
- 1.2、map基本特性
- 2、map的基本操作
- 2.1、插入元素
- 2.2、访问元素
- 2.3、删除元素
- 2.4、遍历map
- 2.5、检查元素是否存在
- 2.6、获取map的大小
- 2.7、清空map
- 2.8、基本样例
- 3、map的基础模拟实现
- 4、测试用例
- 4.1、插入和遍历
- 4.2、查找和删除
- 4.3、统计次数
- 4.4、[ ]的插入
- 4.5、以[ ]再谈统计计数
- 4.6、equal_range
- 5、map的性能分析
- 6、练习题
- 6.1、前K个高频单词
- 6.2、单词识别
C++之map的应用
前言：
前面篇章学习了C++对于set和multiset的基本应用的知识认识和了解，接下来继续学习，C++的map等知识。
/知识点汇总/
1、map的简单介绍
1.1、基本概念
在C++中，map是一个标准模板库（STL）中的关联容器，它包含可以重复的键值对集合，其中每个键都是唯一的，并与一个值相关联。
map通常以一个红黑树作为其内部数据结构，这确保了键值对的自动排序和高效的插入、删除和搜索操作。
格式：
std::map<KeyType, ValueType> variable_name;
1.2、map基本特性
1.键唯一性：map中的每个键都是唯一的，不允许有重复的键。
2.自动排序：map中的元素默认按照键的升序进行排序，这是因为它通常使用红黑树来实现。
3.关联容器：通过键来访问对应的值，而不是通过位置或索引。
4.动态大小：map的大小可以根据需要动态地增长或缩小。
2、map的基本操作
2.1、插入元素
方法一：
variable_name.insert(std::pair<KeyType, ValueType>(key, value));
方法二：
variable_name.insert({key, value}); // C++11及更高版本
方法三：
variable_name[key] = value;
2.2、访问元素
方法一：
ValueType& value_ref = variable_name[key];
方法二：
auto it = variable_name.find(key);
if (it != variable_name.end()) {
ValueType& value_ref = it->second;
// 使用value_ref
}
2.3、删除元素
方法一：
variable_name.erase(key); // 删除键为key的元素
方法二：
auto it = variable_name.find(key);
if (it != variable_name.end()) {
variable_name.erase(it);
}
2.4、遍历map
方法一：使用迭代器
for (auto it = variable_name.begin(); it != variable_name.end(); ++it) {
KeyType key = it->first;
ValueType value = it->second;
// 使用key和value
}
方法二：基于范围的for循环（C++11及更高版本）
for (const auto& pair : variable_name) {
KeyType key = pair.first;
ValueType value = pair.second;
// 使用key和value
}
2.5、检查元素是否存在
if (variable_name.find(key) != variable_name.end()) {
// 键存在
}
2.6、获取map的大小
size_t size = variable_name.size();
2.7、清空map
variable_name.clear();
2.8、基本样例
#include <iostream>
#include <map>
int main()
{
std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
ages.insert({"Charlie", 35});
for (const auto& pair : ages)
{
std::cout << pair.first << ": " << pair.second << std::endl;
}
ages.erase("Bob");
return 0;
}
3、map的基础模拟实现
#include <iostream>
#include <vector>
#include <utility> // for std::pair
template <typename Key, typename Value>
class SimpleMap {
private:
std::vector<std::pair<Key, Value>> elements;
// 简单的线性搜索函数
size_t findIndex(const Key& key) const {
for (size_t i = 0; i < elements.size(); ++i) {
if (elements[i].first == key) {
return i;
}
}
return std::vector<std::pair<Key, Value>>::npos; // 返回一个特殊值表示未找到
}
public:
// 插入元素
void insert(const Key& key, const Value& value) {
size_t index = findIndex(key);
if (index == std::vector<std::pair<Key, Value>>::npos) {
elements.push_back(std::make_pair(key, value));
} else {
// 如果键已存在，可以选择更新值或不做任何操作（这里选择更新值）
elements[index].second = value;
}
}
// 查找元素
bool find(const Key& key, Value& value) const {
size_t index = findIndex(key);
if (index != std::vector<std::pair<Key, Value>>::npos) {
value = elements[index].second;
return true;
}
return false;
}
// 删除元素
bool erase(const Key& key) {
size_t index = findIndex(key);
if (index != std::vector<std::pair<Key, Value>>::npos) {
elements.erase(elements.begin() + index);
return true;
}
return false;
}
// ... 可以添加其他成员函数，如size(), clear()等
};
int main() {
SimpleMap<std::string, int> myMap;
myMap.insert("Alice", 30);
myMap.insert("Bob", 25);
int value;
if (myMap.find("Alice", value)) {
std::cout << "Alice's age is " << value << std::endl;
}
myMap.erase("Bob");
// ... 其他操作
return 0;
}
4、测试用例
4.1、插入和遍历
void test_map1()
{
map<string, string> dict;
pair<string, string> kv1("sort", "排序");//隐式类型转换
dict.insert(kv1);
dict.insert(pair<string, string>("left", "左边"));
dict.insert(make_pair("right", "左边"));
//pair<string, string> kv2 = {"sort", "排序"};//隐式类型转换
dict.insert({"insert","插入"});//隐式类型转换
//initializer_list
map<string, string> dict2 = { {"sort", "排序"},{"left", "左边"},{"right", "左边"} };
map<string, string>::iterator it = dict.begin();
//auto it = dict.begin();
while(it != dict.end())
{
//cout << *it << endl;//error
//因为pair<string, string> --- 二元的
//cout << (*it).first << " : " << (*it).second << endl;
//等价
cout << it->first << " : " << it->second << endl;
//等价原型
//cout << it.operator->()->first << " : " << it.operator->()->second << endl;
++it;
//iterator key不能修改，value可修改
//const_iterator key和value都不能修改
}
cout << endl;
//范围for
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
//了解一些C++17的写法 -- 编译器改配置即可
//for (auto& [x,y] : dict)
//{
// cout << x << ":" << y << endl;
//}
}
4.2、查找和删除
void test_map2()
{
// 创建一个空的map
std::map<std::string, int> myMap;
// 插入元素
myMap["apple"] = 1;
myMap["banana"] = 2;
myMap["cherry"] = 3;
// 遍历map
for (const auto& pair : myMap)
{
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 查找元素
if (myMap.find("banana") != myMap.end())
{
std::cout << "Found banana with value: " << myMap["banana"] << std::endl;
}
else
{
std::cout << "Banana not found" << std::endl;
}
// 删除元素
myMap.erase("cherry");
// 再次遍历map，以查看"cherry"是否已被删除
for (const auto& pair : myMap)
{
std::cout << pair.first << ": " << pair.second << std::endl;
}
}
4.3、统计次数
void test_map3()
{
// 统计水果出现的次数
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (auto& e : arr)
{
auto it = countMap.find(e);
if (it != countMap.end())
{
it->second++;
}
else
{
//const pair<string,int>& val = {e,1};
//pair<string,bool> insert(const value_type& val);
//key存在，插入失败，返回->pair<存在的key所在节点的迭代器,flase>
//key不存在，插入成功，返回->pair<新插入key所在节点的迭代器，true>
countMap.insert({ e,1 });
}
}
for (auto& kv : countMap)
{
//auto& [x, y] = kv;
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
4.4、[ ]的插入
补充：[ ]的底层拆解理解
V& operator[](const k& key)
{
return (*((this->insert(make_pair(k,mapped_type()))).first)).sencond;
}
V& operator[](const k& key)
{
//不管是插入成功还是失败，pair中iterator始终指向key所在节点的iterator
pair<iterator, bool> ret = this->insert(make_pair(key, v()));
iterator it = ret.first;
retrun it->second;
}
void test_map4()
{
map<string, string> dict;
dict.insert({ "string","字符串" });
//插入
dict["right"];
//插入+修改
dict["left"] = "左边";
//查找（已存在就是查找）
cout << dict["string"] << endl;
//修改
dict["right"] = "右边";
string str;
cin >> str;
//size_type count(const key_type& k) const;返回个数
//计数特定元素的个数
if (dict.count(str))
{
cout << "在" << endl;
}
else
{
cout << "不在" << endl;
}
//multimap与map还有一个区别，multimao没有[]
}
4.5、以[ ]再谈统计计数
void test_map5()
{
// 统计水果出现的次数
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (auto& e : arr)
{
countMap[e]++;//插入+修改
}
for (auto& kv : countMap)
{
//auto& [x, y] = kv;
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
//map<int, string> sortMap;
multimap<int, string> sortMap;
for (auto& kv : countMap)
{
//数据丢失，本质原因就是multimap和map的区别，因为对于map中已经已经存在的key会被覆盖造成丢失。
//sortMap[kv.second] = kv.first;
sortMap.insert({ kv.second ,kv.first });
}
cout << endl;
for (auto& kv : sortMap)
{
//auto& [x, y] = kv;
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
4.6、equal_range
equal_range
获取相等元素的范围
返回一个范围的边界，该范围包括容器中具有等价于k的键的所有元素。
它返回一个范围，该范围包含所有与给定键相等的元素。
作用：
equal_range返回一个包含两个迭代器的pair：
first迭代器指向范围中的第一个元素（如果存在）。
second迭代器指向范围之后的第一个元素（即大于给定键的第一个元素），或者如果范围内没有更多的元素，则指向容器的end()。
这个函数的主要用途是当你需要查找一个键的所有出现，或者当你需要在一个有序范围内进行迭代时。
void test_map7()
{
map<char, int> mymap;
mymap['a'] = 10;
mymap['b'] = 20;
mymap['c'] = 30;
mymap['c'] = 40;
mymap['c'] = 50;
mymap['f'] = 60;
pair<map<char, int>::iterator, map<char, int>::iterator> ret;
ret = mymap.equal_range('c');
cout << "lower bound points to: ";
cout << ret.first->first << " => " << ret.first->second << '\n';
cout << "upper bound points to: ";
cout << ret.second->first << " => " << ret.second->second << '\n';
}
5、map的性能分析
时间复杂度
1.插入（Insertion）：在 std::map 中插入一个元素的时间复杂度是 O(log n)，其中 n 是 map 中元素的数量。这是因为红黑树在插入时需要重新平衡树结构以保持其性质。
2.查找（Search）：查找一个元素的时间复杂度同样是 O(log n)。在红黑树中，查找操作通过树的层次结构来减少搜索空间，从而实现对数时间复杂度。
3.删除（Deletion）：删除一个元素的时间复杂度也是 O(log n)。删除操作同样需要保持红黑树的性质，这可能需要重新平衡树结构。
空间复杂度
std::map 的空间复杂度是线性的，即 O(n)，其中 n 是 map
中元素的数量。这是因为每个元素都需要在树中存储一个节点，并且这些节点需要额外的空间来存储键和值，以及指向其子节点的指针。
6、练习题
6.1、前K个高频单词
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
思路：用<单词，单词出现次数>构建键值对，然后将vector中的单词放进去，统计每个单词出现的次数
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;
class Solution {
public:
class KVCompare {
public:
// 在set中进行排序时的比较规则
bool operator()(const pair<string, int>& left, const pair<string, int>& right)
{
return left.second > right.second; // 升序：> 降序：<
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
// 用<单词，单词出现次数>构建键值对，然后将vector中的单词放进去，统计每个单词出现的次数
map<string, int> countMap;
for (auto& e : words)
{
countMap[e]++;
}
vector<pair<string, int>> v(countMap.begin(), countMap.end());
//sort(v.begin(), v.end(), KVCompare());
stable_sort(v.begin(), v.end(), KVCompare());
vector<string> vRet;
for (size_t i = 0; i < k; i++) {
vRet.push_back(v[i].first);
}
return vRet;
}
};
int main()
{
Solution solution;
vector<string> words = { "the", "sky", "is", "blue", "the", "sun", "is", "bright", "the", "sun", "is", "shiny", "then", "the", "sky", "became", "even", "more", "blue" };
int k = 4;
vector<string> topK = solution.topKFrequent(words, k);
// 输出结果
cout << "Top " << k << " frequent words are: ";
for (const auto& word : topK) {
cout << word << " ";
}
cout << endl;
return 0;
}
输出结果：
6.2、单词识别
输入一个英文句子，把句子中的单词(不区分大小写)按出现次数按从多到少把单词和次数在屏幕上输出来，次数一样的按照单词小写的字典序排序输出，要求能识别英文单词和句号。
思路：思路是先截取单词，通过map记录单词个数，再转存vector进行排序。
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef pair<string, int> Word;
bool cmp(Word w1, Word w2)
{
return w1.second > w2.second;
}
int main()
{
map<string, int> mp;
string s;
while (getline(cin, s))
{
for (int i = 0, j = 0; i < s.size(); i++)
{
if (s[i] == ' ' || s[i] == '.')
{
string t = s.substr(j, i - j);
if (isupper(t[0]))
t[0] = tolower(t[0]);
j = i + 1;
mp[t]++;
}
}
vector<Word> v(mp.begin(), mp.end());
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < v.size(); i++)
cout << v[i].first << ":" << v[i].second << endl;
}
return 0;
}
输出结果：
