How to tell std::set to 'refresh' its ordering?

Question

If the value of an element in a set changes the ordering may be no longer correct. As illustrated in this little program:

#include <algorithm>
#include <iostream>
#include <set>
#include <string>

struct Comp
{
    bool operator()(const std::string * lhs, const std::string * rhs)
    {
     return *lhs < *rhs;
    }
};

int main()
{
    typedef std::set<std::string*, Comp> MySet;
    MySet mySet;

    std::string * a = new std::string("a");
    mySet.insert(a);

    std::string * c = new std::string("c");
    mySet.insert(c);

    std::string * b = new std::string("b");
    mySet.insert(b);

    for (MySet::iterator it = mySet.begin(); it != mySet.end(); ++it)
    {
     std::cout << *(*it) << std::endl;
    }

    // Ouput has correct order:
    // a
    // b
    // c


    *b = "z";
    std::cout << std::endl;

    std::string * d = new std::string("d");
    mySet.insert(d); 

    for (MySet::iterator it = mySet.begin(); it != mySet.end(); ++it)
    {
     std::cout << *(*it) << std::endl;
    }

    // Output no longer ordered correctly:
    // a
    // d
    // z
    // c

    return 0;
}

How can I tell the set to 'refresh' its internal sorting?

Answer 1

Very similar subject here (though not quite a duplicate, because you're storing pointers to mutable objects with a custom comparison):

http://stackoverflow.com/questions/908949/what-happens-when-you-modify-an-element-of-an-stdset

Basically, don't do what you're trying to do. Instead, when you want to modify an object that a set holds a pointer to, remove the pointer first, then modify the object, then re-insert the pointer.

Answer 2

Simply, you can't. If you place an item into a set, you should not change the item in a way that changes its ordering. If you need to change an item in this way then you need to remove it from the set (set::erase), and reinsert a new item (std::insert) with the new value.

Answer 3

It's worth point out that if you're using vs 2008, the std::set implementation supports non-const iterators, making the code you describe compile successfully using that library. In other stl implementations (for instance sgi's), set::const_iterator and set::iterator are of the same type which would complain about explicitly setting a new key value.

Answer 4

Copy it into itself using a different comparison predicate.

std::set MySet();

/* add entries*/

MySet = std::set(MySet.begin(), MySet.end(), Comp);

Usually this is used to specify a different comparison operation, eg to sort it using a different part of a stored class/struct.