我有三个相同大小的 vector (约 100 万个项目):
std::vector<wstring> name;
std::vector<int> x;
std::vector<int> y;
可以看作是三个“列”。
如何对 vector name 进行 A->Z 排序:
std::sort(name.begin(), name.end())
但是 vector 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 的好处是，我可以轻松地选择/过滤大型 vector 中的一些项目，只需获取一个索引列表保留(例如:让我们保留项目 12、1872、2834、1831)。
我考虑过使用 std::map 但我担心它不会如此有效:如何保留要保留在 map 中的元素列表？
有几种可能的方法可以做到这一点。最简单的方法是包装 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，并且您处于非常受限的环境中，例如作为高性能游戏)，我建议只对一个 vector 进行排序。除非您知道自己在做什么，否则您需要对这两个选项进行基准测试。
基本上，有一个跟踪排序的 vector :
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以新顺序遍历每个平行 vector 。
额外的间接级别可能会降低效率。例如，CPU 可能认为在没有数据依赖的地方存在数据依赖。此外，我们在 ordering 中跟踪的额外数据可以很容易地在缓存中占用足够的空间来抵消分离 name 的好处, x , 和 y ;您需要了解目标架构和配置文件的规范才能确定。
如果您想以新顺序继续迭代它们，您会想使用这个 ordering vector 对其他 vector 进行排序，因为对元素的访问将变得随机。这会抵消保持 vector 分离的好处(除非 vector 足够小以适合缓存)。
最简单的方法是创建一个新 vector :
std::vector<std::wstring> newNames;
newNames.reserve(name.size());
for (auto i : ordering) {
newNames.push_back(name[i]);
}
如果排序发生在初始化期间，那么像这样重建 vector 可能是您想要做的。