[C++] Как я могу сортировать два вектора одинаково, с критериями, которые используют только один из векторов?


Answers

Сортировка на месте с использованием перестановки

Я бы использовал такую ​​перестановку, как Timothy, хотя, если ваши данные слишком велики, и вы не хотите выделять больше памяти для отсортированного вектора, вы должны сделать это на месте . Ниже приведен пример сортировки места на основе O (n) (линейной сложности) с использованием перестановки :

Хитрость заключается в том, чтобы получить перестановку и обратную перестановку, чтобы знать, куда помещать данные, перезаписанные на последнем этапе сортировки.

template <class K, class T> 
void sortByKey(K * keys, T * data, size_t size){
    std::vector<size_t> p(size,0);
    std::vector<size_t> rp(size);
    std::vector<bool> sorted(size, false);
    size_t i = 0;

    // Sort
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
                    [&](size_t i, size_t j){ return keys[i] < keys[j]; });

    // ----------- Apply permutation in-place ---------- //

    // Get reverse permutation item>position
    for (i = 0; i < size; ++i){
        rp[p[i]] = i;
    }

    i = 0;
    K savedKey;
    T savedData;
    while ( i < size){
        size_t pos = i;
        // Save This element;
        if ( ! sorted[pos] ){
            savedKey = keys[p[pos]];
            savedData = data[p[pos]];
        }
        while ( ! sorted[pos] ){
            // Hold item to be replaced
            K heldKey  = keys[pos];
            T heldData = data[pos];
            // Save where it should go
            size_t heldPos = rp[pos];

            // Replace 
            keys[pos] = savedKey;
            data[pos] = savedData;

            // Get last item to be the pivot
            savedKey = heldKey;
            savedData = heldData;

            // Mark this item as sorted
            sorted[pos] = true;

            // Go to the held item proper location
            pos = heldPos;
        }
        ++i;
    }
}
Question

Как я могу сортировать два вектора одинаково, с критериями, которые используют только один из векторов?

Например, предположим, что у меня два вектора одинакового размера:

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

Затем я сортирую vectorA используя некоторую функцию сравнения. Этот сортировка переупорядочивает vectorA . Как я могу применить одно и то же переупорядочение к vectorB ?

Один из вариантов - создать структуру:

struct ExampleStruct {
    MyObject mo;
    int i;
};

а затем отсортировать вектор, содержащий содержимое vectorA и vectorB в один вектор:

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

Это не похоже на идеальное решение. Существуют ли другие варианты, особенно в C ++ 11?




Я хотел бы внести свой вклад с расширением, которое я придумал. Цель состоит в том, чтобы иметь возможность сортировать несколько векторов одновременно с помощью простого синтаксиса.

sortVectorsAscending(criteriaVec, vec1, vec2, ...)

Алгоритм такой же, как предложенный Тимоти, но с использованием вариационных шаблонов , поэтому мы можем сортировать сразу несколько векторов произвольных типов.

Вот фрагмент кода:

template <typename T, typename Compare>
void getSortPermutation(
    std::vector<unsigned>& out,
    const std::vector<T>& v,
    Compare compare = std::less<T>())
{
    out.resize(v.size());
    std::iota(out.begin(), out.end(), 0);

    std::sort(out.begin(), out.end(),
        [&](unsigned i, unsigned j){ return compare(v[i], v[j]); });
}

template <typename T>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t)
{
    assert(order.size() == t.size());
    std::vector<T> st(t.size());
    for(unsigned i=0; i<t.size(); i++)
    {
        st[i] = t[order[i]];
    }
    t = st;
}

template <typename T, typename... S>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t,
    std::vector<S>&... s)
{
    applyPermutation(order, t);
    applyPermutation(order, s...);
}

template<typename T, typename Compare, typename... SS>
void sortVectors(
    const std::vector<T>& t,
    Compare comp,
    std::vector<SS>&... ss)
{
    std::vector<unsigned> order;
    getSortPermutation(order, t, comp);
    applyPermutation(order, ss...);
}

// make less verbose for the usual ascending order
template<typename T, typename... SS>
void sortVectorsAscending(
    const std::vector<T>& t,
    std::vector<SS>&... ss)
{
    sortVectors(t, std::less<T>(), ss...);
}

Протестируйте его в Ideone .

Я объясняю это немного лучше в этом сообщении в блоге .




Я предполагаю, что vectorA и vectorB имеют равную длину. Вы можете создать другой вектор, назовем его pos, где:

pos[i] = the position of vectorA[i] after sorting phase

а затем вы можете отсортировать вектор B с помощью pos, т. е. создать vectorBsorted, где:

vectorBsorted[pos[i]] = vectorB[i]

а затем vectorBsorted сортируется по той же перестановке индексов, что и vectorA.