--001a11c1d7e0318e4d04ef689caa
Content-Type: text/plain; charset=ISO-8859-1

These functions seems to solve regular problems I have with most containers
that I solve with kind-of-hacks that so far I failed to generalize
efficiently.
Both stable_insert/emplace and always_insert/emplace would be very useful
with my current codebase.
However, it is not clear to me why it wouldn't be useful in std::set too? I
have some use of sets which needs to overwrite values even if the compare
equally,
and so far I have been using hacks.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

--001a11c1d7e0318e4d04ef689caa
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra">These functions seems to solve =
regular problems I have with most containers that I solve with kind-of-hack=
s that so far I failed to generalize efficiently.<br></div><div class=3D"gm=
ail_extra">
Both stable_insert/emplace and always_insert/emplace would be very useful w=
ith my current codebase.<br>However, it is not clear to me why it wouldn&#3=
9;t be useful in std::set too? I have some use of sets which needs to overw=
rite values even if the compare equally,</div>
<div class=3D"gmail_extra">and so far I have been using hacks.=A0<br><br></=
div><div class=3D"gmail_extra"><br></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--001a11c1d7e0318e4d04ef689caa--

.

------=_Part_299_26729894.1389271377819
Content-Type: text/plain; charset=ISO-8859-1



(Sorry, not sure why my previous reply got deleted. Here it is again.)

However, it is not clear to me why it wouldn't be useful in std::set too? I
have some use of sets which needs to overwrite values even if the compare
equally, and so far I have been using hacks.

The reason is of course that keys are immutable, and so there's no sensible
notion of reassigning keys. For the same reason, I don't have any
provisions in my proposal to mutate keys, either.

There's a general problem in principle with keys that are unique-ownership
types: You can't really search for a key that's unique, since you don't
have a second copy that you could search for! The answer to this are
"transparent comparators", which have been introduced in C++14, which allow
non-homogenous comparators. In any event, that's outside the scope of this
proposal (unless someone sees an elegant way of incorporating this).

An alterantive which I did briefly consider would be to say something like
"delete the existing node and insert a new node constructed from the
arguments". That way, no assignment would take place, only construction and
destruction. However, this would invalidate the current iterator, which
goes against the design of node-based containers, and would be at odds with
the existing insert()/emplace() semantics.

(You could take this to an extreme, and tr to abolish all assignments from
the language in favour of destroy-reconstruct. However, this comes with its
own set of problems.)

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_299_26729894.1389271377819
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><span id=3D"docs-internal-guid-2cf4661c-7706-3bd2-46c7-289=
b1461a1d7"><p dir=3D"ltr" style=3D"line-height:1.5;margin-top:0pt;margin-bo=
ttom:0pt;text-align: justify;"><span style=3D"font-family: Arial; white-spa=
ce: pre-wrap;">(Sorry, not sure why my previous reply got deleted. Here it =
is again.)</span></p></span><br>However, it is not clear to me why it would=
n't be useful in std::set too? I have some use of sets which needs to overw=
rite values even if the compare equally, and so far I have been using hacks=
.. <br><span><br><span style=3D"font-family: Arial; white-space: pre-wrap;">=
</span><p dir=3D"ltr" style=3D"line-height:1.5;margin-top:0pt;margin-bottom=
:0pt;text-align: justify;"><span style=3D"font-family: Arial; white-space: =
pre-wrap;">The reason is of course that keys are immutable, and so there's =
no sensible notion of reassigning keys. For the same reason, I don't have a=
ny provisions in my proposal to mutate keys, either.</span></p><br><span st=
yle=3D"font-family: Arial; white-space: pre-wrap;"></span><p dir=3D"ltr" st=
yle=3D"line-height:1.5;margin-top:0pt;margin-bottom:0pt;text-align: justify=
;"><span style=3D"font-family: Arial; white-space: pre-wrap;">There's a gen=
eral problem in principle with keys that are unique-ownership types: You ca=
n't really search for a key that's unique, since you don't have a second co=
py that you could search for! The answer to this are "transparent comparato=
rs", which have been introduced in C++14, which allow non-homogenous compar=
ators. In any event, that's outside the scope of this proposal (unless some=
one sees an elegant way of incorporating this).</span></p><br><span style=
=3D"font-family: Arial; white-space: pre-wrap;"></span><p dir=3D"ltr" style=
=3D"line-height:1.5;margin-top:0pt;margin-bottom:0pt;text-align: justify;">=
<span style=3D"font-family: Arial; white-space: pre-wrap;">An alterantive w=
hich I did briefly consider would be to say something like "delete the exis=
ting node and insert a new node constructed from the arguments". That way, =
no assignment would take place, only construction and destruction. However,=
 this would invalidate the current iterator, which goes against the design =
of node-based containers, and would be at odds with the existing insert()/e=
mplace() semantics.</span></p><br><span style=3D"font-family: Arial; white-=
space: pre-wrap;"></span><span style=3D"font-family: Arial; white-space: pr=
e-wrap;">(You could take this to an extreme, and tr to abolish </span><span=
 style=3D"font-family: Arial; font-style: italic; white-space: pre-wrap;">a=
ll</span><span style=3D"font-family: Arial; white-space: pre-wrap;"> assign=
ments from the language in favour of destroy-reconstruct. However, this com=
es with its own set of problems.)</span></span></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_299_26729894.1389271377819--

.

--047d7b33d75eafea7304ef898169
Content-Type: text/plain; charset=ISO-8859-1

I see, thanks for the explaination.
My use of key values (in the specific cases I was talking about) is
actually surprising to some people (I asked to some experts online) and I
certainly did something wrong, which explain why I didn't understand.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

--047d7b33d75eafea7304ef898169
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra">I see, thanks for the explainat=
ion.<br>My use of key values (in the specific cases I was talking about) is=
 actually surprising to some people (I asked to some experts online) and I =
certainly did something wrong, which explain why I didn&#39;t understand.<b=
r>
<br></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--047d7b33d75eafea7304ef898169--

.

------=_Part_7904_17878698.1389181023473
Content-Type: text/plain; charset=ISO-8859-1


>
> However, it is not clear to me why it wouldn't be useful in std::set too?
> I have some use of sets which needs to overwrite values even if the compare
> equally, and so far I have been using hacks.
>

Well, sets don't support mutating the key. For the same reason, my proposal
doesn't have any part that attempt to mutate the key, either.

I was actually thinking about this (but then deemed it outside the scope of
what I was trying to achieve): Instead of *reassigning* the mapped element,
the "always-insert" function could have mandated that the existing node be
destroyed and a new node, constructed from the arguments, be inserted in
its place. That too would be efficient, but it invalidates the current
iterator, unlike the proposal, and unlike the original insert()/emplace().
You could do that with a set, too, i.e. "if the key compares equal, destroy
the existing node and insert an node constructed from the arguments", but
that suffers the same problem and doesn't appear all that useful to me.

(You could take this idea to an extreme and get rid of *all* assignment
operators by replacing assignment with "destroy-and-reconstruct", but that
comes with its own set of problems<http://stackoverflow.com/questions/8829548/can-i-get-a-fresh-start-in-c-without-failing-again>
..)

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_7904_17878698.1389181023473
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"l=
tr"><div>However, it is not clear to me why it wouldn't be useful in std::s=
et too? I have some use of sets which needs to overwrite values even if the=
 compare equally, and so far I have been using hacks.&nbsp;</div></div></bl=
ockquote><div><br></div><div>Well, sets don't support mutating the key. For=
 the same reason, my proposal doesn't have any part that attempt to mutate =
the key, either.</div><div><br></div><div>I was actually thinking about thi=
s (but then deemed it outside the scope of what I was trying to achieve): I=
nstead of <i>reassigning</i> the mapped element, the "always-insert" functi=
on could have mandated that the existing node be destroyed and a new node, =
constructed from the arguments, be inserted in its place. That too would be=
 efficient, but it invalidates the current iterator, unlike the proposal, a=
nd unlike the original insert()/emplace(). You could do that with a set, to=
o, i.e. "if the key compares equal, destroy the existing node and insert an=
 node constructed from the arguments", but that suffers the same problem an=
d doesn't appear all that useful to me.</div><div><br></div><div>(You could=
 take this idea to an extreme and get rid of <i>all</i> assignment operator=
s by replacing assignment with "destroy-and-reconstruct", but that comes&nb=
sp;<a href=3D"http://stackoverflow.com/questions/8829548/can-i-get-a-fresh-=
start-in-c-without-failing-again">with its own set of problems</a>.)</div><=
/div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_7904_17878698.1389181023473--

.

------=_Part_346_21137221.1389271175908
Content-Type: text/plain; charset=UTF-8

(Sorry, not sure why my previous reply got deleted. Here it is again.)

However, it is not clear to me why it wouldn't be useful in std::set too? I
> have some use of sets which needs to overwrite values even if the compare
> equally, and so far I have been using hacks.
>

The reason is of course that keys are immutable, and so there's no sensible
notion of reassigning keys. For the same reason, I don't have any
provisions in my proposal to mutate keys, either.

There's a general problem in principle with keys that are unique-ownership
types: You can't really search for a key that's unique, since you don't
have a second copy that you could search for! The answer to this are
"transparent comparators", which have been introduced in C++14, which allow
non-homogenous comparators. In any event, that's outside the scope of this
proposal (unless someone sees an elegant way of incorporating this).

An alterantive which I did briefly consider would be to say something like
"delete the existing node and insert a new node constructed from the
arguments". That way, no assignment would take place, only construction and
destruction. However, this would invalidate the current iterator, which
goes against the design of node-based containers, and would be at odds with
the existing insert()/emplace() semantics.

(You could take this to an extreme, and tr to abolish *all* assignments
from the language in favour of destroy-reconstruct. However, this isn't
feasible, as for example discussed in this Stack Overflow post<http://stackoverflow.com/questions/8829548/can-i-get-a-fresh-start-in-c-without-failing-again>
..)

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_346_21137221.1389271175908
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">(Sorry, not sure why my previous reply got deleted. Here i=
t is again.)<div><br><div><blockquote class=3D"gmail_quote" style=3D"margin=
: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div=
 dir=3D"ltr"><div>However, it is not clear to me why it wouldn't be useful =
in std::set too? I have some use of sets which needs to overwrite values ev=
en if the compare equally, and so far I have been using hacks.&nbsp;</div><=
/div></blockquote><div><br></div><div>The reason is of course that keys are=
 immutable, and so there's no sensible notion of reassigning keys. For the =
same reason, I don't have any provisions in my proposal to mutate keys, eit=
her.</div></div></div><div><br></div><div>There's a general problem in prin=
ciple with keys that are unique-ownership types: You can't really search fo=
r a key that's unique, since you don't have a second copy that you could se=
arch for! The answer to this are "transparent comparators", which have been=
 introduced in C++14, which allow non-homogenous comparators. In any event,=
 that's outside the scope of this proposal (unless someone sees an elegant =
way of incorporating this).</div><div><br></div><div>An alterantive which I=
 did briefly consider would be to say something like "delete the existing n=
