5

根据定义，std::equal 算法只需要一个“最后一个”迭代器。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);
}
4

2 回答 2

3

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

改造修复的一个问题是确定四参数调用是两个范围调用(it1, it1_end, it2, it2_end)还是一个(it1, it1_end, it2, predicate)版本。区分技术 (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));
于 2012-09-03T15:14:33.390 回答
1

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

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

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

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

于 2012-09-03T15:05:12.920 回答