c++ - 我将如何封装一个合并排序程序以供 C++ 中的一般客户使用？

Question

我目前有一个合并排序，它接受一个整数列表并从中创建一个数组，然后对它们进行排序，并打印出排序后的数组。目前所有代码都在一个 .cpp 文件中。

向想要对用户定义对象数组进行排序的人提供代码的好方法是什么？

我的直觉是提供一个仅虚拟方法的文件（接口），并要求我的用户覆盖比较运算符和读/写方法。

最好远离数组并使用链表吗？

如果这太模糊/主观，那么只需拍打我并关闭它。我只是想要一些超出我自己的想法。

Answer 1

使用模板来实现排序并使用指针数组而不是对象数组请求实现比较的函子，并提供使用<运算符进行比较的默认函子。

Answer 2

这是使用标准库的方法。

如果客户有自己的类型，他们需要定义operator<排序和operator<<打印到ostream：

class Type {
    //...
};

bool operator<(const Type& lhs, const Type& rhs) {
    //...
}

ostream& operator<<(ostream& os, const Type& object) {
    //...
}

vector<Type> originals;
vector<Type> values = originals;

stable_sort(values.begin(), values.end());
copy(values.begin(), values.end(),
     ostream_iterator<Type>(cout, "\n"));

您的客户必须有充分的理由不这样做。

Answer 3

不，您不需要链表。

无需过多挖掘仿函数的最简单解决方案：

template <class T, int size>
class MergeSort
{
   T* arr[size];

   MergeSort(T* array[size])
   {
     // ...
   }

   void Sort()
   {
      // The rest is simple...
   }
};