ode and insert a new node constructed from the arguments". That way, no ass=
ignment would take place, only construction and destruction. However, this =
would invalidate the current iterator, which goes against the design of nod=
e-based containers, and would be at odds with the existing insert()/emplace=
() semantics.</div><div><br></div><div>(You could take this to an extreme, =
and tr to abolish <i>all</i> assignments from the language in favour of des=
troy-reconstruct. However, this isn't feasible, as for example discussed in=
 <a href=3D"http://stackoverflow.com/questions/8829548/can-i-get-a-fresh-st=
art-in-c-without-failing-again">this Stack Overflow post</a>.)</div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_346_21137221.1389271175908--

.

--001a1134536eeab6ff04eff77ddd
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Tue, Jan 7, 2014 at 1:39 PM, <tkoeppe@google.com> wrote:

> I would like to propose a small addition to the standard library "map" an=
d
> "unordered_map" containers to overcome some limitiations and relax some
> unnecessary restrictions.
>

Sorry if I'm missing something obvious, but couldn't this issue (and
perhaps the proposed fix) also apply to std::set and std::unordered_set?


>
> Here is a small, motivating example (all in namespace std, for brevity):
>
> *// Setup*
> *map<string, unique_ptr<Foo>> m;*
> *static_cast<void>(m["foo"]);*
>
> *// The problem*
> *unique_ptr<Foo> p(new Foo);*
> *auto it =3D m.emplace(**"foo"**, move(p));*
>
>
> Question: What is the state of *p*? Has it been moved from or not?
>
> The answer is in fact that it depends on your library implementation.
> Specifically, it may depend on something like whether internal helper
> functions use deducing templates or "value_type &&" arguments -- in fact,
> GCC 4.6.3 and GCC 4.8.2 give different answers (and it also differs betwe=
en
> ordered and unordered map).
>
> *The problem* is that insert() may fail and not perform an insertion (if
> the key already exists), but in that case it is *unspecified* whether
> arguments are moved-from.
>
> *The solution*, after deliberation and discussion, is to propose
> additional interfaces. Those will turn out to have further benefits besid=
es
> solving the above problem, which are discussed below:
>
> Add the following interfaces to std::map and std::unordered_map:
>
> *pair<iterator, bool>*
>
> *stable_insert(key_type const & k, mapped_type const & v)*
>
>
> *pair<iterator, bool>*
>
> *stable_insert(key_type const & k, mapped_type && v)*
>
>
> *template <typename ...Args>*
>
> *pair<iterator, bool>*
>
> *stable_emplace(key_type const & k, Args &&... args)*
>
>
> *Description:* If the key *k* already exists in the map, does nothing.
> Otherwise, inserts the element constructed from the arguments into the ma=
p.
> Returns [the same as insert/emplace].
>
> *Additional guarantee:* If the key already exists, no dynamic allocations
> are performed and no exceptions are thrown.
>
> Also add the following:
>
> *pair<iterator, bool>*
>
> *always_insert(value_type const & x)*
>
>
> *pair<iterator, bool>*
>
> *always_insert(value_type && x)*
>
>
> *template <typename ...Args>*
>
> *pair<iterator, bool>*
>
> *always_emplace(Args &&... args)*
>
>
> Description: Inserts the element constructed from the arguments at the ke=
y
> determined by that element. Returns: The iterator to the inserted element
> and a boolean indicating whether the key had already existed prior to the
> insertion. Note: This is an improved version of =E2=80=9C*m[k] =3D v;*=E2=
=80=9D which does
> not require unnecessary default construction and returns a more informati=
ve
> result.
>
>
> *A non-solution: *I would like to stress that neither of the following
> "alternatives" works:
>
>    -
>    - m.emplace(k, move(v))
>    m.insert(make_pair(k, move(v)))   // or similar
>    This may create a pair object irrespective of whether the key already
>    exists. The problem here is that this takes ownership of move-only obj=
ects
>    without guaranteeing that the acquired object is stored or destroyed
>    immediately.
>
>    - m.insert(pair<K &&, T &&>(move(k), move(v))
>    Likewise, this may or may not create a pair object even when the key
>    already exists. This one is even more insidious, since it may look lik=
e the
>    caller retains ownership if the insertion does not take place, but thi=
s is
>    in fact not guaranteed. (The implementation may internally create a ne=
w pair<K
>    const, T> from the arguments before checking whether the insertion is
>    needed.)
>
> *A bit of discussion.* Several real-world codebases include helper
> functions to perform "unconditional insertions" ("insert-or-update") into
> maps. All of them require boilerplate, some are inefficient, and none are
> elegant. Here are a few possible implementations:
>
>    - m[k] =3D v; or m[k] =3D move(v);
>    This always default-constructs an element, even though it is
>    immediately assigned-to. (Actually, this *requires*default-constructbi=
lity in the first place, which isn't even necessary
>    otherwise.)
>    - auto it =3D find(k) followed by insert() or *it =3D move(v)
>    Not terrible, but it performs the map search (tree walk or hashing)
>    twice.
>    - auto it =3D lower_bound(k) followed by hinted insertion
>    Near-optimal for std::map, but specific to the container (i.e. does
>    not work for unordered maps), and few people remember this one. Moreov=
er,
>    there is no analogue for std::unordered_map that would avoid repeated
>    hashing.
>
> The proposed new stable-insert/always-insert interfaces would remedy all
> this. They're as efficient as possible. Implementation is a
> straight-forward modification (at least as far as I can tell from
> libstdc++). Usage is straight-forward, too, and fairly self-explanatory
> (modulu figuring out good names for the functions). Finally, the return
> value adds useful information in the case of always-insert which isn't
> available with the operator[]-approach, and which is essentially free to
> obtain.
>
> What sets this interface apart from the other standard library containers
> is that every other interface operates only in terms of the container's
> *value_type*. For this proposal, it is necessary to separate out the
> *key_type* and the *mapped_type*. Perhaps this departure from the norm is
> why such an interface has been missing till now, and at the same time I
> would hope that this is an argument in its favour. It would essentially g=
o
> under a "specialized algorithms" section.
>
> Many thanks, and I would appreaciate your feedback greatly!
>
> Thomas
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

--001a1134536eeab6ff04eff77ddd
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Tue, Jan 7, 2014 at 1:39 PM,  <span dir=3D"ltr">&lt;<a href=3D"mailto:tk=
oeppe@google.com" target=3D"_blank">tkoeppe@google.com</a>&gt;</span> wrote=
:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-le=
ft:1px #ccc solid;padding-left:1ex">
<div dir=3D"ltr">I would like to propose a small addition to the standard l=
ibrary &quot;map&quot; and &quot;unordered_map&quot; containers to overcome=
 some limitiations and relax some unnecessary restrictions.</div></blockquo=
te>
<div><br></div><div>Sorry if I&#39;m missing something obvious, but couldn&=
#39;t this issue (and perhaps the proposed fix) also apply to std::set and =
std::unordered_set?</div><div>=C2=A0</div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir=3D"ltr"><div><br></div><div>Here is a small, motivating example (a=
ll in namespace std, for brevity):</div><div><br></div><blockquote style=3D=
"margin:0 0 0 40px;border:none;padding:0px"><div><font face=3D"courier new,=
 monospace" color=3D"#660000"><b>// Setup</b></font></div>
<div><div><font face=3D"courier new, monospace" color=3D"#660000"><b>map&lt=
;string, unique_ptr&lt;Foo&gt;&gt; m;</b></font></div></div><div><div><font=
 face=3D"courier new, monospace" color=3D"#660000"><b>static_cast&lt;void&g=
t;(m[&quot;foo&quot;]);</b></font></div>
</div><div><div><font face=3D"courier new, monospace" color=3D"#660000"><b>=
<br></b></font></div></div><div><div><font face=3D"courier new, monospace" =
color=3D"#660000"><b>// The problem</b></font></div></div><div><div><font f=
ace=3D"courier new, monospace" color=3D"#660000"><b>unique_ptr&lt;Foo&gt; p=
(new Foo);</b></font></div>
</div><div><div><font face=3D"courier new, monospace" color=3D"#660000"><b>=
auto it =3D m.emplace(</b></font><b style=3D"color:rgb(102,0,0);font-family=
:&#39;courier new&#39;,monospace">&quot;foo&quot;</b><b style=3D"color:rgb(=
102,0,0);font-family:&#39;courier new&#39;,monospace">, move(p));</b></div>
</div></blockquote><div><br></div><div>Question: What is the state of <font=
 face=3D"courier new, monospace"><b>p</b></font>? Has it been moved from or=
 not?</div><div><br></div><div>The answer is in fact that it depends on you=
r library implementation. Specifically, it may depend on something like whe=
ther internal helper functions use deducing templates or &quot;value_type &=
amp;&amp;&quot; arguments -- in fact, GCC 4.6.3 and GCC 4.8.2 give differen=
t answers (and it also differs between ordered and unordered map).</div>
<div><br></div><div><b>The problem</b> is that insert() may fail and not pe=
rform an insertion (if the key already exists), but in that case it is <i>u=
nspecified</i> whether arguments are moved-from.</div><div><br></div><div>
<b>The solution</b>, after deliberation and discussion, is to propose addit=
ional interfaces. Those will turn out to have further benefits besides solv=
ing the above problem, which are discussed below:</div><div><br></div><bloc=
kquote style=3D"margin:0 0 0 40px;border:none;padding:0px">
<div><div><font color=3D"#274e13">Add the following interfaces to std::map =
and std::unordered_map:</font></div></div><div><div><font color=3D"#274e13"=
><br></font></div></div></blockquote><blockquote style=3D"margin:0 0 0 40px=
;border:none;padding:0px">
<blockquote style=3D"margin:0 0 0 40px;border:none;padding:0px"><div><div><=
font color=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;iterator,=
 bool&gt;</b></font></div></div></blockquote><blockquote style=3D"margin:0 =
0 0 40px;border:none;padding:0px">
<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>stable=
_insert(key_type const &amp; k, mapped_type const &amp; v)</b></font></div>=
</div></blockquote><blockquote style=3D"margin:0 0 0 40px;border:none;paddi=
ng:0px">
<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b><br></=
b></font></div></div></blockquote><blockquote style=3D"margin:0 0 0 40px;bo=
rder:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier ne=
w, monospace"><b>pair&lt;iterator, bool&gt;</b></font></div>
</div></blockquote><blockquote style=3D"margin:0 0 0 40px;border:none;paddi=
ng:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monospace"><=
b>stable_insert(key_type const &amp; k, mapped_type &amp;&amp; v)</b></font=
></div>
</div></blockquote><blockquote style=3D"margin:0 0 0 40px;border:none;paddi=
ng:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monospace"><=
b><br></b></font></div></div></blockquote><blockquote style=3D"margin:0 0 0=
 40px;border:none;padding:0px">
<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>templa=
te &lt;typename ...Args&gt;</b></font></div></div></blockquote><blockquote =
style=3D"margin:0 0 0 40px;border:none;padding:0px"><div><div><font color=
=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;iterator, bool&gt;<=
/b></font></div>
</div></blockquote><blockquote style=3D"margin:0 0 0 40px;border:none;paddi=
ng:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monospace"><=
b>stable_emplace(key_type const &amp; k, Args &amp;&amp;... args)</b></font=
></div>
</div></blockquote></blockquote><blockquote style=3D"margin:0 0 0 40px;bord=
er:none;padding:0px"><div><div><font color=3D"#274e13"><br></font></div></d=
iv><div><div><font color=3D"#274e13"><b>Description:</b> If the key <b><fon=
t face=3D"courier new, monospace">k</font></b> already exists in the map, d=
oes nothing. Otherwise, inserts the element constructed from the arguments =
into the map. Returns [the same as insert/emplace].</font></div>
</div><div><div><font color=3D"#274e13"><br></font></div></div><div><div><f=
ont color=3D"#274e13"><b>Additional guarantee:</b> If the key already exist=
s, no dynamic allocations are performed and no exceptions are thrown.</font=
></div>
</div><div><div><font color=3D"#274e13"><br></font></div></div><div><div><f=
ont color=3D"#274e13">Also add the following:</font></div></div><div><div><=
font color=3D"#274e13"><br></font></div></div></blockquote><blockquote styl=
e=3D"margin:0 0 0 40px;border:none;padding:0px">
<blockquote style=3D"margin:0 0 0 40px;border:none;padding:0px"><div><div><=
font color=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;iterator,=
 bool&gt;</b></font></div></div></blockquote><blockquote style=3D"margin:0 =
0 0 40px;border:none;padding:0px">
<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always=
_insert(value_type const &amp; x)</b></font></div></div></blockquote><block=
quote style=3D"margin:0 0 0 40px;border:none;padding:0px"><div><div><font c=
olor=3D"#274e13" face=3D"courier new, monospace"><b><br>
</b></font></div></div></blockquote><blockquote style=3D"margin:0 0 0 40px;=
border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier =
new, monospace"><b>pair&lt;iterator, bool&gt;</b></font></div></div></block=
quote>
<blockquote style=3D"margin:0 0 0 40px;border:none;padding:0px"><div><div><=
font color=3D"#274e13" face=3D"courier new, monospace"><b>always_insert(val=
ue_type &amp;&amp; x)</b></font></div></div></blockquote><blockquote style=
=3D"margin:0 0 0 40px;border:none;padding:0px">
<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b><br></=
b></font></div></div></blockquote><blockquote style=3D"margin:0 0 0 40px;bo=
rder:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier ne=
w, monospace"><b>template &lt;typename ...Args&gt;</b></font></div>
</div></blockquote><blockquote style=3D"margin:0 0 0 40px;border:none;paddi=
ng:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monospace"><=
b>pair&lt;iterator, bool&gt;</b></font></div></div></blockquote><blockquote=
 style=3D"margin:0 0 0 40px;border:none;padding:0px">
<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always=
_emplace(Args &amp;&amp;... args)</b></font></div></div></blockquote></bloc=
kquote><blockquote style=3D"margin:0 0 0 40px;border:none;padding:0px"><div=
><div>
<font color=3D"#274e13"><br></font></div></div><div><div><font color=3D"#27=
4e13">Description: Inserts the element constructed from the arguments at th=
e key determined by that element. Returns: The iterator to the inserted ele=
ment and a boolean indicating whether the key had already existed prior to =
the insertion. Note: This is an improved version of =E2=80=9C<b><font face=
=3D"courier new, monospace">m[k] =3D v;</font></b>=E2=80=9D which does not =
require unnecessary default construction and returns a more informative res=
ult.</font></div>
</div></blockquote><div><br></div><div><b>A non-solution: </b>I would like =
to stress that neither of the following &quot;alternatives&quot; works:</di=
v><div><ul><li></li><li><font face=3D"courier new, monospace"><span style=
=3D"line-height:normal">m.emplace(k, move(v))<br>
</span><span style=3D"line-height:normal">m.insert(make_pair(k, move(v))) =
=C2=A0 // or similar<br></span></font><span style=3D"line-height:normal">Th=
is may create a pair object irrespective of whether the key already exists.=
 The problem here is that this takes ownership of move-only objects without=
 guaranteeing that the acquired object is stored or destroyed immediately.<=
br>
<br></span></li><li><span style=3D"line-height:normal"><font face=3D"courie=
r new, monospace">m.insert(pair&lt;K &amp;&amp;, T &amp;&amp;&gt;(move(k), =
move(v))</font><br></span><span style=3D"line-height:normal">Likewise, this=
 may or may not create a pair object even when the key already exists. This=
 one is even more insidious, since it may look like the caller retains owne=
rship if the insertion does not take place, but this is in fact not guarant=
eed. (The implementation may internally create a new <font face=3D"courier =
new, monospace">pair&lt;K const, T&gt;</font> from the arguments before che=
cking whether the insertion is needed.)</span></li>
</ul></div><div><b>A bit of discussion.</b>=C2=A0Several real-world codebas=
es include helper functions to perform &quot;unconditional insertions&quot;=
 (&quot;insert-or-update&quot;) into maps. All of them require boilerplate,=
 some are inefficient, and none are elegant. Here are a few possible implem=
entations:</div>
<div><ul><li><font face=3D"courier new, monospace" style=3D"line-height:nor=
mal">m[k] =3D v;</font> or <font face=3D"courier new, monospace"><span styl=
e=3D"line-height:normal">m[k] =3D move(v);</span></font><br><span style=3D"=
line-height:normal">This always default-constructs an element, even though =
it is immediately assigned-to. (Actually, this <i>requires</i> default-cons=
tructbility in the first place, which isn&#39;t even necessary otherwise.)<=
/span></li>
<li><font face=3D"courier new, monospace"><span style=3D"line-height:normal=
">auto it =3D find(k)</span></font> followed by <font face=3D"courier new, =
monospace"><span style=3D"line-height:normal">insert()</span></font> or <fo=
nt face=3D"courier new, monospace"><span style=3D"line-height:normal">*it =
=3D move(v)</span></font><br>
Not terrible, but it performs the map search (tree walk or hashing) twice.<=
/li><li><font face=3D"courier new, monospace">auto it =3D lower_bound(k)</f=
ont> followed by hinted insertion<br>Near-optimal for std::map, but specifi=
c to the container (i.e. does not work for unordered maps), and few people =
remember this one. Moreover, there is no analogue for std::unordered_map th=
at would avoid repeated hashing.</li>
</ul><div><span style=3D"line-height:17px">The proposed new stable-insert/a=
lways-insert interfaces would remedy all this. They&#39;re as efficient as =
possible. Implementation is a straight-forward modification (at least as fa=
r as I can tell from libstdc++). Usage is straight-forward, too, and fairly=
 self-explanatory (modulu figuring out good names for the functions). Final=
ly, the return value adds useful information in the case of always-insert w=
hich isn&#39;t available with the operator[]-approach, and which is essenti=
ally free to obtain.</span></div>
</div><div><span style=3D"line-height:17px"><br></span></div><div><span sty=
le=3D"line-height:17px">What sets this interface apart from the other stand=
ard library containers is that every other interface operates only in terms=
 of the container&#39;s <font face=3D"courier new, monospace"><b>value_type=
</b></font>. For this proposal, it is necessary to separate out the <font f=
ace=3D"courier new, monospace"><b>key_type</b></font> and the <font face=3D=
"courier new, monospace"><b>mapped_type</b></font>. Perhaps this departure =
from the norm is why such an interface has been missing till now, and at th=
e same time I would hope that this is an argument in its favour. It would e=
ssentially go under a &quot;specialized algorithms&quot; section.</span></d=
iv>
<div><span style=3D"line-height:17px"><br></span></div><div><span style=3D"=
line-height:17px">Many thanks, and I would appreaciate your feedback greatl=
y!</span></div><span class=3D"HOEnZb"><font color=3D"#888888"><div><span st=
yle=3D"line-height:17px"><br>
</span></div><div><span style=3D"line-height:17px">Thomas</span></div></fon=
t></span></div><span class=3D"HOEnZb"><font color=3D"#888888">

<p></p>

-- <br>
=C2=A0<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</font></span></blockquote></div><br></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--001a1134536eeab6ff04eff77ddd--

.

--001a11c300a645d59f04eff7dafc
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Tue, Jan 14, 2014 at 4:35 PM, Geoffrey Romer <gromer@google.com> wrote:

>
> On Tue, Jan 7, 2014 at 1:39 PM, <tkoeppe@google.com> wrote:
>
>> I would like to propose a small addition to the standard library "map"
>> and "unordered_map" containers to overcome some limitiations and relax s=
ome
>> unnecessary restrictions.
>>
>
> Sorry if I'm missing something obvious, but couldn't this issue (and
> perhaps the proposed fix) also apply to std::set and std::unordered_set?
>

Sorry, I overlooked the prior discussion of this point, which explains why
set::always_* might not make sense. However, I don't see why the basic
problem of recovering from failed insertion, and consequently the solution
of stable_* methods, don't apply to set.


Also, a couple more comments:

Shouldn't basically all the methods you propose have overloads that take a
const_iterator hint, for consistency with the existing insert/emplace
methods?


>
>
>>
>> Here is a small, motivating example (all in namespace std, for brevity):
>>
>> *// Setup*
>> *map<string, unique_ptr<Foo>> m;*
>> *static_cast<void>(m["foo"]);*
>>
>> *// The problem*
>> *unique_ptr<Foo> p(new Foo);*
>> *auto it =3D m.emplace(**"foo"**, move(p));*
>>
>>
>> Question: What is the state of *p*? Has it been moved from or not?
>>
>> The answer is in fact that it depends on your library implementation.
>> Specifically, it may depend on something like whether internal helper
>> functions use deducing templates or "value_type &&" arguments -- in fact=
,
>> GCC 4.6.3 and GCC 4.8.2 give different answers (and it also differs betw=
een
>> ordered and unordered map).
>>
>> *The problem* is that insert() may fail and not perform an insertion (if
>> the key already exists), but in that case it is *unspecified* whether
>> arguments are moved-from.
>>
>> *The solution*, after deliberation and discussion, is to propose
>> additional interfaces. Those will turn out to have further benefits besi=
des
>> solving the above problem, which are discussed below:
>>
>> Add the following interfaces to std::map and std::unordered_map:
>>
>> *pair<iterator, bool>*
>>
>> *stable_insert(key_type const & k, mapped_type const & v)*
>>
>>
>> *pair<iterator, bool>*
>>
>> *stable_insert(key_type const & k, mapped_type && v)*
>>
>>
Couldn't these just be combined into

pair<iterator, bool>
stable_insert(key_type const & k, mapped_type v)

This is less consistent with ordinary insert(), but IIUC the overloading of
insert() is a historical artifact, since removing const value_type&
overload could break existing code. That's not a consideration here.


>
>>  *template <typename ...Args>*
>>
>> *pair<iterator, bool>*
>>
>> *stable_emplace(key_type const & k, Args &&... args)*
>>
>>
>> *Description:* If the key *k* already exists in the map, does nothing.
>> Otherwise, inserts the element constructed from the arguments into the m=
ap.
>> Returns [the same as insert/emplace].
>>
>> *Additional guarantee:* If the key already exists, no dynamic
>> allocations are performed and no exceptions are thrown.
>>
>> Also add the following:
>>
>> *pair<iterator, bool>*
>>
>> *always_insert(value_type const & x)*
>>
>>
>> *pair<iterator, bool>*
>>
>> *always_insert(value_type && x)*
>>
>>
>> *template <typename ...Args>*
>>
>> *pair<iterator, bool>*
>>
>> *always_emplace(Args &&... args)*
>>
>>
I know you've heard from me before on this subject, but I still think it
will cause confusion that the stable_* methods have a separate key arg,
whereas the always_* methods (like the plain ones) do not. I don't know
what to do about it, though.


>
>> Description: Inserts the element constructed from the arguments at the
>> key determined by that element. Returns: The iterator to the inserted
>> element and a boolean indicating whether the key had already existed pri=
or
>> to the insertion. Note: This is an improved version of =E2=80=9C*m[k] =
=3D v;*=E2=80=9D
>> which does not require unnecessary default construction and returns a mo=
re
>> informative result.
>>
>>
>> *A non-solution: *I would like to stress that neither of the following
>> "alternatives" works:
>>
>>    -
>>    - m.emplace(k, move(v))
>>    m.insert(make_pair(k, move(v)))   // or similar
>>    This may create a pair object irrespective of whether the key already
>>    exists. The problem here is that this takes ownership of move-only ob=
jects
>>    without guaranteeing that the acquired object is stored or destroyed
>>    immediately.
>>
>>    - m.insert(pair<K &&, T &&>(move(k), move(v))
>>    Likewise, this may or may not create a pair object even when the key
>>    already exists. This one is even more insidious, since it may look li=
ke the
>>    caller retains ownership if the insertion does not take place, but th=
is is
>>    in fact not guaranteed. (The implementation may internally create a n=
ew pair<K
>>    const, T> from the arguments before checking whether the insertion is
>>    needed.)
>>
>> *A bit of discussion.* Several real-world codebases include helper
>> functions to perform "unconditional insertions" ("insert-or-update") int=
o
>> maps. All of them require boilerplate, some are inefficient, and none ar=
e
>> elegant. Here are a few possible implementations:
>>
>>    - m[k] =3D v; or m[k] =3D move(v);
>>    This always default-constructs an element, even though it is
>>    immediately assigned-to. (Actually, this *requires*default-constructb=
ility in the first place, which isn't even necessary
>>    otherwise.)
>>    - auto it =3D find(k) followed by insert() or *it =3D move(v)
>>    Not terrible, but it performs the map search (tree walk or hashing)
>>    twice.
>>    - auto it =3D lower_bound(k) followed by hinted insertion
>>    Near-optimal for std::map, but specific to the container (i.e. does
>>    not work for unordered maps), and few people remember this one. Moreo=
ver,
>>    there is no analogue for std::unordered_map that would avoid repeated
>>    hashing.
>>
>> The proposed new stable-insert/always-insert interfaces would remedy all
>> this. They're as efficient as possible. Implementation is a
>> straight-forward modification (at least as far as I can tell from
>> libstdc++). Usage is straight-forward, too, and fairly self-explanatory
>> (modulu figuring out good names for the functions). Finally, the return
>> value adds useful information in the case of always-insert which isn't
>> available with the operator[]-approach, and which is essentially free to
>> obtain.
>>
>> What sets this interface apart from the other standard library container=
s
>> is that every other interface operates only in terms of the container's
>> *value_type*. For this proposal, it is necessary to separate out the
>> *key_type* and the *mapped_type*. Perhaps this departure from the norm
>> is why such an interface has been missing till now, and at the same time=
 I
>> would hope that this is an argument in its favour. It would essentially =
go
>> under a "specialized algorithms" section.
>>
>> Many thanks, and I would appreaciate your feedback greatly!
>>
>> Thomas
>>
>> --
>>
>> ---
>> You received this message because you are subscribed to the Google Group=
s
>> "ISO C++ Standard - Future Proposals" group.
>> To unsubscribe from this group and stop receiving emails from it, send a=
n
>> email to std-proposals+unsubscribe@isocpp.org.
>> To post to this group, send email to std-proposals@isocpp.org.
>> Visit this group at
>> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>>
>
>

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

--001a11c300a645d59f04eff7dafc
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Tue, Jan 14, 2014 at 4:35 PM, Geoffrey Romer <span dir=3D"ltr">&lt;<a hr=
ef=3D"mailto:gromer@google.com" target=3D"_blank">gromer@google.com</a>&gt;=
</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=
=3D"gmail_quote">
<div class=3D"im">On Tue, Jan 7, 2014 at 1:39 PM,  <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:tkoeppe@google.com" target=3D"_blank">tkoeppe@google.com</a=
>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);bo=
rder-left-style:solid;padding-left:1ex">

<div dir=3D"ltr">I would like to propose a small addition to the standard l=
ibrary &quot;map&quot; and &quot;unordered_map&quot; containers to overcome=
 some limitiations and relax some unnecessary restrictions.</div></blockquo=
te>

<div><br></div></div><div>Sorry if I&#39;m missing something obvious, but c=
ouldn&#39;t this issue (and perhaps the proposed fix) also apply to std::se=
t and std::unordered_set?</div></div></div></div></blockquote><div><br>
</div><div>Sorry, I overlooked the prior discussion of this point, which ex=
plains why set::always_* might not make sense. However, I don&#39;t see why=
 the basic problem of recovering from failed insertion, and consequently th=
e solution of stable_* methods, don&#39;t apply to set.</div>
<div><br><br></div><div><div class=3D"gmail_extra">Also, a couple more comm=
ents:</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">=
Shouldn&#39;t basically all the methods you propose have overloads that tak=
e a const_iterator hint, for consistency with the existing insert/emplace m=
ethods?</div>
</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);bo=
rder-left-style:solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmai=
l_extra">
<div class=3D"gmail_quote"><div><div class=3D"h5"><div>=C2=A0</div><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-wid=
th:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-l=
eft:1ex">

<div dir=3D"ltr"><div><br></div><div>Here is a small, motivating example (a=
ll in namespace std, for brevity):</div><div><br></div><blockquote style=3D=
"margin:0px 0px 0px 40px;border:none;padding:0px"><div><font face=3D"courie=
r new, monospace" color=3D"#660000"><b>// Setup</b></font></div>

<div><div><font face=3D"courier new, monospace" color=3D"#660000"><b>map&lt=
;string, unique_ptr&lt;Foo&gt;&gt; m;</b></font></div></div><div><div><font=
 face=3D"courier new, monospace" color=3D"#660000"><b>static_cast&lt;void&g=
t;(m[&quot;foo&quot;]);</b></font></div>

</div><div><div><font face=3D"courier new, monospace" color=3D"#660000"><b>=
<br></b></font></div></div><div><div><font face=3D"courier new, monospace" =
color=3D"#660000"><b>// The problem</b></font></div></div><div><div><font f=
ace=3D"courier new, monospace" color=3D"#660000"><b>unique_ptr&lt;Foo&gt; p=
(new Foo);</b></font></div>

</div><div><div><font face=3D"courier new, monospace" color=3D"#660000"><b>=
auto it =3D m.emplace(</b></font><b style=3D"color:rgb(102,0,0);font-family=
:&#39;courier new&#39;,monospace">&quot;foo&quot;</b><b style=3D"color:rgb(=
102,0,0);font-family:&#39;courier new&#39;,monospace">, move(p));</b></div>

</div></blockquote><div><br></div><div>Question: What is the state of <font=
 face=3D"courier new, monospace"><b>p</b></font>? Has it been moved from or=
 not?</div><div><br></div><div>The answer is in fact that it depends on you=
r library implementation. Specifically, it may depend on something like whe=
ther internal helper functions use deducing templates or &quot;value_type &=
amp;&amp;&quot; arguments -- in fact, GCC 4.6.3 and GCC 4.8.2 give differen=
t answers (and it also differs between ordered and unordered map).</div>

<div><br></div><div><b>The problem</b> is that insert() may fail and not pe=
rform an insertion (if the key already exists), but in that case it is <i>u=
nspecified</i> whether arguments are moved-from.</div><div><br></div><div>

<b>The solution</b>, after deliberation and discussion, is to propose addit=
ional interfaces. Those will turn out to have further benefits besides solv=
ing the above problem, which are discussed below:</div><div><br></div>
<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">
<div><div><font color=3D"#274e13">Add the following interfaces to std::map =
and std::unordered_map:</font></div></div><div><div><font color=3D"#274e13"=
><br></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0p=
x 40px;border:none;padding:0px">

<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;ite=
rator, bool&gt;</b></font></div></div></blockquote><blockquote style=3D"mar=
gin:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>stable=
_insert(key_type const &amp; k, mapped_type const &amp; v)</b></font></div>=
</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b><br></=
b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px 4=
0px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"cour=
ier new, monospace"><b>pair&lt;iterator, bool&gt;</b></font></div>

</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monosp=
ace"><b>stable_insert(key_type const &amp; k, mapped_type &amp;&amp; v)</b>=
</font></div>
</div></blockquote></blockquote></div></blockquote></div></div></div></div>=
</div></blockquote><div><br></div><div>Couldn&#39;t these just be combined =
into</div><div><br></div><div><div>pair&lt;iterator, bool&gt;</div><div>
stable_insert(key_type const &amp; k, mapped_type v)</div></div><div><br></=
div><div>This is less consistent with ordinary insert(), but IIUC the overl=
oading of insert() is a historical artifact, since removing const value_typ=
e&amp; overload could break existing code. That&#39;s not a consideration h=
ere.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l=
eft-style:solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extr=
a"><div class=3D"gmail_quote">
<div><div class=3D"h5"><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);bo=
rder-left-style:solid;padding-left:1ex"><div dir=3D"ltr"><blockquote style=
=3D"margin:0px 0px 0px 40px;border:none;padding:0px">
<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>
</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monosp=
ace"><b><br></b></font></div></div></blockquote><blockquote style=3D"margin=
:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>templa=
te &lt;typename ...Args&gt;</b></font></div></div></blockquote><blockquote =
style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font c=
olor=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;iterator, bool&=
gt;</b></font></div>

