質問

2つのベクトルを同じように並べ替えるにはどうしたらよいでしょうか。

例えば、同じ大きさの2つのベクトルがあるとします。

vector<MyObject> vectorA;
vector<int> vectorB;

次に vectorA を何らかの比較関数を使って並べ替えます。この並べ替えは vectorA . どうすれば、同じ並べ替えを vectorB ?

構造体を作成するのも一つの方法です。

struct ExampleStruct {
    MyObject mo;
    int i;
};

の内容を含むベクトルをソートし、さらに vectorA と vectorB を1つのベクターに圧縮しています。

// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;

これは理想的な解決策とは思えません。特に C++11 では、他のオプションがあるのでしょうか？

どのように解決するのですか?

ソート順列を見つける

与えられた std::vector<T> の比較と T の比較で、この比較を用いてベクトルをソートする場合に使用する順列を見つけることができるようにしたい。

template <typename T, typename Compare>
std::vector<std::size_t> sort_permutation(
    const std::vector<T>& vec,
    Compare& compare)
{
    std::vector<std::size_t> p(vec.size());
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
        [&](std::size_t i, std::size_t j){ return compare(vec[i], vec[j]); });
    return p;
}

ソート順列を適用する

与えられた std::vector<T> と並べ替えがあるとき、私たちは新しい std::vector<T> を構築できるようにしたい。

template <typename T>
std::vector<T> apply_permutation(
    const std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<T> sorted_vec(vec.size());
    std::transform(p.begin(), p.end(), sorted_vec.begin(),
        [&](std::size_t i){ return vec[i]; });
    return sorted_vec;
}

もちろん apply_permutation を変更して、新しいソートされたコピーを返すのではなく、 与えられたベクトルを変異させることもできます。このアプローチでも時間の複雑さは線形であり、ベクター内のアイテムごとに 1 つのビットを使用します。理論的には、空間の複雑さもまだ線形ですが、実際には sizeof(T) が大きい場合、メモリ使用量の削減は劇的なものになります。( 詳細を見る )

template <typename T>
void apply_permutation_in_place(
    std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<bool> done(vec.size());
    for (std::size_t i = 0; i < vec.size(); ++i)
    {
        if (done[i])
        {
            continue;
        }
        done[i] = true;
        std::size_t prev_j = i;
        std::size_t j = p[i];
        while (i != j)
        {
            std::swap(vec[prev_j], vec[j]);
            done[j] = true;
            prev_j = j;
            j = p[j];
        }
    }
}

例

vector<MyObject> vectorA;
vector<int> vectorB;

auto p = sort_permutation(vectorA,
    [](T const& a, T const& b){ /*some comparison*/ });

vectorA = apply_permutation(vectorA, p);
vectorB = apply_permutation(vectorB, p);

リソース

• std::vector
• std::iota
• std::sort
• std::swap
• std::transform