pair 类型介绍

map 底层红黑树节点数据：采用pair<Key, T>结构统一存储键（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));
}

可以理解为：key 和 value 不再单独存在，而是被整合进一个 pair 结构体中，pair 内部包含两个成员变量，一个存储 key，另一个存储 value。

使用样例：

int main()
{
	map<string, string> dict;
	//1.插入有名的pair对象
	pair<string, string> kv1("first", "第一个");
	dict.insert(kv1);
	//2.插入匿名的pair对象
	dict.insert(pair<string, string>("second", "第二个"));
	//3.调用make_pair：本质是一个函数模板（不用自己实例化模板参数），返回一个pair对象（常用）
	//与2.等价
	dict.insert(make_pair("sort", "排序"));
    //补充注意点：因为map不允许数据冗余，当再执行插入一个key同为sort的代码，并不会修改原有数据，因为map底层红黑树比较的基准永远都是key，与value无关
    dict.insert(make_pair("sort", "排序mmmmm"));
	//C++11之后允许多参数的隐式类型转换--->
	//4.使用{}，隐式类型转换成pair（最爱用）
	dict.insert({ "auto","自动的" });
    //initializer_list构造
    //内层走隐式类型转换，外层走initializer
    map<string, string> dict = { {"left", "左边"}, {"right", "右边"}, {"insert", "插⼊"},{ "string", "字符串" } };
	return 0;
}

C++ 不支持同时返回两个值，若要一并返回 key 和 value，需用结构体封装 ——将 key 与 value 放入 pair 结构中。且 pair 默认不支持流插入与流提取【因为 C++ 标准库里 没有给 std::pair 写 operator<<和 operator>>】

由于一个节点本身就包含对应的 key 和 value 数据，访问节点数据应使用以下两种方式：

  • *it 是一个 pair 对象，可用 . 访问成员；
  • 迭代器除重载 operator* 外，还重载了 operator->，当迭代器指向结构体对象时，使用 -> 访问成员。
	//打印数据
	auto it = dict.begin();
	while (it != dict.end())
	{
		//C++不支持同时返回两个值
		//cout << *it << endl;
		//*it是一个pair，可以用"  . 对象  "的方式进行访问
		cout << (*it).first << ' : ' << (*it).second << endl;

		//迭代器除了重载 operator* ，还重载了 operator-> ，如果迭代器指向的对象是一个结构的时候就使用 -> 
		cout << it->first << ' : ' << it->second << endl;
		//本源是：
		//it.operator->()->first;
		//it.operator->()：返回数据的指针：也就是pair*
		//pair*->first
		
		it++;
	}
	cout << endl;
	return 0;
}

pair 支持比较大小：

若判断 lhs == rhs / lhs != rhs：两者相等，需要 first 和 second 同时相等。

template <class T1, class T2>
  bool operator== (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first==rhs.first && lhs.second==rhs.second; }

template <class T1, class T2>
  bool operator!= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return !(lhs==rhs); }

如果 pair 满足 lhs < rhs / lhs <= rhs：先比较 first，若 lhs.first 更小，则 lhs 更小为真；若 lhs.first >= rhs.first，再比较 second。

template <class T1, class T2>
  bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }

template <class T1, class T2>
  bool operator<= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return !(rhs<lhs); }

如果 pair 满足 lhs > rhs / lhs >= rhs：先比较 first，若 lhs.first 更大，则 lhs 更大为真；若 lhs.first <= rhs.first，再比较 second。

template <class T1, class T2>
  bool operator>  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return rhs<lhs; }

template <class T1, class T2>
  bool operator>= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return !(lhs<rhs); }

在做 OJ 题目时需按具体场景灵活处理：从上面规则可看出，pair 默认比较优先按 first，若需按 second 比较，需自行实现仿函数（重载 operator ()）。

补充：使用仿函数构建大堆时，需使用 <（这是与其他仿函数使用上的不同点）。

map 的使用

map 其实跟 set 相似，只是 map 多了一个 value 值（second）。

具体参考（点击进入）

  • map 的声明如下：Key 是 map 底层关键字类型，T 是 map 底层 value 类型。set 默认要求 Key 支持小于比较，若不支持或需自定义比较，可自行实现仿函数传给第二个模板参数；注意比较以 Key 为基准。
  • map 底层存储数据的内存由空间配置器申请，一般无需传后两个模板参数。
  • map 底层由红黑树实现，增删查改效率为 O(logN)（修改仅支持对 value 修改）；迭代器遍历采用中序，因此按 key 有序遍历。
  • map 的 insert 与 key、value 相关；erase /find/count /lower_bound/upper_bound 等操作只与 key 有关，与 value 无关。
  • equal_range 用于查找指定数据的左闭右开区间，返回一个 pair，多用于 multi 版本的 set/map，定位相同 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;

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 的增删查

