在向量中找到特定字符串的最好方法是什么？

Question

例如.我有一些结构:

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

一个矢量:

std::vector<s_Some> mSome;

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

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

Answer 1

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

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

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

Answer 2

如果您只搜索几次,或者每次搜索时您的矢量可能会有不同的内容,那么很遗憾没有其他选择; 你将不得不遍历整个向量.

但是,如果您的矢量在创建后不会更改,并且您必须运行大量搜索,请执行以下操作:

1. 按字符串的升序排序向量(它们在字典中的方式,即).
2. 一旦这样排序,对所有搜索使用二进制搜索算法.

这会快得多.