47

やりたいこと: 2 つ、3 つ、または N 個のベクトルを、タプルにコピーせずに、一緒にロックして並べ替えたい。つまり、冗長性はさておき、次のようなものです。

vector<int>    v1 = {  1,   2,   3,   4,   5};
vector<double> v2 = { 11,  22,  33,  44,  55};
vector<long>   v3 = {111, 222, 333, 444, 555};

typedef tuple<int&,double&,long&> tup_t;
sort(zip(v1,v2,v3),[](tup_t t1, tup_t t2){ return t1.get<0>() > t2.get<0>(); });

for(auto& t : zip(v1,v2,v3))
  cout << t.get<0>() << " " << t.get<1>() << " " << t.get<2>() << endl;

これにより、次のように出力されます。

5 55 555
4 44 444
...
1 11 111

現在の方法:独自のクイックソートを実装しました。最初に渡した配列が比較に使用され、順列が他のすべての配列に適用されます。私の問題のために std::sort を再利用する方法がわかりませんでした (例: 順列の抽出)。

私が試したこと: boost::zip_iteratorとboost::zip_range (boost::combine range を使用)、しかし std::sort とboost::range::algorithm::sortの両方が、イテレータ/範囲が読み取り専用であると不平を言うランダムアクセスではありません...

質問:ロック ステップ (zip 形式) で N ベクトルを並べ替えるにはどうすればよいですか? 問題はかなり一般的で一般的なように見えるので、おそらく非常に複雑なライブラリを介した簡単な解決策があるに違いないと思いますが、見つけることができません...

備考:はい、stackoverflow にも同様の質問があります。この質問は、さまざまな形でよく尋ねられます。ただし、それらは常に次のいずれかの回答で閉じられます。

  • ベクターをペア/タプルにコピーし、そのタプルをソートします...
  • ベクトルをベクトルごとに 1 つのメンバーを持つ構造体にコピーし、構造体のベクトルを並べ替えます...
  • 特定の問題に対して独自のソート機能を実装します...
  • インデックスの補助配列を使用...
  • 例なしでboost::zip_iteratorを使用するか、悪い結果をもたらす例を使用してください。

ヒント：

  • Boost メーリング リストでこのスレッドを見つけました。このスレッドは、Anthony Williams のこの論文を示しています。これはペアでしか機能しないようですが、 TupleIteratorType についても議論していますが、見つけることができませんでした。
  • user673679は、2 つのコンテナーの場合の優れたソリューションを含むこの投稿を見つけました。それはまた問題を突き止めます（強調は私のものです）：

[...] 根本的な問題は、配列参照の「ペア」が本来あるべき動作をしないことです [...] イテレータの表記法を悪用して、機能するものを書くことにしました。これには、事実上、値の型の参照が参照の型と同じではない非準拠のイテレータを書くことが含まれていました。

回答:以下の interjay によるコメントを参照してください(これは将来の質問にも部分的に回答します):

#include "tupleit.hh"
#include <vector>
#include <iostream>
#include <boost/range.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/algorithm/for_each.hpp>

template <typename... T>
auto zip(T&... containers)
    -> boost::iterator_range<decltype(iterators::makeTupleIterator(std::begin(containers)...))> {
  return boost::make_iterator_range(iterators::makeTupleIterator(std::begin(containers)...),
                                      iterators::makeTupleIterator(std::end(containers)...));
}

int main() {

  typedef boost::tuple<int&,double&,long&> tup_t;

  std::vector<int>    a = {   1,   2,   3,   4 };
  std::vector<double> b = {  11,  22,  33,  44 };
  std::vector<long>   c = { 111, 222, 333, 444 };

  auto print = [](tup_t t){ std::cout << t.get<0>() << " " << t.get<1>() << " " << t.get<2>() << std::endl; };

  boost::for_each( zip(a, b, c), print);

  boost::sort( zip(a, b, c), [](tup_t i, tup_t j){ return i.get<0>() > j.get<0>(); });

  for ( auto tup : zip(a, b, c) ) print(tup);

  return 0;
}

今後の質問:前の回答はシーケンス コンテナーに有効です。並べ替え可能なコンテナ (シーケンスやリストなど)でも動作するようにできますか? これには、random_access と双方向 TupleIterator、および双方向イテレータで機能するソート アルゴリズムが必要です。

更新:これは、シーケンスのようなコンテナーの組み合わせで機能します。ただし、リストを混在させるには、std::sort が BidirectionalIterator をサポートしている必要があります (そうではありません)。

4

5 に答える 5

7

2 つのコンテナーの場合、上記の論文に基づいて、gcc 4.4.6 でコンパイルされるバージョンを次に示します。gcc の以降のバージョンでは、boost::tuple を std::tuple に交換できます。

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

