C++ Algorithm Partition | "Partition Algorithm" Guide

· 12분 읽기 · 수정 Intermediate Tutorial
C++ Algorithm Partition | "Partition Algorithm" Guide

이 글의 핵심

std::partition and stable_partition: split ranges by predicate in linear time—quickselect, filtering, and STL partition algorithms in C++.

Partitioning reorders a range so that all elements for which the predicate is true appear before those for which it is false. It runs in linear time and is not stable unless you use stable_partition (extra cost / memory). The returned iterator points to the first element that fails the predicate (or end if all pass). Typical uses: quickselect, splitting data for branchy processing, or as a step before partial_sort.

What is partition?

Partition moves “true” elements to the front and “false” elements to the back. Relative order within each group is not guaranteed for std::partition; use stable_partition when order must be preserved.

#include <algorithm>
#include <vector>

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

// Move even numbers to the front
auto pivot = std::partition(v.begin(), v.end(), 
    [](int x) { return x % 2 == 0; });

// [2, 4, 6, 1, 3, 5] (order not guaranteed)

Why is it useful?:

  • Filtering: Group elements based on a condition
  • Performance: O(n) time complexity
  • Flexibility: Supports custom conditions
  • Preprocessing: Partitioning before sorting
// ❌ Manual partitioning: complex
std::vector<int> evens, odds;
for (int x : v) {
    if (x % 2 == 0) {
        evens.push_back(x);
    } else {
        odds.push_back(x);
    }
}

// ✅ Partition: concise
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

How Partition Works:

flowchart LR
    A[""(1, 2, 3, 4, 5, 6"]"] --> B[partition]
    B --> C[""(2, 4, 6, 1, 3, 5"]"]
    C --> D["true group"]
    C --> E["false group"]
    D -.-> |pivot| E

Types of Partition:

AlgorithmStabilityTime ComplexityUse Case
partition❌ UnstableO(n)Fast partitioning
stable_partition✅ StableO(n log n)Preserve order
partition_point-O(log n)Find partition point
partition_copy✅ StableO(n)Partition while copying
std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition: fast, order not guaranteed
auto pivot1 = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

// stable_partition: slower, preserves order
auto pivot2 = std::stable_partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

Basic Usage

#include <algorithm>

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

// Partition
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

std::cout << "Even numbers: ";
for (auto it = v.begin(); it != pivot; ++it) {
    std::cout << *it << " ";
}

std::cout << "\nOdd numbers: ";
for (auto it = pivot; it != v.end(); ++it) {
    std::cout << *it << " ";
}

Practical Examples

Example 1: Filtering

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {1, -2, 3, -4, 5, -6, 7, -8};
    
    // Move positive numbers to the front
    auto pivot = std::partition(numbers.begin(), numbers.end(),
        [](int x) { return x > 0; });
    
    std::cout << "Positive numbers: ";
    for (auto it = numbers.begin(); it != pivot; ++it) {
        std::cout << *it << " ";
    }
}

Example 2: stable_partition

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    
    // Stable partition (preserve order)
    auto pivot = std::stable_partition(v.begin(), v.end(),
        [](int x) { return x % 2 == 0; });
    
    for (int x : v) {
        std::cout << x << " ";  // 2 4 6 1 3 5
    }
}

Example 3: partition_point

#include <algorithm>

int main() {
    std::vector<int> v = {2, 4, 6, 1, 3, 5};
    
    // Already partitioned range
    std::partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
    
    // Find partition point
    auto pivot = std::partition_point(v.begin(), v.end(),
        [](int x) { return x % 2 == 0; });
    
    std::cout << "Partition point: " << std::distance(v.begin(), pivot) << std::endl;
}

