前言
map 是有序的键值对容器，元素的键是唯一的，值允许重复。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度，即O(logn)。底层实现为红黑树。
需要包含模板类头文件，需要关键字和存储对象两个模板参数。
这样就定义了一个用int作为索引，并拥有相关联的指向string的指针.
#include <map>
using namespace std;
void init() {
map<int, string> m1;//空对象
//自带初值
map<int, string> m2(
{
{1, "A"},
{3, "C"},
{2, "B"}
}
);
//默认按照索引less递增输出为
// 1 A
// 2 B
// 3 C
map<int, string,greater<int>> m3(
{
{1, "A"},
{3, "C"},
{2, "B"}
}
);
// 3 C
// 2 B
// 1 A
}
有时候为了使用方便，可以对模板类以及指针定义成为更简单的名字。
typedef map<int,string> istrmap;
typedef map<int,string>::iterator IT;
istrmap map1;
IT iter
C++中文在线手册：
https://zh.cppreference.com/
总共有三种插入方式。
void add1() {
map<int, string> m(
{
{1, "A"},
{3, "C"},
{2, "B"}
}
);
// 当索引是不存在的值，成功插入；当索引已经存在，则不进行操作
//调用make_pair函数模板，好处是构造对象不需要参数，用起来更方便
m.insert(pair<int, string>(24, "Z"));
m.insert(map<int, string>::value_type(23, "Y"));
m.insert(make_pair(1, "Z"));
// 索引是原先没有的，直接插入；索引已经存在直接修改
m[22] = "X";
m[3] = "X";
// 当索引是不存在的值，成功插入；当索引已经存在，则不进行操作
m.emplace(pair<int, string>(21, "W"));
m.emplace(pair<int, string>(1, "W"));
map<int, string>::iterator iter;
for (iter = m.begin(); iter != m.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
}
//1 A
// 2 B
// 3 X
// 21 W
// 22 X
// 23 Y
// 24 Z
以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的:
用insert函数和emplace函数插入数据，在数据的插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的。
用索引[]方式就不同了，它可以覆盖对应的值。
强烈建议使用迭代器遍历集合！
void search1() {
map<int, string> m(
{
{1, "A"},
{3, "C"},
{2, "B"}
}
);
map<int, string>::iterator iter;
for (iter = m.begin(); iter != m.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
}
//1 A
// 2 B
// 3 C
下面介绍一个反面例子，看看直接使用索引去遍历而产生的结果。
void search2() {
map<int, string> m(
{
{1, "A"},
{3, "C"},
{5, "B"}
}
);
cout << "遍历前元素的个数：" << m.size() << endl;
for (int i = 0; i < m.size(); i++) {
cout << i << ' ' << m[i] << endl;
}
cout << "遍历后元素的个数：" << m.size();
}
//遍历前元素的个数：3
// 0
// 1 A
// 2
// 3 C
// 4
// 5 B
// 遍历后元素的个数：6
很明显，因为没有判定是否存在而是直接无脑使用，原意是遍历一遍集合，结果却是修改了集合！
可以清空，也可以用迭代器删除指定范围元素或者单个元素。
但是在遍历的时候要注意，使用迭代器删除元素后，迭代器可能会变成类似野指针的存在！
/*
* 删除有两种方式，
* clear是直接清空
* erase是删除指定迭代器范围内的数字
* 也可以用来删除指定的单个元素
* */
void del1() {
map<int, string> m(
{
{1, "A"},
{2, "B"},
{3, "C"}
}
);
//清空
m.clear();//{}
if (m.empty()) {//判断Vector为空则返回true
m.insert(pair<int, string>(4, "D"));
m.insert(pair<int, string>(5, "E"));
m.insert(pair<int, string>(6, "F"));
//用迭代器删除单个元素，注意指针被删除后就失效了
map<int, string>::iterator iter = m.begin();
m.erase(iter);//所剩元素{5,E},{6,F}，此时的iter仍然是{4,D}
cout << "错误的迭代器内容：" << iter->first << ' ' << iter->second << endl;
//删除一个范围， 只保留最后一个
m.erase(m.begin(), ++m.end()); //{6,F}
//通过关键字索引的数据存在就删除，并返回1；如果关键字索引的数据不存在就不操作，并返回0
m.erase(2);
}
map<int, string>::iterator iter;
for (iter = m.begin(); iter != m.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
}
如果想要遍历整个map，并删除所有满足指定数值的应该如下：
/*
* 遍历集合以删除指定条件的元素
* */
void del2() {
map<int, string> m(
{
{1, "A"},
{2, "B"},
{3, "C"}
}
);
map<int, string>::iterator iter;
// 删除元素后，期望iter指针是继续指向{3,C}的，
// 但是经过iter++后，竟然又到了上一个元素！
// 很明显，删除元素后的迭代器变成了类似野指针的存在！
// for (iter = m.begin(); iter != m.end(); iter++) {
// if (iter->first == 2 || iter->second == "B") {
// m.erase(iter);
// }
// cout << iter->first << ' ' << iter->second << endl;
// }
//结果是：
// 1 A
// 2 B
// 1 A
// 3 C
// 正确做法应该是先复制出来一个临时迭代器
// 接着将原来的迭代器后移一位指向正常的元素
// 最后用临时迭代器删除指定元素！
// 第二步和第三步不能反了，否则也会影响到原来正常的迭代器！
for (iter = m.begin(); iter != m.end();) {
if (iter->first == 2) {
map<int, string>::iterator iterTemp = iter;
++iter;
m.erase(iterTemp);
} else {
cout << iter->first << ' ' << iter->second << endl;
++iter;
}
}
// 结果是
// 1 A
// 3 C
}
用迭代器删除元素，先是断言确定迭代器不是尾迭代器，接着将当前迭代器复制到一个新对象，最后返回的就是这个新的迭代器对象。调用_M_erase_aux方法删除迭代器指向的元素，并且节点数目减一。
void _M_erase_aux(const_iterator __position)
{
_Link_type __y =
static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
(const_cast<_Base_ptr>(__position._M_node),
this->_M_impl._M_header));
_M_drop_node(__y);
--_M_impl._M_node_count;
}
count函数是用来统计一个元素在当前容器内的个数。由于Map的特性，所以只能返回1或者0。
/*
* 用count函数寻找元素，
* */
void find1(set<int> s ){
if (s.count(4) == 1) {
cout << "元素4存在"<<endl;
}
if (s.count(8) == 0) {
cout << "元素8不存在";
}
}
追查源码，我发现他是用的find方法，将结果跟尾迭代器比较，如果不等于尾迭代器就是找到了，返回1；反之就是没找到，返回0。
find(const _Key& __k) const
{
const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
return (__j == end()
|| _M_impl._M_key_compare(__k,
_S_key(__j._M_node))) ? end() : __j;
}
/*
* 用find函数寻找元素，
* */
void find2(set<int> s ){
if (s.find(4)!= s.end() ) {
cout << "元素4存在"<<endl;
}else{
cout << "元素4不存在";
}
if (s.find(8)!= s.end() ) {
cout << "元素8存在"<<endl;
}else{
cout << "元素8不存在";
}
}
而底层是调用的不带const标的find函数，函数体是一样的！而其中的核心逻辑就是用_M_lower_bound函数查找来确定位置。
_M_lower_bound(_Link_type __x, _Base_ptr __y, const _Key &__k){
while (__x != 0) {
if (!_M_impl._M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
}
return iterator(__y);
}
map中默认就是使用key排序的，自动按照key的大小，增序存储，这也是作为key的类型必须能够进行 < 运算比
较的原因。
首先看一眼map模板的定义，重点看下第三个参数：class Compare = less<Key> 。
template < class Key， class T， class Compare = less<Key>，
class Allocator = allocator<pair<const Key，T> > > class map;
与less相对的还有greater，都是STL里面的一个函数对象，那么什么是函数对象呢？
函数对象：即调用操作符的类，其对象常称为函数对象（function object），它们是行为类似函数的对象。表现出一个函数的特征，就是通过“对象名+(参数列表)”的方式使用一个 类，其实质是对operator()操作符的重载。
具体的例子可以去看另一篇文章：Cpp浅析系列-STL之set，这里就不赘述了。
逻辑上是先转为vector数组，接着将数组用指定的规则重新排序得到排序好的结果。至于是否用排序好的数组去转换为map对象则是看要求了。
bool Special(pair<string, int> a, pair<string, int> b) {
return a.second < b.second;//从小到大排序
}
void specialCompare() {
// 初始map集合
map<string, int> m;
m["a"] = 2;
m["b"] = 3;
m["c"] = 1;
// 转为vector集合
vector<pair<string, int> > demo(m.begin(), m.end());
for (auto it = demo.begin(); it != demo.end(); ++it) {
cout << (*it).first << " " << (*it).second << endl;
}
cout << endl;
// 排序后查看效果
sort(demo.begin(), demo.end(), Special);
for (auto it = demo.begin(); it != demo.end(); ++it) {
cout << (*it).first << " " << (*it).second << endl;
}
cout << endl;
// 转换为新的map集合，区别就是前后类型反了。
map<int, string> m2;
for (vector<pair<string, int> >::iterator it = demo.begin(); it != demo.end(); ++it){
m2[(*it).second]=(*it).first;
}
map<int, string>::iterator iter;
for (iter = m2.begin(); iter != m2.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
}
//a 2
// b 3
// c 1
//
// c 1
// a 2
// b 3
//
// 1 c
// 2 a
// 3 b
C++中的STL中map用法详解
C++ STL中Map的按Key排序和按Value排序
感谢现在努力的自己。
