深度解析C++中的map的使用

原创

凯子坚持C

发布于 2025-01-04 10:26:30

570

map的概念

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是O(logN)，迭代器遍历是走的中序，所以是按key有序顺序遍历的。

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // 
map::allocator_type
           > class map;

pair类型介绍

map的底层是红黑树节点中的数据，使用pair<Key,T>存储键值对数据

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair 
{
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    
    pair(): first(T1()), second(T2())
    {}
 
    pair(const T1& a, const T2& b): first(a), second(b)
    {}
    
    template<class U, class V> 
    pair (const pair<U,V>& pr): first(pr.first), second(pr.second)
    {}
};
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{
    return ( pair<T1,T2>(x,y) );
}

map的构造

map的构造我们关注以下几个接口即可。

map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序;支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1)无参默认构造
explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());
// range (2)迭代器区间   
template <class InputIterator>
  map (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& = allocator_type());
// copy (3)拷贝构造   
map (const map& x);
// initializer list (5) initializer   
map (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());
     
//   迭代器是一个双向迭代器
iterator   -> a bidirectional iterator to const value_type
//正向迭代器   
iterator begin();
iterator end();
//反向迭代器   
reverse_iterator rbegin();
reverse_iterator rend();

map的增删查

通过隐士类型转换的直接插入是最简单的

int main()
{
	map<string, string>dict = { {"left","左边"},{"right","右边"} ,{"insert","插入"} ,{"string","字符串"} };

	pair<string, string>kv1("first", "第一个");
	dict.insert(kv1);

	//匿名对象隐式类型转换
	dict.insert(pair<string, string>("first", "第一个"));

	//我们调用make_pair这个模版参数将我们传的两个参数的模版进行推导出来了
	//我们使用make_pair就不用进行模版参数的声明了，直接让他们推
	//make_pair是一个函数模版
	dict.insert(make_pair("sort", "排序"));

	dict.insert({ "auto","自动的" });//多参数的隐士类型转换就行了，这种是最简单的
	for (auto& e : dict)//加上引用的话，那么就相当于将*it给到e
	{//不加引用的话拷贝构造的时间就会很多了
		cout << e.first << ":" << e.second << endl;
	}

	return 0;
}

通过加等的函数赋值重载的话我们是可以实现这个数据的修改操作的

但是只能对second进行修改的操作的，不能对first进行修改的

find函数的返回值

find 函数是 C++ 标准库中的 std::map 和 std::unordered_map 容器提供的一个方法，用来在容器中查找指定的键。它返回的是一个迭代器。

具体来说：

`find` 函数的行为

auto ret = map.find(key);

1. 如果键 `key` 存在：

返回一个指向 key 所对应键值对的迭代器。
通过这个迭代器，可以访问键和它的值：

ret->first  // 键 (key)
ret->second // 值 (value)

2. 如果键 `key` 不存在：

返回一个特殊的迭代器：map.end()。
map.end() 表示容器的尾后位置，不指向任何有效元素。
所以可以用以下条件来判断键是否存在：

if (ret == map.end()) {
    // 键不存在
} else {
    // 键存在
}

举例说明

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

using namespace std;

int main() {
    map<string, int> countMap = {{"apple", 2}, {"banana", 3}};

    // 查找键 "apple"
    auto it = countMap.find("apple");
    if (it != countMap.end()) {
        cout << "Found: " << it->first << " -> " << it->second << endl;
    } else {
        cout << "Key not found" << endl;
    }

    // 查找键 "orange"
    auto it2 = countMap.find("orange");
    if (it2 != countMap.end()) {
        cout << "Found: " << it2->first << " -> " << it2->second << endl;
    } else {
        cout << "Key not found" << endl;
    }

    return 0;
}

输出结果：

Found: apple -> 2
Key not found

总结：

find(key) 返回一个迭代器：
指向 key 对应的键值对（如果找到）。
等于 map.end()（如果没找到）。
通过 ret->first 和 ret->second 可以访问键值对中的键和值。
常用于判断键是否存在或直接操作键值对。

