在向量中查找特定字符串的最佳方法是什么? [英] What is the nicest way to find a specific string in vector?

问题描述

例如.我有一些结构:

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

还有一个向量:

std::vector<s_Some> mSome;

然后我用很多 s_Somes 填充这个向量.

And then I fill this vector with a lot of s_Somes.

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

I need to find an iterator for a single s_Some in this vector, which has a specific lable. So far I just iterate through all of this junk and match every lable with the one wanted. This looks a little bit stupid to me. Is there a better way to do so?

推荐答案

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

Option 1) If you are compelled to use the std::vector, but once the vector is filled it stays unchanged, then you could sort the vector and use the binary search. The only cost would be the sorting then and there will be no additional overhead. Searching time is logarithmic O(logN).

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

Option 2) If you have the freedom and can choose different data structure, then consider using the map (also logarithmic) or unordered_map ( expected O(1), worst O(n) ).

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

I have just noticed that you said you wanted to match every label with the one being looked for. So I conclude you can have duplicate labels. Then for point 2 use corresponding multi_map containers, while for point 1 things get a bit messier.

这篇关于在向量中查找特定字符串的最佳方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！