Strange Behavior of std::set and < Operator Overloading?

Question

I understand that if the < operator is overloaded in C++ (for example, to insert custom structs into std::set), the implementation must be a strict weak order over the underlying type.

Consider the following struct and implementation. This implementation is not a strict weak order, but the code compiles and runs without throwing an error (I would expect it to throw an error, given the requirement of a strict weak order):

#include <iostream>
#include <set>
using namespace std;

struct Pixel {
    int x;
    int y;
};

bool operator < (Pixel lhs, Pixel rhs){
    return lhs.x < rhs.x || lhs.y < rhs.y;
};

int main(){
    set<Pixel> mySet;

    Pixel *newPixelA = new Pixel;
    newPixelA->x = 1;
    newPixelA->y = 3;

    Pixel *newPixelB = new Pixel;
    newPixelB->x = 4;
    newPixelB->y = 2;

    mySet.insert(*newPixelA);
    mySet.insert(*newPixelB);

}

Is this the expected behavior? EDIT: using Xcode.

Undefined behavior is undefined. "Seems to work" is one possible manifestation of undefined behavior. — Igor Tandetnik, Oct 30 '17 at 03:53
Your "appears to work" is indeed an accurate description of what you observed. It is also unclear why you are dynamically allocating source objects for insertion. — AnT stands with Russia, Oct 30 '17 at 03:54
Try with more than 2 items.. Visual Studio thrown an exception immediately in a debug build. — Retired Ninja, Oct 30 '17 at 03:54
Since you expect it to throw an error and it does not, why do you say it "appears to work just fine"? Isn't it not doing what you should expect it to do the very opposite of working just fine? — David Schwartz, Oct 30 '17 at 03:56
@RetiredNinja yes, I did run it; just edited question to be more clear — Daniel, Oct 30 '17 at 04:01
@RetiredNinja interesting observation about Visual Studio...maybe it's a behavior of Xcode (I'm using Xcode) — Daniel, Oct 30 '17 at 04:02
Short answer: if your comparison function doesn't conform to the requirement, your code has undefined behavior. You could get some sort of error message, or it could appear to work, or just about anything else. The standard simply places no requirement on the result. — Jerry Coffin, Oct 30 '17 at 04:07
Guess what: `char *p=nullptr; char c=*p;` will also compile. Doesn't mean that this will run successfully. — Sam Varshavchik, Oct 30 '17 at 04:30

score 4 · Answer 1 · answered Oct 30 '17 at 04:02

The compiler has no way of determining whether your operator< is a strict weak ordering. Instead, what is meant by std::set requiring this is that it will only work correctly if you give it a strict weak ordering. It makes no guarantees about what will happen if you give it something else.

In general, what C++ means when it requires something is that it is your responsibility to make sure that something happens. If you do, then the compiler and library will guarantee that you get the right results.

score 1 · Answer 2 · answered Oct 30 '17 at 04:54

Standard guarantees expected behavior if comparator requirements are met. Otherwise, what happens depends on implementation and data sets. Your comparison function may work properly for some data sets (where for all points greater x implies greater y). Set cannot contain equal elements (as a math concept), and for std::set equivalence means equality, so it'll just prevent you from inserting value a if there is already value b, such that:

a < b == true
b < a == true

even though a may be not equal to b

score 1 · Answer 3 · answered Oct 30 '17 at 05:36

When the comparison operator implements strictly weak ordering of the contained elements, the objects in the std::set are ordered in a predictable patten. If not, there is no telling which object appears first in the std::set when you iterate over the objects.

Take the following sample program in which ordering of Pixel1 is not done right and ordering of Pixel2 is done right.

#include <iostream>
#include <set>

struct Pixel1 {
    int x;
    int y;
};

bool operator < (Pixel1 lhs, Pixel1 rhs){
    return lhs.x < rhs.x || lhs.y < rhs.y;
};

struct Pixel2 {
    int x;
    int y;
};

bool operator < (Pixel2 lhs, Pixel2 rhs){
    if ( lhs.x != rhs.x )
    {
       return (lhs.x < rhs.x);
    }
    return (lhs.y < rhs.y);
};

template <typename Pixel> void print(std::set<Pixel> const& mySet)
{
   for ( Pixel p : mySet )
   {
      std::cout << "(" << p.x << ", " << p.y << ") ";
   }
   std::cout << std::endl;
}

template <typename Pixel> void test1()
{
   std::set<Pixel> mySet;

   Pixel pixelA = {2, 3};
   Pixel pixelB = {4, 2};
   Pixel pixelC = {4, 1};

   mySet.insert(pixelA);
   mySet.insert(pixelB);
   mySet.insert(pixelC);

   print(mySet);
}

template <typename Pixel> void test2()
{
   std::set<Pixel> mySet;

   Pixel pixelA = {2, 3};
   Pixel pixelB = {4, 2};
   Pixel pixelC = {4, 1};

   mySet.insert(pixelB);
   mySet.insert(pixelA);
   mySet.insert(pixelC);

   print(mySet);
}

int main()
{
   std::cout << "Pixel1 ... \n";
   test1<Pixel1>();
   test2<Pixel1>();

   std::cout << "Pixel2 ... \n";
   test1<Pixel2>();
   test2<Pixel2>();
}

Output

Pixel1 ... 
(4, 1) (4, 2) (2, 3) 
(4, 1) (2, 3) (4, 2) 
Pixel2 ... 
(2, 3) (4, 1) (4, 2) 
(2, 3) (4, 1) (4, 2)

The order of objects in the std::set<Pixel1> depends on the order of insertion while the order of objects in the std::set<Pixel2> is independent of the order of insertion.

Only you can tell whether that is acceptable in your application,

Strange Behavior of std::set and < Operator Overloading?

3 Answers3