能否为InputIterator实现符合语义的std::merge_unique？

我实现了merge_unique，语义如下：合并两个非降序的有序范围，仅保留每个等价元素的第一个（若两个范围均存在等价元素，则取第一个范围的）。该功能等效于先执行std::merge再执行std::unique，但只需一次遍历。

template<typename ForwardIterator1, typename ForwardIterator2, typename OutputIterator>
OutputIterator merge_unique(ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2,
                            OutputIterator result)
{
    using FirstTypeRef = typename std::iterator_traits<ForwardIterator1>::reference;
    using SecondTypeRef = typename std::iterator_traits<ForwardIterator2>::reference;
    while (first1 != last1 && first2 != last2) {
        FirstTypeRef&& value1 = *first1;
        SecondTypeRef&& value2 = *first2;
        if (value2 < value1) {
            while (++first2 != last2 && !(value2 < *first2));
            *result++ = std::forward<SecondTypeRef>(value2);
        } else {
            while (++first1 != last1 && !(value1 < *first1));
            if (!(value1 < value2)) {
                while (++first2 != last2 && !(value2 < *first2));
            }
            *result++ = std::forward<FirstTypeRef>(value1);
        }
    }
    while (first1 != last1) {
        FirstTypeRef&& value1 = *first1;
        while (++first1 != last1 && !(value1 < *first1));
        *result++ = std::forward<FirstTypeRef>(value1);
    }
    while (first2 != last2) {
        SecondTypeRef&& value2 = *first2;
        while (++first2 != last2 && !(value2 < *first2));
        *result++ = std::forward<SecondTypeRef>(value2);
    }
    return result;
}

当前实现对ForwardIterator及以上类别的迭代器有效，但无法适配InputIterator——因为InputIterator不提供“多遍保证”，只能单向遍历且元素只能被访问一次。

核心问题：理论上能否为InputIterator实现merge_unique？ #

答案是不能，原因如下：

• InputIterator的特性限制：InputIterator只能单次读取元素，读取后迭代器会前进，无法回头重新读取之前的元素。而merge_unique需要判断当前元素是否和后续元素等价，还要处理两个序列中等价元素的优先级（取第一个序列的）。比如当读取到两个序列的等价元素时，需要跳过第二个序列中所有后续等价副本，但InputIterator读取第一个等价元素后就已前进，无法确认后续元素状态，除非缓存所有元素，但这会打破“一次遍历”的语义，且带来O(n)的空间成本。

• 等价元素处理依赖预读：原实现通过循环预读跳过当前元素的所有等价副本，这是InputIterator做不到的——一旦迭代器前进，之前的元素无法再访问，且部分InputIterator（比如输入流迭代器）读取后数据会直接消失，无法重复获取。

• 替代方案不满足原生需求：如果强行适配，只能先把两个序列的元素全部缓存到内存（比如存入vector），再用ForwardIterator版本处理，但这已经是间接转换，并非针对InputIterator的原生实现，违背了原设计的“一次遍历”初衷。

总结来说，InputIterator的单向、单次访问特性，决定了它无法满足merge_unique所需的预读等价元素、处理跨序列等价优先级的需求，理论上不存在原生的、符合一次遍历语义的InputIterator版本实现。

内容的提问来源于stack exchange，提问作者Tomilov Anatoliy