使用std::pair作为std::set的key

在这篇文章，我们看看如何在C++中使用std::pair作为std::set的key, 使用或者不使用比较对象。

1. 使用默认排序

我们可以使用std::pair作为std::set的key, std::pair定义在<utility>头文件。我们知道C++的pair类将一对相同或不同类型的值组合在一起，单个值可以通过公有成员first和second访问。 

我们可以使用C++11的initializer list初始化使用std::pair作为key的std::set。方法是使用std::make_pair()或{}构造一个pair对象。

#include <iostream>
#include <set>
#include <utility>

int main()
{
	std::set<std::pair<std::string, int>> set = {
		{"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3}
	};

	for (auto const &p: set) {
		std::cout << p.first << " " << p.second << '\n';
	}

	return 0;
}
           

Output:

{A:0}

{A:4}

{B:3}

{B:4}

{C:1}

因为operator<为pairs定义了，所以std::set在两个pair对象上执行字典顺序比较来定义顺序，即它基于first元素进行比较，如果第first元素的值相等，它将基于second元素进行比较。行为如下定义：

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

2. 使用比较对象

我们也可以给std::set传入比较对象来覆盖默认顺序。比较对象是一个二元函数，传入两个pair对象，通过比较两个pair的first和second元素来定义顺序。如果函数返回true，则第一个pair位于第二个pair之前，如果返回false，则第一个pair位于第二个pair之后。

#include <iostream>
#include <set>
#include <utility>

struct comp
{
	template<typename T>
	bool operator()(const T& l, const T& r) const
	{
		if (l.first == r.first)
			return l.second > r.second;

		return l.first < r.first;
	}
};

int main()
{
	std::set<std::pair<std::string,int>, comp> set = {
		{"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3}
	};

	for (auto const &p: set) {
		std::cout << "{" << p.first << ":" << p.second << "}\n";
	}

	return 0;
}
           

Output:

{A:4}

{A:0}

{B:4}

{B:3}

{C:1}

3. 特例化std::less

如果你不想传入比较对象，但仍希望覆盖默认顺序，我们可以特例化std命名空间下的std::less。默认情况下，std::set的第二个模板参数是std::less，std::less委托给operator<。

#include <iostream>
#include <set>
#include <utility>

namespace std {
	template<typename T1, typename T2>
	struct less<std::pair<T1, T2>>
	{
		bool operator()(const std::pair<T1, T2>& l,
						const std::pair<T1, T2>& r) const
		{
			if (l.first == r.first)
				return l.second > r.second;

			return l.first < r.first;
		}
	};
}

int main()
{
	std::set<std::pair<std::string, int>> set = {
		{"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3}
	};

	for (auto const &p: set) {
		std::cout << "{" << p.first << ":" << p.second << "}\n";
	}

	return 0;
}
           

Output:

{A:4}

{A:0}

{B:4}

{B:3}

{C:1}

https://www.techiedelight.com/use-std_pair-as-key-std_set-cpp/