65.9K
CodeProject 正在变化。 阅读更多。
Home

在线泛型数据排序向导

吉姆·佐切利斯
starIconstarIconstarIconstarIconstarIcon

5.00/5 (2投票s)

2013年6月1日

Apache

19分钟阅读

viewsIcon

22461

downloadIcon

127

一个方便的在线工具，用于促进使用泛型 C++ 编程来处理或存储自定义数据类型。

在线使用向导

目录

引言

您是否对一个方便的工具感兴趣，该工具可以促进使用泛型 C++ 编程来处理或存储自定义数据类型？您是否曾经尝试过使用一些著名的 std::sort、std::merge 或 std::lower_bound STL [1] 算法来处理自定义结构或类？您是否曾经尝试过使用 STL 关联容器，如 std::set 或 std::map，来存储您自己的数据类型？或者，您是否觉得实现函数对象（仿函数）、lambda 表达式或自定义 C++ 运算符应该不那么繁琐、麻烦且容易出错？

如果您的答案是肯定的，那么这篇文章很可能会引起您的兴趣。本文的目的是介绍 在线泛型数据排序向导，并展示这个工具如何通过轻松创建专门的 C++ 函数对象、lambda 表达式和自定义 C++ 运算符，使泛型 C++ 编程中的自定义数据排序更加方便。接下来的段落将从非常实用的角度并使用简单的示例来讨论这些内容，同时将理论和技术细节保持在最低限度，以保证清晰度。

摘要

C++ 编译器不会自动处理自定义类或结构的排序，同时，数据排序被大量泛型 C++ 组件（即模板类、结构和函数）广泛使用。因此，许多泛型 C++ 组件，包括一些最著名的 STL 算法和容器，经常无法开箱即用地与用户创建的类或结构一起工作，因为它们无法在没有额外编程工作的情况下对这类数据进行排序。这些问题的典型解决方案是创建一个合适的函数对象（仿函数）、lambda 函数或自定义运算符，并使用它来辅助泛型代码对特定自定义数据类型进行排序。然而，手动创建这些仿函数、lambda 和自定义运算符是一项相当繁琐、耗时且相对容易出错的编程任务。

认识到这种情况实际上阻碍了软件开发者充分利用泛型 C++ 编程的优势，我决定实现本文介绍的 在线泛型数据排序向导。有趣的是，这个工具可以极大地简化以前繁琐且容易出错的泛型数据排序，使得大多数泛型 C++ 编程中的数据排序任务现在可以像填写一个三字段表单一样简单。同时，这个工具允许我们享受一些非常实用的仿函数、lambda 和自定义运算符的优势，而无需担心它们的（相当繁琐的）实现，也无需花费时间去学习和掌握它们。

这个向导能为我们做什么？

《在线泛型数据排序向导》旨在成为 C++ 开发者的实用工具。该工具的使命是帮助我们解决泛型 C++ 编程中的实际问题，并使一些编程任务比以前容易得多。因此，为了认识到这个向导能为我们做什么，理解这个向导旨在解决的问题的性质，以及理解这个工具具体如何帮助 C++ 开发者在实践中克服这些问题是至关重要的。

泛型数据排序有什么问题？

在大多数情况下，在 C++ 中使用模板函数和类，如 STL 算法和容器，来处理或存储标准数据类型，如整数、双精度数或 std::string 对象，是相当容易和直接的。例如，在下面的示例#1中，您可以看到创建 std::set 容器来存储标准 C++ 数据值有多么容易，以及使用 std::sort 来排序 std::vector 中包含的标准 C++ 数据值有多么容易。预期的示例代码在任何不错的 C++ 编译器上都可以编译通过，您可以通过点击相应的编译链接来验证。

示例#1：排序标准 C++ 值 [编译]
#include <vector>
#include <string>
#include <set>

#include <algorithm>

int main()
{
	std::vector<int> v1;
	std::sort(v1.begin(), v1.end()); //Compiles happily with integers

	std::vector<double> v2;
	std::sort(v2.begin(), v2.end()); //Compiles happily with doubles

	std::vector<std::string> v3;
	std::sort(v3.begin(), v3.end()); //Compiles happily with std::string

	std::set<int> s1;
	s1.find(int()); //Compiles happily with integers

	std::set<double> s2;
	s2.find(double()); //Compiles happily with doubles

	std::set<std::string> s3;
	s3.find(std::string()); //Compiles happily with std::string
	
	return 0;
}

