9

次のようなオブジェクトのベクトルがあるとします。

  • コピーの構築と割り当ては高価です
  • デフォルトの構築と 2 つのオブジェクトの交換は安価です。

これは、ベクトルのベクトルなど、ビッグデータへの参照を持つオブジェクトにとって非常に標準的なようです。

質問std::sort: を使用して、または標準ライブラリの他のソート ルーチンを使用して、このベクトルをソートする方法はありますか? 私は事前c++0x解決策を探しています（移動セマンティクスはありません）。

のオーバーロードはstd::swap最初の自然な試みのように思われ、少しは役に立ちますが、コピーのほんの一部しか取り除かれません。

注: gcc の動作例

sort のため100 81 64 49 36 25 16 9 4 1 0 1 4 9 16 25 36 49 64 81に、私の gcc std::sort は 19 個のコピー コンストラクター、92 個の代入、および 6 個のスワップを呼び出します。

4

2 に答える 2

2 
// C++03 solution won't work with arrays and some other custom containers.
// Mostly drop this block:
#include <type_traits>
#include <vector>
#include <algorithm>
#include <iostream>
namespace aux {
  using std::begin; using std::end;
  template<typename C> auto adl_begin( C&& c )->decltype( begin(c) );
  template<typename C> auto adl_end( C&& c )->decltype( end(c) );

  template<typename C>
  struct container_traits:
    std::iterator_traits< typename std::decay< decltype( aux::adl_begin( *(C*)nullptr ) ) >::type >
  {
    typedef typename std::decay< decltype( adl_begin( *(C*)nullptr ) ) >::type iterator_type;
  };
}

// C++03 solution won't work with arrays.  Inside std::less, use Container::value_type:
template<
  typename Container,
  typename Comparison = std::less<
    typename aux::container_traits<Container>::value_type
  >
>
void indirect_sort_then_swap( Container& c, Comparison&& comp = Comparison() ) {
  typedef aux::container_traits<Container> con_traits;
  typedef typename con_traits::value_type value_type;
  typedef typename con_traits::iterator_type iterator_type;
  std::vector< iterator_type > indirect;
  {
    // C++03 solution can use c.begin(), but will not work with arrays:
    using std::begin; using std::end;
    auto begin_ = begin(c);
    auto end_ = end(c);
    for( auto it = begin_; it != end_; ++it ) {
      indirect.push_back( it );
    }
  }
  // In C++03, write a functor class that does this:
  auto indirect_sort = [&comp]( iterator_type const& left, iterator_type const& right )->bool {
    return comp(*left, *right);
  };
  std::sort( indirect.begin(), indirect.end(), indirect_sort );
  // at this point, indirect is a vector with the contents of c sorted by iterator:
  // a hard part remains, namely to take this information and sort c with minimal swaps
  // That is hard.  I will instead create an easy approach, namely create an empty
  // copy of c full of empty elements, and directly swap the correct entry of c into
  // each slot, then I swap c with its copy.
  // the downside is that my container now needs to support push_back.  Oh well.
  Container c2;
  // C++03 solution cannot use auto here.  But we know the type of indirect:
  for (auto it = indirect.begin(); it != indirect.end(); ++it) {
    // See previous comment
    auto itv = *it;
    c2.push_back( value_type() );
    using std::swap;
    swap( *itv, c2.back() );
  }
  // by this point, the contents of c have been swap-moved to c2
  // swap them back:
  {
    using std::swap;
    swap( c, c2 );
  }
}

int main() {
   std::vector<int> foo;
   foo.push_back(7);
   foo.push_back(3);
   indirect_sort_then_swap(foo);
   for (auto i:foo) {
      std::cout << i << "\n";
   }
}

上記のようなものは実行可能なアプローチです。私はそれをC++11でたくさん書きましたが、余分なC ++ 11のものを取り除く方法についてのコメントを含めました（実際にはコードを単純化する場合もありますが、コンテナーのようなものを処理する機能を削除します）。

vector基本的な考え方は、のiteratorを元のコンテナにソートすることです。次に、一時コンテナを作成しvalue_type、その中に些細なものを詰め込みます。これらのswap些細なものvalue_typeには、元のコンテナからの正しいデータ（vector並べ替えられたのによって決定されるiterator）が含まれ、次にswapこの一時的なコンテナが元のコンテナに使用されます。

割り当てはたくさんありますが、うまくいけば安いものです。

これが機能するためには、ソートするデータが簡単に構築できる必要があります。これを効率的にするには、自明に構築されたときに使用するデータが安価であり、swap効率的である必要があります。

私はこれをできるだけADLに適したものにしようとしました。これは、良い習慣だと思ったからです。

于 2013-01-07T15:26:51.883 に答える
1

ヒープソートは、安定していないスワップのみのソートです (ソート中に同等の要素の順序が変わる可能性があります)。ヒープソートを自分で実装した別の同様の質問( PasteBin )に答えましたが、より優れた柔軟な実装が見つかるかもしれません。

結論として、g++std::sortは 20 個の要素に対して 35 回のコピー、19 回の代入、10 回のスワップ、35 回の削除 (全部で 99 回の操作) を使用し、私のヒープ ソートでは 62 回のスワップを使用し、他には何も使用しませんでした。

ここでスタックオーバーフローのスワップのみを使用する安定した並べ替えに遭遇しました。私はそれを深く調べませんでした。

于 2013-02-23T10:26:07.270 に答える