等效范围的STL算法

Question

根据定义,std :: equal算法只需要一个'last'迭代器.stackoverflow上的许多帖子表明,要在两个范围之间执行等效,除了调用std :: equal之外,必须首先检查范围是否具有相同的大小.如果随机访问迭代器可用,则不会添加任何材料开销.但是,似乎没有随机访问迭代器,仅使用现有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

第一个仅适用于前向迭代器，不适用于一般的输入迭代器。

性能将取决于迭代器类型。第一个对于随机访问迭代器来说可能更快，因为 的主循环equal比第二个实现的主循环更简单；distance但如果必须迭代整个范围，可能会更慢。

为了支持输入迭代器，并在所有情况下获得最佳性能，您可能需要针对不同的迭代器类别进行不同的专门化。我会从第二个开始，只有当你发现它还不够时才专门研究。

我不知道为什么它不在标准库中，但你不能指望任何库包含所有可能的算法。