是否有任何可能的方法在C++中使用单一函数对自然意义上的所有类型的数据进行排序?在我的情况下,我定义了一个基于模板数据类型的链表结构,并且我想将它包含的数据作为链表排序。如何在C++中编写一个通用的排序函数?
回答
是的,你可以很自然地用链表实现插入排序。您可以使用与std::sort类似的界面编写模板化功能。
然后,您可以使用operator<
来比较任何类型的元素或Compare
函数。
您可以允许您的列表作为输入,并返回一个排序列表作为输出。
复杂性会下降到O(n^2)
与插入排序,但这是IMO最简单的方法。 我不认为你可以做更好的随机存取容器。也许合并排序可以实现列表。看起来像一个很好的候选人。
或者,您可以将列表复制/移动到支持随机访问迭代器的结构中,并用std::sort
对它进行排序并将其转换回列表。这在技术上具有更好的复杂性,但是由于2次变换操作而具有相当大的常数因子。但对于大名单,最终会更快。
你真的不应该在意拷贝或移动,而是'交换'。这也是'std :: sort'的作用。 – pmr
当你计算纯粹的计算复杂性时,当然是。当你使用数据结构对小集进行排序时(我知道你可以说我不应该关心小数据集,因为它们的定义很快),但值得记住的是复制东西也需要时间。而“交换”无论如何都是副本或移动,不是吗?此外,我认为在一个设计不好的算法中(有点像我这里粗略的草图),你将受到记忆的束缚,交换次数可能变得不那么占优势。我看到一些假设'malloc'很好的例子,并且打破了它们的复杂性。 – luk32
我并没有试图说复制或移动对性能无关紧要,而是交换概括了复制构建/移动构建。如果你有一个很好的定义(在数学意义上)“交换”,你的低层算法不需要关心底层机制。 – pmr
有多种尺寸,你可以通过通用的意思是:
- 通用相对于数据
- 通用相对于容器
第一种是最简单的解决。我们需要考虑排序需要什么工作:我们的数据为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
。
请注意,对于列表,最好修复内部列表指针而不交换数据(可能不可交换)。 – Jarod42
- 1. 如何在C编写一个函数
- 2. 如何在C中编写函数的通用钩子?
- 3. 如何在C++中编写一个默认的构造函数?
- 4. 如何在c#中编写通用函数?
- 5. 如何编写在C++中使用其他函数的函数
- 6. 如何在c#中编写一个通用函数,它将根据类的类型调用不同的函数?
- 7. 如何在c#中编写ajax函数#
- 8. 如何在C中编写函数?
- 9. 如何编写一个函数在Python
- 10. 如何编写通用的“getData”函数?
- 11. 如何在C#中编写这个C++函数?
- 12. 如何用Python语言编写一个比较函数来排序日期
- 13. 在目标c中编写一个简单的C++函数
- 14. 如何编写一个返回另一个函数的函数?
- 15. 如何在php中编写一个通用的db插入函数
- 16. 如何编写通用转换函数?
- 17. 如何编写一个函数用它的参数调用一个函数?
- 18. 如何编写一个排序并附加到新列表的函数?
- 19. 如何用C++编写构造函数?
- 20. 编写一个原型函数(C++)
- 21. 在java中编写通用函数
- 22. 如何编写一个创建空队列的c函数?
- 23. 如何编写一个清除内存池的函数C
- 24. 如何编写一个Objective-C的便利构造函数
- 25. 如何在函数中编写一个Traversable实例,在Haskell中?
- 26. C++如何写一个构造函数?
- 27. 如何在swift中编写这个objective-c函数?
- 28. 如何在swift中编写这个void objective-c函数
- 29. 在Django中,我如何为每个函数编写一个?
- 30. 帮助在C#中编写C函数#
Ahem ['std :: sort'](http://en.cppreference.com/w/cpp/algorithm/sort)? – Borgleader
@Borgleader - 海报说他有一个链表,它不会与'std :: sort'一起工作,因为它不太可能是一个随机访问结构。 – Sean
@肖恩你错过了这一点。问题是“是否可能”。是的,看看std :: sort。 – Borgleader