对集合进行分区（Partitioning ）就是重新排列它，使得满足给定谓词的元素移到最前面，而不满足该谓词的元素移到其后面。第一个不满足谓词的元素称为分区点。这也是满足谓词的子范围的结束点：

分区是一种常见的数据操作，它将一个集合或范围中的元素按照某个条件重新排列，使得满足给定条件的元素都聚集在前面，而不满足条件的元素聚集在后面。这样做的目的是为了后续的其他操作提供便利，比如查找、删除等。分区的关键点在于确定一个"分区点"，它是第一个不满足给定条件的元素的位置。通过分区，可以将原始范围划分为两个子范围：一个包含满足条件的元素，另一个包含不满足条件的元素。

接受一个范围和一个谓词，并对范围中的元素重新排序，使它们按照这个谓词进行分区：

template<typename ForwardIterator, typename Predicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate p);

 函数返回一个指向被重新排序的范围的分区点的迭代器。它的复杂度为 O(n)。

 不能保证满足（或不满足）谓词条件的元素的顺序。如果需要这种保证，可以使用 

 也会返回一个指向重新排序范围分区点的迭代器。

template< class BidirIt, class UnaryPredicate >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );

允许分配临时缓冲区。如果有足够的额外内存来分配，那么它的复杂度是

#include <iostream>
#include <vector>
#include <algorithm>

bool isEven(int n) {
    return n % 2 == 0;
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    auto it = std::stable_partition(numbers.begin(), numbers.end(), isEven);

    std::cout << "Partition point: " << *it << std::endl;

    std::cout << "Partitioned elements: ";
    for (auto iter = numbers.begin(); iter != it; ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    std::cout << "Remaining elements: ";
    for (auto iter = it; iter != numbers.end(); ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    return 0;
}

Partition point: 5
Partitioned elements: 2 4 6 8 10
Remaining elements: 1 3 5 7 9

如果需要保持范围不变，并将输出放在其他地方，可以使用

。它在两个范围中写入输出：第一个范围包含满足谓词的元素，第二个范围包含不满足谓词的元素。

返回一个指向两个输出范围末尾的迭代器对。函数原型：

template<typename InputIt, typename OutputIt1, typename OutputIt2, typename Predicate>
std::pair<OutputIt1, OutputIt2>
        partition_copy(InputIt first, InputIt last,
                       OutputIt first_true, OutputIt first_false,
                       Predicate p);

检查是否根据某个谓词对一个范围进行了分区。函数原型：

template<typename InputIt, typename Predicate>
bool is_partitioned(InputIt first, InputIterator last, Predicate p);

要获取分区范围的分区点，使用

template<typename ForwardIterator, typename Predicate>
ForwardIterator partition_point(ForwardIterator first,
                                ForwardIterator last,
                                Predicate p);

函数。该算法接受一个范围和一个谓词，并返回从该范围不再被分区的首个位置开始的迭代器。

4.1、lower_bound、upper_bound 和 equal_range

可以通过使用分区算法来实现。在给定值a的范围下界之前的每个元素

。下界是第一个不满足该谓词的元素，因此

template<typename ForwardIt, typename T>
ForwardIterator lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    return std::partition_point(first, last, [value](const auto& x){return x < value;});
}

如何将一个范围内满足条件的元素聚集到给定位置？即：

一个可行的想法是将初始范围视为2部分：

都会返回相应的分区点，分别是收集范围的开始和结束。这个范围可以从函数返回。

template<typename BidirIterator, typename Predicate>
Range<BidirIterator> gather(BidirIterator first, BidirIterator last,
                            BidirIterator position, Predicate p)
{
    return { std::stable_partition(first, position, std::not_fn(p)),
             std::stable_partition(position, last, p) };
}

是一个类，可以用两个表示开始和结束的迭代器进行初始化，例如

算法，该函数返回一对迭代器。

知道如何用STL实现分区是很有用的，因为这个概念出现在很多情况下。它是C++工具箱中的另一个重要工具。

学会使用STL中的分区相关算法是很有帮助的，因为这些算法广泛应用于各种数据处理场景。掌握好分区的概念和使用方法，可以让我们在面对需要对元素进行重新排列的问题时，有更加灵活和高效的解决方案。无论是基本的

，都是我们工具箱中不可或缺的重要组件。

掌握 STL 中的分区技术：std::partition 优化 C++ 代码性能

知道如何用STL实现分区是很有用的，它是C++工具箱中的另一个重要工具。无论是基本的std::partition和std::stable_partition，还是一些扩展算法如std::is_partitioned和std::partition_point，都是我们工具箱中不可或缺的重要组件。

编程语言

算法

C++分区操作详解：std::partition和std::stable_partition函数用法，实现集合元素按条件重新排列。了解分区点概念，掌握分区属性检查方法，学习lower_bound等实用案例。高效数据处理必备技能，提升算法实现灵活性。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

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

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

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

掌握 STL 中的分区技术：std::partition 优化 C++ 代码性能

掌握 STL 中的分区技术：std::partition 优化 C++ 代码性能

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