std::set sorting mechanism

[gipsy boy]

I've got a std::set with a custom comparator.
When I add things, it puts them in the right place.
When I change these objects (and I can tell they are effectively
changed), the set doesn't 'auto-sort' with these changes. How can I do this?
I store pointers in the set, but the comparator compares the contents of
these pointers.

 

[Victor Bazarov]

I've got a std::set with a custom comparator.
When I add things, it puts them in the right place.
When I change these objects (and I can tell they are effectively
changed), the set doesn't 'auto-sort' with these changes. How can I do
this?
I store pointers in the set, but the comparator compares the contents of
these pointers.

There is no auto-resort option for std::set or a member function that
would force the set to resort itself. That's the whole point of the
set is that it has a relatively short insertion and retrieval times.

What's wrong with (remove + reinsert) approach I suggested instead of
changing the value?

BTW, why do you feel you need a set? Are the elements supposed to be
unique? OK, if you have 'a', 'b', 'c' in your set, and then change the
first to be 'c', what happens? The set is not a set any longer, is it?

If you feel that you need the capability to edit elements _after_ they
have been stored, but keep them sorted, you need to rethink which of
the standard containers to use (or maybe just roll your own). You can
use 'multiset', it can store object with the same values and still get
them in and out quickly. You can use 'list' and, say, insertion-sort
it when you add things to it, and when you change things.

Victor

 

[chris]

I've got a std::set with a custom comparator.
When I add things, it puts them in the right place.
When I change these objects (and I can tell they are effectively
changed), the set doesn't 'auto-sort' with these changes. How can I do
this?
I store pointers in the set, but the comparator compares the contents of
these pointers.

Unfortunatly sets don't work like that, you shouldn't change the
relative ordering of elements in a set (I can't actually find the bit of
the standard that says that right now. 23.1.2 points 9 and 10 kind of
say it, but I'm not convinced they are worded very well).

If you only want to be able to get to the first element in the the
sorted set, then consider looking at heaps, which are designed for this
kind of thing. Alternatively it's off to a vector and resorting I'm
afraid (or some custom class).

Chris

 

[chris]

There is no auto-resort option for std::set or a member function that
would force the set to resort itself. That's the whole point of the
set is that it has a relatively short insertion and retrieval times.

What's wrong with (remove + reinsert) approach I suggested instead of
changing the value?

Out of interest, do you agree that changing the values of a set in such
a way that the relative order of elements if changed is actually
forbidden? Is it 23.1.2 points 9 and 10 that say this?

It just worries me, because most implementations of set will not just
not be sorted, but simply not work if you start changing the elements
(in particular they will stop making sure that inserted elements are
unique, and it's possible they might crash). I'm kind of suprised now I
think about it you can get a non-constant iterator to the elements of sets.

Chris

 

[Victor Bazarov]

Out of interest, do you agree that changing the values of a set in such
a way that the relative order of elements if changed is actually
forbidden? Is it 23.1.2 points 9 and 10 that say this?

My take on this is actually more cautious [and I also urge you to post
your question to comp.std.c++ for clarification]. I think that 23.1.2/9
and 23.1.2/10 simply indicate that the process of _iterating_ through
a container must present a particular order of elements. It does not
say that we can't change values of elements.

There is an embedded conflict in the description of iterators of 'set'.
OOH, they can allow changing of the value_type (i.e. the value type can
be a reference to a non-const object). OTOH, doing so may require
invalidating the rest of iterators (and the whole iteration procedure)
so that it has to be restarted and 'begin()' or 'rbegin()' actually
force at least a re-check of the "structural integrity" of the container.

If only the requirements were a bit stronger, for example, to prohibit
the assignment to *i (where 'i' is std::set::iterator), then everything
would probably fall into place and an implementation that defines the
std::set::iterator::value_type to be a reference to non-const would
suddenly become non-conforming.

It just worries me, because most implementations of set will not just
not be sorted, but simply not work if you start changing the elements
(in particular they will stop making sure that inserted elements are
unique, and it's possible they might crash). I'm kind of suprised now I
think about it you can get a non-constant iterator to the elements of sets.

I think a good discussion in comp.std.c++ is in order, if it didn't happen
already.

Victor

 

[gipsy boy]

There is no auto-resort option for std::set or a member function that
would force the set to resort itself. That's the whole point of the
set is that it has a relatively short insertion and retrieval times.

What's wrong with (remove + reinsert) approach I suggested instead of
changing the value?

BTW, why do you feel you need a set? Are the elements supposed to be
unique? OK, if you have 'a', 'b', 'c' in your set, and then change the
first to be 'c', what happens? The set is not a set any longer, is it?

Yeah, I agree sets shouldn't auto-sort.
I think I'll still use a set but like you said I'll just remove/insert
each time. All in all it's an assignment and the deadline is in a couple
of hours, I'll keep it in mind, but I'm a bit tired to change my
architecture.
Thanks for all your help with this by the way,

 

[gipsy boy]

If you feel that you need the capability to edit elements _after_ they
have been stored, but keep them sorted, you need to rethink which of
the standard containers to use (or maybe just roll your own). You can
use 'multiset', it can store object with the same values and still get
them in and out quickly. You can use 'list' and, say, insertion-sort
it when you add things to it, and when you change things.

They had to be unique values, and it was nice to provide a comparator.
(adding an object is probably 99:1 times as more likely to happen that
changing one).

Well, what I'm doing now is that, if the objects get changed, I empty
the entire set, and then use an auxiliary vector to put everything back
in. (apparently, erasing and then inserting a pointer didn't work) Why
is that?
std::set<R*,Rcmp> rSet;
.... // (R* rPtr is now in rSet
rPtr->changeMe();
rSet.erase(rPtr);
rSet.insert(rPtr);

The result of this is that, the changed rPtr is back in the set, but
another object has disappeared. I suppose this is what you both said
about not changing the relative order in any way.
So I'll just clear it and then put everything back in. That's the only
solution right?

 

[Victor Bazarov]

They had to be unique values, and it was nice to provide a comparator.
(adding an object is probably 99:1 times as more likely to happen that
changing one).

Well, what I'm doing now is that, if the objects get changed, I empty
the entire set, and then use an auxiliary vector to put everything back
in. (apparently, erasing and then inserting a pointer didn't work) Why
is that?
std::set<R*,Rcmp> rSet;
... // (R* rPtr is now in rSet
rPtr->changeMe();
rSet.erase(rPtr);
rSet.insert(rPtr);

I think you're doing it a bit in the wrong order. You need

rSet.erase(rPtr);
rPtr->changeMe();
rSet.insert(rPtr);

The result of this is that, the changed rPtr is back in the set, but
another object has disappeared. I suppose this is what you both said
about not changing the relative order in any way.
So I'll just clear it and then put everything back in. That's the only
solution right?

No. See above.

Victor

 

[=?iso-8859-1?B?Sm9hcXXtbiBNIEzzcGV6IE118W96?=]

I think this issue was addressed in DR #103:

http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#103
HTH

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo