The dangers of returning const references to values held in a map

[age...@andrewpetermarlow.co.uk]

{ Reformatted; please, pretty please with sugar on top, limit your
lines to 70 characters - mod }

hello chaps and chapesses,

I have come across some code that returns a const reference to a value
held in a map. Both the keys and the values are strings. I think that
the author might have been concerned about performance costs if the
returned value was to be copied. But I think this is wrong (premature
optimisation is the root of all evil). The code was drawn to my
attention because purify gave it an UMR (uninitialised memory
reference). This is what made me look at it, scratching my head to
find out how a UMR could happen. I have an educated guess and would
like to share it here to see what you STL experts have to say :-)

My guess is that because a std::map can be implemented using a tree
that can dynamically rebalance (typically a RB tree) it is dangerous
to return a reference to a value object held in that map. If the tree
were rebalanced then the reference might become invalid. Any thoughts?

Regards,

Andrew Marlow


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Daniel Krügler]

Am 19.10.2012 22:43, schrieb age...@andrewpetermarlow.co.uk:
> I have come across some code that returns a const reference to a value
> held in a map. Both the keys and the values are strings. I think that
> the author might have been concerned about performance costs if the
> returned value was to be copied. But I think this is wrong (premature
> optimisation is the root of all evil). The code was drawn to my
> attention because purify gave it an UMR (uninitialised memory
> reference). This is what made me look at it, scratching my head to
> find out how a UMR could happen. I have an educated guess and would
> like to share it here to see what you STL experts have to say :-)

I think we need to see more concrete code that shows the operations
applied and the scopes of the corresponding objects to give more than
educated guesses here.

> My guess is that because a std::map can be implemented using a tree
> that can dynamically rebalance (typically a RB tree) it is dangerous
> to return a reference to a value object held in that map. If the tree
> were rebalanced then the reference might become invalid. Any thoughts?

The standard imposes quite strong implementation constraints upon
associative containers in regard to the conservation of iterator values
and references to contained elements. E.g. 23.2.5 p9 says:

"The insert and emplace members shall not affect the validity of
iterators and references to the container, and the erase members shall
invalidate only iterators and references to the erased elements."

In other words: Any rebalancing of the internal tree is not allowed to
invalidate references of existing elements. This is quite easy to
realize, because such containers are typically node-based, so
rebalancing will only move the nodes around without affecting the actual
(and observable) elements.

HTH & Greetings from Bremen,

Daniel Krügler

[Tobias Müller]

<age...@andrewpetermarlow.co.uk> wrote:
> I have come across some code that returns a const reference to a
> value held in a map. Both the keys and the values are strings.

I return references all the time in such situations. References are
seldomly stored for longer than a few function calls, but mostly
directly forwarded to other functions as arguments, which are often
also references. If I still want to store it for longer, I'll store a
copy and not a reference, unless I'm totally sure that the reference
will not invalidate. By returning a reference, you let the caller
decide, whether to copy the object or not.

> I think that the author might have been concerned about performance
> costs if the returned value was to be copied. But I think this is
> wrong (premature optimisation is the root of all evil).

Knuth may be a smart guy, but I just cannot hear that that quote
anymore. People look at others code and think they know the problems
better than the one that actually wrote it. How can you say that an
optimization is premature if you weren't there when the code was
written?

I usually try to write performant code from the beginning. All those
small optimizations sum up and will make a difference in the end.
Optimizing the performance afterwards may not be that easy, because
the performance loss is not obviously concentrated in one spot.

It's even more true, if you write a library, or at least a reusable
class. You will never know in advance where and how your classes will
be used. And later, you may not have time/resources to look at the
code again.

> The code was drawn to my attention because purify gave it an UMR
> (uninitialised memory reference).

I don't know purify, but for me UMR seems to be a different problem
than the one you are describing (which is usually called dangling
reference).

This is my understanding of an UMR:
int obj; // not initialized
int& ref = obj; // UMR

> This is what made me look at it, scratching my head to find out how
> a UMR could happen. I have an educated guess and would like to share
> it here to see what you STL experts have to say :-)

I'm not an STL expert at all, but could it be, that the problem lies
actually somewhere else?

Tobi

[age...@andrewpetermarlow.co.uk]

On Friday, October 19, 2012 11:31:48 PM UTC+1, Daniel Krügler wrote:
> Am 19.10.2012 22:43, schrieb age...@andrewpetermarlow.co.uk:
>
> > I have come across some code that returns a const reference to a value
> > held in a map. Both the keys and the values are strings.

> I think we need to see more concrete code that shows the operations

[snip]

