std::partial_sort_copy

#include <algorithm>

// Sắp xếp tăng dần theo mặc định sử dụng toán tử <
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last,
                                        RandomAccessIterator result_first,
                                        RandomAccessIterator result_last);

// Sắp xếp theo tiêu chí so sánh tùy chỉnh
template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last,
                                        RandomAccessIterator result_first,
                                        RandomAccessIterator result_last,
                                        Compare comp);

Sao chép các phần tử từ một phạm vi (range) nguồn sang một phạm vi đích, đồng thời sắp xếp một phần của phạm vi đích đó (các phần tử nhỏ nhất hoặc lớn nhất, tùy theo tiêu chí so sánh) trong quá trình sao chép. Phạm vi nguồn không bị thay đổi.

Tham số

first

• Input Iterator trỏ đến phần tử đầu tiên trong phạm vi nguồn cần sao chép.

last

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

result_first

• Random Access Iterator trỏ đến phần tử đầu tiên trong phạm vi đích.

result_last

• Random Access Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi đích. Phạm vi đích là [result_first, result_last).

comp

• Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (hai phần tử) và trả về true nếu phần tử thứ nhất được coi là nhỏ hơn phần tử thứ hai theo tiêu chí so sánh, false nếu ngược lại. (Phiên bản 2)

Giá trị trả về

• Random Access Iterator trỏ đến phần tử ngay sau phần tử cuối cùng được sao chép trong phạm vi đích. Nếu số phần tử được sao chép (bị giới hạn bởi kích thước phạm vi nguồn hoặc đích) nhỏ hơn kích thước phạm vi đích, iterator trả về sẽ nhỏ hơn result_last.

Đặc điểm

1. Phạm vi nguồn [first, last) và phạm vi đích [result_first, result_last) là "nửa mở", không bao gồm phần tử last và result_last.
2. partial_sort_copy() không thay đổi phạm vi nguồn.
3. Phạm vi đích phải có đủ không gian để chứa các phần tử được sao chép và sắp xếp.
4. partial_sort_copy() trả về iterator trỏ đến sau phần tử cuối cùng được sao chép trong phạm vi đích.
5. partial_sort_copy() yêu cầu Input Iterator cho phạm vi nguồn và Random Access Iterator cho phạm vi đích.
6. Nếu kích thước phạm vi đích (result_last - result_first) lớn hơn kích thước phạm vi nguồn (last - first) thì chỉ những phần tử trong phạm vi nguồn được sao chép và sắp xếp.
7. Thứ tự của các phần tử không được sao chép trong phạm vi nguồn là không xác định.
8. Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm so sánh comp (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
9. partial_sort_copy() kết hợp giữa partial_sort() (sắp xếp một phần) và copy() (sao chép).
10. partial_sort_copy() thường được sử dụng khi:
    • Bạn cần sao chép và đồng thời sắp xếp k phần tử nhỏ nhất (hoặc lớn nhất) từ một phạm vi nguồn sang một phạm vi đích.
    • Bạn muốn tạo một bản sao được sắp xếp một phần từ một tập hợp dữ liệu lớn mà không làm thay đổi dữ liệu gốc.
    • Kích thước của phạm vi đích có thể nhỏ hơn phạm vi nguồn (chỉ sao chép và sắp xếp một số lượng phần tử nhất định).

Phân biệt với partial_sort(), sort(), stable_sort(), và copy()

• sort() và stable_sort() sắp xếp toàn bộ phạm vi tại chỗ.
• partial_sort() sắp xếp một phần của phạm vi tại chỗ.
• copy() sao chép toàn bộ phạm vi mà không sắp xếp.
• partial_sort_copy() sao chép và sắp xếp một phần vào một phạm vi khác.

Ví dụ

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

// Hàm so sánh để sắp xếp giảm dần
bool compareDescending(int a, int b) {
  return a > b;
}

int main() {
  std::vector<int> source = {5, 2, 8, 1, 9, 4, 7, 3, 6};
  std::vector<int> destination(5); // Lưu 5 phần tử nhỏ nhất

  // Sao chép và sắp xếp 5 phần tử nhỏ nhất từ source sang destination
  auto it = std::partial_sort_copy(source.begin(), source.end(),
                                  destination.begin(), destination.end());

  std::cout << "destination after partial_sort_copy (5 smallest): ";
  for (int x : destination) {
    std::cout << x << " ";
  }
  std::cout << std::endl;
  std::cout << "Number of elements copied: " << (it - destination.begin()) << std::endl;

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

  // Sao chép và sắp xếp 3 phần tử lớn nhất từ source2 sang destination2 (giảm dần)
  auto it2 = std::partial_sort_copy(source2.begin(), source2.end(),
                                   destination2.begin(), destination2.end(),
                                   compareDescending);
    
  std::cout << "destination2 after partial_sort_copy (3 largest): ";
  for (int x : destination2) {
      std::cout << x << " ";
  }
  std::cout << std::endl;
  std::cout << "Number of elements copied: " << (it2 - destination2.begin()) << std::endl;

  return 0;
}

Các hàm liên quan

partial_sort	Sắp xếp một phần của 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
copy	Sao chép các phần tử từ một phạm vi nguồn sang một phạm vi đích khác
remove_copy_if	Sao chép các phần tử từ một phạm vi nguồn sang một phạm vi đích khác