保险网站建设,微信的网站,公司官网网站搭建,免费微信微网站模板下载C学习笔记---021 C之map的应用1、map的简单介绍1.1、基本概念1.2、map基本特性 2、map的基本操作2.1、插入元素2.2、访问元素2.3、删除元素2.4、遍历map2.5、检查元素是否存在2.6、获取map的大小2.7、清空map2.8、基本样例 3、map的基础模拟实现4、测试用例4.1、插入和遍历4.2、… C学习笔记---021 C之map的应用1、map的简单介绍1.1、基本概念1.2、map基本特性 2、map的基本操作2.1、插入元素2.2、访问元素2.3、删除元素2.4、遍历map2.5、检查元素是否存在2.6、获取map的大小2.7、清空map2.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::mapKeyType, ValueType variable_name; 1.2、map基本特性 1.键唯一性map中的每个键都是唯一的不允许有重复的键。 2.自动排序map中的元素默认按照键的升序进行排序这是因为它通常使用红黑树来实现。 3.关联容器通过键来访问对应的值而不是通过位置或索引。 4.动态大小map的大小可以根据需要动态地增长或缩小。 2、map的基本操作
2.1、插入元素
方法一
variable_name.insert(std::pairKeyType, ValueType(key, value));方法二
variable_name.insert({key, value}); // C11及更高版本方法三
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循环C11及更高版本
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::mapstd::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::vectorstd::pairKey, 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::vectorstd::pairKey, Value::npos; // 返回一个特殊值表示未找到 } public: // 插入元素 void insert(const Key key, const Value value) { size_t index findIndex(key); if (index std::vectorstd::pairKey, 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::vectorstd::pairKey, Value::npos) { value elements[index].second; return true; } return false; } // 删除元素 bool erase(const Key key) { size_t index findIndex(key); if (index ! std::vectorstd::pairKey, Value::npos) { elements.erase(elements.begin() index); return true; } return false; } // ... 可以添加其他成员函数如size(), clear()等
}; int main() { SimpleMapstd::string, int myMap; myMap.insert(Alice, 30); myMap.insert(Bob, 25); int value; if (myMap.find(Alice, value)) { std::cout Alices age is value std::endl; } myMap.erase(Bob); // ... 其他操作 return 0;
}4、测试用例
4.1、插入和遍历
void test_map1()
{mapstring, string dict;pairstring, string kv1(sort, 排序);//隐式类型转换dict.insert(kv1);dict.insert(pairstring, string(left, 左边));dict.insert(make_pair(right, 左边));//pairstring, string kv2 {sort, 排序};//隐式类型转换dict.insert({insert,插入});//隐式类型转换//initializer_listmapstring, string dict2 { {sort, 排序},{left, 左边},{right, 左边} };mapstring, string::iterator it dict.begin();//auto it dict.begin();while(it ! dict.end()){//cout *it endl;//error//因为pairstring, 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;//范围forfor (auto kv : dict){cout kv.first : kv.second endl;}//了解一些C17的写法 -- 编译器改配置即可//for (auto [x,y] : dict)//{// cout x : y endl;//}
}4.2、查找和删除
void test_map2()
{// 创建一个空的map std::mapstd::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[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){auto it countMap.find(e);if (it ! countMap.end()){it-second;}else{//const pairstring,int val {e,1};//pairstring,bool insert(const value_type val);//key存在插入失败返回-pair存在的key所在节点的迭代器,flase//key不存在插入成功返回-pair新插入key所在节点的迭代器truecountMap.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所在节点的iteratorpairiterator, bool ret this-insert(make_pair(key, v()));iterator it ret.first;retrun it-second;
}void test_map4()
{mapstring, 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[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){countMap[e];//插入修改}for (auto kv : countMap){//auto [x, y] kv;cout kv.first : kv.second endl;}cout endl;//mapint, string sortMap;multimapint, 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()
{mapchar, int mymap;mymap[a] 10;mymap[b] 20;mymap[c] 30;mymap[c] 40;mymap[c] 50;mymap[f] 60;pairmapchar, int::iterator, mapchar, 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 algorithmusing namespace std;class Solution {
public:class KVCompare {public:// 在set中进行排序时的比较规则bool operator()(const pairstring, int left, const pairstring, int right){return left.second right.second; // 升序 降序}};vectorstring topKFrequent(vectorstring words, int k) {// 用单词单词出现次数构建键值对然后将vector中的单词放进去统计每个单词出现的次数mapstring, int countMap;for (auto e : words){countMap[e];}vectorpairstring, int v(countMap.begin(), countMap.end());//sort(v.begin(), v.end(), KVCompare());stable_sort(v.begin(), v.end(), KVCompare());vectorstring vRet;for (size_t i 0; i k; i) {vRet.push_back(v[i].first);}return vRet;}
};int main()
{Solution solution;vectorstring words { the, sky, is, blue, the, sun, is, bright, the, sun, is, shiny, then, the, sky, became, even, more, blue };int k 4;vectorstring 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 pairstring, int Word;
bool cmp(Word w1, Word w2)
{return w1.second w2.second;
}
int main()
{mapstring, 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];}}vectorWord 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;
}输出结果
