C++ std::equal -- rationale behind not testing for the 2 ranges having equal size?

Question

I just wrote some code to test the behavior of std::equal, and came away surprised:

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

The output (a surprise to me):

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

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

Answer 1

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

How? You do do not pass containers to the function, you pass in iterators. The function has no way of knowing the size of the second container. All it can do is assume bona fide that the user passed in two valid container ranges (i.e. that the second range is correctly specified as the half-open interval [lst2.begin(), lst2.begin() - lst1.begin() + lst1.end()[) and act accordingly.

Answer 2

It's giving you the right answer - you told it to check if the two containers were equal in the range lst1.begin() to lst1.end(). You're still comparing two empty lists as far as equal() is concerned. If you change the code to compare from lst2.begin() to lst2.end(), you'll get what you expected.

Answer 3

Because checking the size may be an O(n) operation.

Answer 4

You can always write your own version of equal that does effectively 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);
}

In order to make sure both ranges have the same number of elements, the signature must include an end to the second range.