# include <boost/iterator/iterator_facade.hpp>
# include <boost/tuple/tuple.hpp> 

using namespace std;

template <class T, class T2>
struct helper_type {
  typedef boost::tuple<typename iterator_traits<T>::value_type, typename iterator_traits<T2>::value_type> value_type;
  typedef boost::tuple<typename iterator_traits<T>::value_type&, typename iterator_traits<T2>::value_type&> ref_type;
};

template <typename T1, typename T2>
class dual_iterator : public boost::iterator_facade<dual_iterator<T1, T2>,
                                                    typename helper_type<T1, T2>::value_type,
                                                    boost::random_access_traversal_tag,
                                                    typename helper_type<T1, T2>::ref_type> {
public:
   explicit dual_iterator(T1 iter1, T2 iter2) : mIter1(iter1), mIter2(iter2) {}
   typedef typename iterator_traits<T1>::difference_type difference_type;
private:
   void increment() { ++mIter1; ++mIter2; }
   void decrement() { --mIter1; --mIter2; }
   bool equal(dual_iterator const& other) const { return mIter1 == other.mIter1; }
   typename helper_type<T1, T2>::ref_type dereference() const { return (typename helper_type<T1, T2>::ref_type(*mIter1, *mIter2)); }
   difference_type distance_to(dual_iterator const& other) const { return other.mIter1 - mIter1; }
   void advance(difference_type n) { mIter1 += n; mIter2 += n; }

   T1 mIter1;
   T2 mIter2;
   friend class boost::iterator_core_access;
};

template <typename T1, typename T2>
dual_iterator<T1, T2> make_iter(T1 t1, T2 t2) { return dual_iterator<T1, T2>(t1, t2); }

template <class T1, class T2> struct iter_comp {
  typedef typename helper_type<T1, T2>::value_type T;
  bool operator()(const T& t1, const T& t2) { return get<0>(t1) < get<0>(t2); }
};

template <class T1, class T2> iter_comp<T1, T2> make_comp(T1 t1, T2 t2) { return iter_comp<T1, T2>(); }

template<class T> void print(T& items) {
  copy(items.begin(), items.end(), ostream_iterator<typename T::value_type>(cout, " ")); cout << endl;
}

int main() {
  vector<double> nums1 = {3, 2, 1, 0};
  vector<char> nums2 = {'D','C', 'B', 'A'};
  sort(make_iter(nums1.begin(), nums2.begin()), 
       make_iter(nums1.end(), nums2.end()), 
       make_comp(nums1.begin(), nums2.begin()));
  print(nums1);
  print(nums2);
}
于 2013-09-19T22:02:01.307 に答える
5

インデックス 0..N-1 を含む補助配列を作成します。プライマリ配列の 1 つの要素を比較した結果を実際に返すカスタム コンパレータを使用して、その配列を並べ替えます。次に、ソートされた補助配列を使用して、プライマリ配列を正しい順序で出力します。

于 2012-12-12T15:47:35.327 に答える
3

仲間のインターネット考古学者に会えてうれしいです !

ロックステップ (zip 形式) で N ベクトルをソートするにはどうすればよいですか? 問題はかなり一般的で一般的なように見えるので、おそらく非常に複雑なライブラリを介した簡単な解決策があるに違いないと思いますが、見つけることができません。

時々、私は同じような仮定で同じ宝探しに行きました...
宝物を見つけたことはありません:(

私はあなたと同じ道をたどりました：

  • 通常の容疑者 boost.iterator/boost.range/boost.fusion/boost.oven を調べて、多くの実験と研究を行った後、この特定の問題を解決できないことがわかりました。
  • SOに関する多くの質問に目を通しますが、すべての質問が間違った回答で閉じられていることに気付くだけです(たとえば、ご指摘のようにこの場合は機能しないboost::zip_iteratorを推奨する)、または問題の核心。
  • 多くのブログ投稿、メーリング リストに目を通すと、誰も実際に問題を解決していないことに気付くだけです....
  • 多くの調査の後、最終的に Antonius Wilhelm による古いコーデックスを掘り起こしました。Antonius Wilhelm は、一般的なソリューション「TupleIterator」を作成し、それをアーカイブ「tupleit.zip」内にロックしたと主張しています。これに関する歴史的な情報源は非常に少ないため、このアーカイブが神話なのか伝説なのか、それともインターネットの失われた層のどこかにまだ埋もれているのかはまだわかりません:)

わかりました、もっと真剣に、Anthony Williams の論文は、問題が実際には非常に難しいことを示唆しているため、boost のような既存のライブラリがそれを解決していないことを発見してもそれほど驚くべきことではありません。

于 2012-12-13T11:07:31.360 に答える