-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

基本的には、それぞれが静的に(つまり、コンパイル時に)ソート順を認識している 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>;
}

内側のループにはまだ 3 項ステートメントがありますが、これは定数であるため、簡単に最適化して取り除くことができることに注意してくださいAscending(インスタンス化ごとに定数が異なるだけです)。

よりクリーンな方法は、三項ステートメントを完全に削除し、代わりにある種の比較関数を内部関数テンプレートに渡すことです。関数ポインターまたはラムダを渡すことができます。組み込みの関数オブジェクトを使用しているのは、それらが既に必要なことを行っているためです。

// 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

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

本当にパフォーマンスが必要な場合は、1 つではなく 2 つの関数を作成できます。しかし、重複につながります。これは、C++ がテンプレートで輝くところです。

于 2013-07-19T12:13:12.670 に答える