std::set and boost::shared_ptr unique key identification issues

Question

I am having issues understanding how std::set (or std::map etc) identify unique keys. The thing I am trying to do is wrap a struct object within boost::shared_ptr and then store that shared pointer within std::set container:

Let's say the struct is a color:

struct Color {
    float r;
    float g;
    float b;
};

Then the container and comparison function object is defined in another class:

class AnotherClass {

    typedef boost::shared_ptr<Color> ColorPtr;

    public:

        struct ColorCompare {
            bool operator()(const ColorPtr &a, const ColorPtr &b) const {
                return (a->r > b->r) && (a->g > b->g) && (a->b > b->b);
            }
        };

    private:

        // Container definition
        std::set<ColorPtr, ColorCompare> colors;
};

The code above is failing to uniquely identify shared_ptr objects based on their wrapped Color struct. I always thought that the std::set container would run a comparison function on two objects, and if none of them is greater than or less than the other - it will assume they are equal. Note, that I cannot use default shared_ptr::operator<() and less<...> as that implementation is based on pointer address.

What am I missing?

p.s. I am wrapping colors within shared_ptr since I need to know their reference count at some point (and remove colors that are at ref count 1 - that is, only referenced by std::set container itself). Is there a better way to get the same result?

You could store `weak_ptr`s and remove them if they are `expired()`. — Xeo, Jan 07 '12 at 17:27
But aren't `weak_ptr`'s just observers of `shared_ptr`'s? So I still need to store or give away `shared_ptr`'s at some point. Thanks for the suggestion tho. — Sim, Jan 07 '12 at 19:14

Kerrek SB · Accepted Answer · 2012-01-07T17:25:37.873

4

The comparison needs to be a strict weak ordering, which yours isn't. (For example, how are (1,0,0) and (0,1,0) ordered?) Do this:

return (a->r > b->r)                                   ||
       ((a->r == b->r) && (a->g > b->g))               ||
       ((a->r == b->r) && (a->g == b->g) && (a->b > b->b) );

This is the standard lexicographic ordering on a tuple of elements.

Note that you would write !(b->r > a->r) instead of a->r == b->r in general so that you don't introduce a dependence on a compatible equality operator, though in this simple case of floats we're fine.

By the way, you don't need a struct, you can simply declare a static bool ColorCompare(...); function. Another option is to define an operator< directly in the struct Color to make everything self-contained (so you'll just need a generic dereferencing-comparator for (smart) pointers).

edited Jan 07 '12 at 17:25

answered Jan 07 '12 at 17:09

Kerrek SB

464,522
92
875
1,084

The `operator<` inside `Color` won't work IIRC, as `shared_ptr` won't forward the comparision to the actual object and will simply compare the pointers. Also, this shows again just how ugly a correct implementation of strict-weak-ordering can be. [Glad I found a solution to that!](http://stackoverflow.com/questions/6218812/implementing-comparision-operators-via-tuple-and-tie-a-good-idea) – Xeo Jan 07 '12 at 17:19
@Xeo: You still need a generic "shared-pointer by-value comparator", but that could be done without regard to the internals of the pointee. I added a note. Good link, by the way. – Kerrek SB Jan 07 '12 at 17:23
That was the problem - thanks. I tried your implementation but did get some weird stl exception "invalid operator<". Then I tried [this answer](http://stackoverflow.com/a/979768/454230) and that strict weak ordering algorithm seems to work great. – Sim Jan 07 '12 at 19:11

std::set and boost::shared_ptr unique key identification issues

1 Answers1