STL-map/unordered_map映射
目录键值对容器
Map 映射是一种类似于字典的数据结构。 它是(键,值)对的序列,其中只有单个值与每个唯一键相关联。
map内部自建一颗红黑树,这棵树具有对数据自动排序的功能,因此,map内的数据都是按key的值排好序的。
1.构造初始化
#incude<map>
map<int,string> mapstring;
map<string,int> mapint;
2.数据插入
// 可以使用 insert 或者 map[“key”]=value
//1. 采用创建pair的形式插入 pair<string, string>("string1", "st1")
//2. 采用make_pair的形式进行插入 make_pair("string2", "str2")`
//3. 采用大括号的形式进行插入 { "string3", "str3" }
map<string, int> mp;
// 三种方式实现map容器插入操作
mp.insert(pair<string, int>("admin0", 100));
mp.insert(make_pair("admin1", 200));
mp["admin2"] = 300;
mp.erase("admin2"); // 删除第3个数据
// 定义一个map对象
#include<map>
map<int,string> mp;
// 创建
map<string, string> dict={{"str1", "111"}, {"st2", "222"}};
map<string, int> mymap2{make_pair("str1", 1), make_pair("st2", 2)};
//第一种
dict["003"]="003";
//第二种 用insert函數插入pair
dict.insert(pair<string, string>("000", "student_zero"));
//第三种
dict.insert(make_pair("002", "student_two"));
for(map<string,string>::iterator it=dict.begin();it!=dict.end();it++)
{
cout<<it->first<<" "<<it->second<<endl;
}
// 000 student_zero
// 002 student_two
// 003 003
// st2 222
// str1 111
3.数据查找
// 遍历查找
#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;
int main()
{
// 创建空 map 容器
std::map<std::string, string> myMap;
myMap["123"] = "abc";
myMap["456"] = "def";
myMap["789"] = "ghl";
for (auto i = myMap.begin(); i != myMap.end(); ++i)
{
cout << i->first << " " << i->second << endl;
}
// 反向遍历键值对
for (map<string, string>::reverse_iterator it = myMap.rbegin(); it != myMap.rend();it ++)
cout << "key = " << it->first << " --> value = " << it->second << endl;
return 0;
}
//123 abc
//456 def
//789 ghlf
//mymap.at() 方法 at和[ ]两种 at会作下标检查,而[]不会
#include <iostream>
#include <map> // map
#include <string> // string
using namespace std;
int main()
{
// 创建空 map 容器
std::map<std::string, string> myMap;
myMap["123"] = "abc";
myMap["456"] = "def";
myMap["789"] = "ghl";
cout << myMap["123"] << endl;
cout << myMap.at("123") << endl;
// cout << myMap.at("2") << endl; //越界报错
return 0;
}
4.迭代器遍历
// 借助 find(key) 返回的是一个迭代器
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
map<string, int> mp;
mp["admin0"] = 100;
mp["admin1"] = 200;
mp["admin2"] = 300;
// 寻找admin0存在map中
map<string, int>::iterator pos = mp.find("admin0");
if (pos != mp.end()){
cout << "find key = " << pos->first << " --> value = " << pos->second << endl;
}
else{
cout << "no find key = " << endl;
}
// 寻找admin4 不存在map中
map<string, int>::iterator pos2 = mp.find("admin4");
if (pos2 != mp.end()){
cout << "key = " << pos2->first << " --> value = " << pos2->second << endl;
}
else{
cout << "no find key = " << endl;
}
// lower_bound(keyElem) 返回第一个key=keyElem元素的迭代器
map<string, int>::iterator ret = mp.lower_bound("admin0");
if (ret != mp.end())
cout << "lower_bound key = " << ret->first << " --> lower_bound value = " << ret->second << endl;
// upper_bound(keyElem) 返回第一个key>keyElem元素的迭代器
map<string, int>::iterator ret1 = mp.upper_bound("admin0");
cout << "upper_bound key = " << ret1->first << " --> upper_bound value = " << ret1->second << endl;
system("pause");
return 0;
}
5.删除和清空
#include <iostream>
#include <map>
#include <string>
map<string,int> mymap;
map.size(); // map的大小
mymap["123"] = 100;
mymap["345"] = 200;
mymap["789"] = 300;
//迭代器刪除
iter = mymap.find("123");
mymap.erase(iter);
//用关键字刪除
int n = mymap.erase("123"); //如果刪除了會返回1,否則返回0
//用迭代器范围刪除 : 把整个map清空
mymap.erase(mymap.begin(), mymap.end())
map.cleae();
6.成员方法
成员方法 | 功能 |
---|---|
begin() | 返回指向容器中第一个(注意,是已排好序的第一个)键值对的双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
end() | 返回指向容器最后一个元素(注意,是已排好序的最后一个)所在位置后一个位置的双向迭代器,通常和 begin() 结合使用。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
rbegin() | 返回指向最后一个(注意,是已排好序的最后一个)元素的反向双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。 |
rend() | 返回指向第一个(注意,是已排好序的第一个)元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。 |
cbegin() | 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
cend() | 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
crbegin() | 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
crend() | 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。 |
find(key) | 在 map 容器中查找键为 key 的键值对,如果成功找到,则返回指向该键值对的双向迭代器;反之,则返回和 end() 方法一样的迭代器。另外,如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
lower_bound(key) | 返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
upper_bound(key) | 返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。 |
equal_range(key) | 该方法返回一个 pair 对象(包含 2 个双向迭代器),其中 pair.first 和 lower_bound() 方法的返回值等价,pair.second 和 upper_bound() 方法的返回值等价。也就是说,该方法将返回一个范围,该范围中包含的键为 key 的键值对(map 容器键值对唯一,因此该范围最多包含一个键值对)。 |
empty() | 若容器为空,则返回 true;否则 false。 |
size() | 返回当前 map 容器中存有键值对的个数。 |
max_size() | 返回 map 容器所能容纳键值对的最大个数,不同的操作系统,其返回值亦不相同。 |
operator[] | map容器重载了 [] 运算符,只要知道 map 容器中某个键值对的键的值,就可以向获取数组中元素那样,通过键直接获取对应的值。 |
at(key) | 找到 map 容器中 key 键对应的值,如果找不到,该函数会引发 out_of_range 异常。 |
insert() | 向 map 容器中插入键值对。 |
erase() | 删除 map 容器指定位置、指定键(key)值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。 |
swap() | 交换 2 个 map 容器中存储的键值对,这意味着,操作的 2 个键值对的类型必须相同。 |
clear() | 清空 map 容器中所有的键值对,即使 map 容器的 size() 为 0。 |
emplace() | 在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样,但效率更高。 |
emplace_hint() | 在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的,不同之处在于,使用者必须为该方法提供一个指示键值对生成位置的迭代器,并作为该方法的第一个参数。 |
count(key) | 在当前 map 容器中,查找键为 key 的键值对的个数并返回。注意,由于 map 容器中各键值对的键的值是唯一的,因此该函数的返回值最大为 1。 |
7.multimap
类似于map,multimap也是存储两个元素之间的映射关系的容器,不相同的是,multimap的key值可以重复出现。
#include <iostream>
#include <map>
using namespace std;
int main()
{
multimap<string, string> studentMap = {
{"first", "Tom"},
{"second", "Mali"},
{"third", "John"}};
studentMap.insert(pair<string, string>("first", "Bob"));
multimap<string, string>::iterator itor_begin = studentMap.lower_bound("first");
multimap<string, string>::iterator itor_end = studentMap.upper_bound("first");
while (itor_begin != itor_end)
{
cout << itor_begin->first << " " << itor_begin++->second << endl;
// cout << itor_begin->first<<" "<< itor_begin->second << endl;
// itor_begin++;
}
std::cout << studentMap.count("first") << std::endl; // 输出为2
}
//first Tom
//first Bob
//2
8.unordered_map
unordered_map 内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序是无序的
unordered_map用法和map基本一致
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map < string , int > studentUMap = {
{ "Tom" , 1 },
{ "Ann" , 4 },
{ "Job" , 2 }
};
studentUMap.insert(pair<string, int>("Job", 5));
cout<< "output:"<<endl;
for (auto it = studentUMap.begin(); it != studentUMap.end(); it++) {
cout << (*it).first << ", " << (*it).second << "\n";
}
cout<<endl;
studentUMap["Job"] = 3;
for (auto it = studentUMap.begin(); it != studentUMap.end(); it++) {
cout << (*it).first << ", " << (*it).second << "\n";
}
}
9.unordered_multimap
unordered_multimap 是一个封装哈希表的无序容器。容器中每个元素都是 key/value,每个 key 可重复出现。
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
std::unordered_multimap < int , int > studentUmMap;
studentUmMap.insert(std::pair<int, int>(1, 333));
studentUmMap.insert(std::pair<int, int>(3, 555));
studentUmMap.insert(std::pair<int, int>(5, 666));
studentUmMap.insert(std::pair<int, int>(5, 5));
cout<< "output:"<<endl;
for (auto it = studentUmMap.begin(); it != studentUmMap.end(); it++) {
std::cout << (*it).first << ", " << (*it).second << "\n";
}
std::cout <<"count:"<< studentUmMap.count(5) <<std::endl;
std::cout <<"size: "<< studentUmMap.size() <<std::endl;
std::cout <<"empty?"<< studentUmMap.empty()<<"\n" <<std::endl;
}
10.底层原理
map :map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树),红黑树具有自动排序的功能,因此map内部的所有元素都是有序的.
unordered_map :unordered_map内部实现了一个哈希表 (也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用).
map:
优点:
有序性,这是map结构最大的优点,其元素的有序性在很多应用中都会简化很多的操作
红黑树,内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现,因此效率非常的高
缺点:
空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间
适用处:对于那些有顺序要求的问题,用map会更高效一些
unordered_map:
优点: 因为内部实现了哈希表,因此其查找速度非常的快
缺点: 哈希表的建立比较耗费时间
适用处:对于查找问题,unordered_map会更加高效一些,因此遇到查找问题,常会考虑一下用unordered_map
11.总结
map和unordered_map;//key不允许重复,是单重映射表
multimap和unordered_multimap;//key允许重复,是多重映射表
12.参考资料
https://www.cnblogs.com/LyShark/p/17633742.html
https://zhuanlan.zhihu.com/p/447839310
标签:map,迭代,容器,STL,键值,key,unordered From: https://www.cnblogs.com/tian777/p/17980857