How to Sort Two Vectors in the Same Way, With Criteria That Uses Only One of the Vectors

How can I sort two vectors in the same way, with criteria that uses only one of the vectors?

Finding a sort permutation

Given a std::vector<T> and a comparison for T's, we want to be able to find the permutation you would use if you were to sort the vector using this comparison.

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;
}

Applying a sort permutation

Given a std::vector<T> and a permutation, we want to be able to build a new std::vector<T> that is reordered according to the permutation.

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;
}

You could of course modify apply_permutation to mutate the vector you give it rather than returning a new sorted copy. This approach is still linear time complexity and uses one bit per item in your vector. Theoretically, it's still linear space complexity; but, in practice, when sizeof(T) is large the reduction in memory usage can be dramatic. (See details)

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];
        }
    }
}

Example

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);

Resources

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

C++, Sort One Vector Based On Another One

As already suggested in other answers: Combining the name and the score of each individual is likely the simplest solution.

Generically, this can be achieved with what is sometimes referred to as a "zip" operation: Combining two vectors into a vector of pairs - along with a corresponding "unzip".

Implemented generically, this may look as follows:

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

// Fill the zipped vector with pairs consisting of the
// corresponding elements of a and b. (This assumes 
// that the vectors have equal length)
template <typename A, typename B>
void zip(
    const std::vector<A> &a, 
    const std::vector<B> &b, 
    std::vector<std::pair<A,B>> &zipped)
{
    for(size_t i=0; i<a.size(); ++i)
    {
        zipped.push_back(std::make_pair(a[i], b[i]));
    }
}

// Write the first and second element of the pairs in 
// the given zipped vector into a and b. (This assumes 
// that the vectors have equal length)
template <typename A, typename B>
void unzip(
    const std::vector<std::pair<A, B>> &zipped, 
    std::vector<A> &a, 
    std::vector<B> &b)
{
    for(size_t i=0; i<a.size(); i++)
    {
        a[i] = zipped[i].first;
        b[i] = zipped[i].second;
    }
}


int main(int argc, char* argv[])
{
    std::vector<std::string> names {"Karl", "Martin", "Paul", "Jennie"};
    std::vector<int> score {45, 5, 14, 24};

    // Zip the vectors together
    std::vector<std::pair<std::string,int>> zipped;
    zip(names, score, zipped);

    // Sort the vector of pairs
    std::sort(std::begin(zipped), std::end(zipped), 
        [&](const auto& a, const auto& b)
        {
            return a.second > b.second;
        });

    // Write the sorted pairs back to the original vectors
    unzip(zipped, names, score);

    for(size_t i=0; i<names.size(); i++)
    {
        std::cout << names[i] << " : " << score[i] << std::endl;
    }
    return 0;
}

Efficient sorting of multiple vectors with respect to one vector?

You can populate a map of weights used for the sorting and then provide a custom comparator for sort:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

int main() {
    std::vector<int> I={6,2,3,1,4,5,0};
    std::unordered_map<int,unsigned> weights;
    for (unsigned i = 0; i < I.size(); ++i) weights[I[i]] = i;

    std::vector<int> s{3,6,5};
    std::sort(s.begin(),s.end(), [&weights](int a,int b){
        return weights[a] < weights[b];
    });

    for (const auto& e : s) std::cout << e << " ";
}

To sort many vectors you just need to call sort in a loop. If the numbers in I are always consecutive with no holes in between then using an array as look up table would be more efficient.

Locking two vectors and sorting them

At least as far as I know, none of the sorting algorithms built into the standard library will do this for you directly. The most obvious possibility would probably be to use a Boost Zip Iterator to make the two arrays act like a single collection.

Sorting of two vectors separately?

If you can group them within struct or equivalent, you may create an additional vector for indexes that you sort and use for indirection:

std::vector<double> ages = /**/;
std::vector<string> names = /**/;
// ages.size() == names.size()
std::vector<std::size_t> indexes(names.size());
std::iota(indexes.begin(), indexes.end(), 0u);
std::sort(indexes.begin(), indexes.end(), [&](std::size_t lhs, std::size_t rhs) {
    return names[lhs] < names[rhs];
});

for (auto index : indexes) {
    std::cout << names[index] << " has " << ages[index] << std::endl;
}

And with range-v3 you can do:

std::vector<double> ages = /**/;
std::vector<string> names = /**/;
auto zip = ranges::view::zip(names, ages);

ranges::sort(zip);

for (const auto& z : zip) {
    std::cout << std::get<0>(z) << " " << std::get<1>(z) << std::endl;
}

Demo

---

Related Topics