> > My guess is that because a std::map can be implemented using a tree
> > that can dynamically rebalance (typically a RB tree) it is dangerous
> > to return a reference to a value object held in that map. If the tree
> > were rebalanced then the reference might become invalid. Any thoughts?
>
> The standard imposes quite strong implementation constraints upon
> associative containers in regard to the conservation of iterator values
> and references to contained elements. E.g. 23.2.5 p9 says:
>

[snip]

>
> In other words: Any rebalancing of the internal tree is not allowed to
> invalidate references of existing elements.
>

> HTH & Greetings from Bremen,
>
> Daniel Krügler

Thanks for the stds quote. From this it looks like my theory was wrong
and that it is ok to return references to values held in a map.
I must admit, I am suprised, especially since purify is giving a UMR.
When I changed the code to return a value the UMR went away.
So I take it that the implementation must always use nodes in order to
gaurantee that references to existing items remain valid when the tree
is rebalanced. The rebalancing affects the location of the nodes but not
the values. Hmm. Well, you learn something every day. Thanks again :-)

[James K. Lowden]

On Sun, 21 Oct 2012 15:01:36 CST
Tobias Müller <tro...@bluewin.ch> wrote:

> Knuth may be a smart guy, but I just cannot hear that that quote
> anymore. People look at others code and think they know the problems
> better than the one that actually wrote it. How can you say that an
> optimization is premature if you weren't there when the code was
> written?

If you read Knuth's remark in context, it's clear he was concerned with
"optimization" interfering with clarity. At the time, the idea that
code's main purpose is to convey intent to the reader, not to the
computer, was novel. It bears repeating because, for too many people,
it still is.

Efficiency is borne of design: minimizing copies, minimizing branches,
minimizing *code*. Yet, because that's so nebulous, discussion
often revolves around small, concrete choices that are unlikely to
affect efficiency but do affect clarity.

For example, it's impossible to say definitively if map::insert or
map::operator[] is more efficient. You would think, given their
different semantics, that operator[] would always be preferred for
reasons of clarity unless it was important for insert to fail. But
every time I've asked someone why he chose map::insert, efficiency was
the answer.

So, you're right: you can't know. But if it could be clearer and it's
not called millions of times, it's a safe bet clarity wasn't the
author's foremost concern.

--jkl

[James Lothian]

James K. Lowden wrote:
> [snip]

> For example, it's impossible to say definitively if map::insert or
> map::operator[] is more efficient. You would think, given their
> different semantics, that operator[] would always be preferred for
> reasons of clarity unless it was important for insert to fail. But
> every time I've asked someone why he chose map::insert, efficiency was
> the answer.
>

Hmm.
class MyThing { /* content elided */ };

std::map<std::string, MyThing*> myMap;
myMap["HelloMum"] = new MyThing;

What gets left in the map if MyThing's constructor throws?

James

--
---------------------------------------------
demangle my email address in the obvious way.

[James K. Lowden]

On Tue, 23 Oct 2012 10:41:45 -0700 (PDT)
James Lothian <ja...@firstnamelastname.freeserve.co.uk> wrote:

> James K. Lowden wrote:
> > [snip]
> > For example, it's impossible to say definitively if map::insert or
> > map::operator[] is more efficient. You would think, given their
> > different semantics, that operator[] would always be preferred for
> > reasons of clarity unless it was important for insert to fail.
> > But every time I've asked someone why he chose map::insert,
> > efficiency was the answer.
> >
> Hmm.
> class MyThing { /* content elided */ };
>
> std::map<std::string, MyThing*> myMap;
> myMap["HelloMum"] = new MyThing;
>
> What gets left in the map if MyThing's constructor throws?

map::operator[] calls map::insert for a default-contructed MyThing,
and returns a reference to the mapped_type object. If that
construction fails, the map is unmodified.

The assignment calls MyThing::operator=. If new throws an exeption,
the assignment never happens.

In your particular example, both constructors are the default
constructor. It's possible one would succeed and the other fail but
in this particular case the effect on the map is (logically) the same!

I think your example is more interesting with

myMap["hello"] = new MyThing( many, interesting, parameters );

because then a default MyThing was added as the referent. However, the
problem is simply solved at very little cost:

MyThing *p = new MyThing( many, interesting, parameters );
myMap["hello"] = p;

which I assert is much easier to read than

myMap.insert(
make_pair(
"hello",
new MyThing( many, interesting, parameters )
)
);

--jkl


--

[James Lothian]

