C++ map

C++ 中 map 提供的是一种键值对容器，里面的数据都是成对出现的。

每一对的第一个值称之为关键字key，每个关键字只能在map中出现一次；

第二个值称之为关键字的对应值。

基本概念

• std::map 是关联式容器，存储键值对(key-value)
• 键唯一，自动排序
• 底层实现：红黑树（平衡二叉搜索树）
• 常见应用：字典、映射表、频率统计、索引查找

Map使用

1. 需要导入头文件

    #include <map>
   

2. map对象是一个模板类，需要关键字和存储对象两个模板参数

    std::map<int, std::string> person;
   

3. 可以对模板进行类型定义使其使用更方便

    typedef std::map<int, std::string> MAP_INT_STRING;
    MAP_INT_STRING person;
   

基本语法

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string, int> scores;

    // 插入
    scores["Alice"] = 90;
    scores["Bob"] = 85;
    scores.insert({"Charlie", 92});

    // 遍历
    for (auto &p : scores) {
        cout << p.first << " => " << p.second << endl;
    }

    // 查找
    if (scores.find("Alice") != scores.end()) {
        cout << "Alice's score: " << scores["Alice"] << endl;
    }

    // 删除
    scores.erase("Bob");

    return 0;
}

输出：

Alice => 90
Bob => 85
Charlie => 92
Alice's score: 90

使用方法

构造

std::map<string, int> scores;

添加数据

• insert()函数

map<string, int> scores;

scores.insert(make_pair("Charlie", 92));
scores.insert({"Charlie", 92});
scores.insert(pair<string, int>("Charlie", 92));
scores.insert(pair<const string, int>("Charlie", 92));
scores.insert(map<string, int>::value_type("Charlie", 92));

• 数组插入

scores["Charlie"] = 92;

遍历

• 前向迭代器

    map<string, int> scores;
  
    map<string, int>::iterator it;
    map<string, int>::iterator itEnd;
    it = scores.begin();
    itEnd = scores.end();
  
    while(it != itEnd) {
        cout << it->first << " " << it->second << endl;
        it++;
    }
  

• 反向迭代器

    map<string, int> scores;
  
    map<string, int>::reverse_iterator it;
    for (iter = scores.rbegin(); iter != scores.rend(); iter++) {
        cout << iter->first << " " << iter->second << endl;
    }
  

• 数组形式

    map<string, int> scores;
  
    scores.insert(map<string, int>::value_type("Charlie", 92));
    scores["John"] = 44;
    scores["Hand"] = 28;
  
    int nSize = scores.size();
    for (int n = 1; n <= size; n++) {
        cout << iter->first << " " << iter->second << endl;
    }
  

查找

find()函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器

map<string, int> scores;

map<string, int>::iterator l_it;
l_it = scores.find("Charlie");

if (l_it == scores.end())
	cout << "We could not find" << endl;
else
	cout << "We find Charlie is " << l_it->second << endl;

删除

• 按键删除

    map<string, int> scores;
  
    scores["Alice"] = 90;
    scores["Bob"] = 85;
    scores["Charlie"] = 92;
  
    scores.erase("Bob");
  

  如果Bob这个键值对不存在，则什么都不做也不会报错

• 按迭代器删除

    auto it = scores.find("Alice");
    if (it != scores.end()) {
        scores.erase(it);  // 删除 Alice
    }
  

• 按范围删除

    scores.erase(scores.begin(), scores.find("Charlie"));
  

  删除从begin()到Charlie之前的所有元素

• 清空map

    scores.clear();
  

排序

Map中的元素是自动按key升序排序，因此不能对map使用sort函数

#include <map> 
#include <iostream>
using namespace std;
int main( )
{
	map < int, int > m1;
	map < int, int >::iterator m1_Iter;
	m1.insert ( pair < int, int >  ( 1, 20 ) );
	m1.insert ( pair < int, int >  ( 4, 40 ) );
	m1.insert ( pair < int, int >  ( 3, 60 ) );
	m1.insert ( pair < int, int >  ( 2, 50 ) );
	m1.insert ( pair < int, int >  ( 6, 40 ) );
	m1.insert ( pair < int, int >  ( 7, 30 ) );
	cout << "The original map m1 is:"<<endl;
	for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
	  cout << m1_Iter->first << " " << m1_Iter->second << endl;
}