map的构造遍历以及增删查使用详例

*it 是 map 中当前迭代器指向的元素，这个元素是一个 pair 类型，其中包含了 key-value 键值对。

(*it).first：访问当前键值对中的键（key）。

(*it).second：访问当前键值对中的值（value）。

当然我们也是可以使用范围for的

#include<iostream>
using namespace std;
#include<map>
int main()
{
	pair<string, string> kv1 = { "left","左边" };//键值对

	//imnitializer_list构造及迭代遍历
	map<string, string>dict = { {"left","左边"},{"right","右边"} ,{"insert","插入"} ,{"string","字符串"} };
	//将键值对使用map进行存储起来
	//	auto it = dict.begin();
	map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		//cout << (*it).first << ":"<< (*it).second<<endl;//pair这个类型不支持流插入的
		cout << it->first << ":" << it->second << endl;//pair这个类型不支持流插入的
		//这个箭头是运算符重载的箭头，数据的指针，一个pair的指针
		++it;
	}
	//pair这个类型是不支持流插入的
	cout << endl;

	for (auto& e : dict)//加上引用的话，那么就相当于将*it给到e
	{//不加引用的话拷贝构造的时间就会很多了
		cout << e.first << ":" << e.second << endl;
	}
	return 0;
}
//*it 是 map 中当前迭代器指向的元素，这个元素是一个 pair 类型，其中包含了 key-value 键值对。
//(*it).first：访问当前键值对中的 键（key）。
//(*it).second：访问当前键值对中的 值（value）。

map中的operator[]的使用

insert除了插入还有查找的功能

插入成功的话就返回插入成功的位置的迭代器，找到这个king的节点

插入失败也会返回king位置节点的迭代器的

first是迭代器的

second是是否插入成功，只可能是true或者是false

int main3()
{
	map<string, string>dict;
	dict.insert(make_pair("sort", "插入"));

	//key不存在->插入
	dict["insert"];

	//左边
	dict["left"] = "左边";

	//修改
	dict["left"] = "左边、剩余";

	cout << dict["left"] << endl;

	return 0;
}

int main()
{
	string arr[] = { "苹果","西瓜","西瓜" ,"西瓜" ,"苹果" ,"香蕉","香蕉" };
	map<string, int>countMap;//第二个参数是次数
	//遍历这个数组中的所有水果
	for (const auto& str : arr)
	{
		//auto ret = countMap.find(str);
		////find函数返回一个特殊的迭代器：map.end()。
		////map.end() 表示容器的尾后位置，不指向任何有效元素。
		//if (ret == countMap.end())//find函数返回一个指向 key 所对应键值对的迭代器。就是说明不在
		//{
		//	countMap.insert({ str,1 });//那么我们进行插入的操作
		//}
		//else
		//{
		//	ret->second++;//那么我们进行这个次数的增加就行了
		//}
		countMap[str]++;

	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}

	//结构化绑定声明
	//for (const auto& [key, value] : countMap)
	//{
	//	cout << key << ": " << value << endl;
	//}
	//ey：表示 map 中的键（std::map 的第一个成员 first）。
	//value：表示 map 中的值（std::map 的第二个成员 second）。
	//结构化绑定的语法可以直接将 std::pair 解包成独立的变量，避免使用 it->first 和 it->second 的冗长语法。

	return 0;
}

692. 前K个高频单词