</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monosp=
ace"><b>stable_emplace(key_type const &amp; k, Args &amp;&amp;... args)</b>=
</font></div>

</div></blockquote></blockquote><blockquote style=3D"margin:0px 0px 0px 40p=
x;border:none;padding:0px"><div><div><font color=3D"#274e13"><br></font></d=
iv></div><div><div><font color=3D"#274e13"><b>Description:</b> If the key <=
b><font face=3D"courier new, monospace">k</font></b> already exists in the =
map, does nothing. Otherwise, inserts the element constructed from the argu=
ments into the map. Returns [the same as insert/emplace].</font></div>

</div><div><div><font color=3D"#274e13"><br></font></div></div><div><div><f=
ont color=3D"#274e13"><b>Additional guarantee:</b> If the key already exist=
s, no dynamic allocations are performed and no exceptions are thrown.</font=
></div>

</div><div><div><font color=3D"#274e13"><br></font></div></div><div><div><f=
ont color=3D"#274e13">Also add the following:</font></div></div><div><div><=
font color=3D"#274e13"><br></font></div></div></blockquote><blockquote styl=
e=3D"margin:0px 0px 0px 40px;border:none;padding:0px">

<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;ite=
rator, bool&gt;</b></font></div></div></blockquote><blockquote style=3D"mar=
gin:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always=
_insert(value_type const &amp; x)</b></font></div></div></blockquote><block=
quote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><=
font color=3D"#274e13" face=3D"courier new, monospace"><b><br>

