首页 > 其他分享 >STL-map/unordered_map映射

STL-map/unordered_map映射

时间:2024-01-22 20:00:32浏览次数:31  
标签:map 迭代 容器 STL 键值 key unordered

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

相关文章

  • Elasticsearch-Mapping篇
    官方文档官网:https://www.elastic.co/guide/en/elasticsearch/reference/current/mapping.html映射是定义文档及其包含的字段如何存储和索引的过程。每个文档都是字段的集合,每个字段都有自己的数据类型。映射数据时,您创建一个映射定义,其中包含与文档相关的字段列表。映射定义......
  • 使用Javamail接收imaps协议的邮件
    网上的消息不能说大多,只能说基本都过时了,连imap和imaps都不分了本文基于apache-james项目搭建的邮件服务器,其他邮件服务器仅供参考首先是依赖,这里需要引入两个依赖,如下<dependency><groupId>javax.mail</groupId><artifactId>javax.mail-api</artifactId>......
  • Maptalks内阴影实践
    背景    地图可视化项目中往往有要求进行内阴影的需求,但是对于可视化能力比较弱的giser来说,这个没有现成的方案,一般都会说进行ui切图然后进行贴图就行,但是这样对于动态生成的场景就不太满足,本文基于canvas进行动态绘制内阴影。原理    内阴影的原理主要是用的canvas的......
  • STL—函数对象
    函数对象概念1、重载函数调用操作符的类,其对象常称为函数对象2、函数对象使用重载的()时,行为类似函数调用,也叫仿函数本质函数对象(仿函数)是一个类,不是一个函数函数对象的使用特点:1、函数对象在使用时,可以像普通函数那样调用,也可以有参数,可以有返回值2、函数对象超出普通函数的概念,函......
  • ConcurrentHashMap源码逐行解读基于jdk1.8
    前导知识//node数组最大容量:2^30=1073741824privatestaticfinalintMAXIMUM_CAPACITY=1<<30;//默认初始值,必须是2的幕数privatestaticfinalintDEFAULT_CAPACITY=16;//数组可能最大值,需要与toArray()相关方法关联st......
  • 解决latex在使用lstlisting环境时的Undefined control sequence.错误
    错误描述,如题,Undefinedcontrolsequence.\begin{lstlisting},查了不少的资料,起始就是一句话,缺了宏包的导入。先看代码:\documentclass[11pt,a4paper]{ctexart}\usepackage{listings}%插入代码要引入的宏包\author{gsc}\title{sample}\lstset{columns=fixed,......
  • 简单剖析Hashmap
    剖析JavaHashmap源码在Java的集合框架中,HashMap是一颗璀璨的明珠。通过深入挖掘其源码,我们将揭开HashMap的神秘面纱,理解其底层原理、扩容机制和数据结构。1.HashMap源码导读我们首先来看一段简单的代码,创建一个空的HashMap:importjava.util.HashMap;publicclass......
  • k8s之configmap应用
    一、创建configmap1、基于命令创建configmaproot@k8s-master01:~#kubectlcreateconfigmapdemoapp-cfg--from-literal=listen.port=8080--from-literal=listen.address='127.0.0.1'configmap/demoapp-cfgcreatedroot@k8s-master01:~#kubectlgetcmNAME......
  • STL(下)
    deque容器基本概念功能:双端数组,可以对头端进行插入删除操作deque与vector区别:1.vector对于头的插入删除效率低,数据量越大,效率越低2.deque相对而言,对头部的插入删除速度会比vector快3.vector访问元素时的速度会比deque快,这和两者内部实现有关。deque内部工作原理:deque内部有个中控器......
  • [Java SE/JDK] Map之重定义key对象的hash值
    0序言项目上有个场景:数据源连接池需要对key对象的hash值重写,保证通过相同的关键属性(datasourceName)值去重不同的对象。publicabstractclassAbstractDatabaseConnectorKeyedObjectPool<KextendsDataSource,VextendsAbstractConnector>1重写Map的key对象的hash值......