0

パラメータと同じサイズの2つのベクトルを受け取る関数があります：

void mysort(std::vector<double>& data, std::vector<unsigned int>& index)
{
   // For example :
   // The data vector contains : 9.8 1.2 10.5 -4.3
   // The index vector contains : 0 1 2 3
   // The goal is to obtain for the data : -4.3 1.2 9.8 10.5
   // The goal is to obtain for the index : 3 1 0 2
   // Using std::sort and minimizing copies
}

必要なコピーの数を最小限に抑えてその問題を解決するにはどうすればよいですか？

明らかな方法は、の単一のベクトルを作成しstd::pair<double, unsigned int>、コンパレータを指定して[](std::pair<double, unsigned int> x, std::pair<double, unsigned int> y){return x.first < y.first;}から、結果を2つの元のベクトルにコピーすることですが、効率的ではありません。

注：関数のシグネチャは固定されており、の単一のベクトルを渡すことはできませんstd::pair。

4

5 に答える 5

6

関数内positions = [0,1,2,3...] で、コンパレータを使用して位置を並べ替えるベクトルを作成し(int x, int y){return data[x]<data[y];}ます。

次に、位置を繰り返し処理します。result.push_back(index[*it]);

indexこれは、の値が任意である可能性があることを前提としています。すでに例のようになっていることが保証されている場合は、配列[0,1,2..]を作成するのではなく、その場所で使用して最後のコピーをスキップします。positionsindex

于 2012-11-28T16:42:42.677 に答える
2

http://www.boost.org/doc/libs/1_52_0/libs/iterator/doc/index.html#iterator-facade-and-adaptor

std::pair<double&, signed int&>イテレータのペアを各ベクトルに実際にラップするイテレータを上書きします。唯一のトリッキーな部分はstd::sort、結果がランダムアクセスイテレータであることを認識させることです。

Boostを使用できない場合は、同等のものを自分で作成してください。

これを行う前に、それがあなたのわざわざする価値があるかどうかを判断してください。zip、sort、unzipは記述が簡単で、プログラマーの時間は多くの場所でパフォーマンスと交換できます。最適に使用されている場所がわかるまでは、十分な作業を行ってから、必要な場所でベンチマークを実行する必要があります。物事をスピードアップします。

于 2012-11-28T16:42:29.853 に答える
1

ファンクタークラスを使用して値配列への参照を保持し、それをコンパレーターとして使用してインデックス配列を並べ替えることができます。次に、値を新しい値の配列にコピーし、内容を交換します。

struct Comparator
{
    Comparator(const std::vector<double> & data) : m_data(data) {}
    bool operator()(int left, int right) const { return data[left] < data[right]; }
    const std::vector<double> & m_data;
};

void mysort(std::vector<double>& data, std::vector<unsigned int>& index)
{
    std::sort(index.begin(), index.end(), Comparator(data));
    std::vector<double> result;
    result.reserve(data.size());
    for (std::vector<int>::iterator it = index.begin(), e = index.end();  it != e;  ++it)
        result.push_back(data[*it]);
    data.swap(result);
}
于 2012-11-28T16:42:25.143 に答える
1

カスタムイテレータクラスを使用できます。このクラスは、両方のベクトルを並行して反復します。その内部メンバーはで構成されます

  1. 各ベクトルに1つずつ、2つの参照（またはポインター）
  2. 現在位置を示すインデックス

イテレータの値型は。である必要がありpair<double, unsigned>ます。これは、std::sortアイテムを交換するだけでなく、場合によっては単一の値を一時的に保存するためです。これについての詳細は、この質問のセクション3に書きました。

参照タイプは、ベクトルと現在のインデックスの両方への参照を保持するクラスである必要があります。したがって、注意すれば、参照タイプをイテレータタイプと同じにすることができます。参照型のoperator=は、値型からの割り当てを許可する必要があります。また、swap関数はこの参照に特化して、両方のリストを個別に交換することにより、そのようなリスト項目を所定の場所で交換できるようにする必要があります。

于 2012-11-28T16:45:42.023 に答える
-1

これはそれを行う必要があります：

std::sort(index.begin(), index.end(), [&data](unsigned i1, unsigned i2)->bool
{ return data[i1]<data[i2]; });

std::sort(data.begin(), data.end());
于 2012-11-28T16:44:27.693 に答える