</b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px=
 40px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"co=
urier new, monospace"><b>pair&lt;iterator, bool&gt;</b></font></div></div><=
/blockquote>

<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always_inse=
rt(value_type &amp;&amp; x)</b></font></div></div></blockquote><blockquote =
style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b><br></=
b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px 4=
0px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"cour=
ier new, monospace"><b>template &lt;typename ...Args&gt;</b></font></div>

</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monosp=
ace"><b>pair&lt;iterator, bool&gt;</b></font></div></div></blockquote><bloc=
kquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always=
_emplace(Args &amp;&amp;... args)</b></font></div></div></blockquote></bloc=
kquote></div></blockquote></div></div></div></div></div></blockquote><div>
<br></div><div>I know you&#39;ve heard from me before on this subject, but =
I still think it will cause confusion that the stable_* methods have a sepa=
rate key arg, whereas the always_* methods (like the plain ones) do not. I =
don&#39;t know what to do about it, though.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l=
eft-style:solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extr=
a"><div class=3D"gmail_quote">
<div><div class=3D"h5"><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);bo=
rder-left-style:solid;padding-left:1ex"><div dir=3D"ltr"><blockquote style=
=3D"margin:0px 0px 0px 40px;border:none;padding:0px">
<div><div>
<font color=3D"#274e13"><br></font></div></div><div><div><font color=3D"#27=
4e13">Description: Inserts the element constructed from the arguments at th=
e key determined by that element. Returns: The iterator to the inserted ele=
ment and a boolean indicating whether the key had already existed prior to =
the insertion. Note: This is an improved version of =E2=80=9C<b><font face=
=3D"courier new, monospace">m[k] =3D v;</font></b>=E2=80=9D which does not =
require unnecessary default construction and returns a more informative res=
ult.</font></div>