map 的增删查只需关注以下几个接口：

map 的增接口，插入的是 pair 键值对 数据，这一点与 set 不同；但查和删接口只使用关键字 key，与 set 完全类似。

不过 find 返回迭代器，不仅能判断 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 的数据修改 

前面我提到 map 支持修改 mapped_type 数据，不支持修改 key 数据 —— 修改关键字会破坏底层搜索树结构。【解释：mapped_type 就是 map 中value（second） 的类型，key 是红黑树排序依据，一旦修改会打乱整棵树结构，因此禁止修改】

map 第一种修改方式是通过迭代器：在迭代器遍历或 find 返回 key 所在迭代器时进行修改。【解释：迭代器指向节点后，可通过 it->second 修改 value，不能改 it->first】

map 还有一个非常重要的修改接口 operator[]，它不只是支持修改，还支持插入数据和查找数据，是一个多功能复合接口。【解释：map[key] 存在则返回 value 引用（可改），不存在则自动插入默认值，集查、插、改于一体】

需要注意：从内部实现角度，map 把我们常说的 value 值（T 类型）typedef 为 mapped_type；而 value_type 是红黑树节点中存储的 pair 键值对。【解释：mapped_type = T（value）；value_type = pair<const Key, T>（节点实际存储结构）】

日常使用中，我们仍习惯把 T 映射值叫做 value。【解释：口头 / 做题时仍说 “key-value”，不用刻意区分 mapped_type】

利用 find 和迭代器修改功能，统计水果出现的次数：

int main()
{
	// 利⽤find和iterator修改功能，统计⽔果出现的次数
	string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠",
	"苹果", "⾹蕉", "苹果", "⾹蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		// 先查找⽔果在不在map中
		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1}
		// 2、在，则查找到的节点中⽔果对应的次数++
		auto ret = countMap.find(str);
		if (ret == countMap.end())
		{
			countMap.insert({ str, 1 });
		}
		else
		{
			ret->second++;
		}
	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	return 0;
}

但是在 C++ 中，并不常以这种方式统计次数，而是使用 operator[] 来实现次数统计：

对于 map 重载的 operator[]，不再是单纯像数组那样通过下标访问元素，而是：你传入 key，它返回对应的 value。

mapped_type& operator[] (const key_type& k);
//这里的mapped_type就是我们所指的value
//而他文档写的value_type是我们所指的pair

map 重载的 operator[] 不仅具备查找和修改功能，还兼具插入功能：

  • 当使用 operator[] 访问 map 元素时，若元素已存在，会返回引用，允许修改其值；
  • 若元素不存在，operator[] 会自动插入新元素，并将值初始化为对应类型的默认值。（对比其他语言，此处不会抛异常）

功能样例：

int main()
{
	map<string, string> dict;
	dict.insert({ "sort","排序" });

	//key不存在->插入{"insert",string()};
	dict["insert"];//这时候【】的作用就是进行插入操作

	//key不存在->插入+修改
	dict["tea"] = "茶";

	//key存在->修改
	dict["insert"] = "插入";

	//查找：一定要确保所查找的数据存在，不然就是变成了key不存在的插入行为了
	//应当谨慎使用其查找功能
	cout << dict["tea"] << endl;

	for (auto d : dict)
	{
		cout << d.first << ":" << d.second << endl;
	}
	cout << endl;
	return 0;
}

其插入操作，等价于底层调用：

//A call to this function is equivalent to:
(*((this->insert(make_pair(k,mapped_type()))).first)).second

到这里，我们需要好好理解 map 中 insert 操作的返回值：

穿插：map 中 insert 的返回值

//single element (1)	
pair<iterator,bool> insert (const value_type& val);

可以看出，这里 insert 的返回值是一个 pair，而 value_type 本身也是一个 pair（存储键值对），因此会出现两个 pair。

返回的 pair 中：

  • iterator（迭代器）：返回新插入元素的位置；若已存在相同 key，则指向原有元素位置。
  • bool：标识 insert 是否成功。key 存在则为 false，不存在则为 true。

简单来说：

  • 插入成功：pair<新插入值所在迭代器, true>
  • 插入失败：pair<已存在同 key 元素的迭代器, false>

也就是说，无论插入成功或失败，返回 pair<iterator,bool> 的 first 都会指向 key 所在迭代器。

这意味着 insert 插入失败时，相当于实现了查找功能。正是这一特性，使得 insert 可以用来实现 operator[]。

需要注意：这里有两个 pair，不要混淆：一个是 map 底层红黑树节点存储的 pair<Key, T>；另一个是 insert 返回值 pair<iterator, bool>。

operator [] 的内部实现：

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

