1.map 和 set 的应用和比较
map 和 set 都是关联式容器, 底层容器都是红黑树.
map 以键值对的形式进行存储, 方便进行查找, 关键词起到索引的作用, 值则表示与索引相关联的数据, 以红黑树的结构实现, 插入删除等操作都可以在 O(log n)时间内完成.
所有元素都是键 + 值存在, key=value 组成 pair, 是一组映射关系.
不允许键重复
所有元素是通过键进行自动排序的
map 的键是不能修改的, 但是其键对应的值是可以修改的
- #include<string>
- #include<vector>
- // 模拟 pair 和 make_pair 的底层实现
- //template<class K, class V>
- //struct pair
- //{
- // K first;
- // V second;
- //
- // pair(const K& key, const V& value)
- // :first(key)
- // , second(value)
- // {}
- //};
- //template<class K, class V>
- //pair<K, V> make_pair(const K& key, const V& value)
- //{
- // return pair<K, V>(key, value);
- //}
- //vector<string> GetTopKF(const vector<string>& fruits)
- //{
- // vector<string> topk;
- // typedef map<string, int> CountTop;
- // typedef map<string, int>::iterator CountIt;
- // CountTop counttop;
- // for (size_t i = 0; i <fruits.size(); i++) {
- // CountIt countit = counttop.find(fruits[i]);
- // if (countit != counttop.end())
- // (countit->second)++;
- // else
- // //counttop.insert(pair<string, int>(fruits[i], 1));
- // counttop.insert(make_pair(fruits[i], 1));
- // }
- // return topk;
- //}
- vector<string> GetTopKF(const vector<string>& fruits)
- {
- vector<string> topk;
- typedef map<string, int> CountTop;
- typedef map<string, int>::iterator CountIt;
- CountTop counttop;
- for (size_t i = 0; i <fruits.size(); i++) {
- /*pair<CountIt, bool> retKV = counttop.insert(make_pair(fruits[i], 1));
- if (retKV.second == false)
- {
- retKV.first->second++;
- }*/
- counttop[fruits[i]]++;
- }
- return topk;
- }
- void MapTest()
- {
- typedef map<string, string> Dict;
- typedef map<string, string>::iterator DictIt;
- Dict dict;
- dict.insert(pair<string, string>("right", "右边"));
- dict.insert(pair<string, string>("left", "左边"));
- dict.insert(pair<string, string>("世界", "你好"));
- dict.insert(pair<string, string>("hello", "word"));
- dict.insert(pair<string, string>("key", "键值"));
- DictIt dictit = dict.begin();
- while (dictit != dict.end()) {
- cout <<(*dictit).first << " " << (*dictit).second << endl;
- ++dictit;
- }
- DictIt ret = dict.find("left");
- if(ret != dict.end())
- dict.erase(ret);
- vector<string> v;
- v.push_back("梨");
- v.push_back("苹果");
- v.push_back("西瓜");
- v.push_back("香蕉");
- v.push_back("西瓜");
- v.push_back("香蕉");
- v.push_back("菠萝");
- v.push_back("西瓜");
- v.push_back("草莓");
- GetTopKF(v);
- }
set 支持高效的关键字查询操作 --- 检查每一个给定的关键字是否在 set 中, 也支持高效插入删除.
以平衡二叉检索树实现, 查找使用中序遍历算法, 检索效率高于 vector,deque,list 等容器, 另外使用中序遍历可将键值按照从小到大遍历出来, 构造 set 集合的主要目的是为了快速检索, 不可直接去修改键值.
所得元素的只有 key 没有 value,value 就是 key
不允许出现键值重复
所有的元素都会被自动排序
不能通过迭代器来改变 set 的值, 因为 set 的值就是键
- #pragma once
- #include<iostream>
- #include<set>
- #include<map>
- using namespace std;
- void SetTest()
- {
- set<int> s1; // 没有数据冗余
- s1.insert(4);
- s1.insert(5);
- s1.insert(7);
- s1.insert(7);
- s1.insert(14);
- s1.insert(7);
- s1.insert(9);
- s1.insert(3);
- s1.insert(0);
- s1.insert(30);
- s1.insert(14);
- s1.insert(6);
- s1.insert(28); //set 的插入操作
- set<int>::iterator ite = s1.begin();
- //ite = 10;
- while (ite != s1.end()) { // 利用迭代器遍历打印数据
- cout<<*ite<<" ";
- ite++;
- }
- cout <<endl;
- set<int>::reverse_iterator ret1= s1.rbegin();
- while (ret1 != s1.rend()) { // 降序打印
- cout <<*ret1 << " ";
- ret1++;
- }
- set<int>::iterator ret = s1.find(10); //
- if (ret != s1.end()) //set 的查找, 如果没有找到不会报错
- cout <<"find it" << *ret << endl;
- else
- cout << "null" << endl;
- if (s1.count(14))// 只判断是否存在 14, 返回 1 或 0
- cout << "find it" << endl;
- else
- cout << "null" << endl;
- ret = s1.find(30); //find 后删除
- if (ret != s1.end())
- s1.erase(ret);
- set<int>::iterator last, first;
- first = s1.lower_bound(8); // 返回 8 大的第一个数
- last = s1.upper_bound(20); // 返回 20 大的第一个数
- s1.erase(first, last);// 删除这个范围的数据
- s1.erase(100); // 有就删除, 没有也不报错
- set<int>::iterator ite1 = s1.begin();
- while (ite1 != s1.end()) {
- cout <<*ite1 << " ";
- ite1++;
- }
- }
- void MultisetTest() {
- multiset<int> s2; // 允许数据冗余, 其他操作同 set
- s2.insert(13);
- s2.insert(4);
- s2.insert(6);
- s2.insert(19);
- s2.insert(20);
- s2.insert(16);
- s2.insert(9);
- s2.insert(12);
- s2.insert(9);
- s2.insert(7);
- s2.insert(5);
- s2.insert(13);
- s2.insert(9);
- multiset<int>::iterator mit = s2.begin();
- while (mit != s2.end()) {
- cout <<*mit << " ";
- mit++;
- }
- multiset<int>::iterator mIt = s2.find(20);
- /*++mIt;
- ++mIt;
- ++mIt;
- ++mIt;*/
- }
map 的节点是一对数据, set 的节点是一个数据.
2. 扩展
Multimap 允许数据冗余, 即存储的数据不唯一.
hashmap 是基于散列表 (哈希表, hash table) 实现的. 基本原理是: 使用一个下标范围比较大的数组来存储元素. 可以设计一个函数 (哈希函数, 也叫做散列函数), 使得每个元素的关键字都与一个函数值(即数组下标, hash 值) 相对应, 于是用这个数组单元来存储这个元素; 也可以简单的理解为, 按照关键字为每一个元素 "分类", 然后将这个元素存储在相应 "类" 所对应的地方, 称为桶.
但不能够保证每个元素的关键字与函数值是一一对应的, 有可能出现对于不同的元素, 得到相同的函数值, 这就是哈希冲突, 往往需要专门的哈希冲突处理函数来解决.
hashma 插入和查找的速度与 哈希函数和冲突处理函数的 实现有关, 是这两个函数耗时的总和. 查询时间复杂度是 O(1);
看具体的应用, 不一定常数级别的 hash_map 一定比 log(n)级别的 map 要好, hash_map 的 hash 函数以及解决地址冲突等都要耗时间, 而且众所周知 hash 表是以空间换时间的, 因而 hash_map 的内存消耗肯定要大, 一般情况下, 如果记录非常大, 考虑 hash_map, 查找效率会高很多, 如果要考虑内存消耗, 则要谨慎使用 hash_map.
Multiset 允许数据冗余.
来源: https://www.cnblogs.com/33debug/p/7375876.html