</div></blockquote><div><br></div><div><b>A non-solution: </b>I would like =
to stress that neither of the following &quot;alternatives&quot; works:</di=
v><div><ul><li></li><li><font face=3D"courier new, monospace"><span style=
=3D"line-height:normal">m.emplace(k, move(v))<br>

</span><span style=3D"line-height:normal">m.insert(make_pair(k, move(v))) =
=C2=A0 // or similar<br></span></font><span style=3D"line-height:normal">Th=
is may create a pair object irrespective of whether the key already exists.=
 The problem here is that this takes ownership of move-only objects without=
 guaranteeing that the acquired object is stored or destroyed immediately.<=
br>

<br></span></li><li><span style=3D"line-height:normal"><font face=3D"courie=
r new, monospace">m.insert(pair&lt;K &amp;&amp;, T &amp;&amp;&gt;(move(k), =
move(v))</font><br></span><span style=3D"line-height:normal">Likewise, this=
 may or may not create a pair object even when the key already exists. This=
 one is even more insidious, since it may look like the caller retains owne=
rship if the insertion does not take place, but this is in fact not guarant=
eed. (The implementation may internally create a new <font face=3D"courier =
new, monospace">pair&lt;K const, T&gt;</font> from the arguments before che=
cking whether the insertion is needed.)</span></li>

</ul></div><div><b>A bit of discussion.</b>=C2=A0Several real-world codebas=
es include helper functions to perform &quot;unconditional insertions&quot;=
 (&quot;insert-or-update&quot;) into maps. All of them require boilerplate,=
 some are inefficient, and none are elegant. Here are a few possible implem=
entations:</div>

