CODEWITHSUNDEEP
c++stl
sivabudh
sivabudh

Reputation: 32635

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

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?

Upvotes: 8

Views: 3840

Answers (5)

dhaffey
dhaffey

Reputation: 1374

C++14 added a four-argument overload much like the one in R Samuel Klatchko's answer. And at least the two STL implementations I checked (libc++ and MSVC) implement the obvious distance-check-up-front optimization for random access iterators.

Upvotes: 0

R Samuel Klatchko
R Samuel Klatchko

Reputation: 76541

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.

Upvotes: 4

eduffy
eduffy

Reputation: 40224

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

Upvotes: 3

Carl Norum
Carl Norum

Reputation: 224944

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.

Upvotes: 2

Konrad Rudolph
Konrad Rudolph

Reputation: 545598

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.

Upvotes: 12

Related Questions