Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a safe alternative to std::equal?

Tags:

std::equal() is unsafe because the function cannot know whether it will overrun the length of the second container to be compared. That is:

std::vector< int > v( 100 ); std::vector< int > w( 10 ); bool same = std::equal( v.begin(), v.end(), w.begin() ); 

...will result in a buffer overrun for w.

Naturally we can test for these things (v.size() == w.size()), but compilers like Visual Studio 2010 still report the function itself as unsafe. And indeed it is unsafe in some fundamental sense: a team of programmers of varying levels of experience will eventually forget to compare sizes.

A safe alternative is easy to implement.

template< typename Iter1, typename Iter2 > bool equal_safe( Iter1 begin1, Iter1 end1, Iter2 begin2, Iter2 end2 ) {     while( begin1 != end1 && begin2 != end2 )     {         if( *begin1 != *begin2 )         {             return false;         }         ++begin1;         ++begin2;     }     return begin1 == end1 && begin2 == end2; } 

But is there a safe alternative in the standard library?

like image 614
OldPeculier Avatar asked May 01 '13 20:05

OldPeculier


People also ask

What is std :: equal?

std::equalCompares the elements in the range [first1,last1) with those in the range beginning at first2 , and returns true if all of the elements in both ranges match. The elements are compared using operator== (or pred , in version (2)). The behavior of this function template is equivalent to: 1.

What can we use instead of vector in C?

A block and realloc() is all well and good but you really need a data structure that features like a linked list.

Is std :: find slow?

std::equal_range on bidirectional iterators is extremely slow, because it has to walk step by step through the range. The std::set. find method, on the other hand, uses the tree structure of std::set to find the element really fast. It can, basically, get midpoints of a range really fast.


1 Answers

In C++14, the standard library will contain a version of std::equal that takes two pairs of iterators, similar to your safe_equal. Same for std::mismatch and std::is_permutation.

like image 172
Marshall Clow Avatar answered Oct 21 '22 12:10

Marshall Clow