https://leetcode.cn/problems/top-k-frequent-words/

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        //按照次数进行比较
        //仿函数
        struct Compare
        {
            //比较两个键值对 kv1 和 kv2
            bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2)
            {
                return kv1.second>kv2.second;
            }
        };
        //统计处次数
        //使用 map 记录单词的频率
        map<string,int>countMap;
        //遍历输入单词列表 words，每遇到一个单词，就增加它在 countMap 中对应的计数值。
        for(auto&str:words)
        {
            countMap[str]++;
        }

        //sort是不能对map进行排序的
        //利用迭代器区间进行初始化操作

        //我们将这个map中的数据存储在vector中，利用迭代器
        //map 是有序的，但不支持直接排序。
        //将 map 的内容通过迭代器范围转换为一个 vector，以便后续对 vector 进行排序。
        vector<pair<string,int>>v(countMap.begin(),countMap.end());

        //sort默认是升序，我们期望排降序,但是是不稳定的，
        //stable_sort就是稳定的
        //使用 stable_sort 对 vector 进行排序，保证当两个单词频率相同时，按字典序排序
        stable_sort(v.begin(),v.end(),Compare());//然后进行排序的操作

        //创建一个结果向量 retv，从排序后的 vector 中取出前 k 个单词（即频率最高的单词
        vector<string>retv;
        for(size_t i=0;i<k;++i)
        {
            retv.push_back(v[i].first);
        }
        return retv;
    }
};

/*
统计频率：
countMap = { "i": 2, "love": 2, "leetcode": 1, "coding": 1 }
排序后：
v = [("i", 2), ("love", 2), ("coding", 1), ("leetcode", 1)]
取前 2 个：
结果为 ["i", "love"]。
*/

//std::sort(起始迭代器, 结束迭代器, 比较器);

使用 stable_sort 对 vector 进行排序，保证当两个单词频率相同时，按字典序排序

还有一种解决方法

我们在这个仿函数中多添加一种情况

次数大的在前面

次数相等的时候我们的字典数小的在前面，那么我们的后续排序可以对稳定性没有要求了

我们直接手动控制仿函数

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        //按照次数进行比较
        //仿函数
        struct Compare
        {
            //比较两个键值对 kv1 和 kv2
            bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2)
            {
                return kv1.second>kv2.second||//次数大的在前面
                (kv1.second==kv2.second&&kv1.first<kv2.first);//次数相等的时候我们期望字典数小的在前面
            }
        };
        //统计处次数
        //使用 map 记录单词的频率
        map<string,int>countMap;
        //遍历输入单词列表 words，每遇到一个单词，就增加它在 countMap 中对应的计数值。
        for(auto&str:words)
        {
            countMap[str]++;
        }

        //sort是不能对map进行排序的
        //利用迭代器区间进行初始化操作

        //我们将这个map中的数据存储在vector中，利用迭代器
        //map 是有序的，但不支持直接排序。
        //将 map 的内容通过迭代器范围转换为一个 vector，以便后续对 vector 进行排序。
        vector<pair<string,int>>v(countMap.begin(),countMap.end());

        //sort默认是升序，我们期望排降序,但是是不稳定的，
        //stable_sort就是稳定的
        //使用 stable_sort 对 vector 进行排序，保证当两个单词频率相同时，按字典序排序
        sort(v.begin(),v.end(),Compare());//然后进行排序的操作

        //创建一个结果向量 retv，从排序后的 vector 中取出前 k 个单词（即频率最高的单词
        vector<string>retv;
        for(size_t i=0;i<k;++i)
        {
            retv.push_back(v[i].first);
        }
        return retv;
    }
};

/*
统计频率：
countMap = { "i": 2, "love": 2, "leetcode": 1, "coding": 1 }
排序后：
v = [("i", 2), ("love", 2), ("coding", 1), ("leetcode", 1)]
取前 2 个：
结果为 ["i", "love"]。
*/

//std::sort(起始迭代器, 结束迭代器, 比较器);

pair的具体使用‘

pair也是模版

存储键值对的

std::pair 是 C++ 标准模板库 (STL) 提供的一个非常方便的工具类，用于存储两个相关联的值。它是一个模板类，可以存储不同类型的两个值。以下是对 pair 使用的详细介绍。

1. `pair` 的基本定义

std::pair 的定义如下：

template <class T1, class T2>
struct pair {
    T1 first;
    T2 second;
};

first：表示第一个元素。
second：表示第二个元素。

它是一个简单的容器，可以将两个数据绑定在一起。

2. 创建和初始化 `pair`

方法 1：使用构造函数

#include <iostream>
#include <utility> // 包含 pair

