c++ - 按代理排序(或 : sort one container by the contents of another) in C++

Question

我有一组数据，分为两个数组(我们称它们为 data 和 keys)。也就是说，对于任何具有索引 i 的给定项目，我可以使用 data[i] 访问该项目的数据，并使用 keys 访问该项目的键[我]。我无法更改此结构(例如，将键和数据交织到一个数组中)，因为我需要将 data 数组传递给需要特定数据布局的库函数。

如何根据 keys 数组的内容对两个数组进行排序(最好使用标准库函数)？

Answer 1

创建包含两个数组索引的对象 vector 。定义 operator<该对象根据 keys[index] 进行比较.对该 vector 进行排序。完成后，遍历该 vector 并将原始对象放入这些代理对象定义的顺序中:

// warning: untested code.
struct sort_proxy { 
    size_t i;

    bool operator<(sort_proxy const &other) const { 
        return keys[i] < keys[other.i];
    }
};

// ... key_size = number of keys/data items.
std::vector<sort_proxy> proxies(key_size); 

for (i=0; i<keys_size; i++)
    proxies[i].i = i;

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

// in-place reordering left as an exercise for the reader. :-)
for (int i=0; i<proxies.size(); i++) {
    result_keys[i] = keys[proxies[i].i];
    result_data[i] = data[proxies[i].i];
}