3

例如。我有一些结构：

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

还有一个向量：

std::vector<s_Some> mSome;

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

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

4

5 回答 5

10

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

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

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

于 2009-02-03T16:44:52.703 回答
5

如果您只搜索几次，或者如果您的矢量每次搜索时都可能包含不同的内容，那么很遗憾，别无选择；您将不得不遍历整个向量。

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

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

这会快得多。

于 2009-02-03T16:42:35.813 回答
3

用一个

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。

于 2009-02-03T17:02:12.967 回答
1

您还可以使用列表地图

于 2009-02-03T16:43:59.740 回答
1

您可以使用 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"));
于 2009-02-03T17:00:15.840 回答