STL 排序比较函数。

目录

• 引言
• 如何使用 std::sort
• 全局 < 运算符
• 成员 < 运算符
• 作为比较函数的函数指针
• 作为比较函数的函数对象
• Boost Lambda 库
• C++0x Lambda
• qsort
• stable_sort
• partial_sort
• partial_sort_copy
• nth_element
• 结论
• 历史

引言

本文是关于 STL std::sort 比较函数的一次快速入门。我有一位前同事使用 std::sort 按升序排序字符串数组，然后将排序后的数组以逆序复制到另一个数组中，以实现降序排序。他的方法浪费了处理器周期和内存。他本可以通过使用 functional 头文件中定义的 std::greater<string> 函数对象或为 std::sort 的谓词版本编写比较函数来实现降序排序。那件事促使我撰写了本文。本文是为寻求有关如何为 std::sort 编写比较函数的信息的程序员提供的快速指南。事不宜迟，让我们开始吧！

如何使用 std::sort

template <class RandomAccessIterator>
  void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

让我们快速回顾一下如何在数组和容器（如 std::tr1::array、std::vector 和 std::deque）上使用 std::sort。要按升序排序数组，您需要将数组第一个元素的地址指定为第一个参数，将数组最后一个元素之后一个位置的地址指定为第二个参数。以下是一个示例：

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
	int arr[5];
	arr[0] = 2;
	arr[1] = 3;
	arr[2] = 5;
	arr[3] = 1;
	arr[4] = 4;

	std::sort(arr,arr+5);

	std::cout<<arr[0]<<"\n";
	std::cout<<arr[1]<<"\n";
	std::cout<<arr[2]<<"\n";
	std::cout<<arr[3]<<"\n";
	std::cout<<arr[4]<<std::endl;

	return 0;
}

输出如下

1
2
3
4
5

要实现降序排序，请包含 functional 头文件，并将 std::sort(arr,arr+5); 替换为 std::sort(arr,arr+5,std::greater<int>());

#include <algorithm>
#include <iostream>
#include <string>
#include <functional>

int main()
{
	int arr[5];
	arr[0] = 2;
	arr[1] = 3;
	arr[2] = 5;
	arr[3] = 1;
	arr[4] = 4;

	std::sort(arr,arr+5,std::greater<int>());

	std::cout<<arr[0]<<"\n";
	std::cout<<arr[1]<<"\n";
	std::cout<<arr[2]<<"\n";
	std::cout<<arr[3]<<"\n";
	std::cout<<arr[4]<<std::endl;

	return 0;
}

输出如下

5
4
3
2
1

要对 std::tr1::array、std::vector 或 std::deque 进行升序排序，您需要将返回第一个迭代器的 begin() 方法指定为第一个参数，并将返回最后一个迭代器之后一个迭代器的 end() 方法指定为第二个参数。以下是对 std::vector 进行排序的示例：

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

int main()
{
	std::vector<int> vec;
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(5);
	vec.push_back(1);
	vec.push_back(4);

	std::sort(vec.begin(),vec.end());

	for(size_t i=0; i<vec.size(); ++i)
		std::cout<<vec[i]<<std::endl;

	return 0;
}

上述代码片段的输出如下：

1
2
3
4
5

请注意，您不能使用 std::sort 对 std::list（单链表）进行排序，因为 std::sort 需要随机访问迭代器才能工作，而 std::list 不具备此功能。对于 std::list，请改用其 sort 成员函数。

全局 < 运算符

std::sort 调用 std::less 进行比较，而 std::less 又调用元素类型的 < 运算符。对于 POD 类型，< 运算符已经定义。对于您自己的自定义类，您需要定义自己的 < 运算符。定义自己的 < 运算符有两种方法：您可以将其定义为全局 < 运算符，或者定义为类的成员 < 运算符函数。以下是如何为 Person 类定义全局 < 运算符的示例：

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

class Person
{
public:
	// default constructor
	Person() : age(0) {}
	Person(int age, std::string name) {
		this->age = age; this->name = name;
	}
	int age;
	std::string name;
};

inline bool operator<(const Person& a, const Person& b)
{
	return a.age < b.age;
}

int main()
{
	std::vector<Person> vecPerson;
	vecPerson.push_back(Person(24,"Calvin"));
	vecPerson.push_back(Person(30,"Benny"));
	vecPerson.push_back(Person(28,"Alison"));

	std::sort(vecPerson.begin(),vecPerson.end());

	for(size_t i=0; i<vecPerson.size(); ++i)
		std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl;

	return 0;
}