Example 4: 3-way Partitioning

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // Partition by remainder when divided by 3
    auto pivot1 = std::partition(v.begin(), v.end(),
        [](int x) { return x % 3 == 0; });
    
    auto pivot2 = std::partition(pivot1, v.end(),
        [](int x) { return x % 3 == 1; });
    
    std::cout << "Multiples of 3: ";
    for (auto it = v.begin(); it != pivot1; ++it) {
        std::cout << *it << " ";  // 3 6 9
    }
    
    std::cout << "\nRemainder 1: ";
    for (auto it = pivot1; it != pivot2; ++it) {
        std::cout << *it << " ";  // 1 4 7
    }
    
    std::cout << "\nRemainder 2: ";
    for (auto it = pivot2; it != v.end(); ++it) {
        std::cout << *it << " ";  // 2 5 8
    }
}

Partition Algorithms

// partition: unstable
auto pivot = std::partition(begin, end, pred);

// stable_partition: stable (preserves order)
auto pivot = std::stable_partition(begin, end, pred);

// partition_point: find partition point
auto pivot = std::partition_point(begin, end, pred);

// is_partitioned: check if partitioned
bool partitioned = std::is_partitioned(begin, end, pred);

// partition_copy: partition while copying
std::partition_copy(begin, end, out1, out2, pred);

Common Issues

Issue 1: Order

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

// partition: order not guaranteed
std::partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// Possible: [2, 6, 4, 1, 3, 5]

// stable_partition: preserves order
std::stable_partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// Guaranteed: [2, 4, 6, 1, 3, 5]

Issue 2: partition_point

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

// ❌ Not partitioned
// auto pivot = std::partition_point(v.begin(), v.end(), pred);  // Undefined behavior

// ✅ After partitioning
std::partition(v.begin(), v.end(), pred);
auto pivot = std::partition_point(v.begin(), v.end(), pred);

Issue 3: Performance

// partition: O(n), unstable
std::partition(v.begin(), v.end(), pred);

// stable_partition: O(n log n), stable
std::stable_partition(v.begin(), v.end(), pred);

// Use partition if order is not important

Issue 4: Return Value

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

// partition returns: iterator to partition point
auto pivot = std::partition(v.begin(), v.end(), pred);

// [begin, pivot): true
// [pivot, end): false

Usage Patterns

// 1. Filtering
auto pivot = std::partition(v.begin(), v.end(), pred);

// 2. Stable partitioning
auto pivot = std::stable_partition(v.begin(), v.end(), pred);

// 3. Find partition point
auto pivot = std::partition_point(v.begin(), v.end(), pred);

// 4. Partition while copying
std::partition_copy(v.begin(), v.end(), out1, out2, pred);

Practical Patterns

Pattern 1: Priority Handling

#include <algorithm>
#include <vector>

struct Task {
    std::string name;
    int priority;
    bool urgent;
};

void processTasks(std::vector<Task>& tasks) {
    // Move urgent tasks to the front
    auto pivot = std::stable_partition(tasks.begin(), tasks.end(),
        [](const Task& t) { return t.urgent; });
    
    // Process urgent tasks
    for (auto it = tasks.begin(); it != pivot; ++it) {
        std::cout << "Urgent: " << it->name << '\n';
    }
    
    // Process regular tasks
    for (auto it = pivot; it != tasks.end(); ++it) {
        std::cout << "Regular: " << it->name << '\n';
    }
}

Pattern 2: Conditional Removal

#include <algorithm>
#include <vector>

template<typename T, typename Pred>
void removeIf(std::vector<T>& vec, Pred pred) {
    // Move elements to be removed to the back
    auto pivot = std::partition(vec.begin(), vec.end(),
        [&pred](const T& item) { return !pred(item); });
    
    // Erase elements from the back
    vec.erase(pivot, vec.end());
}

// Usage
std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
removeIf(numbers, [](int x) { return x % 2 == 0; });
// Result: {1, 3, 5}

Pattern 3: Group Processing

#include <algorithm>
#include <vector>
#include <string>

struct User {
    std::string name;
    bool premium;
    int age;
};

