Mapping a vector to specific range

Question

I have a standard vector contains, for example, the following elements

[-6, -7, 1, 2]

I need to map these elements to the range from 1 to 4. i.e I need the vector to be like this

[2, 1, 3, 4]

Note that: the smallest value in the first vector (-7) was mapped to the smallest value in the second vector (1). How can I achieve that with STL?

Getting the range is easy (`1` to `my_vector.size()`). As for the positioning, it might be solved by just placing the values in the second vector from smallest to largest, and then sort it using the values from the first vector. — Some programmer dude, Dec 23 '18 at 20:07
@Someprogrammerdude Yes, creating a range and sorting it would be one option (see e.g. https://stackoverflow.com/a/37369858/3182664 ). In fact, the specific case here can basically be considered as looking for a *sorting permutation* (or its inverse). — Marco13, Dec 24 '18 at 15:03

score 5 · Answer 1 · answered Dec 23 '18 at 20:16

5

With range-v3:

std::vector<int> v{-6, -7, 1, 2};
auto res = ranges::view::ints(1, 1 + (int)v.size()) | ranges::to_vector;

ranges::sort(ranges::view::zip(v, res));

Demo

answered Dec 23 '18 at 20:16

Jarod42

203,559
14
181
302

thanks but I needed a standard solution, but I will remember to use this great library. – sc0rp10n.my7h Dec 23 '18 at 20:47

score 5 · Answer 2 · answered Dec 23 '18 at 22:23

With just the standard library as it exists in C++17 (or really, C++11), you make a vector of indices and sort it - using itself as a projection:

vector<int> idxs(values.size());
iota(idxs.begin(), idxs.end(), 1);
sort(idxs.begin(), idxs.end(), [&](int i, int j){
    return values[i-1] < values[j-1];
});

A different way of generating the indices would be to use generate_n:

vector<int> idxs;
generate_n(back_inserter(idxs),
    values.size(),
    [cnt=1]() mutable { return cnt++; });
// same sort()

Georgi Gerganov · Accepted Answer · 2018-12-23T21:01:26.507

Using a helper vector of pairs:

std::vector<int> a { -6, -7, 1, 2 };

std::vector<std::pair<int, int>> tmp;
for (int i = 0; i < (int) a.size(); ++i) {
    tmp.push_back({ a[i], i });
}

std::sort(tmp.begin(), tmp.end());

std::vector<int> b;
for (auto & x : tmp) {
    b.push_back(x.second + 1);
}

Demo

Using a helper priority_queue of pairs (to avoid explicit sorting):

std::vector<int> a { -6, -7, 1, 2 };

std::priority_queue<std::pair<int, int>> tmp;
for (std::size_t i = 0; i < a.size(); ++i) {
    tmp.push({ -a[i], i});
}

std::vector<int> b;
do {
    b.push_back(tmp.top().second + 1);
} while (tmp.pop(), !tmp.empty());

Demo

Mapping a vector to specific range

3 Answers3