c++ - 等效范围的 STL 算法

Question

根据定义，std::equal 算法仅采用一个“最后”迭代器。 stackoverflow 上的许多帖子表明，要在两个范围之间执行等价，除了调用 std::equal 之外，还必须首先检查范围是否具有相同的大小。如果随机访问迭代器可用，这不会增加任何 Material 开销。但是，似乎没有随机访问迭代器，第一个代码片段(仅使用现有的 STL 算法实现)将比第二个代码片段慢，第二个代码片段表示自定义的“等效”算法(不是 STL 的一部分)。我的问题是，片段 2 是否比任何仅使用现有 STL 算法编码的算法更有效？如果是，为什么这个算法不是 STL 的一部分？

片段 1:

template <typename IITR1, typename IITR2>
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2)
{
    return distance(first1, last1) == distance(first2, last2) &&
        equal( first1, last1, first2 );
}

片段 2:

template <typename IITR1, typename IITR2>
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2)
{
    while ( first1 != last1 && first2 != last2 ) {
       if (!(*first1 == *first2)) return false;
       ++first1; ++first2;
    }
    return first1 == last1 && first2 == last2;
}

注意:我没有检查过，但我非常怀疑编译器是否会优化片段 1，使其生成的代码与片段 2 产生的性能相同。

为了完整起见，以下代码片段几乎毫无用处，因为如果范围大小不相等，它将失败:

template <typename IITR1, typename IITR2>
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2)
{
    return equal(first1, last1, first2) && equal(first2, last2, first1);
}

Answer 1

很可能在STL标准化的时候没有考虑到两个range是非随机访问但长度不同的情况；并查看缺陷报告，因为它似乎并不是一个非常需要的修复程序。正如您所指出的，编写自己的正确版本非常容易。

改造修复的一个问题是决定四参数调用是双范围调用 (it1, it1_end, it2, it2_end) 还是 (it1, it1_end, it2, 谓词) 版本。区分技术(SFINAE，enable_if)最近才可用。

注意 Boost.Range 有一个正确的实现；见http://www.boost.org/doc/libs/1_51_0/boost/range/algorithm/equal.hpp为实现。它还会检测两种迭代器类型何时为随机访问，并在长度不同的情况下调用 distance 进行短路。

#include <boost/range/algorithm.hpp>

boost::equal(boost::make_iterator_range(first1, last1),
    boost::make_iterator_range(first2, last2));