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?

Checking for size of a list is not constant time - you have to iterate the list. — , Mar 16 '10 at 18:33
@Neil: It might have constant time. The Microsoft implementation has a constant time `size()`. In the container requirements, the C++ standard only says `size()` _should_ have constant time complexity. — James McNellis, Mar 16 '10 at 18:52
See http://stackoverflow.com/questions/228908/is-listsize-really-on for a discussion of why `std::list()` might or might not have constant complexity. — Michael Burr, Mar 16 '10 at 19:11
As it turns out, the latest C++0x draft requires that `size()` have constant time complexity (that change to the container requirements was made in N3000). @Michael: Thanks for the link. — James McNellis, Mar 16 '10 at 19:19
Well, list is my least favourite container, so I don't feel too bad on not having kept up with its interface :-) — , Mar 16 '10 at 19:26
It seems like an implication of this discussion is that if the second list is shorter than the first, that std:equal will cause us to walk off the end of the list and SEGV. If that is the case, and you don't know the length of the second list, how can this method possibly be safe to use? — , Dec 18 '12 at 00:53

score 12 · Accepted Answer · answered Mar 16 '10 at 18:33

12

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.

answered Mar 16 '10 at 18:33

Konrad Rudolph

530,221
131
937
1,214

You are right, Konrad. I forgot that I was passing the iterator to the std::equal. Having said that, is there something that does something like: equal(lst1, lst2) provided by STL? – sivabudh Mar 16 '10 at 18:35
2

@ShaChris32: yes, you can compare two lists (or in general two standard containers of the same type) with `==`. – Mike Seymour Mar 16 '10 at 18:43
This is what I hate most about STL. Why does it need to work on iterators all the time. It it was designed to work with containers there would not have been these subtle issues to worry about. – Jeroen Dirks Mar 16 '10 at 18:59
3

That it works with iterators and not containers is in my opinion one of the STL's greatest strengths. – John Dibling Mar 16 '10 at 19:04
2

@James: The idea is to split the algorithm from the container, and iterators do that well. That said, Alexandrescu had a talk fairly recently called "Iterators Must Go" that recommends ranges instead of iterators. I agree with him. – GManNickG Mar 16 '10 at 19:08
@James: An iterator range is more flexible than a container. It can refer to just part of a container or (with a bit of work) can span more than one container. It doesn't need a container at all (for example, iterators from I/O streams). You can also treat raw pointers as iterators, but you can't treat a raw array as a container. – Mike Seymour Mar 16 '10 at 19:13
@Konrad: yes, that's one of the Container requirements. – Mike Seymour Mar 16 '10 at 19:14
1

@Mike: If I'm not mistaken, both a container **and** an iterator range would qualify as a Range (you can make an iterator_range object that stores the two iterators and makes them accessible through the same `begin()` and `end()` method). It is used in boost, and it is very convenient. – UncleBens Mar 16 '10 at 20:12
@Mike iterators may be more 'flexible' but it leaves you with warts like std::remove that do not resize the container and leave garbage at the end. The fact that it is based on iterators may be nice to algorithm implementers that need only one implementation for use with many containers. But for application developers you really do not change container types very often and as long as the containers have similar names for adding inserting, removing, searching, comparing even that would not matter. – Jeroen Dirks Mar 17 '10 at 13:50

score 4 · Answer 2 · answered Mar 16 '10 at 18:46

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.

score 3 · Answer 3 · answered Mar 16 '10 at 18:35

3

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

answered Mar 16 '10 at 18:35

eduffy

39,140
13
95
92

No. There is no portable way of knowing the size of the second container. This information is simply not available to `equals`, neither directly nor indirectly. – Konrad Rudolph Mar 16 '10 at 18:36
@Konrad: Of course there is: just iterate both lists from begin to end & count the number of elements. – John Dibling Mar 16 '10 at 19:06
@John: How did you get the end iterator for list2? – Bill Mar 16 '10 at 19:08
I didn't of course. Don't know what I was thinking of there. – John Dibling Mar 16 '10 at 19:11
The second range doesn't even need to have a size. E.g you have an input iterator that produces random numbers, and you want to compare a bunch of values in say a list against a sequence of those (don't ask me why). – UncleBens Mar 16 '10 at 21:43

score 2 · Answer 4 · answered Mar 16 '10 at 18:35

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.

score 0 · Answer 5 · answered Nov 08 '16 at 01:25

0

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.

answered Nov 08 '16 at 01:25

dhaffey

1,354
9
12

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

5 Answers5

Linked