James K. Lowden wrote:
>
> On Tue, 23 Oct 2012 10:41:45 -0700 (PDT)
> James Lothian <ja...@firstnamelastname.freeserve.co.uk> wrote:
>
>> James K. Lowden wrote:
>>> [snip]
>>> For example, it's impossible to say definitively if map::insert or
>>> map::operator[] is more efficient. You would think, given their
>>> different semantics, that operator[] would always be preferred for
>>> reasons of clarity unless it was important for insert to fail.
>>> But every time I've asked someone why he chose map::insert,
>>> efficiency was the answer.
>>>
>> Hmm.
>> class MyThing { /* content elided */ };
>>
>> std::map<std::string, MyThing*> myMap;
>> myMap["HelloMum"] = new MyThing;
>>
>> What gets left in the map if MyThing's constructor throws?
>
> map::operator[] calls map::insert for a default-contructed MyThing,
> and returns a reference to the mapped_type object. If that
> construction fails, the map is unmodified.

But the map values are pointers in this case. If the RH operand of
operator=() is evaluated first, there is no problem with the ctor
throwing. If the LH operand is evaluated first, a new map entry is
created, containing a default-initialised (i.e. null) pointer, and
then the exception is thrown by MyThing's constructor, leaving the
null pointer in the map for you to trip over later. Yes, you can work
round this by creating MyThing in a separate line, but the fact that
something as innocuous looking as

myMap["HelloMum"] = new MyThing;

can have such subtle consequences tends to put me off using operator[]
for inserting into maps.

James

--
---------------------------------------------
demangle my email address in the obvious way.

[James K. Lowden]

On Wed, 24 Oct 2012 11:41:48 -0700 (PDT)
James Lothian <ja...@firstnamelastname.freeserve.co.uk> wrote:

> Yes, you can work round this by creating MyThing in a separate line,
> but the fact that something as innocuous looking as
> myMap["HelloMum"] = new MyThing;
> can have such subtle consequences tends to put me off using operator[]
> for inserting into maps.

Hmm, OK. It sounds like you prefer the wordy insert/make_pair syntax
because it's atomic.

What do you do if the lhs exists, i.e., if you intend to
overwrite it and map::insert would fail?

--jkl


--

[James Lothian]

James K. Lowden wrote:
> On Wed, 24 Oct 2012 11:41:48 -0700 (PDT)
> James Lothian <ja...@firstnamelastname.freeserve.co.uk> wrote:
>
>> Yes, you can work round this by creating MyThing in a separate line,
>> but the fact that something as innocuous looking as
>> myMap["HelloMum"] = new MyThing;
>> can have such subtle consequences tends to put me off using operator[]
>> for inserting into maps.
>
> Hmm, OK. It sounds like you prefer the wordy insert/make_pair syntax
> because it's atomic.
>
> What do you do if the lhs exists, i.e., if you intend to
> overwrite it and map::insert would fail?
>

It's tricky, isn't it? I guess in that situation, I'd use
operator[], since if the ctor throws, the map should just
be left as it was.

To be honest, I'm just being a complete pedantic s0d about
this. The only reason I picked up on it is that I ended up
falling foul of this a few contracts ago, and the surprise
at figuring out what was going on has stuck with me. It's
a shame that std::map<> doesn't provide (as far as I can tell)
a member fn that gets given a value and inserts a new entry if
there isn't one, or overwrites the value of one that's there
already. Operator[] is close to what you want, but the fact
that the new map entry can be created before you've had a
chance to create the value you're going to put in it seems to
make it unexpectedly hard to use exception-safely.

Cheers,

James


--
---------------------------------------------
demangle my email address in the obvious way.

[Seungbeom Kim]

On 2012-10-25 17:59, James Lothian wrote:
> It's
> a shame that std::map<> doesn't provide (as far as I can tell)
> a member fn that gets given a value and inserts a new entry if
> there isn't one, or overwrites the value of one that's there
> already. Operator[] is close to what you want, but the fact
> that the new map entry can be created before you've had a
> chance to create the value you're going to put in it seems to
> make it unexpectedly hard to use exception-safely.

If you finish creating the value to be inserted (in a separate
statement) before trying to access the map, it's very close to
what you want:

// given std::map<K, V> m = ...; K k = ...;
V v = create_V(...);
m[k] = v;

I feel little need to write a separate function for this (except for
wanting to avoid the slightly inefficient combination of default
construction and assignment), because as you pass the value to the
function as an argument, you automatically finish creating it before
calling the function, and the function reduces to merely executing
'm[k] = v'.

And it's a good idea in general to separate potentially throwing
or modifying operations from one another (i.e. not mix them in a
single statement), anyway.

--
Seungbeom Kim