C++：map类

本文详细介绍了C++中map类的使用。map底层采用红黑树实现，具有O(logN)的增删查改效率，支持按key有序遍历。文章讲解了map的声明方式、pair类型、构造方法、增删查接口，重点分析了operator[]的多功能特性（插入、修改、查找）。同时对比了multimap与map的区别，并通过力扣题目展示了map的实际应用场景，如随机链表复制和前K高频单词统计。最后提供了两种解决前K高频单词问题

诗瑾峤

722人浏览 · 2026-02-12 14:54:25

诗瑾峤 · 2026-02-12 14:54:25 发布

上篇文章：C++：set类

1.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类型介绍

pair是 C++ 标准库提供的通用模板类，专门用来封装 “两个关联的值”；而 map 的每一个元素本质上就是一个pair<const Key, Value>对象。

map底层的红黑树节点中的数据，使用pair<Key，T>存储键值对数据，每个节点存储的都是一个pair对象，但有个关键特性：map中 pair 的 first（键）是 const 类型，无法直接修改。

默认构造：

default (1)	
constexpr pair();

copy / move (2)	
template<class U, class V> pair (const pair<U,V>& pr);
template<class U, class V> pair (pair<U,V>&& pr);
pair (const pair& pr) = default;
pair (pair&& pr) = default;

initialization (3)	
pair (const first_type& a, const second_type& b);
template<class U, class V> pair (U&& a, V&& b);

piecewise (4)	
template <class... Args1, class... Args2>
  pair (piecewise_construct_t pwc, tuple<Args1...> first_args,
                                   tuple<Args2...> second_args);

核心结构：

只有两个公有成员变量：

template <typename T1, typename T2>
struct pair {
    T1 first;   // 第一个值（map中对应key）
    T2 second;  // 第二个值（map中对应value）
    
    // 构造函数等（标准库已实现）
};

示例：

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) );
}

2.map系列使用

2.1map的构造

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();

2.2map的增删查

map增接口，插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value

关注以下几个接口：

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 
pair<iterator,bool> insert (const value_type& val);

// 列表插⼊，已经在容器中存在的值不会插⼊ 
void insert (initializer_list<value_type> il);

// 迭代器区间插⼊，已经在容器中存在的值不会插⼊ 
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

// 查找k，返回k所在的迭代器，没有找到返回end() 
iterator find (const key_type& k);

// 查找k，返回k的个数 
size_type count (const key_type& k) const;

// 删除⼀个迭代器位置的值 
iterator erase (const_iterator position);

// 删除k，k存在返回0，存在返回1 
size_type erase (const key_type& k);

// 删除⼀段迭代器区间的值 
iterator erase (const_iterator first, const_iterator last);

// 返回⼤于等k位置的迭代器 
iterator lower_bound (const key_type& k);

// 返回⼤于k位置的迭代器 
const_iterator lower_bound (const key_type& k) const;

示例：

map<string, string>dict;

// c++98
pair<string, string>kv1("sort", "排序");
dict.insert(kv1);
dict.insert(pair<string, string>("left", "左边"));
dict.insert(make_pair("left", "左边"));

// C++11
dict.insert({ "right", "右边" });
//dict.insert({kv1, pair<string, string>("left", "左边")});
dict.insert({ {"string", "字符串"}, {"map", "地图,映射"} });

// key相同就不会再插入，value不相同也不会插入
dict.insert({ "left", "左边xxx" });

map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
	// cout << (*it).first <<":"<< (*it).second << endl; 
	cout << it->first << ":" << it->second << endl;
	// cout << it.operator->()->first << ":" << it.operator->()->second << endl;
	++it;
}
cout << endl;

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

// 结构化绑定 C++17
auto [x, y] = kv1;
//for (auto [k, v] : dict)
//for (auto& [k, v] : dict)
for (const auto& [k, v] : dict)
{
	cout << k << ":" << v << endl;
}
cout << endl;

auto pos = dict.find("left");
if (pos != dict.end())
{
	dict.erase(pos);
}

for (const auto& [k, v] : dict)
{
	cout << k << ":" << v << endl;
}
cout << endl;

结果：

2.3map的数据修改

前面提到map支持修改mapped_type 数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

map第一个支持修改的方式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改,map还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口

需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。

了解map::operator[]

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的
mapped_type值 
iterator find (const key_type& k);

// ⽂档中对insert返回值的说明 