然而，当我们开始使用泛型代码来处理或存储自定义结构和类时，情况会变得更加困难。也就是说，我们不能简单地将前一个示例中的标准数据类型替换为自定义类型，即使像下一个示例中的 point 结构一样简单，并期望代码仍然像以前一样工作！相反，STL 对于这个 point 结构来说，将比以前对标准 C++ 数据类型来说要不友好得多。在下面的示例#2中，“直接”尝试创建和使用 std::set<point> 容器以及使用 std::sort 算法对 std::vector<point> 容器的元素进行排序，都将无法编译，您可以通过点击相应的编译链接来验证。

示例#2：排序自定义结构 [编译]
#include <vector>
#include <set>

#include <algorithm>

struct point //A simple custom point structure
{
	int x, y;
};

int main()
{
	std::vector<point> v;
	std::sort(v.begin(), v.end()); //Fails to compile with point structures

	std::set<point> s;
	s.find(point()); //Fails to compile with point structures
	
	return 0;
}

在示例#2中出错的原因是，std::set 和 std::sort 模板的实现代码尝试使用小于（<）运算符来排序 point 结构，但由于没有为我们的 point 结构定义小于（<）运算符而导致编译失败。本质上，这只是泛型 C++ 编程中一个非常常见的数据排序问题的实例，这个问题与小于（<）运算符的可用性有关。也就是说，许多泛型 C++ 组件，如 std::set 和 std::sort，默认依赖于小于（<）运算符进行数据排序，但同时 C++ 中的结构和类无法通过小于（<）运算符进行比较，除非我们显式地为它们定义和实现这个运算符。因此，C++ 开发者在使用直接或间接排序自定义结构或类的泛型代码时，经常会遇到困难和复杂性，这并不奇怪。最终，这些困难和复杂性常常阻碍了软件开发者充分利用泛型 C++ 编程的优势。

 更正式地说，许多泛型 C++ 组件（如 std::set 和 std::sort）具有 **小于可比性** [2] 的类型要求，这意味着它们被设计为与模拟 **小于可比性** 概念的数据类型一起工作。 [2,3] 然而，C++ 类和结构默认不是 **小于可比性** 的类型，这一事实使得具有 **小于可比性** 要求的泛型组件（如 std::set 和 std::sort）与大多数自定义数据类型不兼容。

这个向导具体能如何帮助我们？

《在线泛型数据排序向导》旨在帮助我们克服在泛型 C++ 编程中对自定义数据类型进行排序可能引起的许多困难和复杂性。该向导可以使泛型数据排序更加容易和安全，它提供了三种极其简单的解决方案来排序泛型 C++ 编程中的自定义结构和类：一个*严格弱序*仿函数、一个*严格弱序* lambda 函数和一个自定义*小于（<）运算符*。

例如，在下面的示例 3、4 和 5 中，您可以看到向导提供的这三种解决方案如何有效地消除了我们之前 point 结构遇到的问题。使用任何一种方法都足以使我们既能将自定义的 point 结构存储在 std::set 容器中，又能使用 std::sort 对 std::vector<point> 容器的元素进行排序。欢迎您通过点击相应的编译链接，在一个真正的 C++ 编译器上测试向导的解决方案。

示例#3：严格弱序仿函数解决方案 [编译]
#include <vector>
#include <set>

#include <algorithm>
#include <functional>

struct point // A simple custom point structure
{
	int x, y;
};

// Functor created by the wizard
// --------------------------------------------------

struct point_functor
	: public std::binary_function<point, point, bool>
{
	bool operator() (const point &left, const point &right) const
	{
		if (left.x == right.x)
			return (left.y < right.y);
		else
			return (left.x < right.x);
	}
};

// --------------------------------------------------

int main()
{
	std::vector<point> v;
	std::sort(v.begin(), v.end(), point_functor()); //Compiles happily with point structures

	std::set<point, point_functor> s;
	s.find(point()); //Compiles happily with point structures
	
	return 0;
}
示例#4：严格弱序 Lambda 解决方案 [编译]
#include <vector>
#include <set>

#include <algorithm>

struct point // A simple custom point structure
{
	int x, y;
};

int main()
{
	// Lambda created by the wizard
	// --------------------------------------------------
	
	auto point_lambda = [] (const point &left, const point &right) -> bool
	{
		if (left.x == right.x)
			return (left.y < right.y);
		else
			return (left.x < right.x);
	};

	// --------------------------------------------------

	std::vector<point> v;
	std::sort(v.begin(), v.end(), point_lambda); //Compiles happily with point structures
	
	std::set<point, decltype(point_lambda)> s(point_lambda);
	s.find(point()); //Compiles happily with point structures
	
	return 0;
}
示例#5：小于（<）运算符解决方案 [编译]
#include <vector>
#include <set>

#include <algorithm>

