一、简介

本文主要了解如何在直接访问c++容器时高效地进行搜索。在STL容器中搜索，要牢记一个原则：如果可以的话，最好使用容器方法来搜索而不是使用外部算法接口。

有三个原因：

• 它更快：在排序的容器中，所有方法都受益于排序集合中的快速对数搜索。此外，std::string方法实现了最优算法，并受益于字符串的内部表示。
• 它更自然：std::map和std::multimap方法可以直接搜索键，而不像算法那样必须查找std::pair< key, Value>，因为它们的迭代器可以直接指向。
• 它在某些情况下更正确：在排序容器(如map和set)中，所有方法都使用等价而不是相等，而某些算法(如std::count和std::find使用相等)则不是这样。

现在让我们通过研究如何将它应用到 STL 提供的各种容器来深入了解更多细节。

二、std::vector, std::deque, std::list

这些容器没有公开任何与搜索相关的方法，只能通过算法来搜索。

三、std::map, std::multimap, std::set, std::multiset

这些容器有5个类方法，它们与一些算法共享它们的名称：count, find, equal_range, lower_bound和upper_bound。在上一篇文章中有讲解过这些算法。

这些方法和算法的比较：

容器方法	比算法更正确?	比算法还快?	比算法更自然?
count	是	是	是
find	是	是	是
equal_range	相同	是	是
lower_bound	相同	是	是
upper_bound	相同	是	是

• 更好的正确性是因为使用了等效而不是相等。
• 更好的性能来自于为序列容器对元素进行排序这一事实。对于关联容器来说，这是因为它们的迭代器不是随机访问的，所以算法不能通过直接跳过所需的元素来执行分割(它们必须从头开始并向上移动到它们的位置)，而容器的内部没有这种约束。
• 它们对于映射来说更自然，因为传递给各种方法的参数是一个键，而不是std::pair<key, Value>。

注意，没有与std::binary_search等价的容器方法。检查容器中是否存在一个键：

• 对于std::map和std::set：比较find的结果与end迭代器的结果。或者使用count方法。count作为方法不会引起任何性能问题，因为，像find一样，它在第一个与搜索的键相等的键处停止(因为根据std::map和std::set的定义，只能有一个键与搜索的键相等)。
• 对于std::multimap和std::multiset：因为count不会在第一个与搜索的键相等的键处停止，所以find在这里比count有优势。

在std::multimap或std::multiset中，find方法返回与搜索值相等的任何元素，而不一定是第一个元素。如果确实需要第一个元素，可以使用equal_range，因为它具有简单的接口；或者，如果觉得equal_range太慢（因为它显示了整个范围），而只是需要第一个元素，那么可以使用lower_bound。但是，lower_bound同样也有它的缺点，也必须付出代价。

四、std::string

string实际上有24个搜索方法。它们被分成6组，每组有4个重载。对于所有组，4个重载的形式为：

• 搜索由std::string给出的字符串。
• 搜索由char*和size给出的字符串。
• 搜索由char*给出的字符串(止于null字符)。
• 搜索一个字符。

并且所有4个重载都以搜索字符串中的起始位置作为参数，默认值为0(从字符串的开头开始搜索)。

以下是6组方法：

1. find 函数：用于从字符串中查找给定子字符串 str 的第一个匹配项。它返回子字符串在当前字符串中的位置索引，如果找不到则返回 std::string::npos。pos 参数是可选的，用于指定搜索的起始位置，默认为 0。

   size_t find(const std::string& str, size_t pos = 0) const;
   

2. rfind 函数：与 find 函数类似，但它从字符串的末尾开始向前搜索子字符串 str 的最后一个匹配项。它返回子字符串在当前字符串中的位置索引，如果找不到则返回 std::string::npos。pos 参数是可选的，用于指定搜索的起始位置，默认为 std::string::npos，表示从末尾开始搜索。

   size_t rfind(const std::string& str, size_t pos = npos) const;
   

3. find_first_of 函数：用于从字符串中查找与给定字符串 str 中的任何字符匹配的第一个字符。它返回找到的字符在当前字符串中的位置索引，如果找不到则返回 std::string::npos。pos 参数是可选的，用于指定搜索的起始位置，默认为 0。

   size_t find_first_of(const std::string& str, size_t pos = 0) const;
   

4. find_last_of 函数：与 find_first_of 函数类似，但它从字符串的末尾开始向前搜索与给定字符串 str 中的任何字符匹配的最后一个字符。它返回找到的字符在当前字符串中的位置索引，如果找不到则返回 std::string::npos。pos 参数是可选的，用于指定搜索的起始位置，默认为 std::string::npos，表示从末尾开始搜索。

   size_t find_last_of(const std::string& str, size_t pos = npos) const;
   

5. find_first_not_of 函数：用于从字符串中查找第一个不在给定字符串 str 中的字符。它返回找到的字符在当前字符串中的位置索引，如果找不到则返回 std::string::npos。pos 参数是可选的，用于指定搜索的起始位置，默认为 0。

   size_t find_first_not_of(const std::string& str, size_t pos = 0) const;
   

6. find_last_not_of 函数：与 find_first_not_of 函数类似，但它从字符串的末尾开始向前搜索第一个不在给定字符串 str 中的字符。它返回找到的字符在当前字符串中的位置索引，如果找不到则返回 std::string::npos。pos 参数是可选的，用于指定搜索的起始位置，默认为 std::string::npos，表示从末尾开始搜索。

   size_t find_last_not_of(const std::string& str, size_t pos = npos) const;
   

在线性时间内实现字符串算法并不容易。string方法以最佳方式实现它们，当在字符串中搜索某些内容时，可以直接使用容器的方法。

六、总结

本文系统地介绍了在直接访问STL容器时执行有效和正确搜索的方法。通过理解STL容器的内部机制和使用适当的搜索技巧，可以提高代码的性能和可读性。关键要点包括使用迭代器和成员函数进行搜索，利用算法库提供的函数进行查找，以及根据不同的容器类型选择最佳搜索方法。通过掌握本文提供的技术和原则，读者将能够在使用STL容器时更加自信地进行搜索操作，提高代码的质量和效率。