C++中的STL中map用法详解(零基础入门)

什么是map？

map 是 C++ 中的关联式容器，它可以存储 key-value 键值对，其中 key 是唯一的。在 map 中，key 和 value 可以是任何可比较的数据类型。

map 可以用于快速查找和插入数据。其内部实现是基于红黑树（一种自平衡的二叉查找树）的。

map的基本用法

map 定义格式：map<key_type, value_type> map_name

其中，key_type 和 value_type 表示键值对中的 key 和 value 的数据类型。

// 声明一个string为key, int为value的map
#include <map>
#include <string>
using namespace std;

int main()
{
    map<string, int> student;
    return 0;
}

向 map 中插入键值对：

// 声明一个string为key, int为value的map
#include <map>
#include <string>
using namespace std;

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

    // 向 map 中插入键值对
    student.insert(pair<string, int>("张三", 90));
    student.insert(pair<string, int>("李四", 80));
    student.insert(pair<string, int>("王五", 70));

    return 0;
}

从 map 中查找：

// 声明一个string为key, int为value的map
#include <map>
#include <string>
using namespace std;

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

    // 向 map 中插入键值对
    student.insert(pair<string, int>("张三", 90));
    student.insert(pair<string, int>("李四", 80));
    student.insert(pair<string, int>("王五", 70));

    // 查找键值对
    map<string, int>::iterator it = student.find("张三");
    if (it != student.end())
    {
        cout << "张三的成绩为：" << it->second << endl;
    }

    return 0;
}

map的常用操作

插入元素

插入元素可以使用 insert 函数或 [] 运算符。

使用 insert 函数：

student.insert(pair<string, int>("张三", 90));

使用 [] 运算符：

student["张三"] = 90;

删除元素

使用 erase 函数可以删除元素：

student.erase("张三");

查找元素

使用 find 函数查找元素：

map<string, int>::iterator it = student.find("张三");
if (it != student.end())
{
    cout << "张三的成绩为：" << it->second << endl;
}

获取元素数量

使用 size 函数获取元素数量：

int n = student.size();

示例一：统计单词出现次数

下面是一个利用 map 统计单词出现次数的示例代码。

#include <iostream>
#include <map>
#include <string>
#include <sstream>

using namespace std;

int main()
{
    string text = "hello world hello";
    map<string, int> word_count;
    istringstream iss(text);
    string word;
    while (iss >> word)
    {
        ++word_count[word];
    }
    for (const auto& pair : word_count)
    {
        cout << pair.first << "出现了" << pair.second << "次" << endl;
    }
    return 0;
}

输出结果：

hello出现了2次
world出现了1次

示例二：拼图游戏

下面是一个利用 map 实现拼图游戏的示例代码。

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

const int n = 3;
int a[n][n] = {
    {2, 1, 5},
    {3, 0, 4},
    {7, 8, 6}
};

const int dir[][2] = {
    {-1, 0},
    {1, 0},
    {0, -1},
    {0, 1}
};

int hash()
{
    int h = 0;
    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<n; ++j)
        {
            h = h * 10 + a[i][j];
        }
    }
    return h;
}

int main()
{
    map<int, string> dir_map;
    dir_map[0] = "up";
    dir_map[1] = "down";
    dir_map[2] = "left";
    dir_map[3] = "right";

    map<int, pair<int, int>> pos;
    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<n; ++j)
        {
            pos[a[i][j]] = make_pair(i, j);
        }
    }

    map<int, string> ans_map;
    ans_map[hash()] = "";

    bool flag = false;
    string ans;
    while (!ans_map.empty())
    {
        map<int, string>::iterator it = ans_map.begin();
        int h = it->first;
        string str = it->second;
        ans_map.erase(it);
        int x, y;
        for (int i=0; i<n; ++i)
        {
            for (int j=0; j<n; ++j)
            {
                if (a[i][j] == 0)
                {
                    x = i;
                    y = j;
                    break;
                }
            }
        }

        for (int i=0; i<4; ++i)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            swap(a[x][y], a[nx][ny]);  // 交换位置
            int h2 = hash();  // 计算hash值
            if (!ans_map.count(h2))  // 如果该状态没有出现过
            {
                ans_map[h2] = str + dir_map[i];  // 记录答案
            }
            if (h2 == 123456780)  // 找到目标状态
            {
                ans = ans_map[h2];
                flag = true;
                break;
            }
            swap(a[x][y], a[nx][ny]);   // 恢复状态
        }
        if (flag) break;
    }

    cout << ans << endl;

    return 0;
}

输出结果：

rightdownright