8

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?

StackedCrooked
  • 34,653
  • 44
  • 154
  • 278
  • The value should _not_ change. The `value_type` should be `std::set` (though I believe VS doesn't abide by that?) – Lightness Races in Orbit Feb 01 '12 at 14:34
  • 1
    The value type is what the user passes, with a top-level const added. If the user passes `std::string*`, the value type will be `std::string* const`. There's no rule forbidding the user to pass something that doesn't enforce the immutability of the value's sorting position; there's just a rule that says that modifying the value in such a way yields undefined behavior. – Sebastian Redl Oct 18 '13 at 16:12

5 Answers5

12

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

what happens when you modify an element of an std::set?

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.

Community
  • 1
  • 1
Daniel Earwicker
  • 114,894
  • 38
  • 205
  • 284
6

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.

CB Bailey
  • 755,051
  • 104
  • 632
  • 656
2

If the value of an element in a set changes

Stop! This cannot legally occur.

std::set does not provide any means to do what you're asking, because it's already a pre-requisite that a manual re-order shall never be required.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
1

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.

Alan
  • 13,510
  • 9
  • 44
  • 50
  • 1
    Set iterators are const in the standard. If you try to update the members of a set via an iterator you should get compile errors. – jkp Jun 23 '09 at 08:21
0

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.

gbjbaanb
  • 51,617
  • 12
  • 104
  • 148