将许多向量排序在一起

Question

我有三个相同大小的向量（约 100 万个项目）：

std::vector<wstring> name;
std::vector<int> x;
std::vector<int> y;

可以看成三个"columns".

如何对向量进行 A->Z 排序 name:

std::sort(name.begin(), name.end())

但向量 x 和 y 已相应排序？

示例：

name  x  y                 name  x  y
BCD   7  9                 ABC   4  3
ZYX   1  4        =>       BCD   7  9
ABC   4  3                 ZYX   1  4

使用 std::vector 的好处是，我可以轻松地 select/filter 大 vector 中的一些项目，只需保留一个索引列表（例如：让我们保留项目 12、1872、2834、1831）。我考虑过使用 std::map 但我担心它不会那么有效：如何保留要保留在地图中的元素列表？

Answer 1

有几种可能的方法可以做到这一点。最简单的方法是将 name、x 和 y 包装在结构中：

struct Person {
    std::wstring name;
    int x;
    int y;
};

然后你可以得到一个 std::vector<Person> people 并对其进行排序（假设 C++14）

std::sort(people.begin(), people.end(),
    [](auto const& lhs, auto const& rhs) { return lhs.name < rhs.name; });

但是，如果您知道这会由于缓存中适合的元素较少而导致性能问题（也就是说，您经常只迭代 x 或 y 并且你是在非常受限的环境中，例如高性能游戏），我建议只对一个向量进行排序。除非您知道自己在做什么，否则您需要对这两个选项进行基准测试。

基本上，有一个跟踪排序的向量：

std::vector<std::wstring> name;
std::vector<int> x;
std::vector<int> y

std::vector<std::size_t> ordering(name.size());
std::iota(ordering.begin(), ordering.end(), 0);

std::sort(ordering.begin(), ordering.end(),
    [&](auto const& lhs, auto const& rhs) {
        return name[lhs] < name[rhs];
    });

然后您可以简单地迭代 ordering 以新顺序遍历每个并行向量。

额外的间接级别可能会降低效率。例如，CPU 可能认为存在 none 的数据依赖性。此外，我们在 ordering 中跟踪的额外数据很容易在缓存中占用足够的空间来抵消分离 name、x 和 y 的好处；您需要知道目标架构和配置文件的规格才能确定。

如果您希望以新的顺序对它们进行迭代，您会希望使用此 ordering 向量对其他向量进行排序，因为对元素的访问将变得随机。这会抵消保持向量分离的好处（除非向量足够小以适合缓存）。

最简单的方法是创建一个新向量：

std::vector<std::wstring> newNames;
newNames.reserve(name.size());

for (auto i : ordering) {
    newNames.push_back(name[i]);
}

如果排序发生在初始化期间，那么像这样重建向量可能是您想要做的。

Answer 2

听起来您想要一个结构来将数据保存在一起。例如：

struct MyData
{
  wstring name;
  int x;
  int y;
};

...
std::vector<MyData> data;

从那里开始，您需要一个比较函数来执行自定义排序，以确保您从要排序的字段中进行排序：

std::sort(data.begin(), data.end(), compareByName);

bool compareByName(const MyData& lhs, const MyData& rhs)
{
    return lhs.name < rhs.name; // This can be whatever
}

将许多向量排序在一起

Have many vectors sorted together

c++

sorting

vector

stdvector