0 
std::vector<std::string> vec1, vec2, vec3, vec4;
//populate all vectors, all have the same size
//vec1 has different values

现在给定vec1中的一些“key”，比如“foo”，如何快速从其他向量中获取对应的字符串？

我将不得不多次这样做，在 vec1 中使用不同的键，所以这个操作必须很快。

我应该创建一个将 vec1 中的元素映射到索引值（0、1、2、3、4 ...）的映射吗？

这在 C++ 中如何最好地完成？

4

2 回答 2

2

取决于您所说的“快速”是什么意思。

如果您关心按值检索的复杂性，我建议考虑使用关联容器，例如std::unordered_set（常量查找和插入/删除时间）或std::set和std::multiset（对数查找和插入/删除时间，第二个允许重复）一个vector。

但是，必须说vectors 分配了一个连续的内存区域来存储它们的元素，因此线性访问会导致缓存命中率很高：因此，即使复杂性更差，访问总体上仍然“快”，并且您可以使用常规 STL 算法，例如std::find或std::find_if()来查找匹配给定值或满足给定谓词的元素。

通常，数据的局部性可以弥补更糟糕的复杂性。这里的关键是始终进行重复测量以确定什么是能够为您提供最佳性能的解决方案。

也就是说，最佳解决方案可能取决于您的整体工作量：您是否正在对向量进行逐个元素的迭代？您需要多久按位置检索一次元素？如果这些不是频繁的操作，您可能不需要向量。此外，这些向量多久更新一次？您需要多久按值在这些向量中查找一个元素？您的问题对此并没有多说。

如果内存开销对您来说不是问题，您当然可以考虑构建一个单独的映射作为索引，并维护冗余结构。但是，如果您vector的 s 会频繁地通过插入和删除来更新，那么确保索引和vectors 的一致性可能会变得很麻烦。

于 2013-02-10T15:42:26.340 回答
1

听起来你真正想要的是一个std::unordered_map<std::string, std::tuple<std::string, std::string, std::string>>. 这将使您不必维护std::vectors 必须是相同长度的不变量。它还将为您提供其他字符串的持续时间查找。例如，

typedef std::tuple<std::string, std::string, std::string> value_type;
std::unordered_map<std::string, value_type> map;

// Populate the map
map["foo"] = std::make_tuple("first", "second", "third");
// ...

std::get<0>(map["foo"]); // Get the first string that "foo" maps to

如果你真的不想改变使用四个std::vectors 的设计，那么你应该使用std::findand在第一个std::distance中找到索引，然后在其他索引上使用该索引："foo"std::vector

auto key_it = std::find(std::begin(vec1), std::end(vec1), "foo");
int index = std::distance(std::begin(vec1), key_it);
std::string s2 = vec2[index];
std::string s3 = vec3[index];
std::string s4 = vec4[index];
于 2013-02-10T15:42:17.267 回答