142

This is the code from the C++ standard library remove code. Why is inequality tested as if (!(*first == val)) instead of if (*first != val)?

 template <class ForwardIterator, class T>
      ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)
 {
     ForwardIterator result = first;
     while (first!=last) {
         if (!(*first == val)) {
             *result = *first;
             ++result;
         }
         ++first;
     }
     return result;
 }
4
  • 2
    @BeyelerStudios is probably correct. It's also common when implementing operator!=. Just use the operator== implementation: bool operator!=(const Foo& other) { return !(*this == other); }
    – simon
    Sep 29, 2015 at 16:55
  • 1
    actually I correct my statement: the references mention removes all elements that are equal to value so operator== is kind of expected to be used here... Sep 29, 2015 at 16:58
  • Oh, and there should also be a const in the example in my previous comment, but you get the point. (Too late to edit it)
    – simon
    Sep 29, 2015 at 17:04
  • The reason for this is related to another question (that can basically answered with "No, not necessarily"), and the concept of being EqualityComparable that Hurkyl mentioned in his answer.
    – Marco13
    Jan 1, 2018 at 1:53

6 Answers 6

144

Because this means the only requirement on T is to implement an operator==. You could require T to have an operator!= but the general idea here is that you should put as little burden on the user of the template as possible and other templates do need operator==.

