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

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!

CodePudding user response：

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.

CodePudding user response：

All of the standard algorithms related to ordering of elements use only the < operator, and never the <=, >, >=, ==, or != operators.

One thing this means is that a class type which should support ordering only needs to define operator<, and the others might not be needed.

But another reason is that most of the sort/order algorithms do NOT assume that the objects are "completely ordered", meaning that exactly one of a<b or a==b or a>b is always true. Instead, they assume they have a strict weak ordering, where pairs of elements with !(a<b) && !(b<a) true form equivalence classes but are not necessarily equal.

For an example, a simple class for a case-insensitive ASCII string:

#include <string>
#include <strings.h>
class ci_string {
public:
    explicit ci_string(const char* s) : m_str(s) {}
    const char* c_str() const { return m_str.c_str(); }

    friend bool operator<(const ci_string& s1, const ci_string& s2)
    { return strcasecmp(s1.c_str(), s2.c_str()) < 0; }
    friend bool operator>(const ci_string& s1, const ci_string& s2)
    { return s2 < s1; }
    friend bool operator==(const ci_string& s1, const ci_string& s2)
    { return s1.m_str == s2.m_str; }
    friend bool operator!=(const ci_string& s1, const ci_string& s2)
    { return !(s1 == s2); }
private:
    std::string m_str;
};

(Not suitable for multibyte encodings or non-ASCII letters.)

Now ci_string("HELLO"), ci_string("HeLLo"), and ci_string("hello") are all equivalent but not equal. And for code like:

std::vector<ci_string> v1{
    ci_string("alpha"), ci_string("beta"), ci_string("gamma"),
    ci_string("delta"), ci_string("epsilon")};
std::vector<ci_string> v2{ci_string("BETA"), ci_string("Delta")};
bool c = std::includes(v1.begin(), v1.end(), v2.begin(), v2.end());

the implementation using only < will return true, but one using == would probably return false. (Whether this result really makes sense for "includes" is an interesting question, but that's how it's defined.)