代码优化：使用operator [ ] 

int main()
{
	// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数
	string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠",
	"苹果", "⾹蕉", "苹果", "⾹蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		// []先查找⽔果在不在map中
		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了
		// 2、在，则返回⽔果对应的次数++
			countMap[str]++;
	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	return 0;
}

multimap 和 map 的区别

在C++标准库中，map和multimap都是关联容器，它们存储了键值对（key-value pairs），并且提供了基于键的有序访问。它们之间的主要区别在于：

唯一性：

  • map：每个键必须是唯一的。如果尝试插入一个已经存在的键，那么该操作将不会改变容器。
  • multimap：允许有多个元素具有相同的键。这意味着可以存储多个具有相同键的值。

插入操作：

  • map：如果插入的键已经存在，那么插入操作不会成功，容器内容不变。
  • multimap：即使键已经存在，插入操作也会成功，并且会创建一个新的键值对。

迭代器：

  • map：迭代器指向唯一的元素，所以迭代器的 operator* 直接返回一个 pair 对象，其中包含键和值。
  • multimap：迭代器也指向 pair 对象，但由于可能有多个相同的键，所以迭代器的 operator* 返回一个引用到 pair 的对象。

查找操作：

  • map：查找操作返回一个迭代器，指向找到的元素或者在未找到时指向插入点。
  • multimap：查找操作返回一个迭代器范围（一个迭代器对），包含所有具有指定键的元素。

删除操作：

  • map：删除操作会删除键及其关联的值。
  • multimap：删除操作会删除所有具有该键的元素。

成员函数：

  • map：提供了 find, count, equal_range 等成员函数。
  • multimap：提供了 find, count, equal_range 等成员函数，但 count 返回的是具有相同键的元素数量，equal_range 返回一个迭代器对，表示具有相同键的范围。

用途：

  • map：当你需要快速查找、插入和删除唯一键时使用。
  • multimap：当你需要关联多个具有相同键的值时使用。

在C++标准库中，multimap不支持使用 operator[] 的原因是因为 multimap 允许有多个元素具有相同的键。operator[] 通常用于访问元素，并且它返回一个引用，这意味着它应该定位到一个确切的元素。

对于 map，由于每个键是唯一的，使用 operator[] 可以直接访问或创建并访问一个特定的键值对。

然而，对于 multimap，如果使用 operator[] 会遇到以下问题：

  1. 歧义性：如果有多个元素具有相同的键，operator[] 应该返回哪一个元素的引用？
  2. 效率问题：operator[] 通常需要提供一个快速访问，但 multimap 需要遍历以找到正确的元素，这与 operator[] 设计的初衷不符。

如何在 multimap 中访问元素

虽然 multimap 不支持 operator[]，但可以使用其他方法来访问或修改具有特定键的元素：

使用 find 方法：

std::multimap<int, std::string> myMultimap;
myMultimap.insert(std::make_pair(1, "One"));
myMultimap.insert(std::make_pair(2, "Two"));
myMultimap.insert(std::make_pair(2, "Another Two"));

auto it = myMultimap.find(2);
if (it != myMultimap.end()) {
    std::cout << it->second << std::endl; // 输出 "Two"
}
  • find 方法返回一个指向找到元素的迭代器，如果元素不存在，则返回 end() 迭代器。

使用 equal_range 方法：

std::pair<std::multimap<int, std::string>::iterator,
          std::multimap<int, std::string>::iterator> range;

range = myMultimap.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << std::endl; // 输出所有键为2的元素
}
  • equal_range 方法返回一个迭代器对，表示具有指定键的所有元素的范围。

使用 lower_bound 和 upper_bound 方法：

auto lower = myMultimap.lower_bound(2);
auto upper = myMultimap.upper_bound(2);
for (auto it = lower; it != upper; ++it) {
    std::cout << it->second << std::endl; // 输出所有键为2的元素
}
  • 这些方法也可以用来找到具有特定键的元素的范围。

总结：

multimap 不支持 operator[] 是因为它的设计允许多个具有相同键的元素存在，这会导致访问时的歧义性。相反，可以使用 find、equal_range、lower_bound 和 upper_bound 等方法来访问或修改具有特定键的元素。这些方法提供了更灵活的访问方式，可以处理 multimap 中键的重复性。

习题巩固：

学习本章之后，可以通过下面习题进行巩固知识 

# c++ # 数据结构
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

2026知网AIGC检测升级！免费好用的降AI工具实测指南

avatar AtomGit开源社区
cover

免费降AIGC工具实测：20款工具深度对比，论文去AI浓度避坑指南

avatar AtomGit开源社区
cover

2026知网AIGC检测升级！免费好用的降AI工具实测指南

avatar AtomGit开源社区