2014-01-20 57 views
1

是否有任何可能的方法在C++中使用单一函数对自然意义上的所有类型的数据进行排序?在我的情况下,我定义了一个基于模板数据类型的链表结构,并且我想将它包含的数据作为链表排序。如何在C++中编写一个通用的排序函数?

+9

Ahem ['std :: sort'](http://en.cppreference.com/w/cpp/algorithm/sort)? – Borgleader

+0

@Borgleader - 海报说他有一个链表,它不会与'std :: sort'一起工作,因为它不太可能是一个随机访问结构。 – Sean

+0

@肖恩你错过了这一点。问题是“是否可能”。是的,看看std :: sort。 – Borgleader

回答

-1

是的,你可以很自然地用链表实现插入排序。您可以使用与std::sort类似的界面编写模板化功能。

然后,您可以使用operator<来比较任何类型的元素或Compare函数。

您可以允许您的列表作为输入,并返回一个排序列表作为输出。

复杂性会下降到O(n^2)与插入排序,但这是IMO最简单的方法。 我不认为你可以做更好的随机存取容器。也许合并排序可以实现列表。看起来像一个很好的候选人。

或者,您可以将列表复制/移动到支持随机访问迭代器的结构中,并用std::sort对它进行排序并将其转换回列表。这在技术上具有更好的复杂性,但是由于2次变换操作而具有相当大的常数因子。但对于大名单,最终会更快。

+0

你真的不应该在意拷贝或移动,而是'交换'。这也是'std :: sort'的作用。 – pmr

+0

当你计算纯粹的计算复杂性时,当然是。当你使用数据结构对小集进行排序时(我知道你可以说我不应该关心小数据集,因为它们的定义很快),但值得记住的是复制东西也需要时间。而“交换”无论如何都是副本或移动,不是吗?此外,我认为在一个设计不好的算法中(有点像我这里粗略的草图),你将受到记忆的束缚,交换次数可能变得不那么占优势。我看到一些假设'malloc'很好的例子,并且打破了它们的复杂性。 – luk32

+0

我并没有试图说复制或移动对性能无关紧要,而是交换概括了复制构建/移动构建。如果你有一个很好的定义(在数学意义上)“交换”,你的低层算法不需要关心底层机制。 – pmr

1

有多种尺寸,你可以通过通用的意思是:

  1. 通用相对于数据
  2. 通用相对于容器

第一种是最简单的解决。我们需要考虑排序需要什么工作:我们的数据为strict weak ordering。现在我们知道我们需要提供给排序算法的函数的性质,并需要一种方法来传递函数。在C++中,假设operator<实现这样的顺序或将函子传递给实现它的算法已成为常态。所以签名会变成:

template<typename T, typename Comp = std::less<T>> 
my_sort(my_list<T>& l, Comp c = Comp()); 

我们的排序算法必须执行另一个操作:交换元素。正如我们在这个我们自己的小世界中,我们可以假设我们所有的类型都有一个成员函数T::swap(T& rhs),它正是这样做的。在现实世界中,我们将使用免费函数std::swap(具有非限定的调用和使用指令,但这是一个晦涩的技术性)。

第二个问题更棘手,你实际上不想解决它,因为你只希望你的排序算法在你的列表实现上工作。我鼓励您深入探讨std::sort及其要求,了解为什么它以这种方式实施,以及为什么它不适用于std::list

+2

请注意,对于列表,最好修复内部列表指针而不交换数据(可能不可交换)。 – Jarod42

相关问题