struct point // A simple custom point structure
{
	int x, y;
};

// Operator created by the wizard
// --------------------------------------------------

inline bool operator< (const point &left, const point &right)
{
	if (left.x == right.x)
		return (left.y < right.y);
	else
		return (left.x < right.x);
}

// --------------------------------------------------

int main()
{
	std::vector<point> v;
	std::sort(v.begin(), v.end()); //Compiles happily with point structures
	
	std::set<point> s;
	s.find(point()); //Compiles happily with point structures
	
	return 0;
}

这个向导在实践中有多大用处？

我预计《在线泛型数据排序向导》对许多 C++ 开发者来说将非常有用，因为我相信许多 C++ 开发者经常需要使用对自定义数据类型进行排序的泛型代码，并且让向导处理这些数据排序任务也非常方便。在接下来的段落中，我将尝试解释为什么我对这个向导有这种看法。

我们需要多久对自定义数据进行排序？

在软件开发中，对数据值进行排序的需求非常频繁，泛型 C++ 编程也不例外。例如，如果我们查看下面的表#1，我们将清楚地看到，大量的 STL 算法和容器需要对泛型数据进行排序才能工作。但值得注意的是不仅仅是这些算法和容器的数量，更重要的是表#1实际上包含了最著名和最有用的 STL 组件，例如所有的排序、合并、堆和二分查找 STL 算法以及所有的关联 STL 容器！

表#1：需要对泛型数据进行排序的 STL 组件
排序算法 sort, stable_sort, partial_sort, partial_sort_copy, nth_element
二分查找算法 lower_bound, upper_bound, equal_range, binary_search
合并算法 merge, inplace_merge
已排序范围上的集合算法 includes, set_union, set_intersection, set_difference, set_symmetric_difference
堆算法 push_heap, pop_heap, make_heap, sort_heap 
最小/最大算法 min, max, min_element, max_element
其他算法 lexicographical_compare, next_permutation, prev_permutation
已排序关联容器 set, map, multiset, multimap

STL 中对数据排序的广泛使用只是泛型 C++ 编程总体情况的反映。大多数泛型 C++ 库期望广泛使用数据排序，无论是直接在其自己的代码中，还是通过使用 STL 算法和容器间接实现，而这些算法和容器反过来又需要对泛型数据进行排序。同时，用户创建的结构和类在 C++ 中也扮演着非常重要的角色，C++ 最初被命名为C with Classes并非偶然。因此，毫无疑问，只要 C++ 开发者经常使用 STL 或其他泛型 C++ 库，那么该开发者将经常需要使用对自定义数据进行排序的泛型代码。

考虑到上述讨论，不难想象，一个能使泛型数据排序比通常情况更容易的工具，实际上可以成为许多 C++ 开发者的相当有用的工具。而这正是《在线泛型数据排序向导》的目标：成为一个有用的在线工具，它能够尽可能方便和轻松地为尽可能多的 C++ 开发者提供泛型 C++ 编程。

让向导处理数据排序有多方便？

由于 C++ 中经常需要对自定义结构和类进行排序，因此可以预期我们已经有了可行的解决方案来完成这些相对频繁的任务。事实上，《在线泛型数据排序向导》生成的解决方案既不新颖，也与最熟练的 C++ 开发者手工创建的解决方案没有本质区别。显然，手动编写向导生成的代码并获得完全相同的功能是完全可行的，而无需使用向导！然而，我们现在将看到，使用向导比手动编写处理这些问题所需的代码要方便得多，也容易得多。

为了使讨论更具体，让我们仔细看看下面的代码片段，其中您可以看到我们已经在示例#3中使用的*严格弱序*仿函数实现的完全相同版本，去除了一些额外的示例代码。*严格弱序*仿函数是用于处理泛型数据排序的最有效、泛型且通用的解决方案，也是我个人推荐的几乎所有情况下的方法。特别是如果您不确定选择哪种方法，或者想避免令人不快的意外，这无疑是正确的选择。

#include <functional> //Header file requirement

struct point_functor
	: public std::binary_function<point, point, bool>
{
	bool operator()(const point &left, const point &right) const
	{
		if (left.x == right.x)
			return (left.y < right.y);
		else
			return (left.x < right.x);
	}
};