<div><ul><li><font face=3D"courier new, monospace" style=3D"line-height:nor=
mal">m[k] =3D v;</font> or <font face=3D"courier new, monospace"><span styl=
e=3D"line-height:normal">m[k] =3D move(v);</span></font><br><span style=3D"=
line-height:normal">This always default-constructs an element, even though =
it is immediately assigned-to. (Actually, this <i>requires</i> default-cons=
tructbility in the first place, which isn&#39;t even necessary otherwise.)<=
/span></li>

<li><font face=3D"courier new, monospace"><span style=3D"line-height:normal=
">auto it =3D find(k)</span></font> followed by <font face=3D"courier new, =
monospace"><span style=3D"line-height:normal">insert()</span></font> or <fo=
nt face=3D"courier new, monospace"><span style=3D"line-height:normal">*it =
=3D move(v)</span></font><br>

Not terrible, but it performs the map search (tree walk or hashing) twice.<=
/li><li><font face=3D"courier new, monospace">auto it =3D lower_bound(k)</f=
ont> followed by hinted insertion<br>Near-optimal for std::map, but specifi=
c to the container (i.e. does not work for unordered maps), and few people =
remember this one. Moreover, there is no analogue for std::unordered_map th=
at would avoid repeated hashing.</li>

</ul><div><span style=3D"line-height:17px">The proposed new stable-insert/a=
lways-insert interfaces would remedy all this. They&#39;re as efficient as =
possible. Implementation is a straight-forward modification (at least as fa=
r as I can tell from libstdc++). Usage is straight-forward, too, and fairly=
 self-explanatory (modulu figuring out good names for the functions). Final=
ly, the return value adds useful information in the case of always-insert w=
hich isn&#39;t available with the operator[]-approach, and which is essenti=
ally free to obtain.</span></div>

</div><div><span style=3D"line-height:17px"><br></span></div><div><span sty=
le=3D"line-height:17px">What sets this interface apart from the other stand=
ard library containers is that every other interface operates only in terms=
 of the container&#39;s <font face=3D"courier new, monospace"><b>value_type=
</b></font>. For this proposal, it is necessary to separate out the <font f=
ace=3D"courier new, monospace"><b>key_type</b></font> and the <font face=3D=
"courier new, monospace"><b>mapped_type</b></font>. Perhaps this departure =
from the norm is why such an interface has been missing till now, and at th=
e same time I would hope that this is an argument in its favour. It would e=
ssentially go under a &quot;specialized algorithms&quot; section.</span></d=
iv>

<div><span style=3D"line-height:17px"><br></span></div><div><span style=3D"=
line-height:17px">Many thanks, and I would appreaciate your feedback greatl=
y!</span></div><span><font color=3D"#888888"><div><span style=3D"line-heigh=
t:17px"><br>

</span></div><div><span style=3D"line-height:17px">Thomas</span></div></fon=
t></span></div><span><font color=3D"#888888">

<p></p>

-- <br>
=C2=A0<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</font></span></blockquote></div></div></div><br></div></div>
</blockquote></div><br></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--001a11c300a645d59f04eff7dafc--

.

------=_Part_985_6069685.1389785062809
Content-Type: text/plain; charset=UTF-8

On Wednesday, 15 January 2014 01:01:44 UTC, Geoffrey Romer wrote:
>
>
> On Tue, Jan 14, 2014 at 4:35 PM, Geoffrey Romer <gro...@google.com<javascript:>
> > wrote:
>
>>
>> On Tue, Jan 7, 2014 at 1:39 PM, <tko...@google.com <javascript:>> wrote:
>>
>>> I would like to propose a small addition to the standard library "map"
>>> and "unordered_map" containers to overcome some limitiations and relax some
>>> unnecessary restrictions.
>>>
>>
>> Sorry if I'm missing something obvious, but couldn't this issue (and
>> perhaps the proposed fix) also apply to std::set and std::unordered_set?
>>
>
> Sorry, I overlooked the prior discussion of this point, which explains why
> set::always_* might not make sense. However, I don't see why the basic
> problem of recovering from failed insertion, and consequently the solution
> of stable_* methods, don't apply to set.
>

I'm not at all opposed to including sets in the proposal, but at this point
I cannot see the benefit very clearly. In order for the proposal to be
*different* from the existing set interface, you would have to have a
move-only key. In that case, for key insertion to fail you would need to
provide a key that compares equal with an existing key, although it is
"unique". You could probably contrive such applications, but they seem much
rarer to me. I have a note into the actual proposal text, though,
explaining this point and inviting suggestions to broaded the proposal.



> Also, a couple more comments:
>
> Shouldn't basically all the methods you propose have overloads that take a
> const_iterator hint, for consistency with the existing insert/emplace
> methods?
>

Good point. I was thinking that you would use the new methods singularly,
but there's no reason to not accept a hint if for some reason the user has
a useful hint already.



> Add the following interfaces to std::map and std::unordered_map:
>>>
>>> *pair<iterator, bool>*
>>>
>>> *stable_insert(key_type const & k, mapped_type const & v)*
>>>
>>>
>>> *pair<iterator, bool>*
>>>
>>> *stable_insert(key_type const & k, mapped_type && v)*
>>>
>>>
> Couldn't these just be combined into
>
> pair<iterator, bool>
> stable_insert(key_type const & k, mapped_type v)
>
> This is less consistent with ordinary insert(), but IIUC the overloading
> of insert() is a historical artifact, since removing const value_type&
> overload could break existing code. That's not a consideration here.
>

I don't think that would work: The point of "stability" is to accept a
reference and promise not to construct-from it. Passing by value would
unconditionally move-from the original object, wouldn't it?


Also add the following:
>>>
>>> *pair<iterator, bool>*
>>>
>>> *always_insert(value_type const & x)*
>>>
>>>
>>> *pair<iterator, bool>*
>>>
>>> *always_insert(value_type && x)*
>>>
>>>
>>> *template <typename ...Args>*
>>>
>>> *pair<iterator, bool>*
>>>
>>> *always_emplace(Args &&... args)*
>>>
>>>
> I know you've heard from me before on this subject, but I still think it
> will cause confusion that the stable_* methods have a separate key arg,
> whereas the always_* methods (like the plain ones) do not. I don't know
> what to do about it, though.
>

I actually agree. It would probably be saner to give both versions the same
signature. I used to feel that passing a value_type would be less
restrictive that requiring split arguments (especially for emplace), but
I'm more and more offended by the asymmetry now. I will change it.

Thanks for the comments!

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_985_6069685.1389785062809
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, 15 January 2014 01:01:44 UTC, Geoffrey Romer=
  wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0=
..8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div>=
<br><div class=3D"gmail_quote">On Tue, Jan 14, 2014 at 4:35 PM, Geoffrey Ro=
mer <span dir=3D"ltr">&lt;<a href=3D"javascript:" target=3D"_blank" gdf-obf=
uscated-mailto=3D"SZguMyKG8CcJ" onmousedown=3D"this.href=3D'javascript:';re=
turn true;" onclick=3D"this.href=3D'javascript:';return true;">gro...@googl=
e.com</a>&gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div dir=3D"ltr"><div><br><div class=3D"gmail_quote">
<div>On Tue, Jan 7, 2014 at 1:39 PM,  <span dir=3D"ltr">&lt;<a href=3D"java=
script:" target=3D"_blank" gdf-obfuscated-mailto=3D"SZguMyKG8CcJ" onmousedo=
wn=3D"this.href=3D'javascript:';return true;" onclick=3D"this.href=3D'javas=
cript:';return true;">tko...@google.com</a>&gt;</span> wrote:<br><blockquot=
e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width=
:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-lef=
t:1ex">

<div dir=3D"ltr">I would like to propose a small addition to the standard l=
ibrary "map" and "unordered_map" containers to overcome some limitiations a=
nd relax some unnecessary restrictions.</div></blockquote>

<div><br></div></div><div>Sorry if I'm missing something obvious, but could=
n't this issue (and perhaps the proposed fix) also apply to std::set and st=
d::unordered_set?</div></div></div></div></blockquote><div><br>
</div><div>Sorry, I overlooked the prior discussion of this point, which ex=
plains why set::always_* might not make sense. However, I don't see why the=
 basic problem of recovering from failed insertion, and consequently the so=
lution of stable_* methods, don't apply to set.</div></div></div></div></bl=
ockquote><div><br></div><div>I'm not at all opposed to including sets in th=
e proposal, but at this point I cannot see the benefit very clearly. In ord=
er for the proposal to be <i>different</i> from the existing set interface,=
 you would have to have a move-only key. In that case, for key insertion to=
 fail you would need to provide a key that compares equal with an existing =
key, although it is "unique". You could probably contrive such applications=
, but they seem much rarer to me. I have a note into the actual proposal te=
xt, though, explaining this point and inviting suggestions to broaded the p=
roposal.</div><div><br></div><div>&nbsp;</div><blockquote class=3D"gmail_qu=
ote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padd=
ing-left: 1ex;"><div dir=3D"ltr"><div class=3D"gmail_quote">
<div>Also, a couple more comments:<br></div><div><div><br></div><div>Should=
n't basically all the methods you propose have overloads that take a const_=
iterator hint, for consistency with the existing insert/emplace methods?</d=
iv></div></div></div></blockquote><div><br></div><div>Good point. I was thi=
nking that you would use the new methods singularly, but there's no reason =
to not accept a hint if for some reason the user has a useful hint already.=
</div><div><br></div><div>&nbsp;</div><blockquote class=3D"gmail_quote" sty=
le=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left=
: 1ex;"><div dir=3D"ltr"><div class=3D"gmail_quote"><div>
</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b=
order-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:s=
olid;padding-left:1ex"><div dir=3D"ltr"><div><div class=3D"gmail_quote"><di=
v><div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;=
border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:=
solid;padding-left:1ex"><div dir=3D"ltr"><blockquote style=3D"margin:0px 0p=
x 0px 40px;border:none;padding:0px"><div><div><font color=3D"#274e13">Add t=
he following interfaces to std::map and std::unordered_map:</font></div></d=
iv><div><div><font color=3D"#274e13"><br></font></div></div></blockquote><b=
lockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">

<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;ite=
rator, bool&gt;</b></font></div></div></blockquote><blockquote style=3D"mar=
gin:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>stable=
_insert(key_type const &amp; k, mapped_type const &amp; v)</b></font></div>=
</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b><br></=
b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px 4=
0px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"cour=
ier new, monospace"><b>pair&lt;iterator, bool&gt;</b></font></div>

</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monosp=
ace"><b>stable_insert(key_type const &amp; k, mapped_type &amp;&amp; v)</b>=
</font></div>
</div></blockquote></blockquote></div></blockquote></div></div></div></div>=
</div></blockquote><div><br></div><div>Couldn't these just be combined into=
</div><div><br></div><div><div>pair&lt;iterator, bool&gt;</div><div>
stable_insert(key_type const &amp; k, mapped_type v)</div></div><div><br></=
div><div>This is less consistent with ordinary insert(), but IIUC the overl=
oading of insert() is a historical artifact, since removing const value_typ=
e&amp; overload could break existing code. That's not a consideration here.=
</div></div></div></blockquote><div><br></div><div>I don't think that would=
 work: The point of "stability" is to accept a reference and promise not to=
 construct-from it. Passing by value would unconditionally move-from the or=
iginal object, wouldn't it?</div><div>&nbsp;</div><div><br></div><blockquot=
e class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: =
1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div class=3D"gmail_quo=
te"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bor=
der-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:sol=
id;padding-left:1ex"><div dir=3D"ltr"><div><div class=3D"gmail_quote"><div>=
<div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bo=
rder-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:so=
lid;padding-left:1ex"><div dir=3D"ltr"><blockquote style=3D"margin:0px 0px =
0px 40px;border:none;padding:0px"><div><div><font color=3D"#274e13">Also ad=
d the following:</font></div></div><div><div><font color=3D"#274e13"><br></=
font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;=
border:none;padding:0px">

<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;ite=
rator, bool&gt;</b></font></div></div></blockquote><blockquote style=3D"mar=
gin:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always=
_insert(value_type const &amp; x)</b></font></div></div></blockquote><block=
quote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><=
font color=3D"#274e13" face=3D"courier new, monospace"><b><br>

</b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px=
 40px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"co=
urier new, monospace"><b>pair&lt;iterator, bool&gt;</b></font></div></div><=
/blockquote>

<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always_inse=
rt(value_type &amp;&amp; x)</b></font></div></div></blockquote><blockquote =
style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b><br></=
b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px 4=
0px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"cour=
ier new, monospace"><b>template &lt;typename ...Args&gt;</b></font></div>

</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monosp=
ace"><b>pair&lt;iterator, bool&gt;</b></font></div></div></blockquote><bloc=
kquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">

<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always=
_emplace(Args &amp;&amp;... args)</b></font></div></div></blockquote></bloc=
kquote></div></blockquote></div></div></div></div></div></blockquote><div>
<br></div><div>I know you've heard from me before on this subject, but I st=
ill think it will cause confusion that the stable_* methods have a separate=
 key arg, whereas the always_* methods (like the plain ones) do not. I don'=
t know what to do about it, though.</div></div></div></blockquote><div><br>=
</div><div>I actually agree. It would probably be saner to give both versio=
ns the same signature. I used to feel that passing a value_type would be le=
ss restrictive that requiring split arguments (especially for emplace), but=
 I'm more and more offended by the asymmetry now. I will change it.</div><d=
iv>&nbsp;</div><div>Thanks for the comments!</div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_985_6069685.1389785062809--

.

--089e0112cb9e42bca404f002e79d
Content-Type: text/plain; charset=ISO-8859-1

Not pushing for this, just commenting on your response.

On Wed, Jan 8, 2014 at 6:37 AM, <tkoeppe@google.com> wrote:

>
>> Well, sets don't support mutating the key. For the same reason, my
> proposal doesn't have any part that attempt to mutate the key, either.
>

Mutating the key might not be necessary if willing to pay a higher cost.
That is, the operation might find the point of insertion, create a new node
and replace the old node with the new node, then release the old node back
to the allocator. This would not require mutating a key, but it would come
with a higher cost.

The second comment is that the above might not even be necessary. There is
no requirement that keys are 'const' inside the container, only that the
container does not provide access to the keys that would allow user code to
change it. The container might maintain non-const keys internally as long
as both 'iterator' and 'const_iterator' yield const references to them.
This is a big difference from 'std::map', where the keys in the map *must*
be 'const' (you cannot bind a reference to 'pair<const K, T>' to a
'pair<K,T>', but you can always bind a reference 'K const &' to a 'K' value.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

--089e0112cb9e42bca404f002e79d
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra">Not pushing for this, just comm=
enting on your response.<br><br><div class=3D"gmail_quote">On Wed, Jan 8, 2=
014 at 6:37 AM,  <span dir=3D"ltr">&lt;<a href=3D"mailto:tkoeppe@google.com=
" target=3D"_blank">tkoeppe@google.com</a>&gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"im"><blockquo=
te class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
<div dir=3D"ltr"><div><br></div></div></blockquote></div><div>Well, sets do=
n&#39;t support mutating the key. For the same reason, my proposal doesn&#3=
9;t have any part that attempt to mutate the key, either.</div></div></bloc=
kquote>
<div>=A0</div><div>Mutating the key might not be necessary if willing to pa=
y a higher cost. That is, the operation might find the point of insertion, =
create a new node and replace the old node with the new node, then release =
the old node back to the allocator. This would not require mutating a key, =
but it would come with a higher cost.<br>
<br>The second comment is that the above might not even be necessary. There=
 is no requirement that keys are &#39;const&#39; inside the container, only=
 that the container does not provide access to the keys that would allow us=
er code to change it. The container might maintain non-const keys internall=
y as long as both &#39;iterator&#39; and &#39;const_iterator&#39; yield con=
st references to them. This is a big difference from &#39;std::map&#39;, wh=
ere the keys in the map *must* be &#39;const&#39; (you cannot bind a refere=
nce to &#39;pair&lt;const K, T&gt;&#39; to a &#39;pair&lt;K,T&gt;&#39;, but=
 you can always bind a reference &#39;K const &amp;&#39; to a &#39;K&#39; v=
alue.</div>
</div></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--089e0112cb9e42bca404f002e79d--

.

--047d7b676f7c0a6bda04f0041eb1
Content-Type: text/plain; charset=UTF-8

On Wed, Jan 15, 2014 at 3:24 AM, Thomas Koeppe <tkoeppe@google.com> wrote:

> On Wednesday, 15 January 2014 01:01:44 UTC, Geoffrey Romer wrote:
>>
>>
>> On Tue, Jan 14, 2014 at 4:35 PM, Geoffrey Romer <gro...@google.com>wrote:
>>
>>
>>> On Tue, Jan 7, 2014 at 1:39 PM, <tko...@google.com> wrote:
>>>
>>>> I would like to propose a small addition to the standard library "map"
>>>> and "unordered_map" containers to overcome some limitiations and relax some
>>>> unnecessary restrictions.
>>>>
>>>
>>> Sorry if I'm missing something obvious, but couldn't this issue (and
>>> perhaps the proposed fix) also apply to std::set and std::unordered_set?
>>>
>>
>> Sorry, I overlooked the prior discussion of this point, which explains
>> why set::always_* might not make sense. However, I don't see why the basic
>> problem of recovering from failed insertion, and consequently the solution
>> of stable_* methods, don't apply to set.
>>
>
> I'm not at all opposed to including sets in the proposal, but at this
> point I cannot see the benefit very clearly. In order for the proposal to
> be *different* from the existing set interface, you would have to have a
> move-only key. In that case, for key insertion to fail you would need to
> provide a key that compares equal with an existing key, although it is
> "unique". You could probably contrive such applications, but they seem much
> rarer to me. I have a note into the actual proposal text, though,
> explaining this point and inviting suggestions to broaded the proposal.
>

It's not entirely clear to me that move-only types are necessarily
"unique", particularly in sense of STL equivalence or equality, and my
sense is that the STL tends to favor consistency even when that consistency
isn't obviously useful (that's kind of why we're in this mess in the first
place), which would argue for giving sets the same treatment.

That said, so long as you have an explicit key argument, you can't promote
these methods to requirements on the [unordered] associative container
concepts, so maybe the consistency argument doesn't carry as much force.
Also, sets of move-only types are already fairly awkward (since elements
can't be nondestructively removed), so maybe one marginal additional pain
point isn't worth addressing.


>
>
>
>> Also, a couple more comments:
>>
>> Shouldn't basically all the methods you propose have overloads that take
>> a const_iterator hint, for consistency with the existing insert/emplace
>> methods?
>>
>
> Good point. I was thinking that you would use the new methods singularly,
> but there's no reason to not accept a hint if for some reason the user has
> a useful hint already.
>
>
>
>> Add the following interfaces to std::map and std::unordered_map:
>>>>
>>>> *pair<iterator, bool>*
>>>>
>>>> *stable_insert(key_type const & k, mapped_type const & v)*
>>>>
>>>>
>>>> *pair<iterator, bool>*
>>>>
>>>> *stable_insert(key_type const & k, mapped_type && v)*
>>>>
>>>>
>> Couldn't these just be combined into
>>
>> pair<iterator, bool>
>> stable_insert(key_type const & k, mapped_type v)
>>
>> This is less consistent with ordinary insert(), but IIUC the overloading
>> of insert() is a historical artifact, since removing const value_type&
>> overload could break existing code. That's not a consideration here.
>>
>
> I don't think that would work: The point of "stability" is to accept a
> reference and promise not to construct-from it. Passing by value would
> unconditionally move-from the original object, wouldn't it?
>

Ah, you're right. Good point.


>
>
> Also add the following:
>>>>
>>>> *pair<iterator, bool>*
>>>>
>>>> *always_insert(value_type const & x)*
>>>>
>>>>
>>>> *pair<iterator, bool>*
>>>>
>>>> *always_insert(value_type && x)*
>>>>
>>>>
>>>> *template <typename ...Args>*
>>>>
>>>> *pair<iterator, bool>*
>>>>
>>>> *always_emplace(Args &&... args)*
>>>>
>>>>
>> I know you've heard from me before on this subject, but I still think it
>> will cause confusion that the stable_* methods have a separate key arg,
>> whereas the always_* methods (like the plain ones) do not. I don't know
>> what to do about it, though.
>>
>
> I actually agree. It would probably be saner to give both versions the
> same signature. I used to feel that passing a value_type would be less
> restrictive that requiring split arguments (especially for emplace), but
> I'm more and more offended by the asymmetry now. I will change it.
>

> Thanks for the comments!
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

--047d7b676f7c0a6bda04f0041eb1
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Wed, Jan 15, 2014 at 3:24 AM, Thomas Koeppe <span dir=3D"ltr">&lt;<a hre=
f=3D"mailto:tkoeppe@google.com" target=3D"_blank">tkoeppe@google.com</a>&gt=
;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div dir=3D"ltr">On Wednesday, 15 January 2014 01:01:44 UT=
C, Geoffrey Romer  wrote:<blockquote class=3D"gmail_quote" style=3D"margin:=
0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);=
border-left-style:solid;padding-left:1ex">
<div dir=3D"ltr"><div><br><div class=3D"gmail_quote">On Tue, Jan 14, 2014 a=
t 4:35 PM, Geoffrey Romer <span dir=3D"ltr">&lt;<a>gro...@google.com</a>&gt=
;</span> wrote:<div class=3D"im"><br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div dir=3D"ltr"><div><br><div class=3D"gmail_quote">
<div>On Tue, Jan 7, 2014 at 1:39 PM,  <span dir=3D"ltr">&lt;<a>tko...@googl=
e.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"m=
argin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204=
,204);border-left-style:solid;padding-left:1ex">


