Dlaczego nie ma std :: inplace_merge_unique?

Question

Próbowałem szukać algorytmu, który zrobiłby to, co zrobiłby std::inplace_merge , a następnie std::unique. Wydaje się, że jest to wydajniejsze w 1 przebiegu niż w 2. Nie można go znaleźć w standardowej bibliotece lub przez oogling.

1. Czy jest tam implementacja gdzieś w boostu pod inną nazwą?
2. Czy taki algorytm jest możliwy (w tym sensie, że ma takie same gwarancje złożoności jak normalne inplace_merge)?

Answer 1

To nie działa w miejscu, ale przy założeniu, że żadna oferta zawiera duplikaty wcześniej, std::set_union znajdzie taki sam wynik jak scaleniu następuje niepowtarzalny.

Answer 2

W sekcji algorytmów brakuje wielu interesujących algorytmów. Oryginalne zgłoszenie STL było niepełne ze stanowiska Stepanowa, a niektóre algorytmy zostały nawet usunięte. The proposal autorstwa Alexandra Stiepanowa i Menga Lee wydaje się nie zawierać algorytmu inplace_merge_unique() lub jakiejkolwiek jego odmiany.

Jednym z potencjalnych powodów, dla których nie ma takiego algorytmu, jest to, że nie jest jasne, który element powinien zostać usunięty: ponieważ porównanie jest tylko ściśle słabym porządkiem, wybór elementu ma znaczenie. Jednym ze sposobów realizacji inplace_merge_unique() jest

1. Zastosowanie std::remove_if() do usunięcia elementu, który jest kopią z drugiego zakresu.
2. Użyj funkcji inplace_merge(), aby wykonać faktyczne scalenie.

Predykat na std::remove_if() śledziłby bieżącą pozycję w pierwszej części sekwencji, która ma zostać scalona. Poniższy kod nie jest testowany, ale coś takiego powinno zadziałać:

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; 
}