此外，除了丑陋、繁琐和麻烦之外，*严格弱序*仿函数的编码也可能是一项相对容易出错的任务，因为在创建该仿函数时涉及几个棘手的问题。也就是说，在下面的列表中，您可以看到在*严格弱序*仿函数实现过程中，有三个重要问题需要我们特别注意：

  • 一个正确的*严格弱序*仿函数实现应该在每一个细节上都小心地遵循*严格弱序*概念 [4]。例如，尽管我们可以在上面的仿函数实现中用大于（>）运算符替换小于（<）运算符，但完全禁止使用小于等于（<=）或大于等于（>=）运算符。
  • 当*严格弱序*仿函数的参数没有通过引用传递时，其性能会受到很大影响，因为仿函数实现通常非常轻量级，以至于按值传递结构或类的性能成本会变得非常显著。
  • 为了正确适应，*严格弱序*仿函数应该派生自 std::binary_function 基类 [5]。 [6] 不幸的是，正确选择 std::binary_function 模板参数既不直观，也未得到充分记录。

与上述复杂性形成鲜明对比的是，《在线泛型数据排序向导》提供了一个超级简单、同时创建*严格弱序*仿函数、*严格弱序* lambda 函数和自定义运算符的功能，瞬间完成。如图下所示，程序员在使用此向导时只需执行三个简单的操作：在向导表单中填写三个简单字段，然后选择三种可用解决方案中最喜欢的一种。并且，作为一个简单的 HTML 页面，就客户端而言，这个向导无需安装，可在所有现代操作系统上运行，支持任何现代网页浏览器，并且只要您在线，它就始终只需一次点击即可访问。

该工具在泛型数据排序方面提供的明显便利性，对我来说有力地表明该向导将对许多 C++ 开发者非常有用。当然，您不必依赖我所说的关于该工具的便利性或有用性。相反，鼓励您访问《在线泛型数据排序向导》网页，并在网上试用该向导，以便亲身体验！

更多关于向导解决方案

我们已经提到，《在线泛型数据排序向导》提供了三种替代解决方案来排序泛型 C++ 编程中的自定义结构和类：一个*严格弱序*仿函数、一个*严格弱序* lambda 函数和一个自定义*小于（<）运算符*。现在让我们讨论一些关于这三种解决方案的有趣且可能很有用的细节。

严格弱序仿函数解决方案

在泛型 C++ 编程中，*严格弱序仿函数*是您可以使用的最有效、最通用、最通用的自定义数据排序解决方案，也是我个人几乎所有情况下的推荐方法。特别是如果您不确定选择哪种方法，或者想避免不愉快的意外，这无疑是正确的选择。

严格弱序 Lambda 解决方案

与*严格弱序仿函数*相比，*严格弱序 Lambda* 在手动实现时需要稍微不那么复杂和繁琐的代码。然而，当仿函数和 lambda 同时由《在线泛型数据排序向导》创建时，这种优势就完全无关紧要了。此外，Lambda 解决方案可能比等效的仿函数更优雅、更易读，特别是在与模板函数一起使用时。但同时，*严格弱序 Lambda* 的灵活性不如*严格弱序仿函数*，并且不可适应 [6]，只能与符合新的 C++11 标准的编译器一起工作。因此，目前我的建议是，通常优先选择*严格弱序仿函数*，而不是*严格弱序 Lambda*。

小于（<）运算符解决方案

小于（<）运算符解决方案在某种程度上与其他两种向导解决方案不同，因为它不是为我们想使用的泛型组件添加额外的功能，而是为我们需要处理的数据添加新的特性。这就是为什么在我看来，*小于（<）运算符*是向导提供的解决方案中最不灵活、最受限制且问题最多的。这种方法的一个重要问题是，它不允许以多种方式对同一数据进行排序，这意味着它将使我们很难在运行时选择多种排序方法。

此外，在实践中，仅仅因为我们代码的某个地方需要特定类型的排序而改变我们数据的特性，通常是不合适的。例如，如果我们想按照与默认升序不同的方式对数据进行排序，那么我们将不得不实现一个相当不常规且违反直觉的*小于（<）运算符*。这个违反直觉的运算符反过来很可能会在我们程序的其他部分，甚至在我们使用该特定数据结构的其他人那里，引起不期望的副作用。因此，考虑到以上所有因素，除非您有非常充分的理由选择*小于（<）运算符*方法，否则我不推荐它。

向导的其他可能用途

《在线泛型数据排序向导》主要设计用于处理泛型 C++ 编程中自定义结构和类的排序。然而，这并不意味着它不能与标准 C++ 类一起使用，如 std::string 或 std::vector。当然，由于这些标准类已经为它们定义了*小于（<）运算符*，因此使用这个向导实际上没有意义，除非我们需要默认*小于（<）运算符*无法提供的非标准排序类型。

