Добавить в алгоритмы merge_unique

[tomilov]

<Описание вашей идеи> Не хватает функции, которая за один проход сливает две неубывающих последовательности в строго возрастающую

<Примеры, где ваша идея будет полезна. Чем больше примеров и чем большую аудиторию они охватывают - тем лучше> Базовый алгоритм

<Код c реализацией вашей идеи, если есть>

template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator merge_unique(InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, InputIterator2 last2,
                            OutputIterator result)
{
    while (first1 != last1 && first2 != last2)
    {
        if (*first1 < *first2)
        {
            *result = *first1;
            while (++first1 != last1 && !(*std::prev(first1) < *first1));
        }
        else if (*first2 < *first1)
        {
            *result = *first2;
            while (++first2 != last2 && !(*std::prev(first2) < *first2));
        }
        else // *first1 == *first2
        {
            *result = *first1;
            while (++first1 != last1 && !(*std::prev(first1) < *first1));
            while (++first2 != last2 && !(*std::prev(first2) < *first2));
        }
        ++result;
    }
    while (first1 != last1) {
        *result++ = *first1;
        while (++first1 != last1 && !(*std::prev(first1) < *first1));
    }
    while (first2 != last2) {
        *result++ = *first2;
        while (++first2 != last2 && !(*std::prev(first2) < *first2));
    }
    return result;
}

[tomilov]

Да, здесь не InputIterator-ы, а Bidirectional, но можно и на Input переписать, наверное.

template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator merge_unique(InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, InputIterator2 last2,
                            OutputIterator result)
{
    while (first1 != last1 && first2 != last2) {
        auto&& value1 = *first1;
        auto&& value2 = *first2;
        if (value1 < value2) {
            while (++first1 != last1 && !(value1 < *first1));
            *result++ = std::move(value1);
        } else if (value2 < value1) {
            while (++first2 != last2 && !(value2 < *first2));
            *result++ = std::move(value2);
        } else {
            while (++first1 != last1 && !(value1 < *first1));
            while (++first2 != last2 && !(value2 < *first2));
            *result++ = std::move(value1);
        }
    }
    while (first1 != last1) {
        auto&& value1 = *first1;
        while (++first1 != last1 && !(value1 < *first1));
        *result++ = std::move(value1);
    }
    while (first2 != last2) {
        auto&& value2 = *first2;
        while (++first2 != last2 && !(value2 < *first2));
        *result++ = std::move(value2);
    }
    return result;
}