std::partition

#include <algorithm>

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,
                                 BidirectionalIterator last,
                                 UnaryPredicate pred);

Sắp xếp lại các phần tử trong một phạm vi (range) sao cho tất cả các phần tử thỏa mãn một điều kiện cụ thể (được xác định bởi một hàm vị từ) sẽ được di chuyển lên đầu phạm vi, và tất cả các phần tử không thỏa mãn điều kiện sẽ được di chuyển xuống cuối phạm vi. Thứ tự tương đối của các phần tử trong mỗi nhóm (thỏa mãn và không thỏa mãn) có thể không được giữ nguyên.

Tham số

first

• Bidirectional Iterator trỏ đến phần tử đầu tiên trong phạm vi cần phân hoạch.

last

• Bidirectional Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi cần phân hoạch. Phạm vi là [first, last).

pred

• Một hàm vị từ (unary predicate) nhận một đối số là phần tử trong phạm vi và trả về true nếu phần tử thỏa mãn điều kiện để được xếp vào nhóm đầu tiên, false nếu không.

Giá trị trả về

• Bidirectional Iterator trỏ đến phần tử đầu tiên của nhóm thứ hai (nhóm các phần tử không thỏa mãn điều kiện). Nói cách khác, nó trỏ đến phần tử đầu tiên không thỏa mãn pred trong dãy mới. Nếu tất cả các phần tử đều thỏa mãn pred thì iterator trả về sẽ là last.

Đặc điểm

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. partition() thay đổi trực tiếp thứ tự các phần tử trong phạm vi gốc, không tạo ra một phạm vi mới.
3. partition() yêu cầu Bidirectional Iterator, cho phép di chuyển theo cả hai hướng (tiến và lùi).
4. Thứ tự tương đối của các phần tử trong mỗi nhóm (thỏa mãn và không thỏa mãn điều kiện) có thể không được giữ nguyên. Nếu bạn cần giữ nguyên thứ tự, hãy sử dụng stable_partition().
5. Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm vị từ pred để code ngắn gọn và dễ đọc hơn.
6. partition() thường được sử dụng để:
   • Phân tách dữ liệu thành hai nhóm dựa trên một tiêu chí nhất định.
   • Chuẩn bị dữ liệu cho các thuật toán khác yêu cầu dữ liệu được phân hoạch (ví dụ: nth_element, quicksort).
   • Di chuyển các phần tử mong muốn lên đầu hoặc xuống cuối container.

Ví dụ

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

// Hàm vị từ kiểm tra số lớn hơn 5
bool isGreaterThan5(int n) {
  return n > 5;
}

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

  // Phân hoạch numbers sao cho các số lớn hơn 5 đứng đầu
  auto partitionPoint = std::partition(numbers.begin(), numbers.end(), isGreaterThan5);

  std::cout << "numbers after partition: ";
  for (int x : numbers) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

  std::cout << "Partition point index: " << (partitionPoint - numbers.begin()) << std::endl;

  std::cout << "Elements satisfying the condition: ";
  for (auto it = numbers.begin(); it != partitionPoint; ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  std::cout << "Elements not satisfying the condition: ";
  for (auto it = partitionPoint; it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

Các hàm liên quan

reverse	Đảo ngược thứ tự các phần tử trong một phạm vi được chỉ định
rotate	Xoay các phần tử trong một phạm vi sang trái
find_if	Tìm kiếm phần tử đầu tiên trong một phạm vi thỏa mãn một điều kiện cụ thể được xác định bởi một hàm vị từ
swap	Hoán đổi giá trị của hai đối tượng