输出如下

24, Calvin
28, Alison
30, Benny

成员 < 运算符

接下来是为 Person 类定义成员 < 运算符的示例

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

class Person
{
public:
	// default constructor
	Person() : age(0) {}
	Person(int age, std::string name) {
		this->age = age; this->name = name;
	}
	bool operator<(const Person& rhs)
	{
		return this->age < rhs.age;
	}
	int age;
	std::string name;
};

int main()
{
	std::vector<Person> vecPerson;
	vecPerson.push_back(Person(24,"Calvin"));
	vecPerson.push_back(Person(30,"Benny"));
	vecPerson.push_back(Person(28,"Alison"));

	std::sort(vecPerson.begin(),vecPerson.end());

	for(size_t i=0; i<vecPerson.size(); ++i)
		std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl;

	return 0;
}

输出与全局 < 运算符示例相同。

24, Calvin
28, Alison
30, Benny

您可能会问，成员运算符函数与全局运算符函数相比有什么优势吗？是的，有！成员运算符函数可以访问类的 private 和 protected 数据成员，而全局运算符函数不能。如果 Person 类中的年龄是 private 成员，全局运算符函数就无法在不使用访问器函数的情况下访问它。

作为比较函数的函数指针

如果我们想按降序排序 Person 向量怎么办？有两种方法：我们可以定义一个比较函数并将其函数指针传递给 std::sort 的谓词版本，或者定义一个比较函数对象（也称为函数子）并将其作为比较谓词传递给 std::sort 的谓词版本。

如果我们想知道谁是年龄较大的长者，我们可以按年龄降序排序，然后按姓名升序排序。这是自定义排序，而不是降序排序。以下是使用函数指针作为排序谓词的示例。

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

class Person
{
public:
	// default constructor
	Person() : age(0) {}
	Person(int age, std::string name) {
		this->age = age; this->name = name;
	}

	int age;
	std::string name;
};

bool Greater(const Person& a, const Person& b)
{
	if(a.age == b.age)
		return a.name < b.name;

	return a.age > b.age;
}

int main()
{
	std::vector<Person> vecPerson;
	vecPerson.push_back(Person(24,"Calvin"));
	vecPerson.push_back(Person(30,"Benny"));
	vecPerson.push_back(Person(30,"Alice"));
	vecPerson.push_back(Person(28,"Alison"));

	std::sort(vecPerson.begin(),vecPerson.end(),Greater);

	for(size_t i=0; i<vecPerson.size(); ++i)
		std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl;

	return 0;
}

输出如下

30, Alice
30, Benny
28, Alison
24, Calvin

作为比较函数的函数对象

以下是使用函数对象（也称为函数子）作为谓词进行排序的示例。函数对象实际上是一个重载了 () 运算符的类。您可以阅读此 关于函数对象的维基百科文章 以获取更多信息。

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>

class Person
{
public:
	// default constructor
	Person() : age(0) {}
	Person(int age, std::string name) {
		this->age = age; this->name = name;
	}

	int age;
	std::string name;
};

// function object
struct GreaterAge : public std::binary_function<Person,Person,bool>
{
	inline bool operator()(const Person& a, const Person& b)
	{
		if(a.age == b.age)
			return a.name < b.name;

		return a.age > b.age;
	}
};

int main()
{
	std::vector<Person> vecPerson;
	vecPerson.push_back(Person(24,"Calvin"));
	vecPerson.push_back(Person(30,"Benny"));
	vecPerson.push_back(Person(30,"Alice"));
	vecPerson.push_back(Person(28,"Alison"));

	std::sort(vecPerson.begin(),vecPerson.end(),GreaterAge());

	for(size_t i=0; i<vecPerson.size(); ++i)
		std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl;

	return 0;
}

这是输出

30, Alice
30, Benny
28, Alison
24, Calvin

注意：如果我们的函数对象没有派生自 std::binary_function 类，上述示例同样可以正常工作。以下是上述函数对象不继承自任何类的示例：

// function object
struct GreaterAge
{
	inline bool operator()(const Person& a, const Person& b)
	{
		if(a.age == b.age)
			return a.name < b.name;

		return a.age > b.age;
	}
};

你可能会问，在函数指针和函数对象之间，哪个是编写比较的首选。答案是函数对象，因为我们可以内联函数对象以获得更好的性能，而不能内联函数指针。这就是 std::sort 比 C 的 qsort 性能更好的原因。作为 C++ 程序员，我们应该始终使用 std::sort 而不是 qsort，因为 qsort 没有类型安全性。

