c++ - 相对于另一个 vector 对一个 vector 进行排序 - 最有效的方法？

Question

我知道这个问题 has already been asked a few times ，但针对简单情况(紧凑性、可读性或用户熟练程度是决定因素)提供了不同的答案，我不确定哪个是最有效，因为我担心重复该操作 O(1M) 次。

设置如下:

• float 的两个 vector A 和B；这无法更改，但可以从 A 和 B 创建其他结构。
• A 和 B 的长度相等，至少为 4，最多为 20(如果这有任何帮助的话)。
• A 需要根据其条目的值按降序排序，而 B 只需要匹配 A 的排序。

示例:

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

问题:

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

Answer 1

一种常见的方法是创建索引并对其进行排序，而不是对原始值进行排序。这称为间接排序 或argsort。

例子:

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

输出:

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