等效范围的STL算法

根据定义，std :: equal算法只需要一个'last'迭代器。在stackoverflow上的许多帖子指出，为了执行两个范围之间的等价性，除了调用std :: equal之外，还必须首先检查范围是否具有相同的大小。如果随机访问迭代器可用，则不会添加任何材料开销。然而，似乎没有随机访问迭代器，第一个代码片段只用现有的STL算法实现，将比第二个代码片段慢，后者代表一个自定义“等效”算法（不是STL的一部分）。我的问题是，片段2比仅使用现有STL算法编码的算法更有效吗？如果是这样，为什么这个算法不是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); 
}

来源

2012-09-03 MarkB

问题是我不知道范围长度是否相同，并检查它们是否符合成本运行时间。 – MarkB

没关系，我没有意识到那些是* alternatives *。片段2看起来不错，并且像最好的解决方案。 –

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

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

为了支持输入迭代器，并在所有情况下获得最佳性能，对于不同的迭代器类别可能需要不同的专业化。我会从第二部分开始，只有在发现不足时才专门研究。

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

来源

2012-09-03 15:05:12

是啊...我有一个坏习惯，认为前向迭代器是输入迭代器，因为我从来没有直接处理输入迭代器。 :) – MarkB

当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-03 15:14:33 ecatmur

等效范围的STL算法

回答

相关问题