c++ - 在 vector 中查找特定字符串的最佳方法是什么？

Question

例如。我有一些结构:

s_Some{
  std::string lable;
  s_some_junk some_junk;
};

还有一个 vector :

std::vector<s_Some> mSome;

然后我用很多 s_Some 填充这个 vector 。

我需要为这个 vector 中的单个 s_Some 找到一个迭代器，它有一个特定的标签。到目前为止，我只是遍历所有这些垃圾并将每个标签与想要的标签进行匹配。这对我来说看起来有点愚蠢。有更好的方法吗？

Answer 1

选项 1)如果您被迫使用 std::vector，但一旦 vector 被填充它就保持不变，那么您可以对 vector 进行排序并使用二进制搜索。唯一的成本就是排序，不会有额外的开销。搜索时间为对数O(logN)。

选项 2)如果你有自由并且可以选择不同的数据结构，那么考虑使用 map(也是对数的)或 unordered_map(预期 O(1)，最差 O(n))。

我刚刚注意到您说您想将每个标签与正在寻找的标签相匹配。所以我得出结论，你可以有重复的标签。然后对于第 2 点使用相应的 multi_map 容器，而对于第 1 点事情变得有点困惑。