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

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)
如果您有自由并且可以选择不同的数据结构，请考虑使用映射（也是对数）或 unordered_map （预期 O(1)，最差 O(n) ）。

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

Answer 2

如果您只搜索几次，或者每次搜索时您的向量可能有不同的内容，那么不幸的是没有其他选择； 你将不得不迭代整个向量。

但是，如果您的向量一旦创建就不会更改，并且您必须运行大量搜索，请执行以下操作：

1. 按字符串的升序（即它们在字典中的方式）对向量进行排序。
2. 排序后，对所有搜索使用二分搜索算法。

这会快得多。

Answer 3

使用 a

std::multimap< string, s_Some > mSome;

并

mSome.insert( std::make_pair( aSome.lable, aSome ) );

通过 查找所需标签值的第一个实例 下

mSome.find( lable_you_want );

一个实例将通过递增迭代器找到。

参见 http://www.cppreference.com/wiki/stl/multimap/start

也就是说，除非您需要使用 std::vector。

Answer 4

您还可以使用 地图 www.cppreference.com/wiki/stl/list/start" rel="nofollow noreferrer">列表

Answer 5

您可以使用 find_if 算法来执行此操作。 定义一个像这样的谓词：

struct isEqual
{
    isEqual(const std::string& s): m_s(s)
    {}
    bool operator()(S_Some& l)
    {
        return l.lable == m_s;
    }

    std::string m_s;
};

在搜索时你可以使用

std::vector<S_Some>::iterator iter = std::find_if(mSome.begin(),
                                                  mSome.end(),
                                                  isEqual(std::string("AAAA"));