// The single element versions (1) return a pair, with its member pair::first 
set to an iterator pointing to either the newly inserted element or to the 
element with an equivalent key in the map. The pair::second element in the pair
 is set to true if a new element was inserted or false if an equivalent key 
already existed.

// insert插⼊⼀个pair<key, T>对象 

// 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象
first是key所在结点的迭代器，second是false 

// 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象
first是新插⼊key所在结点的迭代器，second是true 

// 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭
代器 

// 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现
operator[]

// 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另
⼀个是insert返回值pair<iterator,bool> 
pair<iterator,bool> insert (const value_type& val);
mapped_type& operator[] (const key_type& k);

// operator的内部实现 
mapped_type& operator[] (const key_type& k)
{
 // 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储
mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能 
 // 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的
迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能 

 pair<iterator, bool> ret = insert({ k, mapped_type() });
 iterator it = ret.first;
 return it->second;
}

代码示例：

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countmap;

for (auto& e : arr)
{
	auto it = countmap.find(e);
	if (it != countmap.end())
	{
		it->second++;
	}
	else
	{
		countmap.insert({ e,1 });
	}
}

for (auto& e : arr)
{
	countmap[e]++;
}

for (auto& [k, v] : countmap)
{
	cout << k << ":" << v << endl;
}
cout << endl;

运行结果：

修改：

map<string, string> dict;
// 插入
dict["sort"];
// 插入+修改
dict["left"] = "左边";
// 修改
dict["sort"] = "排序";
// 查找
cout << dict["sort"] << endl;

// 纯粹的查找+修改
// at
dict.at("left") = "xxxxx";
// key不存在，会抛异常
// dict.at("insert") = "xxxxx";

3.multimap和map差异

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。

代码示例：

multimap<string, string> dict;
dict.insert({ "right", "右边" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边xx" });
dict.insert({ "right", "右边" });


for (const auto& [k, v] : dict)
{
	cout << k << ":" << v << endl;
}
cout << endl;

4.力扣练习map的使用

4.1随机链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer/

数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。这里我们直接让{原结点,拷贝结点}建立映射关系放到map中，控制随机指针会非常简单方便，这里体现了map在解决一些问题时的价值，完全是降维打击。

class Solution {
public:
    Node* copyRandomList(Node* head) {
      map<Node*, Node*> nodeMap;
      // 深拷贝链表
      Node* copyhead = nullptr, *copytail = nullptr;
      Node* cur = head;
      while(cur)
      {
        Node* copy = new Node(cur->val);
        // 尾插
        if(copytail == nullptr)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copy;
        }

        nodeMap.insert({cur, copy});
        cur = cur->next;
      }

      cur = head;
      Node* copy = copyhead;
      while(cur)
      {
        if(cur->random == nullptr)
        {
            copy->random = nullptr;
        }
        else
        {
            copy->random = nodeMap[cur->random];
        }
        cur = cur->next;
        copy = copy->next;
      }
      return copyhead;
    }
};

4.2前k个高频单词

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

本题自我们利用map统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。

解决思路1：

用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的。

class Solution {
public:
    struct kv_pair
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            return kv1.second > kv2.second;
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        map<string, int> countMap;
        for(auto& str : words)
        {
            countMap[str]++;
        }
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        // sort(v.begin(), v.end(), kv_pair());
        stable_sort(v.begin(), v.end(), kv_pair());
        for(auto& [k,v] : v)
        {
            cout << k << ":" << v << endl;
        }
        cout << endl;

        vector<string> ret;
        for(size_t i = 0; i < k; ++i)
        {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

解决思路2：

将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。

class Solution {
public:
    struct kv_pair
    {
        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);
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        map<string, int> countMap;
        for(auto& str : words)
        {
            countMap[str]++;
        }
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        sort(v.begin(), v.end(), kv_pair());
       // stable_sort(v.begin(), v.end(), kv_pair());
        for(auto& [k,v] : v)
        {
            cout << k << ":" << v << endl;
        }
        cout << endl;

        vector<string> ret;
        for(size_t i = 0; i < k; ++i)
        {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

class Solution {
public:
    struct kv_pair
    {
        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);
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        map<string, int> countMap;
        for(auto& str : words)
        {
            countMap[str]++;
        }
        
        priority_queue<pair<string, int>, vector<pair<string, int>>, kv_pair > pq(countMap.begin(), countMap.end());

        vector<string> ret;
        for(size_t i = 0; i < k; ++i)
        {
            ret.push_back(pq.top().first);
            pq.pop();
        }
        return ret;
    }
};

本章完。