9
  • 14
    template <class T> inline bool operator!=<T a, T b> { return !(a == b); }
    – Joshua
    Sep 29, 2015 at 21:34
  • 8
    Would there be any scenario where a compiler wouldn't be able to interchange all instances of =! to !(==)? Why would this not already be the default action for the compiler to take? Sep 30, 2015 at 1:11
  • 20
    @AidanGomez For better or worse you can overload the operators to do whatever you want. It doesn't have to make sense or be consistent.
    – Neil Kirk
    Sep 30, 2015 at 2:20
  • 10
    x != y is not defined to be the same as !(x == y). What if these operators return the parse tree of an embedded DSL? Sep 30, 2015 at 8:29
  • 7
    @Joshua That breaks badly if attempting to use SFINAE to detect whether != is supported (would incorrectly return true -- even if operator== isn't supported!). I'm also worried it will cause some uses of != to become ambiguous.
    – user743382
    Sep 30, 2015 at 8:29
36

Most functions in STL work only with operator< or operator==. This requires the user only to implement these two operators (or sometimes at least one of them). For example std::set uses operator< (more precisely std::less which invokes operator< by default) and not operator> to manage ordering. The remove template in your example is a similar case - it uses only operator== and not operator!= so the operator!= doesn't need to be defined.

4
  • 2
    Functions do not use operator< directly but instead use std::less, which in turn defaults to operator<. Sep 29, 2015 at 17:30
  • 1
    Actually, it seems that standard algorithm functions, unlike e.g. std::set, indeed do use operator< directly. Strange... Sep 29, 2015 at 17:51
  • 1
    These functions doesn't use std::equal_to, they use operator== as noted in the question. The situation with std::less is similar. Well, maybe std::set isn't the best example. Sep 29, 2015 at 17:59
  • 2
    @ChristianHackl, std::equal_to and std::less are used as default template parameters where the comparator is taken as parameter. operator== and operator< are used directly where the type is required to satisfy equality comparable and strict weak ordering respectively, e.g. iterators and random access iterators.
    – Jan Hudec
    Sep 30, 2015 at 6:10
28

This is the code from the C++ standard library remove code.

Wrong. It's not the C++ standard library remove code. It's one possible internal implementation of the C++ standard library remove function. The C++ standard does not prescribe actual code; it prescibes function prototypes and required behaviours.

In other words: From a strict language point of view, the code you are seeing does not exist. It may be from some header file that comes with your compiler's standard-library implementation. Note that the C++ standard does not even require those header files to exist. Files are just a convenient way for compiler implementors to meet the requirements for a line like #include <algorithm> (i.e. making std::remove and other functions available).

Why is inequality tested as if (!(*first == val)) instead of if (*first != val) ?

Because only operator== is required by the function.

When it comes to operator overloading for custom types, the language allows you to do all kinds of weird things. You could very well create a class which has an overloaded operator== but no overloaded operator!=. Or even worse: You could overload operator!= but have it do completely unrelated things.

Consider this example:

#include <algorithm>
#include <vector>

struct Example
{
    int i;

    Example() : i(0) {}

    bool operator==(Example const& other) const
    {
        return i == other.i;
    }

    bool operator!=(Example const& other) const
    {
        return i == 5; // weird, but nothing stops you
                       // from doing so
    }

};

int main()
{
  std::vector<Example> v(10);
  // ...
  auto it = std::remove(v.begin(), v.end(), Example());
  // ...
}

If std::remove used operator!=, then the result would be quite different.

8
  • 1
    Another thing to consider is that it may be possible for both a==b and a!=b to return false. While it may not always be clear whether such a situation would be more meaningfully regarded as "equal" or "not-equal", a function which defines equality solely in terms of the "==" operator must regard them as "not-equal", regardless of which behavior would make more sense [if I had my druthers, all types would be expected to make boolean-yielding "==" and "!=" operators behave consistently, but the fact that IEEE-754 mandates broken equality operators would make such expectation difficult].
    – supercat
    Sep 29, 2015 at 17:45
  • 18
    "From a strict language point of view, the code you are seeing does not exist." -- when a point of view says something doesn't exist, but you're actually looking at that thing, then the point of view is wrong. In fact the standard doesn't say the code doesn't exist, it merely doesn't say it does exist :-) Sep 29, 2015 at 17:56
  • @SteveJessop: You can replace the expression "from a strict language point of view" with something like "strictly, on the language level". The point is that the code posted by the OP is not the concern of the language standard. Sep 29, 2015 at 18:16
  • 2
    @supercat: IEEE-754 does make == and != behave consistently, although I've always thought that all six relations should evaluate to false when at least one operand is NaN.
    – Ben Voigt
    Sep 29, 2015 at 18:30
  • @BenVoigt: Ah, that's right. It makes the two operators behave in the same broken fashion such that they're consistent with each other, but still manage to violate all the other normal axioms associated with equivalence (e.g. they uphold neither a==a, nor the guarantee that operations performed on equal values will yield equal results).
    – supercat
    Sep 29, 2015 at 18:59
15

Some good answers here. I just wanted to add a little note.

Like all good libraries, the standard library is designed with (at least) two very important principles in mind:

  1. Put the least amount of responsibility on users of your library that you can get away with. Part of this has to do with giving them the least amount of work to do when using your interface. (like defining as few operators as you can get away with). The other part of it has to do with not surprising them or requiring them to check error codes (so keep interfaces consistent and throw exceptions from <stdexcept> when things go wrong).

  2. Eliminate all logical redundancy. All comparisons can be deduced merely from operator<, so why demand that users define others? e.g:

    (a > b) is equivalent to (b < a)

    (a >= b) is equivalent to !(a < b)

    (a == b) is equivalent to !((a < b) || (b < a))

    and so on.

    Of course on this note, one might ask why unordered_map requires operator== (at least by default) rather than operator<. The answer is that in a hash table the only comparison we ever require is one for equality. Thus it is more logically consistent (i.e. makes more sense to the library user) to require them to to define an equality operator. Requiring an operator< would be confusing because it's not immediately obvious why you'd need it.

11
  • 10
    Regarding your second point: There are types which can logically be compared for equality even if no logical order exists, or for which establishing an order would be very artificial. For example, red is red and red is not green, but is red inherently less than green? Sep 29, 2015 at 18:20
  • 1
    Completely agree. One would not store these items in an ordered container because there is no logical order. They might more suitably be stored in a unordered container which requires operator== (and hash). Sep 29, 2015 at 18:27
  • 3. Overload least standard operators as possible. This is another reason that they implemented !(a==b). Because unreflected overloading of operators may easily cause C++ program to get entirely messed up (plus, make the programmer go crazy because debugging his code may become a mission impossible, since finding the culprit of a particular bug is resembling an odyssey). Sep 29, 2015 at 19:36
  • !((a < b) || (b < a)) uses one less bool operator, so it's probably faster Sep 29, 2015 at 20:10
  • 1
    In reality they don't. In assembly language all comparisons are implemented as a subtract followed by testing carry and zero bits in the flags register. Everything else is just syntactic sugar. Sep 30, 2015 at 21:05
8

The EqualityComparable concept only requires that operator== be defined.

Consequently, any function that professes to work with types satisfying EqualityComparable cannot rely on the existence of operator!= for objects of that type. (unless there are additional requirements that imply the existence of operator!=).

1

The most promising approach is to find a method of determining if operator== can be called for a particular type, and then supporting it only when it is available; in other situations, an exception would be thrown. However, to date there is no known way to detect if an arbitrary operator expression f == g is suitably defined. The best solution known has the following undesirable qualities:

  • Fails at compile-time for objects where operator== is not accessible (e.g., because it is private).
  • Fails at compile-time if calling operator== is ambiguous.
  • Appears to be correct if the operator== declaration is correct, even though operator== may not compile.

From Boost FAQ : source

Knowing that requiring == implementation is a burden, you never want to create additional burden by requiring != implementation as well.

For me personally it's about SOLID (object-oriented design) L part - Liskov substitution principle : “objects in a program should be replaceable with instances of their subtypes without altering the correctness of that program.”. In this case it is the operator != that i can replace with == and boolean inverse in boolean logic.

0

Not the answer you're looking for? Browse other questions tagged or ask your own question.