59

いくつかstd::vectorありますが、すべて同じ長さです。これらのベクトルの 1 つを並べ替え、他のすべてのベクトルに同じ変換を適用したいと考えています。これを行うきちんとした方法はありますか？（できればSTLまたはBoostを使用してください）？一部のベクトルはints を保持し、一部のベクトルは s を保持しますstd::string。

擬似コード:

std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };

Transformation = sort(Index);
Index is now { 1, 2, 3};

... magic happens as Transformation is applied to Values ...
Values are now { "First", "Second", "Third" };
4

13 に答える 13

30

friol のアプローチは、あなたのアプローチと組み合わせると優れています。まず、番号 1…<em>n で構成されるベクトルを、ソート順を指示するベクトルの要素とともに作成します。

typedef vector<int>::const_iterator myiter;

vector<pair<size_t, myiter> > order(Index.size());

size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
    order[n] = make_pair(n, it);

これで、カスタム ソーターを使用してこの配列を並べ替えることができます。

struct ordering {
    bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
        return *(a.second) < *(b.second);
    }
};

sort(order.begin(), order.end(), ordering());

orderこれで、再配置の順序を内部(より正確には、アイテムの最初のコンポーネント内)にキャプチャできました。この順序付けを使用して、他のベクトルを並べ替えることができます。同時に非常に巧妙なインプレース バリアントが実行されている可能性がありますが、他の誰かがそれを思いつくまで、インプレースではない 1 つのバリアントをここに示します。order各要素の新しいインデックスのルックアップ テーブルとして使用します。

template <typename T>
vector<T> sort_from_ref(
    vector<T> const& in,
    vector<pair<size_t, myiter> > const& reference
) {
    vector<T> ret(in.size());

    size_t const size = in.size();
    for (size_t i = 0; i < size; ++i)
        ret[i] = in[reference[i].first];

    return ret;
}
于 2008-10-25T10:24:07.063 に答える
10 
typedef std::vector<int> int_vec_t;
typedef std::vector<std::string> str_vec_t;
typedef std::vector<size_t> index_vec_t;

class SequenceGen {
  public:
    SequenceGen (int start = 0) : current(start) { }
    int operator() () { return current++; }
  private:
    int current;
};

class Comp{
    int_vec_t& _v;
  public:
    Comp(int_vec_t& v) : _v(v) {}
    bool operator()(size_t i, size_t j){
         return _v[i] < _v[j];
   }
};

index_vec_t indices(3);
std::generate(indices.begin(), indices.end(), SequenceGen(0));
//indices are {0, 1, 2}

int_vec_t Index = { 3, 1, 2 };
str_vec_t Values = { "Third", "First", "Second" };

std::sort(indices.begin(), indices.end(), Comp(Index));
//now indices are {1,2,0}

これで、「インデックス」ベクトルを使用して「値」ベクトルにインデックスを付けることができます。

于 2008-12-05T04:47:38.177 に答える
8

値をBoost Multi-Index コンテナに入れ、反復処理を行って必要な順序で値を読み取ります。必要に応じて、それらを別のベクターにコピーすることもできます。

于 2008-10-26T14:48:07.897 に答える
4

私の頭に浮かぶ大まかな解決策は 1 つだけです。他のすべてのベクトルの合計であるベクトル ({3,Third,...},{1,First,...} などの構造のベクトル) を作成し、これを並べ替えます。最初のフィールドでベクトル化し、構造体を再度分割します。

おそらく、Boost 内または標準ライブラリを使用するより良い解決策があります。

于 2008-10-25T10:15:33.727 に答える
3

ここで必要なことを実行するカスタムの「ファサード」イテレータをおそらく定義できます。すべてのベクトルにイテレータを格納するか、最初のベクトルのオフセットから最初のベクトルを除くすべてのベクトルのイテレータを導出します。トリッキーな部分は、イテレータが逆参照するものです。boost:: tupleのようなものを考え、boost::tieを巧みに利用します。（このアイデアを拡張したい場合は、テンプレートを使用してこれらのイテレーター型を再帰的に構築できますが、おそらくその型を書き留めたくないでしょう-したがって、範囲を取るソートにはc ++ 0x autoまたはラッパー関数が必要です）

于 2010-11-24T10:42:00.320 に答える
3

あなたが本当に必要としているのは(間違っていたら訂正してください)、ある順序でコンテナの要素にアクセスする方法だと思います。

元のコレクションを再配置するのではなく、データベースの設計から概念を借用します。特定の基準に従って並べ替えられたインデックスを保持します。このインデックスは、優れた柔軟性を提供する追加の間接化です。

このようにして、クラスのさまざまなメンバーに従って複数のインデックスを生成できます。

using namespace std;

template< typename Iterator, typename Comparator >
struct Index {
    vector<Iterator> v;

    Index( Iterator from, Iterator end, Comparator& c ){
        v.reserve( std::distance(from,end) );
        for( ; from != end; ++from ){
            v.push_back(from); // no deref!
        }
        sort( v.begin(), v.end(), c );
    }

};

template< typename Iterator, typename Comparator >
Index<Iterator,Comparator> index ( Iterator from, Iterator end, Comparator& c ){
    return Index<Iterator,Comparator>(from,end,c);
}

struct mytype {
    string name;
    double number;
};

template< typename Iter >
struct NameLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; }
};

template< typename Iter >
struct NumLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->number < t2->number; }
};

void indices() {

    mytype v[] =    { { "me"    ,  0.0 }
                    , { "you"   ,  1.0 }
                    , { "them"  , -1.0 }
                    };
    mytype* vend = v + _countof(v);

    Index<mytype*, NameLess<mytype*> > byname( v, vend, NameLess<mytype*>() );
    Index<mytype*, NumLess <mytype*> > bynum ( v, vend, NumLess <mytype*>() );

    assert( byname.v[0] == v+0 );
    assert( byname.v[1] == v+2 );
    assert( byname.v[2] == v+1 );

    assert( bynum.v[0] == v+2 );
    assert( bynum.v[1] == v+0 );
    assert( bynum.v[2] == v+1 );

}
于 2008-10-26T14:33:26.303 に答える
1

ltjaxの答えは素晴らしいアプローチです - 実際にはboostのzip_iterator http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.htmlに実装されています

提供するイテレータが何であれ、タプルにまとめてパッケージ化します。

次に、タプル内の反復子値の任意の組み合わせに基づいて、並べ替え用の独自の比較関数を作成できます。この質問では、タプルの最初の反復子になります。

このアプローチの優れた機能は、個々のベクトルのメモリを連続した状態に保つことができることです (ベクトルを使用していて、それが必要な場合)。また、int の個別のインデックス ベクトルを格納する必要もありません。

于 2011-12-21T02:53:27.387 に答える
1

単一のベクトルに基づいてすべてのベクトルを反復処理するだけの場合は、 xtofl の答えのもう少しコンパクトな変形ですkeys。順列ベクトルを作成し、これを使用して他のベクトルにインデックスを付けます。

#include <boost/iterator/counting_iterator.hpp>
#include <vector>
#include <algorithm>

std::vector<double> keys = ...
std::vector<double> values = ...

std::vector<size_t> indices(boost::counting_iterator<size_t>(0u), boost::counting_iterator<size_t>(keys.size()));
std::sort(begin(indices), end(indices), [&](size_t lhs, size_t rhs) {
    return keys[lhs] < keys[rhs];
});

// Now to iterate through the values array.
for (size_t i: indices)
{
    std::cout << values[i] << std::endl;
}
于 2014-10-23T16:38:14.087 に答える