Boost Lambda 库

我们还可以使用 Boost Lambda 库或 C++0x Lambda 将比较函数指定为匿名函数。我们将看到一个使用 Boost Lambda 作为匿名比较函数，以降序排序整数数组的示例。我们需要将 lambda 的返回类型指定为布尔值。_1 和 _2 是传递给 Lambda 比较函数的两个整数参数。注意：如本文早期第二个代码示例所示，我们可以使用 greater<int> 谓词实现相同的功能。

#include <algorithm>
#include <iostream>
#include <string>
#include <cstdlib>
#include <functional>
#include <boost/lambda/lambda.hpp>

int main()
{
	int arr[5];
	arr[0] = 2;
	arr[1] = 3;
	arr[2] = 5;
	arr[3] = 1;
	arr[4] = 4;

	using namespace boost::lambda;
	std::sort(arr,arr+5, ret<bool>(_1 > _2));

	std::cout<<arr[0]<<"\n";
	std::cout<<arr[1]<<"\n";
	std::cout<<arr[2]<<"\n";
	std::cout<<arr[3]<<"\n";
	std::cout<<arr[4]<<std::endl;

	return 0;
}

输出如下

5
4
3
2
1

在第二个 Boost Lambda 示例中，我们将按升序排序 Person 对象的向量。

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/casts.hpp>
#include <boost/function/function_base.hpp>

class Person
{
public:
	// default constructor
	Person() : age(0) {}
	Person(int age, std::string name) {
		this->age = age; this->name = name;
	}

	int age;
	std::string name;
};

int main()
{
	std::vector<Person> vecPerson;
	vecPerson.push_back(Person(24,"Calvin"));
	vecPerson.push_back(Person(30,"Benny"));
	vecPerson.push_back(Person(28,"Alison"));

	using namespace boost::lambda;
	std::sort(vecPerson.begin(),vecPerson.end(), 
		ret<bool>( (&_1 ->* &Person::age) < (&_2 ->* &Person::age) ) );

	for(size_t i=0; i<vecPerson.size(); ++i)
		std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl;

	return 0;
}

输出如下

24, Calvin
28, Alison
30, Benny

如我们所见，这个 Boost Lambda 语法更为复杂。首先指定返回类型，然后是比较 Person::age 的表达式。为了获取 Person::age 成员的值，我们需要在参数（_1 和 _2）的左侧放置与号，将其转换为指针，以便我们可以使用指向成员的运算符（->*）访问 Person::age 成员。与号也放在 Person::age 的左侧以获取其地址。如果您的普通比较函数不仅仅是比较类成员，您将很难将其转换为 Boost Lambda 函数，因为您必须使用 Boost Lambda 不自然的构造来执行 if-else、switch-case、while-loop 等。有关 Boost Lambda 的更多信息，请参阅其文档 此处。接下来，让我们看看 C++0x Lambda。

C++0x Lambda

Lambda 是即将推出的 C++ 标准中的一个语言特性。要尝试下面列出的 C++0x Lambda 示例，您需要安装 Visual Studio 2010 Beta 1。您可以在 此处 下载。建议您在 Virtual PC 中安装 Visual Studio 2010 Beta 1，以免干扰您当前的 Visual Studio 安装。您可以在 此处 下载 Virtual PC 的 OS 镜像。有关如何安装 Visual Studio 2010 Beta 1 的更多说明，您可以参考此 网站。

让我们看看使用 C++0x Lambda 作为匿名比较函数，以降序排序整数数组的示例。

#include <algorithm>
#include <iostream>
#include <string>
#include <cstdlib>

int main()
{
	int arr[5];
	arr[0] = 2;
	arr[1] = 3;
	arr[2] = 5;
	arr[3] = 1;
	arr[4] = 4;

	std::sort(arr,arr+5, [](int x, int y){return x > y;});

	std::cout<<arr[0]<<"\n";
	std::cout<<arr[1]<<"\n";
	std::cout<<arr[2]<<"\n";
	std::cout<<arr[3]<<"\n";
	std::cout<<arr[4]<<std::endl;

	return 0;
}

[] 表示 C++0x lambda 的开始。x 和 y 是 lambda 的参数。我们可以自由地命名这两个参数，不像在 Boost Lambda 中，它必须是 _1 和 _2。我们没有指定 lambda 的返回类型，它会自动从唯一的返回语句推断。我们可以不指定 lambda 的返回类型，但我们只受限于一个表达式，即返回语句。

