Why is there no std::inplace_merge_unique?

Question

I tried looking for an algorithm that would do what std::inplace_merge followed by std::unique would do. Seems more efficient to do it in 1 pass than in 2. Could not find it in standard library or by oogling.

1. So is there implementation somewhere in boost under different name maybe?
2. Is such algorithn possible (in a sense that it has same complexity guarantees as normal inplace_merge)?

Answer 1

It doesn't operate in-place, but assuming that neither range contains duplicates beforehand, std::set_union will find the same result as merge followed by unique.

Answer 2

There are many interesting algorithms missing from the algorithms section. The original submission of STL was incomplete from Stepanov's view and some algorithms were even removed. The proposal by Alexander Stepanov and Meng Lee doesn't seem to include an algorithm inplace_merge_unique() or any variation thereof.

One of the potential reasons why there is no such algorithm is that it isn't clear which of the element should be dropped: since the comparison is only a strict weak ordering, the choice of element matters. One approach to implement inplace_merge_unique() is to

1. Use std::remove_if() to remove any element which is a duplicate from the second range.
2. Use inplace_merge() to do the actual merge.

The predicate to std::remove_if() would track the current position in the first part of the sequence to be merged. The code below isn't tested but something like that should work:

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