Geek asks and answers

STL algorithm for equivalent ranges

By definition, the std :: equal algorithm accepts only one "last" iterator. Many posts on stackoverflow indicate that in order to perform equivalence between two ranges, you must first verify that the ranges are the same size in addition to calling std :: equal. If random access iterators are available, this does not add any significant overhead. However, it seems that without random access iterators, the first code fragment, implemented only with existing STL algorithms, will be slower than the second code fragment, which is a user-defined “equivalent” algorithm (which is not part of the STL). My question is, is fragment 2 more efficient than any algorithm encoded using existing STL algorithms only? If yes,then why is this algorithm not part of the STL?

Fragment 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 );
}

Fragment 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;
}

Note. I did not test it, but I would very much doubt that the compiler would optimize fragment 1 so that it would generate code with the same performance as fragment 2.

To be complete, the following code snippet is close to useless, as it will not work if the size of the range is not equal:

template <typename IITR1, typename IITR2>
bool equivalent(IITR1 first1, IITR1 last1, IITR2 first2, IITR2 last2)
{
    return equal(first1, last1, first2) && equal(first2, last2, first1);
}
+5
source share
2 answers

It is likely that when the STL standardized the situation where the two ranges are non-random access, but different lengths were not taken into account; and looking at the defect reports, since it did not seem to be such a popular fix. As you already noted, it’s quite easy to write your own version that will fix it.

, (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));
+3

, .

. , , , equal , ; , , , distance .

, , , . , .

, , , - .

+1

More articles:


All Articles