map容器

map容器

map的介绍

map 字典 映射 map是一个关系式容器，以模版的方式实现。 map的底层是一个红黑树结构 map由键（key）和值（value）组成 map里所有的key都是有序的，并且不会存在重复。

map的特点

map是一个容器，容器里面存放元素，把这个元素分成两个逻辑块。 第一个逻辑块叫key，第二个逻辑块叫value，他们一一对应。这两个区块当成一个组来管理。 每一个节点的内容都是由一个pair<key,value>构成。

map的基本操作

原型是一个类模版：

template <template k,template v> class pair{ public: k first; v seconed; pair(k& first,v& seconed):first(first),seconed(seconed){} } //通过函数构造 pair<K,V> make_pair(K key,V value);

初始化

map<int,string> m; map<int,string>m={3,“wangwu”}

插入数据：

m.insert(pair<int,string>(66,"zhangsan"); m.insert(make_pair(67, "张三")); m.insert({69,"李四"});

访问数据:

cout<<m.at(66)<<endl; cout<<m[66]<<endl;

注意，at不能修改数据，【】能修改数据，但使用【】时可能会产生新的节点，容易发生错乱，所以，一般来说只用【】来修改数据。如果，【】修改数据时没有找到key，则会新增一个节点。

m[66]=("小明");

【】和insert的区别； insert不能够插入重复的数据，如果数据重复了，就插入无效。 【】能够插入重复的数据，如果插入重复的数据，则修改原本的数据。

迭代器操作

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（） m.erase(55); //查找一个元素； m.find(66); //通过key访问或修改数据 m.at(66); iterator begin(); //返回指向map头部的迭代器 iterator end(); //返回指向map末尾的迭代器 reverse_iterator rbegin(); //返回一个指向map尾部的逆向迭代器 reverse_iterator rend(); //返回一个指向map头部的逆向迭代器 const_reverse_iterator crbeing(); const_reverse_iterator crend(); int size(); // 返回map中元素的个数 long max_size(); // 返回可以容纳的最大元素个数 void clear(); // 删除所有元素 int count(); // 返回指定key出现的次数 map中key只会出现一次,所以只会返回1或者 是0 void empty(); // 判断容器是否为空，如果map为空则返回true void swap(); // 交换两个map内的元素 void lower_bound(); // 返回键值>=给定元素的第一个位置 void upper_bound(); // 返回键值>给定元素的第一个位置 void get_allocator(); // 返回map的配置器 void equal_range(); // 返回特殊条目的迭代器对 void key_comp(); // 返回比较元素key的函数 void value_comp(); // 返回比较元素value的函数

map的优点：

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

multimap 多表映射

特点： key的值可以重复，key的值仍然会排序； 不可以通过键的值进行访问 不可以at() 不可以operator[]

unordered_map 无序映射

#include<unordered_map> 特点： key的值不会重复，key的值不会排序，但是会去重。 优点：内部的结构是哈希表，查找0（1），效率高。 缺点：哈希表的建立耗费时间。 应用场景：对于频繁的查找，用unordered_map更高效。 底层是一个哈希表值。 unordered_map记录元素的hash值,根据hash值判断元素是否相同。

函数操作：

与map的函数操作基本一致。

unordered_multimp 无序多表映射

特点： 该容器既不排序也不去重。 底层是一个哈希表 用法与map相似。 虽然不会排序，但是重复的数据会被排列在一起。

集合set

头文件#include #include <unordered_set>

set容器：

set容器相比其他容器，没有value值，而只有key值

总结

熟悉map，multimap，unorderd_multimap,unordered_map，set的特点，优点，缺点，底层实现。 熟悉map，multimap，unorderd_multimap,unordered_map，set的函数操作。 了解迭代器输出。