Tại sao không có tiêu chuẩn :: inplace_merge_unique?

Question

Tôi đã thử tìm kiếm một thuật toán có thể làm những gì std::inplace_merge theo sau là std::unique sẽ thực hiện. Có vẻ hiệu quả hơn khi thực hiện nó trong 1 lần vượt qua trong 2. Không thể tìm thấy nó trong thư viện chuẩn hoặc bằng cách giải quyết.

1. Vì vậy, có triển khai ở đâu đó để tăng cường dưới tên gọi khác không?
2. Thuật toán như vậy có thể (theo nghĩa là nó có độ phức tạp tương tự như bảo đảm như inplace_merge bình thường) không?

Answer 1

Nó không hoạt động tại chỗ, nhưng giả sử rằng không có phạm vi nào chứa trùng lặp trước, std::set_union sẽ tìm thấy kết quả tương tự như hợp nhất theo sau là duy nhất.

Answer 2

Có nhiều thuật toán thú vị bị thiếu trong phần thuật toán. Việc đệ trình ban đầu của STL không đầy đủ từ quan điểm của Stepanov và một số thuật toán thậm chí còn bị loại bỏ. Các proposal bởi Alexander Stepanov và Meng Lee dường như không bao gồm một thuật toán inplace_merge_unique() hoặc bất kỳ biến thể nào của chúng.

Một trong những lý do tiềm năng tại sao không có thuật toán như vậy là không rõ yếu tố nào nên được loại bỏ: vì so sánh chỉ là thứ tự yếu nghiêm ngặt, lựa chọn yếu tố quan trọng. Một cách tiếp cận để triển khai inplace_merge_unique() là

1. để xóa bất kỳ phần tử nào trùng lặp khỏi phạm vi thứ hai.
2. Sử dụng inplace_merge() để thực hiện hợp nhất thực tế.

Vị từ để std::remove_if() sẽ theo dõi vị trí hiện tại trong phần đầu tiên của chuỗi được hợp nhất. Mã bên dưới không được kiểm tra nhưng một số thông tin như vậy sẽ hoạt động:

template <typename BiDirIt, typename Comp> 
BiDirIt inplace_merge_unique(BiDirIt begin, BiDirIt middle, BiDirIt end, Comp comp) { 
    using reference = typename std::iterator_traits<BiDirIt>::reference; 
    BiDirIt result = std::remove_if(middle, end, [=](reference other) mutable -> bool { 
      begin = std::find_if(begin, middle, [=](reference arg)->bool { 
        return !comp(arg, other); 
       }); 
      return begin != middle && !comp(other, *begin); 
     }); 
    std::inplace_merge(begin, middle, result, comp); 
    return result; 
}