How can I create a std::set of structures?

Question

I need to create a stl::set of structures. Therefore, I wrote the following:

stl::set <Point> mySet; // Point - name of the structure.

Then I tried to add a structure instance to mySet as follows:

Point myPoint;
mySet.insert(myPoint);

However, I get several compilation errors (error C2784, error C2676):

1>C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xfunctional(125): error C2784: bool std::operator <(const std::vector<_Ty,_Ax> &,const std::vector<_Ty,_Ax> &): failed to bring the argument to a template "const std::vector<_Ty,_Ax> &" from"const Point"

1>C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xfunctional(125): error C2676: binary "<": "const Point "does not define this operator or a conversion to a type acceptable to the integrated operator

How do I get my code compiled?

Answer 1

The std::set template provides an associative container that contains a sorted set of unique objects. The key words there is sorted and unique. To support sorting, a number of possibilities ensue, but ultimately the all must lead to a conforming with strict weak ordering.

The second template argument to std::set is a comparison type. The default, std::less<Key>, is supplied by the standard library, where Key is the type of object you're storing in your container (in your case, Point). That default simply generates a comparison using any allowable available operator < supporting the key type. Which means one way or another, if you're using the default comparator (std::less<Point> in your case), then your class must suppose operations like this:

Point pt1(args);
Point pt2(args);

if (pt1 < pt2)  // <<=== this operation
    dosomething();

Multiple methods for doing this appear below:

Provide a member operator <

By far the easiest method to accomplish this is to provide a member operator < for your Point class. In doing so pt1 < pt2 becomes valid and std::less<Point> is then happy. Assuming your class is a traditional x,y point, it would look like this:

struct Point
{
    int x,y;

    // compare for order.     
    bool operator <(const Point& pt) const
    {
        return (x < pt.x) || ((!(pt.x < x)) && (y < pt.y));
    }
};

---

Provide a Custom Comparator Type

Another method would be to provide a custom comparator type rather than relying on std::less<Point>. The biggest advantage in this is the ability to define several that can mean different things, and use them in containers or algorithms as appropriately needed.

struct CmpPoint
{
    bool operator()(const Point& lhs, const Point& rhs) const
    {
        return (lhs.x < rhs.x) || ((!(rhs.x < lhs.x)) && (lhs.y < rhs.y));
    }
};

With that, you can now declare your std::set like this:

std::set<Point,CmpPoint> mySet;

Something to consider with this approach: The type is not part of Point, so any access to private member variables or functions has to be accounted for via friending in come capacity.

---

Provide a free-function operator <

Another less common mechanism is simply provide a global free-function that provides operator <. This is NOT a member function. In doing this, once again, the default std::less<Point> will result in valid code.

bool operator <(const Point& lhs, const Point& rhs)
{
    return (lhs.x < rhs.x) || ((!(rhs.x < lhs.x)) && (lhs.y < rhs.y));
}

This may seem a mix of both the custom comparator and the member operator, and indeed many of the pros and cons of each come along. Ex: like the member operator <, you can just use the default std::less<Point>. Like the custom comparator, this is a non-class function, so access to private members must be provided via friending or accessors.

---

Summary

For your needs, I'd go with the simple approach; just make a member operator <. Chances are you'll always want to order your Points in that fashion. If not, go with the custom comparator. In either case make sure you honor strict weak ordering.

Answer 2

To expand on WhozCraig's answer, since C++11 you can also use a lambda expression instead of defining a comparison object. For the lambda expression in the following code, I'm also assuming that your Point class just consists of x and y members:

auto comp = [](const Point& p1, const Point& p2) {
    return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
};
std::set<Point, decltype(comp)> mySet(comp);

Point myPoint;
mySet.insert(myPoint);

As for the solutions given by WhozCraig, also comp must fulfil the strict weak ordering condition.

Code on Ideone