Is set's iterator a const_iterator?

0 views
Skip to first unread message

Andy Champ

unread,
May 19, 2010, 3:31:23 PM5/19/10
to
We're experimenting with MS VC2010 - we wish to upgrade from 2008 - and
we've had an error come out which is a little bit of a surprise. I'd
just like to check with the experts here.

An object in a set must be comparable with other objects in the set,
typically with its inbuilt operator< but perhaps with another predicate.
This comparison must be stable, transitive and various other rules
that I'm sure everyone knows.

We've taken the view that we can do anything we like to the objects in
the set *provided that what we do does nothing to alter the way it
sorts*. It looks as though this wasn't correct - that we can't do
anything at all that requires non-const behaviour on the object. In
fact it looks as though set's iterator is almost identical to its
const_iterator, so what we'll have to do is pull the object out of the
set, copy it, fiddle with the copy, then put the copy back. This sounds
expensive :(

Have I understood this correctly?

Andy

Leigh Johnston

unread,
May 19, 2010, 3:39:04 PM5/19/10
to
"Andy Champ" <no....@nospam.invalid> wrote in message
news:AYqdnev1poUXoWnW...@eclipse.net.uk...

You have understood this correctly yes, however there are other options to
the remove/mutate/reinsert option, take a look at:

http://i42.co.uk/stuff/mutable_set.htm

(my work).

/Leigh

Jonathan Lee

unread,
May 19, 2010, 3:41:27 PM5/19/10
to
On May 19, 3:31 pm, Andy Champ <no....@nospam.invalid> wrote:
> Have I understood this correctly?
>
> Andy

Yup. I had the exact same problem recently. By
[lib.associative.reqmts] point 5: Keys in an associative
container are immutable.

And in a set, the value is also the key.

--Jonathan

Juha Nieminen

unread,
May 20, 2010, 6:00:53 AM5/20/10
to
Jonathan Lee <jle...@uwo.ca> wrote:
> Yup. I had the exact same problem recently. By
> [lib.associative.reqmts] point 5: Keys in an associative
> container are immutable.
>
> And in a set, the value is also the key.

That's why we have std::map: It's like a set, but with a mutable part on
each "key". It's what you should use when you want to change a part of the
key which isn't used to determine its ordering.

Bo Persson

unread,
May 20, 2010, 1:53:31 PM5/20/10
to

Yes. :-)

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#103


If you really, really, REALLY know what you are doing, you can beat
the compiler with a const_cast. The slightest mistake, and you are
toast, of course...

Bo Persson


Andy Champ

unread,
May 21, 2010, 3:07:09 PM5/21/10
to
Bo Persson wrote:
>
> Yes. :-)
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#103
>
>
> If you really, really, REALLY know what you are doing, you can beat
> the compiler with a const_cast. The slightest mistake, and you are
> toast, of course...
>

Thanks for the link. It explains everything - and it's silly.

If I want to break set I can very easily. I just have a const reference
in my set members to an external data item which is part of the key -
then change the data item through some other non-const reference.

So making iterator const has not cured the problem they were trying to
avoid.

But it has caused this new problem that you have to take the item out of
the set (copy construct) modify the copy, then put it back (another copy
construct)

Andy

Andy Champ

unread,
May 21, 2010, 3:12:31 PM5/21/10
to
Jonathan Lee wrote:
Leigh Johnston wrote:


As I went back through the posts to forward them to my work account (no
NNTP) it occurred to me - Are you guys related :P

Andy

Pete Becker

unread,
May 21, 2010, 3:17:17 PM5/21/10
to
On 2010-05-21 15:07:09 -0400, Andy Champ said:

> Bo Persson wrote:
>>
>> Yes. :-)
>>
>> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#103
>>
>>
>> If you really, really, REALLY know what you are doing, you can beat the
>> compiler with a const_cast. The slightest mistake, and you are toast,
>> of course...
>>
>
> Thanks for the link. It explains everything - and it's silly.
>
> If I want to break set I can very easily. I just have a const
> reference in my set members to an external data item which is part of
> the key - then change the data item through some other non-const
> reference.
>
> So making iterator const has not cured the problem they were trying to avoid.

There is no way of preventing users from writing perverse code to
deliberately break invariants. The change makes it harder to do this
accidentally.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jonathan Lee

unread,
May 21, 2010, 4:54:19 PM5/21/10
to

The near name reversal is indicative of the fact that one of us is
from a parallel universe and has a goatee.

You don't get to know which one.

--Jonathan

Brian

unread,
May 22, 2010, 4:13:54 PM5/22/10
to
On May 20, 5:00 am, Juha Nieminen <nos...@thanks.invalid> wrote:

I would say that's why we have boost::multi_index_container and
boost::intrusive containers. std::map it seems to me speaks
with a forked tongue, pair<key, value>. Although it takes a
little more effort, using an alternative to map avoids the
useless "first" and "second" terminology required by maps.
You can get by with maps in small programs, but how things
are named is more important in larger programs. I think
that some projects start out using maps and although they
would benefit from switching to an alternative, they lack
the resources to go back and rework things.


Brian Wood
http://webEbenezer.net
(651) 251-9384

Reply all
Reply to author
Forward
0 new messages