更具体地说，让我们假设例如我们需要对 std::string 对象向量（即 vector<string> 容器）的元素进行排序。 std::sort 的默认行为将是按字母顺序对这些字符串进行排序，因为 std::string 的*小于（<）运算符*执行字典序比较。但是，如果我们想按照字符串大小的升序对该向量中的项目进行排序呢？（即根据它们的字母数量）在这种情况下，我们将不得不使用*严格弱序*仿函数或 lambda 来排序我们的数据，而让向导为我们实现这些仿函数和 lambda 将绝对是一个好主意！

如果我们使用《在线泛型数据排序向导》来按大小排序我们的 std::string 数据，我们只需转到向导页面，在向导表单中填写三个显而易见的字段（例如：size_sorter / std::string / size()），然后按创建按钮。下一步是像我在示例#6中所做的那样，将向导创建的代码与您自己的代码结合使用。（像往常一样，通过点击编译链接，您可以准确地看到示例#6如何构建和运行）

示例#6：按大小排序字符串 [编译]
#include <vector>
#include <string>

#include <algorithm>
#include <functional>
#include <iterator>

#include <iostream>

// ------------------------------------

typedef std::vector<std::string> string_vector;

// Functor created by the wizard
struct size_sorter
	: public std::binary_function<std::string, std::string, bool>
{
	bool operator() (const std::string &left, const std::string &right) const
	{
		return (left.size() < right.size());
	}
};

void test_functor_solution(string_vector sv)
{	
	std::sort(sv.begin(), sv.end(), size_sorter());
	std::copy(sv.begin(), sv.end(), std::ostream_iterator<std::string>(std::cout, " "));
}

// ------------------------------------

void test_lambda_solution(string_vector sv)
{
	// Sort with lambda created by the wizard
	std::sort(sv.begin(), sv.end(),
		[] (const std::string &left, const std::string &right) -> bool
		{
			return (left.size() < right.size());
		}
	);
	
	std::copy(sv.begin(), sv.end(), std::ostream_iterator<std::string>(std::cout, " "));
}

// ------------------------------------

int main()
{
	string_vector test_data;
	
	test_data.push_back("george");
	test_data.push_back("nick");
	test_data.push_back("peter");

	test_functor_solution(test_data);
	std::cout << std::endl;
	test_lambda_solution(test_data);
	
	return 0;
}

向导的局限性

像大多数工具一样，《在线泛型数据排序向导》也有其局限性。也就是说，该向导生成的代码专门用于处理类和结构对象的比较，并且只能通过比较最多四个公共成员变量或方法来完成。此外，在此比较中使用的所有成员变量和方法都应可以通过*小于（<）运算符*进行比较。

此外，尽管我们已经看到《在线泛型数据排序向导》可以让我们免于一些繁琐且容易出错的编码，但它仍然不能保证其生成的代码能够正确编译和执行。向导不会对其生成的代码执行任何语法检查，当然也无法知道其代码是否与我们代码的其余部分兼容。这完全取决于我们在向导表单中提供的参数。然而，通过使用这个向导，我们很可能会避免许多在手动编写严格弱序仿函数、严格弱序 lambda 或*小于（<）运算符*时极有可能发生的错误。

向导实现

从实现的角度来看，《在线泛型数据排序向导》只是一个简单的 PHP-5 Web 应用程序。我创建这个 Web 应用程序时的主要设计目标是使其在各个方面都方便实用。也就是说，我希望这个工具能够有用、非常易于使用，并且对用户或管理员的要求尽可能少。

在服务器端，我只使用了纯粹简单的 PHP-5，没有任何额外的 CMS [7] 依赖项（如 droupal、Joomla 或 WordPress）。除了 PHP-5 之外没有任何额外的依赖项，可以最大化其可移植性和易于安装性，同时预计托管成本将尽可能低。

在客户端，《在线泛型数据排序向导》只需要用户拥有一个能够渲染简单 HTML/CSS 的 Web 浏览器。不需要 Javascript、cookie、Flash 等。因此，该向导预计将在任何现代操作系统上运行，支持任何现代 Web 浏览器，并且很有可能在一些旧的或配置受限的环境中也能很好地工作。作为概念验证，我甚至尝试并成功地通过 ELinks [8] 控制台浏览器从终端模拟器内部使用此向导，如您在下图中所见，尽管我不建议大多数用户使用这种风格。

最后但同样重要的是，《在线泛型数据排序向导》是一个开源项目，其所有实现代码都可以在online-programming-utils [9] Google Code [10] 项目中找到，并根据Apache 2.0 许可证 [11] 授权。因此，您可以自由地以任何您喜欢的方式修改或扩展此向导工具。如果您进行了任何上述操作，请考虑让我知道，您将使一位程序员同事非常高兴！

修订历史

2013年6月1日
首次发布

参考文献

© . All rights reserved.