027网址导航

C++STL查找算法find和binary_search使用

作者：

027导航

在

std::find适用于无序数据的线性查找，返回元素位置，时间复杂度O(N)；std::binary_search要求数据有序，仅判断存在性，时间复杂度O(log N)，效率更高。

c++stl查找算法find和binary_search使用

在C++ STL中，和是两种核心的查找算法，它们各自适用于不同的场景和数据特性。简单来说，是一种线性查找，不要求数据有序，它会遍历序列直到找到目标或遍历结束；而则是一种二分查找，它严格要求数据必须已经有序，效率远高于，但它只告诉你元素是否存在，不会返回具体位置。选择哪一个，核心在于你的数据是否已排序，以及你需要的是元素的存在性判断还是其精确位置。

和是C++标准库（STL）中两种非常实用的查找算法，它们都定义在头文件中。理解它们的适用场景和工作原理，对于编写高效且正确的C++代码至关重要。

：线性查找的通用解法

是最基础的查找算法之一。它接受一个迭代器范围和一个待查找的值。它的工作方式很简单：从指向的元素开始，逐个比较，直到找到第一个与相等的元素，或者遍历到。

立即学习“C++免费学习笔记（深入）”；

  • 特点：

    • 不要求数据有序： 这是它最大的优点，你可以对任何序列类型（如、、等）使用它，无论它们是否排序。
    • 返回迭代器： 如果找到目标元素，它会返回一个指向该元素的迭代器；如果没有找到，则返回迭代器。这使得你可以进一步操作找到的元素。
    • 时间复杂度： 平均和最坏情况下都是O(N)，N是序列中的元素数量。这意味着，数据量越大，查找时间越长。
  • 何时使用：

    • 当你的数据是无序的。
    • 当你需要找到元素的具体位置（迭代器），而不仅仅是判断它是否存在。
    • 当数据量相对较小，O(N)的性能开销可以接受时。

：高效查找的有序利器

是一个基于二分查找的算法，它的效率非常高，但前提是它操作的范围必须是已排序的（默认是升序，也可以提供自定义比较器）。它不会返回元素的具体位置，只返回一个布尔值，指示元素是否存在。

  • 特点：

    • 要求数据有序： 这是它使用的前提条件。如果数据无序，结果将是未定义的或错误的。
    • 只返回布尔值： 表示找到，表示未找到。
    • 时间复杂度： O(log N)。对于大型数据集，这比O(N)的线性查找快得多。例如，在一百万个元素中查找，线性查找可能需要一百万次比较，而二分查找只需要大约20次。
  • 何时使用：

    • 当你的数据已经有序，或者你愿意为了一系列查找而先对数据进行排序。
    • 当你只需要判断某个元素是否存在，而不需要知道它的具体位置。

这是一个非常实际的问题，在我个人的开发经验中，如果数据量稍大且确定有序，我几乎总是倾向于或者其他基于二分查找的变体。原因很简单，但其背后的性能差异是巨大的。

的工作方式是线性的，它从头到尾一个一个地检查元素。想象一下你在图书馆找一本书，如果书架上的书是随机摆放的，你只能一本一本翻过去看书名，直到找到为止。这就是O(N)的复杂度，最坏情况下你需要检查所有书。

而则利用了数据有序的特性。它就像你在查字典：你知道字母顺序，所以你可以直接翻到中间，如果目标字母在你翻到的这一页之前，你就只在前半部分找；如果之后，就只在后半部分找。每次查找都将搜索范围缩小一半。这种“分而治之”的策略，使得查找次数呈对数增长，也就是O(log N)。

举个例子，假设有一个包含100万个元素的：

  • 平均需要进行50万次比较（最坏情况100万次）。
  • 最多只需要大约20次比较（log₂1,000,000 ≈ 19.9）。

这种效率上的天壤之别，在处理大数据集时尤为明显。如果你的应用程序对性能有要求，并且数据可以保持有序，那么选择或其同类算法是毫无疑问的优化方向。当然，如果数据量特别小，比如只有几十个元素，的O(N)和的O(log N)在实际执行时间上可能差别不大，甚至由于其更简单的内部逻辑，在某些极端情况下可能略快一点（因为的逻辑分支更多）。但从扩展性考虑，无疑是更优的选择。