void processUsers(std::vector<User>& users) {
    // Move premium users to the front
    auto pivot = std::stable_partition(users.begin(), users.end(),
        [](const User& u) { return u.premium; });
    
    // Process premium users
    std::cout << "Premium Users:\n";
    for (auto it = users.begin(); it != pivot; ++it) {
        std::cout << "- " << it->name << '\n';
    }
    
    // Process regular users
    std::cout << "Regular Users:\n";
    for (auto it = pivot; it != users.end(); ++it) {
        std::cout << "- " << it->name << '\n';
    }
}

Troubleshooting & gotchas

  • Predicate side effects: std::partition may invoke the predicate more than once per element; keep predicates pure and cheap.
  • Iterator invalidation: For std::vector, partitioning moves elements; iterators before erase in remove-if style code must follow the erase-remove idiom carefully.
  • Already sorted vs partitioned: A sorted range is partitioned for monotonic predicates, but partition_point requires the range to be partitioned for that specific predicate—do not confuse with binary search preconditions.
  • Parallelism: The standard partition algorithms are single-threaded; for huge arrays, manual block partitioning plus merge may be needed—measure before splitting.

FAQ

Q1: What is partition?

A: An algorithm that divides elements into two groups based on a condition.

auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

Q2: What about stability?

A:

  • partition: Unstable (order not guaranteed)
  • stable_partition: Stable (preserves order)
// partition: [2, 6, 4, 1, 3, 5] (possible)
// stable_partition: [2, 4, 6, 1, 3, 5] (guaranteed)

Q3: What does it return?

A: Iterator to the partition point.

auto pivot = std::partition(v.begin(), v.end(), pred);

// [begin, pivot): true
// [pivot, end): false

Q4: What about performance?

A:

  • partition: O(n)
  • stable_partition: O(n log n)
// Fast
std::partition(v.begin(), v.end(), pred);

// Slow (preserves order)
std::stable_partition(v.begin(), v.end(), pred);

Q5: What is partition_point?

A: Finds the partition point in an already partitioned range. O(log n) time complexity.

// After partitioning
std::partition(v.begin(), v.end(), pred);

// Find partition point
auto pivot = std::partition_point(v.begin(), v.end(), pred);

Q6: What is partition_copy?

A: Partitions while copying.

std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::vector<int> evens, odds;

std::partition_copy(v.begin(), v.end(),
    std::back_inserter(evens),
    std::back_inserter(odds),
    [](int x) { return x % 2 == 0; });

Q7: How to check if partitioned?

A: Use std::is_partitioned.

if (std::is_partitioned(v.begin(), v.end(), pred)) {
    std::cout << "Partitioned\n";
}

Q8: Resources for learning Partition?

A:

Related Posts: algorithm, sort, remove_if.

Summary: Partition is an STL algorithm that divides elements into two groups based on a condition.

Here are other posts related to this topic:

Practical Tips

Here are tips for applying this concept in real-world scenarios.

Debugging Tips

  • Check compiler warnings first when issues arise
  • Reproduce the problem with a simple test case

Performance Tips

  • Avoid optimization without profiling
  • Set measurable metrics before optimizing

Code Review Tips

  • Anticipate common review feedback
  • Follow your team’s coding conventions

Practical Checklist

Use this checklist when applying this concept in practice.

Before Writing Code

  • Is this the best approach for solving the problem?
  • Can team members understand and maintain this code?
  • Does it meet performance requirements?

While Writing Code

  • Have you resolved all compiler warnings?
  • Have you considered edge cases?
  • Is error handling appropriate?

During Code Review

  • Is the intent of the code clear?
  • Are there sufficient test cases?
  • Is the code well-documented?

Use this checklist to reduce errors and improve code quality.

Keywords Covered in This Post (Related Search Terms)

Search for C++, algorithm, partition, STL, sort to find relevant information on this topic.