输出如下

5
4
3
2
1

在第二个 C++0x Lambda 示例中，我们将对 Person 对象的向量进行排序，按 age 值降序排列，如果两个 age 值相等，则按名称升序排列。由于此 lambda 有多个语句，我们需要使用 -> bool 语法指定其布尔返回类型。

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

class Person
{
public:
	// default constructor
	Person() : age(0) {}
	Person(int age, std::string name) {
		this->age = age; this->name = name;
	}

	int age;
	std::string name;
};

int main()
{
	std::vector<Person> vecPerson;
	vecPerson.push_back(Person(24,"Calvin"));
	vecPerson.push_back(Person(30,"Benny"));
	vecPerson.push_back(Person(30,"Alice"));
	vecPerson.push_back(Person(28,"Alison"));

	std::sort(vecPerson.begin(),vecPerson.end(),
		[](const Person& a, const Person& b) -> bool
	{
		if(a.age == b.age)
			return a.name < b.name;

		return a.age > b.age;
	});

	for(size_t i=0; i<vecPerson.size(); ++i)
		std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl;

	return 0;
}

与 Boost Lambda 相比，C++0x Lambda 可以做更多的事情，因为 C++0x Lambda 主体语法（指大括号中包含的代码）是正常的 C++ 语法，因此它更自然且易于理解。有关 C++0x Lambda 语法的更多信息，请参阅此 页面。

输出如下

30, Alice
30, Benny
28, Alison
24, Calvin

Boost Lambda 作为库实现，而 C++0x Lambda 作为语言特性实现。这解释了为什么 Boost Lambda 语法与 C++0x Lambda 语法相比显得复杂，这是为了克服 C98 C++ 语言限制而采取的变通方法。

qsort

既然我们谈到了比较函数，让我简要地向您展示如何编写 qsort 的比较函数。要按升序排序，如果两个参数相等，比较函数必须返回 0；如果第一个参数大于第二个参数，则应返回大于零的值；如果第一个参数小于第二个参数，则返回小于零的值。当然，如果您想按降序排序，则需要反转返回值。以下是 qsort 比较函数的示例。有关更多信息，请阅读此 MSDN 链接。

#include <iostream>
#include <string>
#include <cstdlib>

int compare(const void* x, const void* y)
{
	int* a = (int*)x;
	int* b = (int*)y;

	if(*a==*b)
		return 0;

	return *a > *b ? +1 : -1;
}

int main()
{
	int arr[5];
	arr[0] = 2;
	arr[1] = 3;
	arr[2] = 5;
	arr[3] = 1;
	arr[4] = 4;

	std::qsort(arr,5,sizeof(int),compare);

	std::cout<<arr[0]<<"\n";
	std::cout<<arr[1]<<"\n";
	std::cout<<arr[2]<<"\n";
	std::cout<<arr[3]<<"\n";
	std::cout<<arr[4]<<std::endl;

	return 0;
}

输出如下

1
2
3
4
5

std::stable_sort

template <class RandomAccessIterator>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp );

既然我们谈到 std::sort，我将简要介绍 std::stable_sort 和其他 STL 排序算法。std::stable_sort 的用法与 std::sort 相同。唯一的区别是 std::stable_sort 会尊重相等元素的原始顺序，而 std::sort 不会。std::stable_sort 以牺牲一些性能为代价来实现此功能，因为需要进行更多的比较以确定任意两个元素是否相等。奇怪的是，std::stable_sort 不需要元素类型定义相等运算符（==）；std::stable_sort 使用表达式 !(x 来确定两个元素是否相等。比较函数与 std::sort 相同。有关 std::stable_sort 的更多信息，您可以阅读 此处。

template <class RandomAccessIterator>
  void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,
                      RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,
                      RandomAccessIterator last, Compare comp );

template <class InputIterator, class RandomAccessIterator>
  RandomAccessIterator
    partial_sort_copy ( InputIterator first,InputIterator last,
                        RandomAccessIterator result_first,
                        RandomAccessIterator result_last );

template <class InputIterator, class RandomAccessIterator, class Compare>
  RandomAccessIterator
    partial_sort_copy ( InputIterator first,InputIterator last,
                        RandomAccessIterator result_first,
                        RandomAccessIterator result_last, Compare comp );

template <class RandomAccessIterator>
  void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
  void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                    RandomAccessIterator last, Compare comp);