C ++ std :: equal - justification for the lack of testing for two ranges having the same size?

Question

I just wrote code to test the behavior of std :: equal and left in surprise:

int main() { try { std::list<int> lst1; std::list<int> lst2; if(!std::equal(lst1.begin(), lst1.end(), lst2.begin())) throw std::logic_error("Error: 2 empty lists should always be equal"); lst2.push_back(5); if(std::equal(lst1.begin(), lst1.end(), lst2.begin())) throw std::logic_error("Error: comparing 2 lists where one is not empty should not be equal"); } catch(std::exception& e) { std::cerr << e.what(); } } 

Result (surprise for me):

 Error: comparing 2 lists where one is not empty should not be equal 

Observation: why does this std :: equal not check first whether 2 containers have the same size() ? Was there a legitimate reason?

Answer 1

Observation: why doesn't std :: equal first check if 2 containers have the same size ()? Was there a legitimate reason?

How? You don't skip containers into a function, you pass iterators . The function has no way of knowing the size of the second container. All he can do is assume that the user has walked in two valid container ranges (i.e. that the second range is correctly specified as a half-open interval [ lst2.begin() , lst2.begin() - lst1.begin() + lst1.end() [) and act accordingly.

Answer 2

You can always write your own version of peer that effectively does what you want:

 template <class InputIterator1, class InputIterator2> bool equalx(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) { while ((first1 != last1) && (first2 != last2)) { if (*first1 != *first2) // or: if (!pred(*first1,*first2)), for pred version return false; ++first1; ++first2; } return (first1 == last1) && (first2 == last2); } 

To ensure that both ranges have the same number of elements, the signature must include an end to the second range.

Answer 3

Since size checking can be an O(n) operation.

Answer 4

This gives you the correct answer - you told him to check if the two containers were equal in the range from lst1.begin() to lst1.end() . You are still comparing two empty lists to equal() . If you change the comparison code from lst2.begin() to lst2.end() , you will get what you expect.

Answer 5

C ++ 14 added an overload with four arguments, similar to the one in R Samuel Klatchko's answer. And at least the two STL implementations I tested (libC ++ and MSVC) implement the obvious remote check optimization for random access iterators.