<div dir=3D"ltr">I would like to propose a small addition to the standard l=
ibrary &quot;map&quot; and &quot;unordered_map&quot; containers to overcome=
 some limitiations and relax some unnecessary restrictions.</div></blockquo=
te>


<div><br></div></div><div>Sorry if I&#39;m missing something obvious, but c=
ouldn&#39;t this issue (and perhaps the proposed fix) also apply to std::se=
t and std::unordered_set?</div></div></div></div></blockquote><div><br>

</div><div>Sorry, I overlooked the prior discussion of this point, which ex=
plains why set::always_* might not make sense. However, I don&#39;t see why=
 the basic problem of recovering from failed insertion, and consequently th=
e solution of stable_* methods, don&#39;t apply to set.</div>
</div></div></div></div></blockquote><div><br></div><div>I&#39;m not at all=
 opposed to including sets in the proposal, but at this point I cannot see =
the benefit very clearly. In order for the proposal to be <i>different</i> =
from the existing set interface, you would have to have a move-only key. In=
 that case, for key insertion to fail you would need to provide a key that =
compares equal with an existing key, although it is &quot;unique&quot;. You=
 could probably contrive such applications, but they seem much rarer to me.=
 I have a note into the actual proposal text, though, explaining this point=
 and inviting suggestions to broaded the proposal.</div>
</div></blockquote><div><br></div><div>It&#39;s not entirely clear to me th=
at move-only types are necessarily &quot;unique&quot;, particularly in sens=
e of STL equivalence or equality, and my sense is that the STL tends to fav=
or consistency even when that consistency isn&#39;t obviously useful (that&=
#39;s kind of why we&#39;re in this mess in the first place), which would a=
rgue for giving sets the same treatment.</div>
<div><br></div><div>That said, so long as you have an explicit key argument=
, you can&#39;t promote these methods to requirements on the [unordered] as=
sociative container concepts, so maybe the consistency argument doesn&#39;t=
 carry as much force. Also, sets of move-only types are already fairly awkw=
ard (since elements can&#39;t be nondestructively removed), so maybe one ma=
rginal additional pain point isn&#39;t worth addressing.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l=
eft-style:solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"im"><div><=
br></div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-l=
eft-style:solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_quot=
e">
<div>Also, a couple more comments:<br></div><div><div><br></div><div>Should=
n&#39;t basically all the methods you propose have overloads that take a co=
nst_iterator hint, for consistency with the existing insert/emplace methods=
?</div>
</div></div></div></blockquote><div><br></div></div><div>Good point. I was =
thinking that you would use the new methods singularly, but there&#39;s no =
reason to not accept a hint if for some reason the user has a useful hint a=
lready.</div>
<div class=3D"im"><div><br></div><div>=C2=A0</div><blockquote class=3D"gmai=
l_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-lef=
t-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir=
=3D"ltr">
<div class=3D"gmail_quote"><div>
</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b=
order-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:s=
olid;padding-left:1ex"><div dir=3D"ltr"><div><div class=3D"gmail_quote"><di=
v><div>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;p=
adding-left:1ex"><div dir=3D"ltr"><blockquote style=3D"margin:0px 0px 0px 4=
0px;border:none;padding:0px">
<div><div><font color=3D"#274e13">Add the following interfaces to std::map =
and std::unordered_map:</font></div></div><div><div><font color=3D"#274e13"=
><br></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0p=
x 40px;border:none;padding:0px">


<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;ite=
rator, bool&gt;</b></font></div></div></blockquote><blockquote style=3D"mar=
gin:0px 0px 0px 40px;border:none;padding:0px">


<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>stable=
_insert(key_type const &amp; k, mapped_type const &amp; v)</b></font></div>=
</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px">


<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b><br></=
b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px 4=
0px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"cour=
ier new, monospace"><b>pair&lt;iterator, bool&gt;</b></font></div>


</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monosp=
ace"><b>stable_insert(key_type const &amp; k, mapped_type &amp;&amp; v)</b>=
</font></div>

</div></blockquote></blockquote></div></blockquote></div></div></div></div>=
</div></blockquote><div><br></div><div>Couldn&#39;t these just be combined =
into</div><div><br></div><div><div>pair&lt;iterator, bool&gt;</div><div>

stable_insert(key_type const &amp; k, mapped_type v)</div></div><div><br></=
div><div>This is less consistent with ordinary insert(), but IIUC the overl=
oading of insert() is a historical artifact, since removing const value_typ=
e&amp; overload could break existing code. That&#39;s not a consideration h=
ere.</div>
</div></div></blockquote><div><br></div></div><div>I don&#39;t think that w=
ould work: The point of &quot;stability&quot; is to accept a reference and =
promise not to construct-from it. Passing by value would unconditionally mo=
ve-from the original object, wouldn&#39;t it?</div>
</div></blockquote><div><br></div><div>Ah, you&#39;re right. Good point.</d=
iv><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0=
px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);borde=
r-left-style:solid;padding-left:1ex">
<div dir=3D"ltr"><div class=3D"im"><div>=C2=A0</div><div><br></div><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-wid=
th:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-l=
eft:1ex">
<div dir=3D"ltr"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-colo=
r:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir=3D"lt=
r"><div>
<div class=3D"gmail_quote"><div><div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(2=
04,204,204);border-left-style:solid;padding-left:1ex"><div dir=3D"ltr"><blo=
ckquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">
<div><div><font color=3D"#274e13">Also add the following:</font></div></div=
><div><div><font color=3D"#274e13"><br></font></div></div></blockquote><blo=
ckquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">

<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>pair&lt;ite=
rator, bool&gt;</b></font></div></div></blockquote><blockquote style=3D"mar=
gin:0px 0px 0px 40px;border:none;padding:0px">


<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always=
_insert(value_type const &amp; x)</b></font></div></div></blockquote><block=
quote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><=
font color=3D"#274e13" face=3D"courier new, monospace"><b><br>


</b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px=
 40px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"co=
urier new, monospace"><b>pair&lt;iterator, bool&gt;</b></font></div></div><=
/blockquote>


<blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
<div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always_inse=
rt(value_type &amp;&amp; x)</b></font></div></div></blockquote><blockquote =
style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">


<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b><br></=
b></font></div></div></blockquote><blockquote style=3D"margin:0px 0px 0px 4=
0px;border:none;padding:0px"><div><div><font color=3D"#274e13" face=3D"cour=
ier new, monospace"><b>template &lt;typename ...Args&gt;</b></font></div>


</div></blockquote><blockquote style=3D"margin:0px 0px 0px 40px;border:none=
;padding:0px"><div><div><font color=3D"#274e13" face=3D"courier new, monosp=
ace"><b>pair&lt;iterator, bool&gt;</b></font></div></div></blockquote><bloc=
kquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px">


<div><div><font color=3D"#274e13" face=3D"courier new, monospace"><b>always=
_emplace(Args &amp;&amp;... args)</b></font></div></div></blockquote></bloc=
kquote></div></blockquote></div></div></div></div></div></blockquote><div>

<br></div><div>I know you&#39;ve heard from me before on this subject, but =
I still think it will cause confusion that the stable_* methods have a sepa=
rate key arg, whereas the always_* methods (like the plain ones) do not. I =
don&#39;t know what to do about it, though.</div>
</div></div></blockquote><div><br></div></div><div>I actually agree. It wou=
ld probably be saner to give both versions the same signature. I used to fe=
el that passing a value_type would be less restrictive that requiring split=
 arguments (especially for emplace), but I&#39;m more and more offended by =
the asymmetry now. I will change it.</div>
</div></blockquote><blockquote class=3D"gmail_quote" style=3D"margin:0px 0p=
x 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border=
-left-style:solid;padding-left:1ex"><div dir=3D"ltr"><div>=C2=A0</div><div>=
Thanks for the comments!</div>
</div><div class=3D""><div class=3D"h5">

<p></p>

-- <br>
=C2=A0<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--047d7b676f7c0a6bda04f0041eb1--

.

------=_Part_4819_11657602.1389831967163
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Wednesday, 15 January 2014 14:12:47 UTC, David Rodr=C3=ADguez Ibeas wrot=
e:
>
> Not pushing for this, just commenting on your response.
>
> On Wed, Jan 8, 2014 at 6:37 AM, <tko...@google.com> wrote:
>
>>
>>> Well, sets don't support mutating the key. For the same reason, my=20
>> proposal doesn't have any part that attempt to mutate the key, either.
>>
> =20
> Mutating the key might not be necessary if willing to pay a higher cost.=
=20
> That is, the operation might find the point of insertion, create a new no=
de=20
> and replace the old node with the new node, then release the old node bac=
k=20
> to the allocator. This would not require mutating a key, but it would com=
e=20
> with a higher cost.
>
=20
I did actually think about this a little bit: Yes, you could always release=
=20
nodes entirely and create new ones. But that would invalidate the current=
=20
iterator, which would be a fairly unusual departure from the rest of the=20
 library, and there would be new exception complications.

