std::stable_partition

#include <algorithm>

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

Phân hoạch các phần tử trong một phạm vi (range), giữ nguyên thứ tự tương đối của các phần tử trong mỗi nhóm (nhóm thỏa mãn điều kiện và nhóm không thỏa mãn điều kiệ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.

Đặc điểm

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. stable_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. stable_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 giữ nguyên.
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. stable_partition() sử dụng nhiều bộ nhớ hơn partition() và có thể chậm hơn partition() trong một số trường hợp, tuy nhiên nó đảm bảo tính ổn định.
7. stable_partition() thường được sử dụng khi:
   • Bạn cần phân tách dữ liệu thành hai nhóm dựa trên một tiêu chí, đồng thời giữ nguyên thứ tự ban đầu của các phần tử trong mỗi nhóm.
   • Bạn cần đảm bảo tính ổn định (stability) của việc phân hoạch, điều này quan trọng trong một số thuật toán và ứng dụng.

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

• partition() phân hoạch phạm vi thành hai nhóm nhưng không đảm bảo thứ tự tương đối của các phần tử trong mỗi nhóm.
• stable_partition() phân hoạch phạm vi thành hai nhóm và giữ nguyên thứ tự tương đối của các phần tử trong mỗi nhóm.

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 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  // Phân hoạch numbers sao cho các số chẵn đứng đầu, giữ nguyên thứ tự
  auto partitionPoint = std::stable_partition(numbers.begin(), numbers.end(), isEven);

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

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

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

  std::cout << "Odd numbers: ";
  for (auto it = partitionPoint; it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  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
sort	Sắp xếp các phần tử trong một phạm vi theo thứ tự tăng dần hoặc theo một tiêu chí so sánh tùy chỉnh
reverse	Đảo ngược thứ tự các phần tử trong một phạm vi được chỉ định
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ừ