std::is_partitioned

 

C++

Compiler support

Freestanding and hosted

Language

Standard library

Standard library headers

Named requirements

Feature test macros (C++20)

Language support library

Concepts library (C++20)

Diagnostics library

Memory management library

Metaprogramming library (C++11)

General utilities library

Containers library

Iterators library

Ranges library (C++20)

Algorithms library

Strings library

Text processing library

Numerics library

Date and time library

Input/output library

Filesystem library (C++17)

Concurrency support library (C++11)

Execution control library (C++26)

Technical specifications

Symbols index

External libraries

 

Algorithm library

Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Non-modifying sequence operations     Batch operations for_each for_each_n (C++17) Search operations all_ofany_ofnone_of (C++11)(C++11)(C++11) countcount_if mismatch equal findfind_iffind_if_not (C++11) find_end find_first_of adjacent_find search search_n Modifying sequence operations Copy operations copycopy_if (C++11) copy_backward copy_n (C++11) move (C++11) move_backward (C++11) Swap operations swap iter_swap swap_ranges Transformation operations replacereplace_if transform replace_copyreplace_copy_if Generation operations fill fill_n generate generate_n Removing operations removeremove_if unique remove_copyremove_copy_if unique_copy Order-changing operations reverse reverse_copy rotate rotate_copy random_shuffleshuffle (until C++17)(C++11) shift_leftshift_right (C++20)(C++20) Sampling operations sample (C++17)	Sorting and related operations Partitioning operations partition partition_copy (C++11)     stable_partition is_partitioned (C++11)     partition_point (C++11) Sorting operations sort stable_sort partial_sort partial_sort_copy is_sorted (C++11) is_sorted_until (C++11) nth_element Binary search operations (on partitioned ranges) lower_bound upper_bound equal_range binary_search Set operations (on sorted ranges) includes set_union set_intersection          set_difference set_symmetric_difference Merge operations (on sorted ranges) merge inplace_merge Heap operations push_heap pop_heap make_heap sort_heap is_heap (C++11) is_heap_until (C++11) Minimum/maximum operations max min minmax (C++11) clamp (C++17) max_element min_element minmax_element (C++11) Lexicographical comparison operations lexicographical_compare lexicographical_compare_three_way (C++20) Permutation operations next_permutation prev_permutation is_permutation (C++11)	Execution policies (C++17) is_execution_policy (C++17) execution::seqexecution::parexecution::par_unseqexecution::unseq (C++17)(C++17)(C++17)(C++20) execution-policy (exposition only*)(C++26) execution::sequenced_policyexecution::parallel_policyexecution::parallel_unsequenced_policyexecution::parallel_unsequenced (C++17)(C++17)(C++17)(C++20) Numeric operations iota (C++11) inner_product      reduce (C++17) accumulate adjacent_difference transform_reduce (C++17) partial_sum inclusive_scan (C++17)     exclusive_scan (C++17) transform_inclusive_scan (C++17) transform_exclusive_scan (C++17) Specialized <memory> algorithms Specialized <random> algorithms ranges::generate_random (C++26) C library qsort bsearch

 

Defined in header <algorithm>
template< class InputIt, class UnaryPred > bool is_partitioned( InputIt first, InputIt last, UnaryPred p );	(1)	(since C++11) (constexpr since C++20)
template< class ExecutionPolicy, class ForwardIt, class UnaryPred > bool is_partitioned( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, UnaryPred p );	(2)	(since C++17)

1) Checks whether the elements e in the source range [first, last) are partitioned with respect to the expression bool(p(e)): all elements satisfy p appear before all elements that do not.

2) Same as (1), but executed according to policy.

This overload participates in overload resolution only if the value of the following expression is true:

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>	(until C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>	(since C++20)

Parameters

first, last	-	the pair of iterators defining the source range
p	-	unary predicate which returns ​true for the elements before the partition point. The expression p(v) must be convertible to bool for every argument v of type (possibly const) VT, where VT is the value type of InputIt, regardless of value category, and must not modify v. Thus, a parameter type of VT&is not allowed, nor is VT unless for VT a move is equivalent to a copy(since C++11). ​
policy	-	the execution policy to use
Type requirements
- InputIt must meet the requirements of LegacyInputIterator.
- ForwardIt must meet the requirements of LegacyForwardIterator. and its value type must be convertible to UnaryPred's parameter type.
- UnaryPred must meet the requirements of Predicate.

Return value

true if the elements of the source range are partiationed as descibed above or the source range is empty, false otherwise.

Complexity

Given \(\scriptsize N\)N as std::distance(first, last):

1) At most \(\scriptsize N\)N applications of p.

2) \(\scriptsize \mathcal{O}(N)\)𝓞(N) applications of p.

Exceptions

2) During the execution process:

• If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
• If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).

Possible implementation

template<class InputIt, class UnaryPred> bool is_partitioned(InputIt first, InputIt last, UnaryPred p) { for (; first != last; ++first) if (!p(*first)) break; for (; first != last; ++first) if (p(*first)) return false; return true; }

Example

Run this code

#include <algorithm>
#include <array>
#include <iostream>

int main()
{
    std::array<int, 9> v{1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    auto is_even = [](int i) { return i % 2 == 0; };
    std::cout.setf(std::ios_base::boolalpha);
    std::cout << std::is_partitioned(v.begin(), v.end(), is_even) << ' ';
    
    std::partition(v.begin(), v.end(), is_even);
    std::cout << std::is_partitioned(v.begin(), v.end(), is_even) << ' ';
    
    std::reverse(v.begin(), v.end());
    std::cout << std::is_partitioned(v.cbegin(), v.cend(), is_even) << ' ';
    std::cout << std::is_partitioned(v.crbegin(), v.crend(), is_even) << '\n';
}

Output:

false true false true

See also

ranges::is_partitioned (C++20)	determines if the range is partitioned by the given predicate (algorithm function object)
partition	divides a range of elements into two groups (function template & algorithm function object)
ranges::partition (C++20)
partition_point (C++11)	locates the partition point of a partitioned range (function template & algorithm function object)
ranges::partition_point (C++20)