map

文章目录

mapmap介绍map的特点map的基本操作节点pair初始化方式插入数据迭代器操作遍历方式map的基本操作函数map的优缺点multimap 多表映射unordered_map 无序映射函数操作unordered_multimap总结

map介绍

map 字典 映射

map是一个关系式容器 ,以模板(泛型)方式实现

底层通常是由一颗红黑树组成

第一个可以称为键(key)

第二个可以称为该键的值(value)

在map内部所有的key都是有序的,并且不会有重复的值

map的特点

map是一个容器，容器里面存放元素，把这个元素分成两个逻辑区块

第一个称为键(key)每个*键(key)*只能在map中出现一次,并且会进行有序的排列第二个称为该键值(value)，这两个区块当成一个组来进行管理每一个节点的内容是由一个pair<key,value>构成。

key和value 的条件

key是唯一的,不重复的,里面的key会自动去除重数据map会根据key的值自动的进行一个排序每个key对应着一个value

map的基本操作

map中每个键值对称之为节点

#include <map> //导入头文件

map的存放的节点容器时一个pair的类

节点pair

原型

template <typename K,typename V>class pair{public:K first;//key的值V seconed;//value的值pair(K& first,V& seconed): first(first),seconed(seconed){}}

用法,pair节点通常是通过map返回的一数据类型

pair<T1, T2> p;

pair<T1, T2> p(v1, v2);

pair<T1, T2> p = {v1, v2}

make_pair(v1, v2);

初始化方式

map<模板1,模板2> 变量名

map<key,value> m;//定义了一个 m 的空对象

map聚合初始化方式初始化map

map<string,int> mymap = {{"alpha", 0 },{"beta", 1 },{"gamma", 2},};cout<<map["beta"]<<endl;

插入数据

m.insert(pair<k,v>(key,value)); //插入键值对 只负责插入数据,不进行修改数据m.insert(make_pair(key,value)); //同上,该函数会自动识别类型//c++11 新增加的插入方式m2.insert({key, value });m.at(key); //访问和修改键值对,所以只负责查找数据和修改数据,不负责插入数据//访问数据和//修改键值//如果不存在会自动插入一个新的元素进去m[key]=value;//KEY可以改吗//可以删除一个Key,然后添加一个新的key

operator[] at() 的区别

相同点:都可以通过key的值访问value

不同点:at不能新增节点,如何节点不存在,则报错

[] 如果key的值不存在,则新创建一个节点

迭代器操作

map迭代器不能进行+和-运算符操作可以使用++--运算符进行遍历

map常见用途

需要建立字符串与整数之间映射关系通过一个唯一的key来建立存储关系的

遍历方式

//for循环遍历for(map<T1,T>::iterator iter=m.begin();iter!=end;iter++){cout<<iter->first<<":"<<iter->seconed<<endl;}//foreach遍历for (auto e:map){cout<<e.first<<":"<<e.seconed<<endl;}

map的基本操作函数

// 插入元素void insert(); // 删除一个元素参数是迭代器 通过find找到key的迭代器,然后删除void erase(iterator iter); // 查找一个元素 通过key的值查找 返回一个迭代器 ,如果没有找到的话会返回 end()iterator find();//通过key访问或修改数据 (不存在会报错)Value at();//修改数据,访问数据,插入数据 (不存在会自动创建)Value operator [Key k];iterator begin();//返回指向map头部的迭代器iterator end(); //返回指向map末尾的迭代器reverse_iterator rbegin(); //返回一个指向map尾部的逆向迭代器reverse_iterator rend(); //返回一个指向map头部的逆向迭代器int size();// 返回map中元素的个数long max_size();// 返回可以容纳的最大元素个数void clear(); // 删除所有元素void count(); // 返回指定key出现的次数 map中key只会出现一次,所以只会返回1或者是0void empty(); // 如果map为空则返回truevoid swap();// 交换两个mapvoid lower_bound(); // 返回键值>=给定元素的第一个位置void upper_bound(); // 返回键值>给定元素的第一个位置void get_allocator(); // 返回map的配置器void equal_range(); // 返回特殊条目的迭代器对void key_comp();// 返回比较元素key的函数map中没有实现这个函数void value_comp(); // 返回比较元素value的函数map中没有实现这个函数

map的优缺点

优点: 有序性：map结构的红黑树自身是有序的,不停的插入数据,总是获取到一个有序的数据时间复杂度低：内部结构时红黑树，红黑树很多操作都是在log(n)的时间复杂度下实现的，因此效率高。 缺点:空间占有率高:因为map内部实现是红黑树，每一个节点都需要额外保存，这样使得每一个节点都占用大量的空间。

multimap 多表映射

#include <map> //头文件

多表映射的结构与map 相似,但是多表映射可以允许有多个重复的键值

特点:

key的值可以重复key的值仍然会进行排序

可以用做多个key时使用,由于会排序,所有key的位置都是连续的并排下去

在无序映射中不能进行直接的键值操作

at()

operator[]

不可以直接通过键的值进行访问

int count()//返回指定key出现的次数,multimap中key会出现多次

unordered_map 无序映射

英 [ˌʌnˈɔːdəd] 美[ʌnˈɔrdərd]

#include<unordered_map> //头文件

c++11以下的的版本使用#include <hash_map>

特点:

无序映射的key的值不会进行排序,但是会去除重复的key值优点：内部结构是哈希表，查找为O(1)，效率高.缺点：哈希表的建立耗费时间。应用场景:对于频繁查找的问题，用unordered_map更高效.底层:是一个哈希表完成的unordered_map记录元素的hash值,根据hash值判断元素是否相同

函数操作

unordered_map 函数操作基本上与map的值一致

只要注意unordered_map的key值不会排序就行

void bucket_count();//返回槽（Bucket）数void bucket_size();//返回槽大小 void bucket();//返回元素所在槽的序号 void rehash();//设置槽数 void reserve();//请求改变容器容量

unordered_multimap

无序多表映射

特点

该容器底层是哈希表实现里面的key既不会去重,也不会排序用法与unordered_map类似虽然不会排序,但重复的数据也会排列在一起

总结

map 的基本使用四个容器之间的区别与特性mapmultimap``unordered_map`unordered_multimap

扩展知识点

set 集合 //集合内的元素是不重复的 类似map中的key元素,但是没有对应的valueset<类型> s;s.inert(10);//插入元素10s.erase(10);//删除元素10s.clear();//清空集合s.size();//集合元素的个数s.empty();//判断集合是否为空集合不会被排序unordered_set 无序集合 //底层实现哈希表(hash)实现的 unordered_set::insertunordered_set::findunordered_set::erasemultiset 集合数据可以重复 std::set<int> numbers {8, 7, 6, 5, 4, 3, 2, 1};

//set 对应map 去重排序set<int> s = {2, 5, 4, 7, 9, 6, 4, 3, 5, 8, 0, 5, 34, 23 };for (auto e : s){cout << e << " ";}cout << endl;//multiset 对应multimap 排序multiset<int> ms = {2, 5, 4, 7, 9, 6, 4, 3, 5, 8, 0, 5, 34, 23 };for (auto e : ms){cout << e << " ";}cout << endl;