Sorting a vector using values in another vector

Question

I have a std::vector called foo_vec containing objects of class Foo. Suppose that Foo has a member variable int x, and I also implemented a function CompareInts(int a, int b) which returns the minimum of a and b. Then, I could do an std::sort the vector in terms of the object's x values.

However, what if these x values are not member variables of Foo, but are in another std::vector called x_vec. Here, the first element of x_vec corresponds to the first element of foo_vec, and so on. How can I perform an std::sort on foo_vec based on the corresponding values in x_vec?

I'm voting to close this question as off-topic because it lacks a minimal example. — gsamaras, Dec 13 '15 at 01:27
This technique is known as "parallel arrays" and it's as old as FORTRAN, before the days is structs. As you've noticed, it can be awkward. — Pete Becker, Dec 13 '15 at 02:36

Kerrek SB · Accepted Answer · 2015-12-14T01:47:01.360

6

You can make a third vector of indexes and sort that indirectly. After it's sorted, you can access the original vector through the sorted indexes:

std::vector<Foo> foo_vec = /* ... */;
std::vector<int> x_vec = /* ... */;
std::vector<std::size_t> index_vec;

assert(foo_vec.size() == x_vec.size());
for (std::size_t i = 0; i != foo_vec.size(); ++i) { index_vec.push_back(i); }

std::sort(
    index_vec.begin(), index_vec.end(),
    [&](std::size_t a, std::size_t b) { return x_vec[a] < x_vec[b]; });

for (std::size_t i = 0; i != index_vec.size(); ++i)
{
    std::cout << "Sorted element " << i << " is "
              << foo_vec[index_vec[i]] << "\n";
}

Note that this operation is entirely non-invasive, since everything happens indirectly.

edited Dec 14 '15 at 01:47

answered Dec 13 '15 at 01:28

Kerrek SB

464,522
92
875
1,084

1

Here's a [link](http://stackoverflow.com/a/1267878/4859885) to a nice algorithm for reordering vectors based on indices – Brian Rodriguez Dec 13 '15 at 01:32
Foo class needs to overload the ´<<` operator I think – Ely Dec 13 '15 at 02:35
@Elyasin: Sure, that was just for demonstrating how to access the element. – Kerrek SB Dec 13 '15 at 03:10
It's allright. I reckoned it's basic for you. Just mentioned so others know. Excellent example I have to say. To me it shows a very good use case for lambda expression. Thumbs up. – Ely Dec 13 '15 at 03:24
@KerrekSB It seems the `index_vec` is not sorted using `x_vec` but using its own members. Wouldn't this just leave the `index_vec` unchanged? – legends2k Dec 13 '15 at 11:15
@legends2k: Why does it seem that way? We are clearly passing iterators of `index_vec` to `sort`...? – Kerrek SB Dec 13 '15 at 11:43
@KerrekSB That's true, but the key to sort the elements, as per the question, should come from `x_vec.x`, where is that part in the above code? The comparator lambda uses `index_vec[a]`, not `x_vec[a]`, as the key; perhaps it's a typo. – legends2k Dec 14 '15 at 01:01
@legends2k: Oh, sorry, that was a typo. The comparator should reference `x_vec`. Fixed (?). – Kerrek SB Dec 14 '15 at 01:47

score 2 · Answer 2 · answered Dec 13 '15 at 01:25

You create a third vector of int, which are the indexes into the original two vectors. Initially populate the third vector with number 0 .. length of vector. Then construct your compare function to take the index from the third vector and then do the compare against the second vector holding the keys.

The data in the first and second vector will not be modified (which is good) and the values in the the third vector will represent the sort order once done.

Sorting a vector using values in another vector

2 Answers2

Linked