std::partition_point

#include <algorithm>

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
                                 UnaryPredicate pred);

Tìm vị trí "điểm phân hoạch" (partition point) đầu tiên trong một phạm vi (range) đã được phân hoạch (partitioned) dựa trên một hàm vị từ (predicate). Điểm phân hoạch là vị trí mà tại đó, tất cả các phần tử trước nó đều thỏa mãn điều kiện, và tất cả các phần tử từ vị trí đó trở đi đều không thỏa mãn điều kiện (hoặc ngược lại, tùy vào cách bạn định nghĩa phân hoạch).

Tham số

first

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi đã được phân hoạch cần tìm điểm phân hoạch.

last

• Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi. 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 phân hoạch, false nếu không.

Giá trị trả về

• Forward Iterator trỏ đến điểm phân hoạch trong phạm vi. Điểm phân hoạch này là phần tử đầu tiên mà không thỏa mãn điều kiện pred. Nói cách khác, iterator trả về trỏ đến phần tử đầu tiên của nhóm thứ hai (nhóm không thỏa mãn pred). Nếu tất cả các phần tử đều thỏa mãn pred, 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_point() yêu cầu phạm vi đầu vào đã được phân hoạch theo điều kiện pred. Nếu phạm vi chưa được phân hoạch, kết quả sẽ không chính xác.
3. partition_point() trả về iterator trỏ đến phần tử đầu tiên không thỏa mãn pred.
4. partition_point() yêu cầu Forward Iterator, cho phép di chuyển một chiều về phía trước.
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_point() thường được sử dụng để:
   • Tìm vị trí của phần tử đầu tiên không thỏa mãn điều kiện trong một phạm vi đã được phân hoạch.
   • Xác định ranh giới giữa hai nhóm phần tử (thỏa mãn và không thỏa mãn điều kiện) trong một phạm vi đã được phân hoạch.
   • Kết hợp với các thuật toán tìm kiếm nhị phân (binary search) trên các phạm vi đã được phân hoạch.

Phân biệt với partition() và stable_partition()

• partition() và stable_partition() thực hiện phân hoạch một phạm vi thành hai nhóm.
• partition_point() tìm điểm phân hoạch trong một phạm vi đã được phân hoạch.

Ví dụ

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

// Hàm vị từ kiểm tra số chẵn
bool isEven(int n) {
  return n % 2 == 0;
}

int main() {
  std::vector<int> numbers = {2, 4, 6, 8, 1, 3, 5, 7}; // Đã được phân hoạch

  // Tìm điểm phân hoạch (phần tử đầu tiên không phải là số chẵn)
  auto it = std::partition_point(numbers.begin(), numbers.end(), isEven);

  std::cout << "Partition point index: " << (it - numbers.begin()) << std::endl;
  std::cout << "Value at partition point: " << *it << std::endl;

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

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

  return 0;
}

Các hàm liên quan

partition	Sắp xếp lại các phần tử trong một phạm vi
find_if_not	Tìm kiếm phần tử đầu tiên trong một phạm vi không thỏa mãn một điều kiện cụ thể được xác định bởi một hàm vị từ
binary_search	Kiểm tra xem một giá trị cho trước có tồn tại trong một phạm vi đã được sắp xếp hay không, sử dụng thuật toán tìm kiếm nhị phân