Invalidating set of pointers through indirection

Question

Consider the following program. It creates a set of pointer-to-ints, and uses a custom indrect_less comparator that sorts the set by the value of the pointed-to integer. Once this is done, I then change the value of one of the pointed-to integers. Then, it can be seen the order of the set is no longer sorted (I suppose because the set doesn't know something got changed).

(Don't mind the C++0x loops, I'm running on VS2010)

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

struct indirect_less {
    bool operator()(int* l, int* r) const
    {
        return *l < *r;
    }
};

int main()
{
    set<int*, indirect_less> myset;

    int* a = new int(5);
    int* b = new int(6);
    int* c = new int(7);

    myset.insert(a);
    myset.insert(b);
    myset.insert(c);

    cout << "Set contains: ";
    // (outputs: 5 6 7)

    for (auto i = myset.begin(), end = myset.end(); i != end; ++i)
    {
        cout << **i << " ";
    }

    cout << endl << "Modifying *a" << endl;
    *a = 9;         // point of interest
    cout << "Set contains: ";
    // (outputs: 9 6 7 - unsorted order)

    for (auto i = myset.begin(), end = myset.end(); i != end; ++i)
    {
        cout << **i << " ";
    }

    cout << endl;

    cin.get();

    return 0;
}

1) Am I right that I am invoking undefined behavior? Is the entire state of myset invalid after the line *a = 9;?

2) Is the only correct way to do this to erase then re-insert a?

3) Is there any way, once *a = 9; has been run, to re-balance the set in to sorted order, with well-defined behavior?

Answer 1

Yes, std::set assumes elements are immutable. It's possible, if dangerous, to reorder it yourself after each change. I wouldn't recommend it, though: use another collection type.

Answer 2

1) Yes, set doesn't allow modification of it's elements.

2) Besides deleting the old value and inserting the new value, you could also replace the old set with a newly constructed one.

3) No

Answer 3

1) I don't know that the behavior is undefined. The additional twist in this example is that the elements of the set are not altered -- each element of the set is a pointer. Were you to print out the (pointer) elements of the set before and after executing the line '*a = 9", I believe you would find that the pointer values are in the same order before and after the assignment. What has changed is the value that one set element points to. This took place outside the auspices of the set, and so the set has no way of maintaining the order you desire.

2) A qualified "yes". This will force use of indirect_less() to order the elements of the set. Again, be aware that you are ordering the elements of the set, pointers, by the value of each dereferenced pointer. However, this strikes me as somewhat risky, for exactly the reason you describe.

From the legend "Set contains:" in the printed output, I presume that this example strives to form a set of integers. However, the set defined, i.e., "set" actually consists of pointers to integers, not the integers themselves. I believe this misalignment between the desired and actual collections is the underlying cause of the problem.

3) See 2).