本文章旨在涵盖所有在STL中（甚至稍微超出）关于搜索的知识，尽管在集合中搜索某些东西的需求是一个很容易理解的概念，但是要彻底地涵盖这个主题，还有很多内容要讲。

本文主要介绍在元素范围上执行搜索的经典STL算法，后面会继续讲解

当直接访问STL容器时，如何执行有效和正确的搜索，而不是简单的范围；以及介绍的绝大多数开发人员不知道但很有用的算法

这篇文章展示如何在一个范围内搜索。这里坚持用标准版本的STL，并考虑由2个迭代器表示的范围。

STL可以被分成两部分：对已排序元素进行操作的部分以及对未排序元素进行操作的部分。

来表示，并结合与范围末尾的比较：

vector<int> v = {...}; // v filled with values
if (std::find(v.begin(), v.end(), 42) != v.end())
{
    ...
}

vector<int> v = {...}; // v filled with values
if (std::count(v.begin(), v.end(), 42))
{
    ...
}

值：在这里，如果范围内至少有一个元素等于42，则计算结果为

注意，要检查是否存在满足谓词而不等于值的元素，用

关于已排序元素，要用的算法是

值，表示搜索值是否在集合中具有等效元素。

std::set<int> numbers = {...}; // sorted elements
bool is42InThere = std::binary_search(numbers.begin(), numbers.end(), 42);

更准确地说，希望获得指向搜索元素出现位置的迭代器。

。返回指向第一个和搜索值相等的元素的迭代器，如果没有找到该值，则返回指向集合末尾的迭代器。

std::vector<int> numbers = {...};
auto searchResult = std::find(numbers.begin(), numbers.end(), 42);

if (searchResult != numbers.end()) {
    ...
}

并不是真正为排序集合而设计的，因为它用的是相等而不是等价，并且它在线性时间而不是对数时间内操作。

对于给定的集合，如果确定现在和将来元素的类型的相等性与等价性是相同的，并且接受付出线性时间，

将是不错的选择，引起它是简单的接口。必须注意，

不是专门为排序范围进行操作而设计的。

template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );

 返回与搜索值等价的元素范围。该范围由指向集合内部的 

 迭代器对表示， 该对中的两个迭代器分别表示与搜索值等价的子范围中第一个和最后一个元素。

std::vector<int> v = {3, 7, 3, 11, 3, 3, 2};
sort(v.begin(), v.end());

// equal_range, attempt 1: natively clumsy
std::pair<std::vector<int>::iterator, std::vector<int>::iterator> range1 = equal_range(v.begin(), v.end(), 3);
std::for_each(range1.first, range1.second, doSomething);

使用类型定义可以使其更轻巧：

std::vector<int> v = {3, 7, 3, 11, 3, 3, 2};
sort(v.begin(), v.end());

using IteratorPair = std::pair<std::vector<int>::iterator, std::vector<int>::iterator>;

// equal_range, attempt 2: with the classical typedef
IteratorPair range2 = equal_range(v.begin(), v.end(), 3);
std::for_each(range2.first, range2.second, doSomething);

上面的示例确实少了笨拙，但仍然有一个基本的问题：抽象的层次没有得到遵守。事实上，当操作由

强迫使用代码的“first”和“second”，而它应该是一个范围。而一个范围应该用“begin”和“end”来表达。

为了解决这个问题，可以使用一个类将std::equal_range返回的一对迭代器包装成一个具有范围语义的对象：

template<typename Container>
class Range
{
public:
    Range(std::pair<typename Container::iterator, typename Container::iterator> range)
    : m_begin(range.first), m_end(range.second)
    {}
    typename Container::iterator begin() { return m_begin; }
    typename Container::iterator end() { return m_end; }
 
private:
    typename Container::iterator m_begin;
    typename Container::iterator m_end;
};

这类存在于诸如Boost.range或range-v3之类的range库中。如果查看它们的实现代码(这里是boost的实现代码，这里是range-v3的实现代码)，会发现它们包含的内容远不止上面的简单包装器，这里只是为了说明要点，而不是用于实际生产代码)。

这有效地将一对迭代器提升到范围的抽象级别。

的结果，即使它是一个范围！包装器才能真正解决了这个问题。

std::vector<int> v = {3, 7, 3, 11, 3, 3, 2};
sort(v.begin(), v.end());
 
// equal_range, attempt 3: natural al last
Range<std::vector<int>> range3 = equal_range(v.begin(), v.end(), 3);
std::for_each(range3.begin(), range3.end(), doSomething);

都会返回一个范围，所以可以通过比较两个迭代器来检查它是否为空，并使用

bool noElementFound = range3.begin() == range3.end();
size_t numberOfElementFound = std::distance(range3.begin(), range3.end())

这个问题只对已排序的范围有意义，因为对于未排序的范围，元素可以在范围中的任何位置。对于一个已排序的范围，更精确地说是：“如果它在那里，那么它在哪里，如果它不在那里，那么它应该在哪里?”。有点绕，对不对，没关系，继续往下阅读。

返回的第一个迭代器和第二个迭代器。

不同，从而知道元素是否在集合中。如果元素不存在，

返回它应该在的位置，而不是集合的末尾。因此，需要检查返回的迭代器是否不在范围的末尾，并检查它指向的元素的值是否与搜索的元素的值相等。

要特别要小心：相等，不相等。如果对类型并不意味着相同的事情，则需要编写等价测试，通常采用

，而是自定义比较器，则需要使用自定义比较器。如果比较器发生变化，一定要更新代码。

下面的表格总结了在一个范围内搜索时使用的算法：

如何在C++的STL中巧妙运用std::find实现高效查找

本文章旨在涵盖所有在STL中（甚至稍微超出）关于搜索的知识，主要介绍在元素范围上执行搜索的经典STL算法。

后端

编程语言

算法

STL搜索算法详解：比较未排序与已排序范围的搜索方法，包括std::find、binary_search、equal_range等，提升C++开发效率。

容器

AI驱动 智领未来

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

如何在C++的STL中巧妙运用std::find实现高效查找

如何在C++的STL中巧妙运用std::find实现高效查找

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