More generally, as I said earlier, you could ask to abolish assignment=20
altogether and replace it with destruction-followed-by-construction, but=20
that is also problematic <http://stackoverflow.com/questions/8829548> in=20
general.

The second comment is that the above might not even be necessary. There is=
=20
> no requirement that keys are 'const' inside the container, only that the=
=20
> container does not provide access to the keys that would allow user code =
to=20
> change it. The container might maintain non-const keys internally as long=
=20
> as both 'iterator' and 'const_iterator' yield const references to them.=
=20
> This is a big difference from 'std::map', where the keys in the map *must=
*=20
> be 'const' (you cannot bind a reference to 'pair<const K, T>' to a=20
> 'pair<K,T>', but you can always bind a reference 'K const &' to a 'K' val=
ue.
>

Nice observation, indeed, the set key_type is not const. Well, I'm very=20
open to ideas and suggestions. It's simply that I still can't really see a=
=20
*useful* "stable insertion" scenario for sets. Would you perhaps have a=20
reasonable example? The maps proposal came out of a very real piece of code=
=20
that tried to update a map of unique pointers, just as in the example...


Geoffrey said:

>  It's not entirely clear to me that move-only types are necessarily=20
> "unique", particularly in sense of STL equivalence or equality, and my=20
> sense is that the STL tends to favor consistency even when that consisten=
cy=20
> isn't obviously useful (that's kind of why we're in this mess in the firs=
t=20
> place), which would argue for giving sets the same treatment.


> That said, so long as you have an explicit key argument, you can't promot=
e=20
> these methods to requirements on the [unordered] associative container=20
> concepts, so maybe the consistency argument doesn't carry as much force.=
=20
> Also, sets of move-only types are already fairly awkward (since elements=
=20
> can't be nondestructively removed), so maybe one marginal additional pain=
=20
> point isn't worth addressing.


Yeah, I'm aware of heterogeneous comparisons and non-trivial equivalence=20
classes, and as I said, I'd welcome a *useful* addition to the proposal; I=
=20
just don't see one myself. That said, a comparator with non-trivial=20
equivalence classes of *unique* objects is probably something very arcane..=
..


Anyway, thanks to some offline discussion, the current (final?) state of=20
the proposal is now this:

*template <typename M> *
*pair<iterator, bool> *
*emplace_stable(const key_type & k, M && obj) *

*template <typename M> *
*pair<iterator, bool> *
*emplace_stable(const_iterator hint, const key_type & k, M && obj)*

*template <typename M> *
*pair<iterator, bool> *
*emplace_or_update(const key_type & k, M && obj) *

*template <typename M> *
*pair<iterator, bool> *
*emplace_or_update(const_iterator hint, const key_type & k, M && obj)*


I removed the "insert" forms altogether, and distilled the proposal down=20
into just two new names, "emplace_stable" and "emplace_or_update". As=20
Geoffrey suggested, that way we don't break the tradition that "insert"=20
takes a single value argument, and "emplace" has already been associated=20
with multiple, broken down arguments. Moreover, we already have "emplace"=
=20
and "emplace_hint", so there's precedent for adding variants. Finally, by=
=20
changing "always_emplace" to "emplace_or_update", it should be even more=20
readable.

>=20

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

------=_Part_4819_11657602.1389831967163
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, 15 January 2014 14:12:47 UTC, David Rodr=C3=
=ADguez Ibeas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0px =
0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204=
); border-left-style: solid; padding-left: 1ex;"><div dir=3D"ltr">Not pushi=
ng for this, just commenting on your response.<br><br><div class=3D"gmail_q=
uote">On Wed, Jan 8, 2014 at 6:37 AM,&nbsp;<span dir=3D"ltr">&lt;<a target=
=3D"_blank" gdf-obfuscated-mailto=3D"gzCr9X_cMakJ" style=3D"color: rgb(102,=
 17, 204);">tko...@google.com</a>&gt;</span>&nbsp;wrote:<br><blockquote cla=
ss=3D"gmail_quote" style=3D"margin: 0px 0px 0px 0.8ex; border-left-width: 1=
px; border-left-color: rgb(204, 204, 204); border-left-style: solid; paddin=
g-left: 1ex;"><div dir=3D"ltr"><div><blockquote class=3D"gmail_quote" style=
=3D"margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: r=
gb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir=
=3D"ltr"><br></div></blockquote></div><div>Well, sets don't support mutatin=
g the key. For the same reason, my proposal doesn't have any part that atte=
mpt to mutate the key, either.</div></div></blockquote><div>&nbsp;</div><di=
v>Mutating the key might not be necessary if willing to pay a higher cost. =
That is, the operation might find the point of insertion, create a new node=
 and replace the old node with the new node, then release the old node back=
 to the allocator. This would not require mutating a key, but it would come=
 with a higher cost.</div></div></div></blockquote><div>&nbsp;</div><div>I =
did actually think about this a little bit: Yes, you could always release n=
odes entirely and create new ones. But that would invalidate the current it=
erator, which would be a fairly unusual departure from the rest of the &nbs=
p;library, and there would be new exception complications.<div><br></div><d=
iv>More generally, as I said earlier, you could ask to abolish assignment a=
ltogether and replace it with destruction-followed-by-construction, but tha=
t is also<a href=3D"http://stackoverflow.com/questions/8829548"> problemati=
c</a> in general.<br><br><blockquote class=3D"gmail_quote" style=3D"margin:=
 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204=
, 204); border-left-style: solid; padding-left: 1ex;"><div dir=3D"ltr"><div=
 class=3D"gmail_quote">The second comment is that the above might not even =
be necessary. There is no requirement that keys are 'const' inside the cont=
ainer, only that the container does not provide access to the keys that wou=
ld allow user code to change it. The container might maintain non-const key=
s internally as long as both 'iterator' and 'const_iterator' yield const re=
ferences to them. This is a big difference from 'std::map', where the keys =
in the map *must* be 'const' (you cannot bind a reference to 'pair&lt;const=
 K, T&gt;' to a 'pair&lt;K,T&gt;', but you can always bind a reference 'K c=
onst &amp;' to a 'K' value.</div></div></blockquote><div><br></div><div>Nic=
e observation, indeed, the set key_type is not const. Well, I'm very open t=
o ideas and suggestions. It's simply that I still can't really see a <i>use=
ful</i> "stable insertion" scenario for sets. Would you perhaps have a reas=
onable example? The maps proposal came out of a very real piece of code tha=
t tried to update a map of unique pointers, just as in the example...</div>=
<div><br></div><div><br></div><div>Geoffrey said:<br class=3D"Apple-interch=
ange-newline"><blockquote class=3D"gmail_quote" style=3D"margin: 0px 0px 0p=
x 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); bor=
der-left-style: solid; padding-left: 1ex;">&nbsp;It's not entirely clear to=
 me that move-only types are necessarily "unique", particularly in sense of=
 STL equivalence or equality, and my sense is that the STL tends to favor c=
onsistency even when that consistency isn't obviously useful (that's kind o=
f why we're in this mess in the first place), which would argue for giving =
sets the same treatment.</blockquote></div><div><blockquote class=3D"gmail_=
quote" style=3D"margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-l=
eft-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;=
"><br></blockquote><blockquote class=3D"gmail_quote" style=3D"margin: 0px 0=
px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204)=
; border-left-style: solid; padding-left: 1ex;">That said, so long as you h=
ave an explicit key argument, you can't promote these methods to requiremen=
ts on the [unordered] associative container concepts, so maybe the consiste=
ncy argument doesn't carry as much force. Also, sets of move-only types are=
 already fairly awkward (since elements can't be nondestructively removed),=
 so maybe one marginal additional pain point isn't worth addressing.</block=
quote></div><div><br></div><div>Yeah, I'm aware of heterogeneous comparison=
s and non-trivial equivalence classes, and as I said, I'd welcome a <i>usef=
ul</i> addition to the proposal; I just don't see one myself. That said, a =
comparator with non-trivial equivalence classes of <i>unique</i> objects is=
 probably something very arcane...</div><div><br></div><div><br></div><div>=
Anyway, thanks to some offline discussion, the current (final?) state of th=
e proposal is now this:</div><div><br></div></div></div><blockquote style=
=3D"margin: 0 0 0 40px; border: none; padding: 0px;"><div><div><div><div><f=
ont face=3D"courier new, monospace"><b>template &lt;typename M&gt;&nbsp;</b=
></font></div></div></div></div><div><div><div><font face=3D"courier new, m=
onospace"><b>pair&lt;iterator, bool&gt;&nbsp;</b></font></div></div></div><=
div><div><div><font face=3D"courier new, monospace"><b>emplace_stable(const=
 key_type &amp; k, M &amp;&amp; obj)&nbsp;</b></font></div></div></div><div=
><div><div><font face=3D"courier new, monospace"><b><br></b></font></div></=
div></div><div><div><div><font face=3D"courier new, monospace"><b>template =
&lt;typename M&gt;&nbsp;</b></font></div></div></div><div><div><div><font f=
ace=3D"courier new, monospace"><b>pair&lt;iterator, bool&gt;&nbsp;</b></fon=
t></div></div></div><div><div><div><font face=3D"courier new, monospace"><b=
>emplace_stable(const_iterator hint, const key_type &amp; k, M &amp;&amp; o=
bj)</b></font></div></div></div><div><div><font face=3D"courier new, monosp=
ace"><b><br></b></font></div></div><div><div><div><font face=3D"courier new=
, monospace"><b>template &lt;typename M&gt;&nbsp;</b></font></div></div></d=
iv><div><div><div><font face=3D"courier new, monospace"><b>pair&lt;iterator=
, bool&gt;&nbsp;</b></font></div></div></div><div><div><div><font face=3D"c=
ourier new, monospace"><b>emplace_or_update(const key_type &amp; k, M &amp;=
&amp; obj)&nbsp;</b></font></div></div></div><div><div><div><font face=3D"c=
ourier new, monospace"><b><br></b></font></div></div></div><div><div><div><=
font face=3D"courier new, monospace"><b>template &lt;typename M&gt;&nbsp;</=
b></font></div></div></div><div><div><div><font face=3D"courier new, monosp=
ace"><b>pair&lt;iterator, bool&gt;&nbsp;</b></font></div></div></div><div><=
div><div><font face=3D"courier new, monospace"><b>emplace_or_update(const_i=
terator hint, const key_type &amp; k, M &amp;&amp; obj)</b></font></div></d=
iv></div></blockquote><div><div><br></div><div>I removed the "insert" forms=
 altogether, and distilled the proposal down into just two new names, "empl=
ace_stable" and "emplace_or_update". As Geoffrey suggested, that way we don=
't break the tradition that "insert" takes a single value argument, and "em=
place" has already been associated with multiple, broken down arguments. Mo=
reover, we already have "emplace" and "emplace_hint", so there's precedent =
for adding variants. Finally, by changing "always_emplace" to "emplace_or_u=
pdate", it should be even more readable.</div><blockquote class=3D"gmail_qu=
ote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padd=
ing-left: 1ex;"><div dir=3D"ltr"><div><div class=3D"gmail_quote">
</div></div></div>
</blockquote></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_4819_11657602.1389831967163--

.