-1

我尝试编写一个插入排序函数，该函数将根据其参数 ( order) 的符号在升序和降序之间切换。它可以工作，但看起来不正确，因为我用作开关的条件运算符会给内部循环的每次迭代增加一些开销。因此，我想就如何编写更好的函数版本征求您的意见。

void Array::sort(int order) //Array is a struct that contains a vector of pointers named vect, as well as this function.
{
  if (order==0) return;
  bool ascending = (order>0);
  int i,j;
  Data* buffer; //Data is a struct containing some variables, including the key that has to be sorted.
  for (i=1; i<_size; i++)
  {
    buffer = vect[i]; //A vector of pointers to Data objects declared in the Array struct.
    j=i-1;
    while ( j>=0 && (ascending?(vect[j]->key > buffer->key):(vect[j]->key < buffer->key)))
    {
      vect[j+1] = vect[j];
      j--;
    }
    vect[++j] = buffer;
  }
}
4

3 回答 3

2

您实际上想编写两个函数，每个函数都静态知道其排序顺序（即在编译时），然后选择动态调用哪一个。

最简单的改变是这样的：

// original code, templated
template <bool Ascending>
void Array::sort() {
  int i,j;
  Data* buffer;
  for (i=1; i<_size; i++) {
    buffer = vect[i];
    j=i-1;
    while (j>=0 && (Ascending?(vect[j]->key > buffer->key):(vect[j]->key < buffer->key)))
    {
      vect[j+1] = vect[j];
      j--;
    }
    vect[++j] = buffer;
  }
}

// original prototype
void Array::sort(int order) {
  if (order > 0)
    sort<true>();
  else if (order < 0)
    sort<false>;
}

请注意，尽管内部循环中仍然有一个三元语句，但它可以很容易地被优化掉，因为Ascending它是常量（每个实例中只是一个不同的常量）。

一种更简洁的方法是完全删除三元语句，而是将某种比较函数传递给内部函数模板。我们可以传递一个函数指针或一个 lambda - 我正在使用内置函数对象，因为它们已经做了我们想要的。

// Comparitor is some type you can call to compare two arguments
template <typename Comparitor>
void Array::sort(Comparitor comp) {
  int i,j;
  Data* buffer;
  for (i=1; i<_size; i++) {
    buffer = vect[i];
    j=i-1;
    while (j>=0 && comp(vect[j]->key, buffer->key)) {
      vect[j+1] = vect[j];
      j--;
    }
    vect[++j] = buffer;
  }
}

// std::greater and less come from <functional>
void Array::sort(int order) {
  typedef decltype(vect[0]->key) KeyType; // or use the real type directly
  if (order > 0)
    sort(std::greater<KeyType>());
  else if (order < 0)
    sort(std::less<KeyType>());
}
于 2013-07-19T12:16:16.937 回答
1

一种选择是使用模板，并将您的功能重新定义为

template<class T> void Array::sort(T op)
{
    ...
    while ( j>=0 && op(vect[j]->key,buffer->key))
    ...
}

然后您可以使用适当的排序对象调用您的排序

struct LessThan : public std::binary_function<int, int, bool>   {
    bool operator() (int x, int y) const { return x < y; }
};
struct GreaterThan : public std::binary_function<int, int, bool>    {
    bool operator() (int x, int y) const { return x > y; }
};

Array::sort(LessThan());
于 2013-07-19T12:12:53.823 回答
0

如果你真的想要性能，你可以写两个函数，而不是一个。但会导致重复。这就是 C++ 模板的亮点所在。

于 2013-07-19T12:13:12.670 回答