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

Question

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

For example, suppose I have two vectors of the same size:

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

I then sort vectorA using some comparison function. That sorting reordered vectorA. How can I have the same reordering applied to vectorB?

---

One option is to create a struct:

struct ExampleStruct {
    MyObject mo;
    int i;
};

and then sort a vector that contains the contents of vectorA and vectorB zipped up into a single vector:

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

This doesn't seem like an ideal solution. Are there other ways of doing this?

Answer 1

Want to add my solution too

suppose you have two vectors(or more):

vector<int> a;
vector<int> b;
...

create one additional vector helper:

vector<int> helper(v.size(),0);
std::iota(helper.begin(), helper.end(), 0);//fill it from 0 to the helper.size()-1 in ascending order

at this point you just should do a classic sort with custom comparator on helper vector:

sort(helper.begin(),helper.end(),[&](auto&i1, auto&i2){
    return a[i1]<a[i2];//basically you sort the helper based on values of a or whatever you need
});

now each element of helper will show what element should be in that place, like

if helper[0]==5 => element at index 5 should be at index 0

sorting others at this point is easy in +-linear time(not sure if implementation is linear but maybe it can be optimized:

for(int i=0;i<=helper.size();++i){
  int toSwapIndex=i;
  //if helper[i]==i, element is in place already, the code will continue to the next index
  while(helper[toSwapIndex]!=i){

    //here we try to find the pair where:
    //helper[toSwapIndex]==i, basically we are searching
    //for the element that is using what is currently at position [i]
    toSwapIndex=helper[toSwapIndex];
  }
  //we put at position [i] the element that should be here AND
  //we move what's at position [i] to the position helper[i]
  swap(a[i],a[helper[i]]);
  ...//do other vector swaps here

  //now we need to fix a problem we created:
  //remember the *toSwapIndex* that was using position [i]?
  //we moved that to the position helper[i] and as consequence
  //we should update the helper[toSwapIndex] to point towards helper[i]
  swap(helper[i],helper[toSwapIndex]);
  
  //as result, at position i the correct element is placed
}

Answer 2

I would like to contribute with a extension I came up with. The goal is to be able to sort multiple vectors at the same time using a simple syntax.

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

The algorithm is the same as the one Timothy proposed but using variadic templates, so we can sort multiple vectors of arbitrary types at the same time.

Here's the code snippet:

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

Test it in Ideone.

I explain this a little bit better in this blog post.

Answer 3

Based on Timothy Shields answer.
With a small tweak to apply_permutaion you can apply the permutation to multiple vectors of different types at once with use of a fold expression.

template <typename T, typename... Ts>
void apply_permutation(const std::vector<size_t>& perm, std::vector<T>& v, std::vector<Ts>&... vs) {

    std::vector<bool> done(v.size());
    for(size_t i = 0; i < v.size(); ++i) {
        if(done[i]) continue;
        done[i] = true;
        size_t prev = i;
        size_t curr = perm[i];
        while(i != curr) {
            std::swap(v[prev], v[curr]);
            (std::swap(vs[prev], vs[curr]), ...);
            done[curr] = true;
            prev = curr;
            curr = perm[curr];
        }
    }
}

Answer 4

I have recently wrote a proper zip iterator which works with the stl algorithms. It allows you to produce code like this:

std::vector<int> a{3,1,4,2};
std::vector<std::string> b{"Alice","Bob","Charles","David"};

auto zip = Zip(a,b);
std::sort(zip.begin(), zip.end());

for (const auto & z: zip) std::cout << z << std::endl;

It is contained in a single header and the only requirement is C++17. Check it out on GitHub.

There is also a post on codereview which contains all the source code.

Answer 5

With range-v3, it is simple, sort a zip view:

std::vector<MyObject> vectorA = /*..*/;
std::vector<int> vectorB = /*..*/;

ranges::v3::sort(ranges::view::zip(vectorA, vectorB));

or explicitly use projection:

ranges::v3::sort(ranges::view::zip(vectorA, vectorB),
                 std::less<>{},
                 [](const auto& t) -> decltype(auto) { return std::get<0>(t); });

Demo

Answer 6

I am not sure if this works but i would use something like this. For example to sort two vectors i would use descending bubble sort method and vector pairs.

For descending bubble sort, i would create a function that requires a vector pair.

void bubbleSort(vector< pair<MyObject,int> >& a)
{
    bool swapp = true;
    while (swapp) {
        int key;
        MyObject temp_obj;
        swapp = false;
        for (size_t i = 0; i < a.size() - 1; i++) {
            if (a[i].first < a[i + 1].first) {
                temp_obj = a[i].first;
                key = a[i].second;

                a[i].first = a[i + 1].first;
                a[i + 1].first = temp_obj;

                a[i].second = a[i + 1].second;
                a[i + 1].second = key;

                swapp = true;
            }
        }
    }
}

After that i would put your 2 vector values into one vector pair. If you are able to add values at the same time use this one and than call the bubble sort function.

vector< pair<MyObject,int> > my_vector;

my_vector.push_back( pair<MyObject,int> (object_value,int_value));

bubbleSort(my_vector);

If you want to use values after adding to your 2 vectors, you can use this one and than call the bubble sort function.

vector< pair<MyObject,int> > temp_vector;

for (size_t i = 0; i < vectorA.size(); i++) {
            temp_vector.push_back(pair<MyObject,int> (vectorA[i],vectorB[i]));
        }

bubbleSort(temp_vector);

I hope this helps. Regards, Caner

Answer 7

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

Answer 8

In-place sorting using permutation

I would use a permutation like Timothy, although if your data is too large and you don't want to allocate more memory for the sorted vector you should do it in-place. Here is a example of a O(n) (linear complexity) in-place sorting using permutation:

The trick is to get the permutation and the reverse permutation to know where to put the data overwritten by the last sorting step.

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

Answer 9

1. Make a vector of pairs out of your individual vectors.
   initialize vector of pairs
   Adding to a vector of pair

2. Make a custom sort comparator:
   Sorting a vector of custom objects
   http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B

3. Sort your vector of pairs.

4. Separate your vector of pairs into individual vectors.

5. Put all of these into a function.

Code:

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

struct less_than_int
{
    inline bool operator() (const std::pair<MyObject,int>& a, const std::pair<MyObject,int>& b)
    {
        return (a.second < b.second);
    }
};

sortVecPair(vectorA, vectorB, less_than_int());

// make sure vectorA and vectorB are of the same size, before calling function
template <typename T, typename R, typename Compare>
sortVecPair(std::vector<T>& vecA, std::vector<R>& vecB, Compare cmp)
{

    std::vector<pair<T,R>> vecC;
    vecC.reserve(vecA.size());
    for(int i=0; i<vecA.size(); i++)
     {
        vecC.push_back(std::make_pair(vecA[i],vecB[i]);   
     }

    std::sort(vecC.begin(), vecC.end(), cmp);

    vecA.clear();
    vecB.clear();
    vecA.reserve(vecC.size());
    vecB.reserve(vecC.size());
    for(int i=0; i<vecC.size(); i++)
     {
        vecA.push_back(vecC[i].first);
        vecB.push_back(vecC[i].second);
     }
}

Answer 10

I'm assuming that vectorA and vectorB have equal lengths. You could create another vector, let's call it pos, where:

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

and then, you can sort vectorB using pos, i.e create vectorBsorted where:

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

and then vectorBsorted is sorted by the same permutation of indexes as vectorA is.