c++ - 同时就地 std::sort 键 vector 和值 vector

Question

我有一个 vector<uint64_t> keys和一个 vector<char> vals , 尺寸均为 N .我想对 keys 进行排序和 vals基于 keys 中的条目.

一个明显的解决方案是复制到 vector<pair<uint64_t, char>> ，对其进行排序，然后将排序后的数据复制回来，但我想避免复制，并且我想避免对齐填充:sizeof(pair<uint64_t, char>)是2*sizeof(uint64_t) , 或 16 个字节，由于对齐；远远超过所需的 9 个字节。

换句话说，虽然下面的C++11实现是正确的，但是效率不够高:

#include <algorithm>
#include <tuple>
using namespace std;
void aux_sort(vector<uint64_t> & k, vector<char> & v) {
    vector<pair<uint64_t, char> > kv(k.size());
    for (size_t i = 0; i < k.size(); ++i) kv[i] = make_pair(k[i], v[i]);
    sort(kv.begin(), kv.end());
    for (size_t i = 0; i < k.size(); ++i) tie(k[i], v[i]) = kv[i];
}

虽然下面的C++11实现是正确的，但我想用std::sort而不是手动编写我自己的排序算法:

#include <algorithm>
using namespace std;
void aux_sort(vector<uint64_t> & k, vector<char> & v) {
    for (size_t i = 0; i < k.size(); ++i)
        for (size_t j = i; j--;)
            if (k[j] > k[j + 1]) {
                iter_swap(&k[j], &k[j + 1]);
                iter_swap(&v[j], &v[j + 1]);
            }
}

(编辑添加，回应@kfsone)虽然下面的实现是正确的，但它不是就地的，因为排列根据indices需要一个拷贝(或者，一个非常复杂的线性时间就地置换算法，我不打算实现):

#include <algorithm>
#include <tuple>
using namespace std;
void aux_sort(vector<uint64_t> & k, vector<char> & v) {
    vector<size_t> indices(k.size());
    iota(indices.begin(), indices.end(), 0);
    sort(indices.begin(), indices.end(),
        [&](size_t a, size_t b) { return k[a] < k[b]; });
    vector<uint64_t> k2 = k;
    vector<char> v2 = v;
    for (size_t i = 0; i < k.size(); ++i)
        tie(k[i], v[i]) = make_pair(k2[indices[i]], v2[indices[i]]);
}

什么是应用 STL 算法最简单的方法，例如 std::sort到就地键/值对序列，键和值存储在单独的 vector 中？

背景:我的应用程序正在读取代表地形的大型(40000 x 40000)栅格，一次读取一行。一个栅格为每个像元分配一个 0 到 10000000 之间的标签，这样标签是连续的，另一个栅格为每个像元分配一个 0 到 255 之间的值。我想以一种有效的方式对每个标签的值求和，我认为最快的方法是对标签行进行排序，并且对于排序期间的每个交换，在值行中应用相同的交换。我想避免手动编写 std::sort、std::set_intersection 和其他代码。

Answer 1

范围适配器。最直接的路线是一个 zip 范围，它分别在 T 和 U 上采用两个相等长度的范围，并产生一个超过 pair<T&,U&> 的范围。 . (容器是一种范围——拥有其内容的范围)

然后按 .first 排序(或使用默认排序，其中 .second 决定关系)。

范围从来都不是容器，包装成对是在每次取消引用 zip 迭代器时即时发生的。

boost有一个 zip 迭代器和 zip 范围，但你可以自己编写它们。 boost 迭代器/范围 may be read only ，但该链接还包含一个压缩的实现，它不是，也许 boost 已经升级。