本文介绍可以在各种上下文中使用的算法，但它们有一个共同点：它们返回一个或多个范围的布尔特征。

本文介绍了如何使用STL的范围谓词来轻松应对复杂的数据逻辑。范围谓词是STL中强大而灵活的工具，可以帮助开发人员处理各种条件和筛选要素，以提高代码的可读性和性能。

STL提供了3种算法，用于指示范围中的所有、部分或全部元素是否满足给定条件。条件本身由谓词表示，也就是说，一个函数指针(或对象)接受范围的一个元素并返回

这就是STL，但Boost更进一步提出了以下算法：

在空范围的情况下，它们的行为与它们对应的原生类型完全相同。

可以用来比较两个范围，检查元素是否分别相等(比较是通过

或自定义比较器完成的)。注意，

，即第一个范围由开始迭代器和结束迭代器表示，而第二个范围没有结束迭代器：

template<template InputIterator1, template InputIterator2 >
bool equal(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2);

因此，该算法会一直运行到第1个范围的结束，即使第2个范围较短，也会进行比较，因为它并不知道第2个范围的长度。

从C++ 14开始，这个问题得到了纠正，新的

重载接受两个完整的范围，包括开始和结束。

假设有两个集合，如何确定其中一个集合是另一个集合的排列？或者换句话说，如果两个集合包含相同的元素，即使它们的顺序不同，如何确定这一点？

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {4, 2, 3, 1, 5};
std::vector<int> v3 = {2, 3, 4, 5, 6};

std::is_permutation(v1.begin(), v1.end(),
                    v2.begin(), v2.end());

std::is_permutation(v1.begin(), v1.end(),
                    v3.begin(), v3.end());

接口，也就是说它接受第一个范围的

std::is_permutation(v1.begin(), v1.end(),
                    v2.begin());

因此，如果第二个集合比第一个小，那么算法会开心地一直查询第二个集合，直到查询到第一个集合的末尾，从而导致未定义的行为。结果是，必须确保第二个集合至少和第一个一样大。

但这在C++ 14中得到了纠正，它为两个集合添加了带有

比较元素，并提供一个接受自定义比较器的重载。

4.1、std::is_permutation 的算法复杂度

的复杂度在最糟糕的情况下为O(n²)。这听起来可能有点不可思议：实际上，STL的算法被认为是用最好的算法复杂度实现的。难道我们可以做得比O(n²)复杂度更好吗？

是的，可以做得比O(n²)复杂度更好，但代价是额外的内存分配。所以这是CPU和内存之间的权衡。

4.2、std::is_permutation 的使用示例

假设有一个函数，它返回一个值的集合（或通过输出迭代器生成），但没有指定这些元素在集合中的位置顺序。如何为这个函数编写单元测试？

无法对预期输出和实际输出进行 EXPECT_EQ 测试，因为无法确切知道输出应该等于什么，也不知道其元素的顺序。

std::vector<int> expected = {1, 2, 3, 4, 5};

std::vector<int> results = f();

EXPECT_TRUE(std::is_permutation(begin(expected), end(expected),
                                begin(results), end(results)));

返回1、2、3、4和5，但顺序可以任意。

这两种算法可以在范围上实现某种排序，可以用它来比较两个范围。更具体地说：

从两个输入范围的开头开始比较它们各自的元素，并以迭代器

的形式返回它们第一个不同的位置：

的第一个元素是指向第一个范围内第一个不匹配元素的迭代器，

的第二个元素是指向第二个范围内第一个不匹配元素的迭代器。

template<typename InputIt1, typename InputIt2, typename BinaryPredicate>
std::pair<InputIt1,InputIt2>
    mismatch(InputIt1 first1, InputIt1 last1,
             InputIt2 first2,
             BinaryPredicate p);

问题，所以确保先通过较短的范围。如果使用它进行比较，这可能会很麻烦。但和

实际上提供了对范围的排序，其操作方式与

提供对字符串的排序相同，因此得名。它使用

(或自定义比较器)比较2乘2的元素。

template<typename InputIt1, typename InputIt2, typename Compare>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2,
                             Compare comp );

需要2个完整的范围，所以它没有1.5个范围的问题。

非常方便，它允许对包装容器的类进行自然而简单的编码顺序。例如，当处理类似CSV的数据时，设计一个Entry类来表示CSV文件中给定行上用逗号分隔的所有数据块：

class Entry
{
public:
    // ...Entry interface...
    bool operator<(const Entry& other)
    {
        return std::lexicographical_compare(begin(data_), end(data_),
                                            begin(other.data_), end(other.data_));
    }
private:
    std::vector<std::string> data_;
};

这允许以自然的方式对条目进行简单排序，从而实现快速搜索和相关功能(插入等)。它还使Entry与

本文详细介绍了STL的范围谓词的概念。范围谓词是处理复杂数据逻辑的有力工具，通过定义和使用谓词函数可以轻松地筛选和操作数据集合。结合STL的算法，范围谓词可以帮助编写简洁、高效的代码，提高开发效率和代码可读性。

玩转STL的范围谓词：轻松应对复杂数据逻辑

本文详细介绍了STL的范围谓词的概念。范围谓词是处理复杂数据逻辑的有力工具，通过定义和使用谓词函数可以轻松地筛选和操作数据集合。

编程语言

本文深入解析STL范围谓词算法，包括all_of、any_of、none_of等核心函数及其Boost扩展版本。详细介绍std::equal、std::is_permutation等范围比较算法，分析其复杂度及使用场景，帮助开发者高效处理数据筛选与比较逻辑，提升代码质量和性能表现。

单元测试

容器

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

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

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

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

玩转STL的范围谓词：轻松应对复杂数据逻辑

玩转STL的范围谓词：轻松应对复杂数据逻辑

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