Sorting one vector with respect to another - most efficient way?

Question

I'm aware that this question has already been asked a few times, but different answers have been provided for simple cases (where compactness, readability or user proficiency are the deciding factors) and I'm not sure which one is the most efficient, as I'm concerned with repeating that operation O(1M) times.

The setup is the following:

• Two vectors A and B of float's; this cannot be changed, but additional structures can be created from A and B.
• A and B have equal length, which is at least 4 and at most 20 (if that's helpful in any way).
• A needs to be sorted in descending order based on the values of its entries, while B simply needs to match A's ordering.

Example:

A = {2,4,3,1} -> {4,3,2,1}
     | | | |
B = {1,2,3,4} -> {2,3,1,4}

Question:

What's the most efficient (= fast + memory saving) way of doing this?

Answer 1

One common way is to create an index and sort it, rather than sorting the original values. This is known as indirect sort or argsort.

Example:

using values_t = std::vector<float>;
using index_t = std::vector<uint8_t>;

index_t make_sorted_index(values_t const& values) {
    index_t index(values.size());
    std::iota(index.begin(), index.end(), 0);
    std::sort(index.begin(), index.end(), [&values](uint8_t a, uint8_t b) { return values[a] > values[b]; } );
    return index;
}

int main() {
    values_t a = {2,4,3,1};
    values_t b = {1,2,3,4};

    auto index = make_sorted_index(a);

    std::cout << "A = {";
    for(auto i : index)
        std::cout << a[i] << ',';
    std::cout << "\b}\n";

    std::cout << "B = {";
    for(auto i : index)
        std::cout << b[i] << ',';
    std::cout << "\b}\n";
}

Outputs:

A = {4,3,2,1}
B = {2,3,1,4}