C++ Sort based on other int array

Question

suppose i have two vector

std::vector<int>vec_int = {4,3,2,1,5};

std::vector<Obj*>vec_obj = {obj1,obj2,obj3,obj4,obj5};

How do we sort vec_obj in regard of sorted vec_int position? So the goal may look like this:

std::vector<int>vec_int = {1,2,3,4,5};

std::vector<Obj*>vec_obj = {obj4,obj3,obj2,obj1,obj5};

I've been trying create new vec_array:

for (int i = 0; i < vec_int.size(); i++) {

    new_vec.push_back(vec_obj[vec_int[i]]);
}

But i think it's not the correct solution. How do we do this? thanks

std library may be the best solution,but i can't find the correct solution to implement std::sort

I would create a `std::map< int, Obj* >` - its entries are automatically sorted by key. After that you can throw away the keys again and just put the values back in a vector. [edit] Making this into an answer. — CompuChip, Aug 25 '14 at 13:24
Possible duplicate of [zip iterators](http://stackoverflow.com/questions/13840998/sorting-zipped-locked-containers-in-c-using-boost-or-the-stl). — nwp, Aug 25 '14 at 13:48
does vec_int always contain a permutation of the indices or could it be some general property of obj that serves as key when sorting? Do you want to perform the sort in-place? — MadScientist, Aug 25 '14 at 13:50
There is a pretty nice solution with lambdas in this thread [http://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes][1] [1]: http://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes — Juanjo Martin, Aug 25 '14 at 14:10

Anton Savin · Accepted Answer · 2014-08-25T14:01:15.553

You don't have to call std::sort, what you need can be done in linear time (provided the indices are from 1 to N and not repeating)

std::vector<Obj*> new_vec(vec_obj.size());
for (size_t i = 0; i < vec_int.size(); ++i) {
    new_vec[i] = vec_obj[vec_int[i] - 1];
}

But of course for this solution you need the additional new_vec vector.

If the indices are arbitrary and/or you don't want to allocate another vector, you have to use a different data structure:

typedef pair<int, Obj*> Item;
vector<Item> vec = {{4, obj1}, {3, obj2}, {2, obj3}, {1, obj4}, {5, obj5}};
std::sort(vec.begin(), vec.end(), [](const Item& l, const Item& r) -> bool {return l.first < r.first;});

score 1 · Answer 2 · answered Aug 25 '14 at 13:29

Maybe there is a better solution, but personally I would use the fact that items in a std::map are automatically sorted by key. This gives the following possibility (untested!)

// The vectors have to be the same size for this to work!
if( vec_int.size() != vec_obj.size() ) { return 0; }

std::vector<int>::const_iterator intIt = vec_int.cbegin();
std::vector<Obj*>::const_iterator objIt = vec_obj.cbegin();

// Create a temporary map
std::map< int, Obj* > sorted_objects;
for(; intIt != vec_int.cend(); ++intIt, ++objIt )
{
    sorted_objects[ *intIt ] = *objIt;
}

// Iterating through map will be in order of key
//  so this adds the items to the vector in the desired order.
std::vector<Obj*> vec_obj_sorted;
for( std::map< int, Obj* >::const_iterator sortedIt = sorted_objects.cbegin();
  sortedIt != sorted_objects.cend(); ++sortedIt )
{
  vec_obj_sorted.push_back( sortedIt->second );
}

score 0 · Answer 3 · answered Aug 25 '14 at 14:13

[Not sure this fits your usecase, but putting the elements into a map will store the elements sorted by key by default.]

Coming to your precise solution if creation of the new vector is the issue you can avoid this using a simple swap trick (like selection sort)

//Place ith element in its place, while swapping to its position the current element.
for (int i = 0; i < vec_int.size(); i++) {
    if (vec_obj[i] != vec_obj[vec_int[i])
        swap_elements(i,vec_obj[i],vec_obj[vec_int[i]])
}

rcgldr · Answer 4 · 2014-08-25T19:15:46.153

The generic form of this is known as "reorder according to", which is a variation of cycle sort. Unlike your example, the index vector needs to have the values 0 through size-1, instead of {4,3,2,1,5} it would need to be {3,2,1,0,4} (or else you have to adjust the example code below). The reordering is done by rotating groups of elements according to the "cycles" in the index vector or array. (In my adjusted example there are 3 "cycles", 1st cycle: index[0] = 3, index[3] = 0. 2nd cycle: index[1] = 2, index[2] = 1. 3rd cycle index[4] = 4). The index vector or array is also sorted in the process. A copy of the original index vector or array can be saved if you want to keep the original index vector or array. Example code for reordering vA according to vI in template form:

template <class T>
void reorder(vector<T>& vA, vector<size_t>& vI)  
{
size_t i, j, k;
T t;
    for(i = 0; i < vA.size(); i++){
        if(i != vI[i]){
            t = vA[i];
            k = i;
            while(i != (j = vI[k])){
            // every move places a value in it's final location
                vA[k] = vA[j];
                vI[k] = k;
                k = j;
            }
            vA[k] = t;
            vI[k] = k;
        }
    }
}

Simple still would be to copy vA to another vector vB according to vI:

    for(i = 0; i < vA.size(); i++){
        vB[i] = vA[vI[i]];

C++ Sort based on other int array

4 Answers4

Linked