输出结果：

The original map m1 is:
1 20
2 50
3 60
4 40
6 40
7 30

可以用比较函数进行降序排序：

#include <iostream>
#include <map>

using namespace std;

struct Desc {
    bool operator()(const int &a, const int &b) const {
        return a > b; // 降序
    }
};

int main() {
    map<int, string, Desc> m;
    m[1] = "one";
    m[3] = "three";
    m[2] = "two";

    for (auto &p : m) cout << p.first << " " << p.second << endl;
}

程序输出：

3 three
2 two
1 one

在上面的程序中，关键点在于Desc函数，std::map的完整模板定义：

template <
    class Key,
    class T,
    class Compare = std::less<Key>,   // 比较器，默认升序
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;

Compare决定了红黑树里键的排序顺序，每次在map中插入元素时，都会调用Desc()(a, b)来比较键的大小，a > b表示如果a大于b，就认为a应该排在前面，因此结果是降序排序

swap交换

swap的作用是将两个容器交换，而不是一个容器的两个元素交换

m1.swap(m2);

// 或
std::swap(m1, m2);

程序示例：

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string, int> scores1 = {
        {"Alice", 90},
        {"Bob", 85}
    };

    map<string, int> scores2 = {
        {"Charlie", 92},
        {"David", 88}
    };

    cout << "Before swap:\n";
    cout << "scores1:\n";
    for (auto &p : scores1) cout << p.first << " => " << p.second << endl;
    cout << "scores2:\n";
    for (auto &p : scores2) cout << p.first << " => " << p.second << endl;

    scores1.swap(scores2);  // 交换内容

    cout << "\nAfter swap:\n";
    cout << "scores1:\n";
    for (auto &p : scores1) cout << p.first << " => " << p.second << endl;
    cout << "scores2:\n";
    for (auto &p : scores2) cout << p.first << " => " << p.second << endl;

    return 0;
}

输出

Before swap:
scores1:
Alice => 90
Bob => 85
scores2:
Charlie => 92
David => 88

After swap:
scores1:
Charlie => 92
David => 88
scores2:
Alice => 90
Bob => 85

常用操作

操作	方法
插入	m[key] = value; / m.insert({key, value});
查找	m.find(key) 返回迭代器，没找到则 end()
删除	m.erase(key) / m.erase(it)
遍历	for (auto &p : m)
大小	m.size()
清空	m.clear()
判断是否存在	if (m.count(key))

常用方法

方法	作用
begin()	返回指向 map 第一个元素 的迭代器
clear()	删除所有元素
count(const Key& k)	返回 key 出现的次数（map 中 key 唯一，所以结果是 0 或 1）
empty()	如果 map 为空则返回 true
end()	返回指向 map 尾后元素 的迭代器（不指向实际元素）
equal_range(const Key& k)	返回一对迭代器，范围包含所有等于 key 的元素（map 里最多一个元素）
erase()	删除一个元素（按 key、迭代器或范围）
find(const Key& k)	查找一个元素，返回迭代器，不存在则返回 end()
get_allocator()	返回 map 的分配器对象（一般很少用）
insert()	插入元素（返回 pair<iterator,bool>）
key_comp()	返回用于比较 key 的比较器对象
lower_bound(const Key& k)	返回第一个 key >= k 的迭代器
max_size()	返回 map 能容纳的最大元素个数
rbegin()	返回指向 map 最后一个元素 的逆向迭代器
rend()	返回指向 map 头部之前位置 的逆向迭代器
size()	返回 map 中元素的数量
swap(map& x)	交换两个 map 的内容
upper_bound(const Key& k)	返回第一个 key > k 的迭代器
value_comp()	返回用于比较 pair<const Key, T> 的比较器对象