Why does std::inlcudes use the less than operator in the condition rather than the equality operator?

I have this implementation of the algorithm std::includes from https://en.cppreference.com/w/cpp/algorithm/includes

template<class InputIt1, class InputIt2>
bool includes(InputIt1 first1, InputIt1 last1,
              InputIt2 first2, InputIt2 last2)
{
    for (; first2 != last2; ++first1)
    {
        if (first1 == last1 || *first2 < *first1)
            return false;
        if ( !(*first1 < *first2) )
            ++first2;
    }
    return true;
}
  • It works just fine however I wonder why in the second if statement inside the loop uses less than operator < rather than equality operator ==?

  • Here is my similar implementation:

    template<class InputIt1, class InputIt2>
    bool including(InputIt1 first1, InputIt1 last1,
                InputIt2 first2, InputIt2 last2){
    
       while (first2 != last2){
          if (first1 == last1 || *first2 < *first1)
             return false;
          if ( *first1 == *first2 )
             ++first2;
          ++first1;
       }
        return true;
    }
    
    
    int main(){
       std::vector<int> v{1, 5, 7, 23, 24, 57, 77};
      //  std::sort(v.begin(), v.end());
        int a[]{7, 24};
        std::cout << including(v.begin(), v.end(), a, a + 2) << 'n'; // 1
        std::cout << std::includes(v.begin(), v.end(), a, a + 2) << 'n'; // 1
    
    }
    
  • So I’ve concluded this:

  • The first condition: *first2 < *first1 -> returns false.

  • The second condition: !(*first1 < *firs2) -> *first1 >= *first2

So *first1 > *first2 causes the algorithm return false and *first1 >= *first2 causes firsts2 be incremented so the only condition first2 gets incremented is when *first1 == *first2 So why using the less than < along with negation operator ! operators rather than using directly equals operator == like in my implementation?

  • Is that only for some sort of readability and compatibility sake?
  • Is my analysis correct? Thank you!

Answer

The algorithm is working on a sorted range. You need a < relation to sort a range of elements, but not necessarily a == relation, hence using < poses less restrictions and is more generic.


Also consider that most algorithms and containers use < rather than == to compare elements. See for example std::map:

Everywhere the standard library uses the Compare requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a).

Two keys in a map are considered equivalent (not equal!) when !comp(a,b) && !comp(b,a). Most of the time this is the same as a == b, but not necessarily.