Почему нет std:: inplace_merge_unique?

Я попытался найти алгоритм, который бы сделал то, что std::inplace_merge а затем std::unique. Кажется более эффективным сделать это за 1 проход, чем в 2. Не удалось найти его в стандартной библиотеке или ооглинге.

  • Так может ли быть реализация где-то в boost под другим именем?
  • Возможно ли, что такой алгоритм (в том смысле, что он имеет такую ​​же сложность, что и обычный inplace_merge)?

Ответы

Ответ 1

Он не работает на месте, но если предположить, что ни один диапазон не содержит дубликатов заранее, std::set_union найдет тот же результат, что и слияние, за которым следует уникальный.

Ответ 2

В разделе алгоритмов отсутствует много интересных алгоритмов. Оригинальное представление STL было неполным из взгляда Степанова, и некоторые алгоритмы были даже удалены. Предложение Александра Степанова и Мэн Ли не включает в себя алгоритм inplace_merge_unique() или любые его варианты.

Одна из потенциальных причин, почему нет такого алгоритма, заключается в том, что не ясно, какой из элементов следует отбросить: поскольку сравнение является лишь строгим слабым порядком, выбор элемента имеет значение. Один из подходов к реализации inplace_merge_unique() -

  • Используйте std::remove_if() для удаления любого элемента, который является дубликатом из второго диапазона.
  • Используйте inplace_merge() для выполнения фактического слияния.

Предикат std::remove_if() будет отслеживать текущую позицию в первой части последовательности, которая должна быть объединена. Код ниже не протестирован, но что-то вроде этого должно работать:

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