int main() {
    std::pair<int, std::string> p(1, "apple");
    std::cout << p.first << " " << p.second << std::endl;
    return 0;
}

输出：

1 apple

方法 2：使用 `std::make_pair`

#include <iostream>
#include <utility>

int main() {
    auto p = std::make_pair(1, "banana");
    std::cout << p.first << " " << p.second << std::endl;
    return 0;
}

输出：

1 banana

方法 3：使用列表初始化

#include <iostream>
#include <utility>

int main() {
    std::pair<int, double> p = {3, 3.14};
    std::cout << p.first << " " << p.second << std::endl;
    return 0;
}

输出：

3 3.14

3. 修改 `pair` 的值

#include <iostream>
#include <utility>

int main() {
    std::pair<int, std::string> p(10, "orange");
    p.first = 20;                // 修改 first 的值
    p.second = "grape";          // 修改 second 的值
    std::cout << p.first << " " << p.second << std::endl;
    return 0;
}

输出：

20 grape

4. `pair` 的常见用法

(1) 在容器中使用

pair 通常与 STL 容器（如 std::map 或 std::vector）结合使用。

在 `map` 中使用

std::map 使用 pair 来存储键值对：

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> fruit_count;
    fruit_count["apple"] = 3;
    fruit_count["banana"] = 5;

    for (const auto &entry : fruit_count) {
        std::cout << entry.first << " " << entry.second << std::endl;
    }
    return 0;
}

输出：

apple 3
banana 5

在 `vector` 中使用

std::vector 可以存储 pair 元素：

#include <iostream>
#include <vector>
#include <utility>

int main() {
    std::vector<std::pair<std::string, int>> v = {
        {"apple", 3}, {"banana", 5}, {"cherry", 2}
    };

    for (const auto &p : v) {
        std::cout << p.first << ": " << p.second << std::endl;
    }
    return 0;
}

输出：

apple: 3
banana: 5
cherry: 2

(2) 用于返回多个值

pair 可以用来从函数返回多个值：

#include <iostream>
#include <utility>

std::pair<int, int> find_min_max(const std::vector<int>& nums) {
    int min_val = nums[0], max_val = nums[0];
    for (int num : nums) {
        if (num < min_val) min_val = num;
        if (num > max_val) max_val = num;
    }
    return {min_val, max_val};
}

int main() {
    std::vector<int> nums = {3, 1, 4, 1, 5, 9};
    auto result = find_min_max(nums);
    std::cout << "Min: " << result.first << ", Max: " << result.second << std::endl;
    return 0;
}

输出：

Min: 1, Max: 9

5. `pair` 的比较操作

pair 支持按字典序的比较：

首先比较 first，如果 first 相等，再比较 second。
支持 ==, !=, <, >, <=, >= 等操作符。

#include <iostream>
#include <utility>

int main() {
    std::pair<int, int> p1 = {1, 2};
    std::pair<int, int> p2 = {1, 3};

    if (p1 < p2) {
        std::cout << "p1 is less than p2" << std::endl;
    }
    return 0;
}

输出：

p1 is less than p2

6. 常见问题

(1) 自定义排序 `pair`

可以结合 sort 或 stable_sort 使用自定义比较规则：

#include <iostream>
#include <vector>
#include <algorithm>

bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.second > b.second; // 按 second 降序
}

int main() {
    std::vector<std::pair<int, int>> v = {{1, 3}, {2, 2}, {3, 5}};
    std::sort(v.begin(), v.end(), compare);

    for (const auto& p : v) {
        std::cout << "(" << p.first << ", " << p.second << ") ";
    }
    return 0;
}

输出：

(3, 5) (1, 3) (2, 2)

总结

pair 用于存储两个值，可以是不同的类型，方便关联信息的存储。
常见操作：初始化、修改值、结合容器（如 map、vector）使用。
支持比较操作，方便排序和查找。
可以结合 std::make_pair 或列表初始化简化代码。

如果你还有更具体的问题，可以进一步探讨！

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S11#重启人生

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S11#重启人生

登录后参与评论

0 条评论

热度