STL的查找算法远不止这两个，它提供了一系列工具来应对各种复杂的查找需求。在我看来，掌握这些工具能让你更灵活地处理数据。

  1. 和 ：

    • 这两个算法是的“升级版”，它们也要求数据有序。
    • 返回一个迭代器，指向序列中第一个不小于的元素。
    • 返回一个迭代器，指向序列中第一个大于的元素。
    • 它们常用于查找一个元素可能插入的位置，或者查找一个区间内所有与相等的元素。
    • 示例：

  2. ：

    • 结合了和的功能，同样要求数据有序。
    • 它返回一个，其中是的结果，是的结果。
    • 对于查找某个值在有序序列中的所有出现位置，这个函数非常方便。

  3. 和 ：

    • 这两个是的“条件查找”版本。它们不查找具体的值，而是查找满足特定条件的第一个元素。
    • 查找第一个使返回的元素。
    • 查找第一个使返回的元素。
    • 示例：

  4. 和 ：

    • 用于计算某个值或满足某个条件的元素在序列中出现的次数。
    • 计算出现的次数。
    • 计算满足条件的元素次数。

  5. 和 ：

    • 用于在一个序列中查找另一个子序列的出现。
    • 查找第一个出现的子序列。
    • 查找最后一个出现的子序列。

除了这些通用算法，别忘了STL容器自身也提供了高效的查找方法，比如、、、。这些容器的成员函数通常比全局算法更高效，因为它们利用了容器内部的数据结构（红黑树或哈希表）来实现O(log N)或平均O(1)的查找速度。当你需要频繁查找时，选择合适的容器本身就是一种强大的查找策略。

尽管STL算法强大，但在实际使用中，如果不注意一些细节，可能会掉入性能陷阱。我个人在项目中就遇到过不少因为选择不当或理解偏差导致的性能瓶颈。

  1. 对未排序数据使用： 这是最常见的错误，也是最致命的。要求数据有序，如果你在一个无序的上调用它，结果是未定义的，很可能返回错误的结果，而编译器不会报错。如果你需要对无序数据进行高效查找，要么先排序（如果查找次数多于一次），要么考虑使用哈希表。

  2. 频繁地对大型数据集进行排序后单次查找： 如果你只有一个查找操作，并且数据是无序的，那么先用进行O(N log N)的排序，然后用进行O(log N)的查找，总成本是O(N log N)。这通常比直接用进行O(N)的线性查找要慢。只有当你需要进行多次查找时，预排序的成本才能被摊销。

  3. 选择错误的容器类型：

    • ： 对于来说，由于其内存连续性，缓存局部性好，表现不错。但对于大量插入/删除操作，它效率不高。
    • ： 在上的表现通常比差，因为的元素不连续，缓存命中率低。无法直接应用于（需要随机访问迭代器）。
    • / ： 这些基于红黑树的容器，其成员函数提供O(log N)的查找效率，且数据始终保持有序。如果你的核心需求是高效查找和自动排序，它们是很好的选择。
    • / ： 基于哈希表的容器，提供平均O(1)的查找效率。这是在需要极致查找速度且不关心元素顺序时的首选。但在最坏情况下（哈希冲突严重），性能可能退化到O(N)。

  4. 自定义比较器的效率： 如果你为或提供了自定义比较器（lambda表达式或函数对象），请确保这个比较器本身是高效的。一个复杂的比较器可能会抵消二分查找带来的性能优势。

  5. 不必要的拷贝： 当查找对象是复杂类型时，确保比较操作是按引用进行的，避免不必要的对象拷贝。例如，如果你的存储的是大对象，在比较时会使用，如果这个操作涉及大量拷贝，会影响性能。

  6. 迭代器失效： 虽然不直接是查找算法本身的性能陷阱，但在使用查找算法得到迭代器后，如果对容器进行了修改（如插入、删除），可能会导致迭代器失效，后续使用失效迭代器会引发未定义行为。这是STL编程中一个非常基础但又容易被忽视的问题。

优化建议：

  • 了解你的数据： 数据是否需要有序？查找频率如何？数据量大小？这些是选择算法和容器的关键。
  • 选择合适的容器： 如果你需要频繁查找且数据有序，考虑或。如果查找是主要的且不需要有序，或通常是最快的。
  • 预排序： 如果数据大部分时间是静态的，但需要多次高效查找，那么一次性排序的成本是值得的。
  • 使用等： 当你需要获取有序序列中元素的精确位置或范围时，、和比更有用，因为它们提供了迭代器。
  • 剖析（Profiling）： 如果对性能有疑问，不要猜测，使用性能分析工具（如Valgrind, gprof, Visual Studio Profiler等）来找出真正的瓶颈。有时候，你认为的瓶颈可能并不是实际的。

总之，STL提供了丰富的查找工具，关键在于理解它们的工作原理和适用场景，并结合实际需求做出明智的选择。

以上就是C++STL查找算法find和binary_search使用的详细内容，更多请关注php中文网其它相关文章！

更多文章