------=_Part_6278_1100056328.1443569446780
Content-Type: multipart/alternative;
 boundary="----=_Part_6279_1116108392.1443569446780"

------=_Part_6279_1116108392.1443569446780
Content-Type: text/plain; charset=UTF-8



std::list contain splice method, that can move values from on list to
another, but std::map - not. Why std::map don't have same functional? Very
simple proposal - include splice method into std::map. If target map
already have same keys as moved values, splice throw exception. In other
case splice grant no-throw guarantee. Yes, i can move values through pair
of map1.insert(*it) and map2.erase(it). But in this case my code can't
grant any no-throw guarantee, because any call of std::map::insert can
throw std::bad_alloc.

--

---
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_6279_1116108392.1443569446780
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><p>std::list contain splice method, that can move values f=
rom on list to another, but std::map - not. Why std::map don&#39;t have sam=
e functional? Very simple proposal - include splice method into std::map. I=
f target map already have same keys as moved values, splice throw exception=
.. In other case splice grant no-throw guarantee. Yes, i can move values thr=
ough pair of map1.insert(*it) and map2.erase(it). But in this case my code =
can&#39;t grant any no-throw guarantee, because any call of std::map::inser=
t can throw std::bad_alloc.<br></p></div>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_6279_1116108392.1443569446780--
------=_Part_6278_1100056328.1443569446780--

.

On Sep 29, 2015, at 7:30 PM, Aso Renji <asorenji@gmail.com> wrote:
>=20
> std::list contain splice method, that can move values from on list to ano=
ther, but std::map - not. Why std::map don't have same functional? Very sim=
ple proposal - include splice method into std::map. If target map already h=
ave same keys as moved values, splice throw exception. In other case splice=
 grant no-throw guarantee. Yes, i can move values through pair of map1.inse=
rt(*it) and map2.erase(it). But in this case my code can't grant any no-thr=
ow guarantee, because any call of std::map::insert can throw std::bad_alloc=
..

Alan Talbot has graciously submitted revision 2 of N3645 "Splicing Maps and=
 Sets" to the pre-Kona mailing.  The mailing deadline was just last Friday =
and so it is not available yet (give it a week or two).  Here is a convenie=
nce link to the previous revision:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3645.pdf

Spoiler:  there is not a proposal for a member function called splice.  But=
 the functionality of transferring ownership of a node from one container t=
o another is there.  And there is even more (and more powerful) functionali=
ty proposed.  For example one can efficiently change the value of a key usi=
ng this functionality (with no deallocation/reallocation sequence).

This includes functionality that many people have asked for over an extende=
d period of time.  And yet the committee has not yet allowed your std::lib =
vendor to provide it.  If you care about access to this functionality so yo=
u can use it in your code, make sure you locate a committee member and let =
them know.  If you and 1,000 others don=E2=80=99t go to the effort to do th=
at, then Alan and his coauthors have an uphill battle in Kona next month.

Howard

--=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_32_2104874734.1443574514246
Content-Type: multipart/alternative;
 boundary="----=_Part_33_1882048387.1443574514247"

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

Really cool paper!=20

This would cross off one of my STL wishlist items (move element out of a=20
std::set).

Jared

On Tuesday, September 29, 2015 at 5:14:29 PM UTC-7, Howard Hinnant wrote:
>
> On Sep 29, 2015, at 7:30 PM, Aso Renji <asor...@gmail.com <javascript:>>=
=20
> wrote:=20
> >=20
> > std::list contain splice method, that can move values from on list to=
=20
> another, but std::map - not. Why std::map don't have same functional? Ver=
y=20
> simple proposal - include splice method into std::map. If target map=20
> already have same keys as moved values, splice throw exception. In other=
=20
> case splice grant no-throw guarantee. Yes, i can move values through pair=
=20
> of map1.insert(*it) and map2.erase(it). But in this case my code can't=20
> grant any no-throw guarantee, because any call of std::map::insert can=20
> throw std::bad_alloc.=20
>
> Alan Talbot has graciously submitted revision 2 of N3645 "Splicing Maps=
=20
> and Sets" to the pre-Kona mailing.  The mailing deadline was just last=20
> Friday and so it is not available yet (give it a week or two).  Here is a=
=20
> convenience link to the previous revision:=20
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3645.pdf=20
>
> Spoiler:  there is not a proposal for a member function called splice.=20
>  But the functionality of transferring ownership of a node from one=20
> container to another is there.  And there is even more (and more powerful=
)=20
> functionality proposed.  For example one can efficiently change the value=
=20
> of a key using this functionality (with no deallocation/reallocation=20
> sequence).=20
>
> This includes functionality that many people have asked for over an=20
> extended period of time.  And yet the committee has not yet allowed your=
=20
> std::lib vendor to provide it.  If you care about access to this=20
> functionality so you can use it in your code, make sure you locate a=20
> committee member and let them know.  If you and 1,000 others don=E2=80=99=
t go to=20
> the effort to do that, then Alan and his coauthors have an uphill battle =
in=20
> Kona next month.=20
>
> Howard=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_33_1882048387.1443574514247
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Really cool paper! <br><br>This would cross off one of my =
STL wishlist items (move element out of a std::set).<br><br>Jared<br><br>On=
 Tuesday, September 29, 2015 at 5:14:29 PM UTC-7, Howard Hinnant wrote:<blo=
ckquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-=
left: 1px #ccc solid;padding-left: 1ex;">On Sep 29, 2015, at 7:30 PM, Aso R=
enji &lt;<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D=
"HVLIO_sdCgAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;javascript:=
&#39;;return true;" onclick=3D"this.href=3D&#39;javascript:&#39;;return tru=
e;">asor...@gmail.com</a>&gt; wrote:
<br>&gt;=20
<br>&gt; std::list contain splice method, that can move values from on list=
 to another, but std::map - not. Why std::map don&#39;t have same functiona=
l? Very simple proposal - include splice method into std::map. If target ma=
p already have same keys as moved values, splice throw exception. In other =
case splice grant no-throw guarantee. Yes, i can move values through pair o=
f map1.insert(*it) and map2.erase(it). But in this case my code can&#39;t g=
rant any no-throw guarantee, because any call of std::map::insert can throw=
 std::bad_alloc.
<br>
<br>Alan Talbot has graciously submitted revision 2 of N3645 &quot;Splicing=
 Maps and Sets&quot; to the pre-Kona mailing. =C2=A0The mailing deadline wa=
s just last Friday and so it is not available yet (give it a week or two). =
=C2=A0Here is a convenience link to the previous revision:
<br>
<br><a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n364=
5.pdf" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;h=
ttp://www.google.com/url?q\75http%3A%2F%2Fwww.open-std.org%2Fjtc1%2Fsc22%2F=
wg21%2Fdocs%2Fpapers%2F2013%2Fn3645.pdf\46sa\75D\46sntz\0751\46usg\75AFQjCN=
GFVfWufiTjVZWe663hOe3QmOgHfA&#39;;return true;" onclick=3D"this.href=3D&#39=
;http://www.google.com/url?q\75http%3A%2F%2Fwww.open-std.org%2Fjtc1%2Fsc22%=
2Fwg21%2Fdocs%2Fpapers%2F2013%2Fn3645.pdf\46sa\75D\46sntz\0751\46usg\75AFQj=
CNGFVfWufiTjVZWe663hOe3QmOgHfA&#39;;return true;">http://www.open-std.org/j=
tc1/<wbr>sc22/wg21/docs/papers/2013/<wbr>n3645.pdf</a>
<br>
<br>Spoiler: =C2=A0there is not a proposal for a member function called spl=
ice. =C2=A0But the functionality of transferring ownership of a node from o=
ne container to another is there. =C2=A0And there is even more (and more po=
werful) functionality proposed. =C2=A0For example one can efficiently chang=
e the value of a key using this functionality (with no deallocation/realloc=
ation sequence).
<br>
<br>This includes functionality that many people have asked for over an ext=
ended period of time. =C2=A0And yet the committee has not yet allowed your =
std::lib vendor to provide it. =C2=A0If you care about access to this funct=
ionality so you can use it in your code, make sure you locate a committee m=
ember and let them know. =C2=A0If you and 1,000 others don=E2=80=99t go to =
the effort to do that, then Alan and his coauthors have an uphill battle in=
 Kona next month.
<br>
<br>Howard
<br>
<br></blockquote></div>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_33_1882048387.1443574514247--
------=_Part_32_2104874734.1443574514246--

.

------=_Part_160_1092864891.1443625672181
Content-Type: multipart/alternative;
 boundary="----=_Part_161_294445455.1443625672181"

------=_Part_161_294445455.1443625672181
Content-Type: text/plain; charset=UTF-8

On Wednesday, 30 September 2015 01:14:29 UTC+1, Howard Hinnant wrote:
>
>  And there is even more (and more powerful) functionality proposed.  For
> example one can efficiently change the value of a key using this
> functionality (with no deallocation/reallocation sequence).
>

How? *a.extract(k) would still return pair<Key const, T>& so there's no
actual legal way to modify the key, notwithstanding that modifying it
wouldn't break container invariants.

I still think this is a great proposal, I just don't think it should be
oversold.

--

---
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_161_294445455.1443625672181
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, 30 September 2015 01:14:29 UTC+1, Howard Hin=
nant  wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">=C2=A0And there is=
 even more (and more powerful) functionality proposed. =C2=A0For example on=
e can efficiently change the value of a key using this functionality (with =
no deallocation/reallocation sequence).
<br></blockquote><div><br></div><div>How? <font face=3D"courier new, monosp=
ace">*a.extract(k)</font> would still return <font face=3D"courier new, mon=
ospace">pair&lt;Key const, T&gt;&amp;</font> so there&#39;s no actual legal=
 way to modify the key, notwithstanding that modifying it wouldn&#39;t brea=
k container invariants.</div><div><br></div><div>I still think this is a gr=
eat proposal, I just don&#39;t think it should be oversold.</div></div>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_161_294445455.1443625672181--
------=_Part_160_1092864891.1443625672181--

.

On Sep 30, 2015, at 11:07 AM, Edward Catmur <ed@catmur.co.uk> wrote:
>=20
> On Wednesday, 30 September 2015 01:14:29 UTC+1, Howard Hinnant wrote:
>>  And there is even more (and more powerful) functionality proposed.  For=
 example one can efficiently change the value of a key using this functiona=
lity (with no deallocation/reallocation sequence).=20
>>=20
> How? *a.extract(k) would still return pair<Key const, T>& so there's no a=
ctual legal way to modify the key, notwithstanding that modifying it wouldn=
't break container invariants.
>=20
> I still think this is a great proposal, I just don't think it should be o=
versold.

The original intent was that *a.extract(k) would return a reference to a pa=
ir<Key, T> instead of a pair<Key const, T>.  See my comment dated 2009-09-1=
9 in LWG issue 839:

http://cplusplus.github.io/LWG/lwg-active.html#839

for a sketch. (extract is renamed to remove there).  This can be made possi=
ble by having the map store a union{pair<Key, T>, pair<Key const, T>} and r=
eturning the proper member as requested.  Technically this is not implement=
able in portable C++, but that is one of the reasons the std::lib exists:  =
to write non-portable code so you don=E2=80=99t have to.

The technique has been field tested in libc++ for the last 6 or so years:

https://github.com/llvm-mirror/libcxx/blob/master/include/map#L616-L654

When *a.extract(k) is accessed, the node is no longer stored in the map.  I=
t is owned uniquely by the node_ptr, and you have to re-insert it into the =
map if desired (see LWG 839 for a more thorough =E2=80=94 but still brief =
=E2=80=94 sketch of the original idea).

I=E2=80=99m reviewing N3645 and I agree that it is not consistent with my d=
escription above.  I was not present at the meeting where this was discusse=
d, and N3645 is a product of that meeting, so I am behind on some of the de=
tails.

That being said, I have reviewed the pre-Kona version (which will be P0083R=
0).  In this paper the syntax for modifying the key is different:

    auto np =3D a.extract(k);
    np.key() =3D new_key;
    a.insert(std::move(np));

Personally I prefer the old syntax:

    auto np =3D a.extract(k);
    np->first =3D new_key;
    a.insert(std::move(np));

However I want the functionality far more than I want any specific syntax t=
o do it with.  So I=E2=80=99m a happy camper. :-)

Howard

--=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/.

.

On Sep 30, 2015, at 11:34 AM, Howard Hinnant <howard.hinnant@gmail.com> wrote:
>
> (which will be P0083R0)

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0083r0.pdf

Howard

--

---
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/.

.

--001a11496780f5507b0521077e3d
Content-Type: text/plain; charset=UTF-8

On Thu, Oct 1, 2015 at 6:00 AM, Howard Hinnant <howard.hinnant@gmail.com>
wrote:

> On Sep 30, 2015, at 11:34 AM, Howard Hinnant <howard.hinnant@gmail.com>
> wrote:
> >
> > (which will be P0083R0)
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0083r0.pdf
>
>
  The document states:

"Although these [splice operations, a.t.] will have the same complexity as
a conventional insert and erase, the actual cost will typically be much
less since the objects do not need to be copied nor the nodes reallocated."

  Hope I didn't miss anything, but for generalized tree-based
associative-containers (that is, both node based and ordered-vector based),
*split* and *join* operations - which are specialized cases of splice - can
be done without exceptions and with excellent complexity (llogarithmic for
red-black trees, linear for ordered vectors). *Split* transfers keys that
are larger (smaller) than some key, and *join* merges two containers where
one set of keys is smaller (larger) than the other. The complexity is much
lower than an equivalent sequence of inserts and erases, not only because
the individual nodes are transferred rather than allocated, copied, and
deallocated, but also because entire sub-trees can be transferred without
restructuring (see Introduction To Algorithms - Red-Black Trees
<https://mitpress.mit.edu/books/introduction-algorithms>).
  The suggested operations can be implemented in terms of these operations,
and, depending on the usage pattern, this can be very efficient (it stands
to reason that the use of tree-based containers coincides with dealing with
contiguous ranges of keys).
  I've implemented this many years ago as a libstdc++ extension
<https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_based_containers.html>
..



> Howard
>
> --
>
> ---
> 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/.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Thu, Oct 1, 2015 at 6:00 AM, Howard Hinnant <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:howard.hinnant@gmail.com" target=3D"_blank">howard.hinnant@=
gmail.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(20=
4,204,204);border-left-style:solid;padding-left:1ex">On Sep 30, 2015, at 11=
:34 AM, Howard Hinnant &lt;<a href=3D"mailto:howard.hinnant@gmail.com">howa=
rd.hinnant@gmail.com</a>&gt; wrote:<br>
&gt;<br>
&gt; (which will be P0083R0)<br>
<br>
<a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0083r0.=
pdf" rel=3D"noreferrer" target=3D"_blank">http://www.open-std.org/jtc1/sc22=
/wg21/docs/papers/2015/p0083r0.pdf</a><br>
<div class=3D""><div class=3D"h5"><br></div></div></blockquote><div><br></d=
iv><div>=C2=A0 The document states:</div><div><br></div><div>&quot;Although=
 these [splice operations, a.t.] will have the same complexity as a convent=
ional
insert and erase, the actual cost will typically be much less since the obj=
ects do not need
to be copied nor the nodes reallocated.&quot;</div><div><br></div><div>=C2=
=A0 Hope I didn&#39;t miss anything, but for generalized tree-based associa=
tive-containers (that is, both node based and ordered-vector based), <i>spl=
it</i>=C2=A0and <i>join</i>=C2=A0operations - which are specialized cases o=
f splice - can be done without exceptions and with excellent complexity (ll=
ogarithmic for red-black trees, linear for ordered vectors). <i>Split</i>=
=C2=A0transfers keys that are larger (smaller) than some key, and <i>join</=
i>=C2=A0merges two containers where one set of keys is smaller (larger) tha=
n the other. The complexity is much lower than an equivalent sequence of in=
serts and erases, not only because the individual nodes are transferred rat=
her than allocated, copied, and deallocated, but also because entire sub-tr=
ees can be transferred without restructuring (see=C2=A0<a href=3D"https://m=
itpress.mit.edu/books/introduction-algorithms">Introduction To Algorithms -=
 Red-Black Trees</a>).</div><div>=C2=A0 The suggested operations can be imp=
lemented in terms of these operations, and, depending on the usage pattern,=
 this can be very efficient (it stands to reason that the use of tree-based=
 containers coincides with dealing with contiguous ranges of keys).</div><d=
iv>=C2=A0 I&#39;ve implemented this many years ago as <a href=3D"https://gc=
c.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_based_containers.html">a libs=
tdc++ extension</a>.</div><div><br></div><div>=C2=A0</div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;bo=
rder-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">=
<div class=3D""><div class=3D"h5">
Howard<br>
<br>
--<br>
<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">std-propo=
sals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" rel=3D"noreferrer" target=3D"_blank">http://groups.google.c=
om/a/isocpp.org/group/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div></div>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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 />

--001a11496780f5507b0521077e3d--

.

On 2015-09-30 20:00 , Howard Hinnant wrote:
> On Sep 30, 2015, at 11:34 AM, Howard Hinnant <howard.hinnant@gmail.com> wrote:
>>
>> (which will be P0083R0)
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0083r0.pdf
>
> Howard
>

is there a reason the proposal doesn't include operations like

map<Key, T, Comp, Allocator> extract(const_iterator first,
                                      const_iterator last);

for map,multimap,set,multiset? replace map<> above with "my type"

combined with merge, this would allow me to move a subtree from one
sorted container (sorry, i don't know the preferred term) to another
without any allocations.  i'm also thinking of use cases where i have
a shared set from which i'd like to quickly extract a range of items
and then do stuff with that range whilst minimizing the critical section
and/or minimizing iterative interlocking.

supporting the same operations for the hash containers probably doesn't
make any sense.

--

---
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/.

.

On Oct 1, 2015, at 6:00 AM, maurice barnum <pixi@burble.org> wrote:
>
> On 2015-09-30 20:00 , Howard Hinnant wrote:
>> On Sep 30, 2015, at 11:34 AM, Howard Hinnant <howard.hinnant@gmail.com> wrote:
>>>
>>> (which will be P0083R0)
>>
>> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0083r0.pdf
>>
>> Howard
>>
>
> is there a reason the proposal doesn't include operations like
>
> map<Key, T, Comp, Allocator> extract(const_iterator first,
>                                     const_iterator last);
>
> for map,multimap,set,multiset? replace map<> above with "my type"
>
> combined with merge, this would allow me to move a subtree from one
> sorted container (sorry, i don't know the preferred term) to another
> without any allocations.  i'm also thinking of use cases where i have
> a shared set from which i'd like to quickly extract a range of items
> and then do stuff with that range whilst minimizing the critical section
> and/or minimizing iterative interlocking.
>
> supporting the same operations for the hash containers probably doesn't
> make any sense.

The authors of this proposal have no implementation experience for your suggestion.  Perhaps you could propose this additional API.

Howard

--

---
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/.

.

--001a114235fc52ebed05210c6a24
Content-Type: text/plain; charset=UTF-8

On Thu, Oct 1, 2015 at 5:46 PM, Howard Hinnant <howard.hinnant@gmail.com>
wrote:

> On Oct 1, 2015, at 6:00 AM, maurice barnum <pixi@burble.org> wrote:
> >
> > On 2015-09-30 20:00 , Howard Hinnant wrote:
> >> On Sep 30, 2015, at 11:34 AM, Howard Hinnant <howard.hinnant@gmail.com>
> wrote:
> >>>
> >>> (which will be P0083R0)
> >>
> >> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0083r0.pdf
> >>
> >> Howard
> >>
> >
> > is there a reason the proposal doesn't include operations like
> >
> > map<Key, T, Comp, Allocator> extract(const_iterator first,
> >                                     const_iterator last);
> >
> > for map,multimap,set,multiset? replace map<> above with "my type"
> >
> > combined with merge, this would allow me to move a subtree from one
> > sorted container (sorry, i don't know the preferred term) to another
> > without any allocations.  i'm also thinking of use cases where i have
> > a shared set from which i'd like to quickly extract a range of items
> > and then do stuff with that range whilst minimizing the critical section
> > and/or minimizing iterative interlocking.
> >
> > supporting the same operations for the hash containers probably doesn't
> > make any sense.
>
> The authors of this proposal have no implementation experience for your
> suggestion.  Perhaps you could propose this additional API.
>
> Howard
>

  I'd like to point out again, that, unless I misunderstood something, this
can be done, without exceptions and in sublinear time, using well-known
algorithms for balanced trees (details in my previous message).


>
> --
>
> ---
> 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/.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Thu, Oct 1, 2015 at 5:46 PM, Howard Hinnant <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:howard.hinnant@gmail.com" target=3D"_blank">howard.hinnant@=
gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span cl=
ass=3D"">On Oct 1, 2015, at 6:00 AM, maurice barnum &lt;<a href=3D"mailto:p=
ixi@burble.org">pixi@burble.org</a>&gt; wrote:<br>
&gt;<br>
&gt; On 2015-09-30 20:00 , Howard Hinnant wrote:<br>
&gt;&gt; On Sep 30, 2015, at 11:34 AM, Howard Hinnant &lt;<a href=3D"mailto=
:howard.hinnant@gmail.com">howard.hinnant@gmail.com</a>&gt; wrote:<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; (which will be P0083R0)<br>
&gt;&gt;<br>
&gt;&gt; <a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015=
/p0083r0.pdf" rel=3D"noreferrer" target=3D"_blank">http://www.open-std.org/=
jtc1/sc22/wg21/docs/papers/2015/p0083r0.pdf</a><br>
&gt;&gt;<br>
&gt;&gt; Howard<br>
&gt;&gt;<br>
&gt;<br>
&gt; is there a reason the proposal doesn&#39;t include operations like<br>
&gt;<br>
&gt; map&lt;Key, T, Comp, Allocator&gt; extract(const_iterator first,<br>
&gt;=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0const_iterato=
r last);<br>
&gt;<br>
&gt; for map,multimap,set,multiset? replace map&lt;&gt; above with &quot;my=
 type&quot;<br>
&gt;<br>
&gt; combined with merge, this would allow me to move a subtree from one<br=
>
&gt; sorted container (sorry, i don&#39;t know the preferred term) to anoth=
er<br>
&gt; without any allocations.=C2=A0 i&#39;m also thinking of use cases wher=
e i have<br>
&gt; a shared set from which i&#39;d like to quickly extract a range of ite=
ms<br>
&gt; and then do stuff with that range whilst minimizing the critical secti=
on<br>
&gt; and/or minimizing iterative interlocking.<br>
&gt;<br>
&gt; supporting the same operations for the hash containers probably doesn&=
#39;t<br>
&gt; make any sense.<br>
<br>
</span>The authors of this proposal have no implementation experience for y=
our suggestion.=C2=A0 Perhaps you could propose this additional API.<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
Howard<br></font></span></blockquote><div><br></div><div>=C2=A0 I&#39;d lik=
e to point out again, that, unless I misunderstood something, this can be d=
one, without exceptions and in sublinear time, using well-known algorithms =
for balanced trees (details in my previous message).</div><div>=C2=A0</div>=
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><span class=3D"HOEnZb"><font color=3D"#88888=
8">
</font></span><div class=3D"HOEnZb"><div class=3D"h5"><br>
--<br>
<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">std-propo=
sals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" rel=3D"noreferrer" target=3D"_blank">http://groups.google.c=
om/a/isocpp.org/group/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div></div>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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 />

--001a114235fc52ebed05210c6a24--

.

On Oct 1, 2015, at 11:08 AM, Ami Tavory <atavory@gmail.com> wrote:
>
>> The authors of this proposal have no implementation experience for your suggestion.  Perhaps you could propose this additional API.
>>
>   I'd like to point out again, that, unless I misunderstood something, this can be done, without exceptions and in sublinear time, using well-known algorithms for balanced trees (details in my previous message).
>

Thank you.  The proposal process is like an open-source software project.  Anyone willing to do the work can participate.  I encourage anyone with implementation experience to do so.

Howard

--

---
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/.

.

--001a1149678065ecb605210caa02
Content-Type: text/plain; charset=UTF-8

On Thu, Oct 1, 2015 at 6:20 PM, Howard Hinnant <howard.hinnant@gmail.com>
wrote:

> On Oct 1, 2015, at 11:08 AM, Ami Tavory <atavory@gmail.com> wrote:
> >
> >> The authors of this proposal have no implementation experience for your
> suggestion.  Perhaps you could propose this additional API.
> >>
> >   I'd like to point out again, that, unless I misunderstood something,
> this can be done, without exceptions and in sublinear time, using
> well-known algorithms for balanced trees (details in my previous message).
> >
>
> Thank you.  The proposal process is like an open-source software project.
> Anyone willing to do the work can participate.  I encourage anyone with
> implementation experience to do so.
>

  Sorry again if I'm misunderstanding you, but I tried to point out that
I've implemented this in a libstdc++ extension which I think has been
bundled with g++ for the last decade (at least I always see it in the
ext/pb_ds directory of /usr/include/c++/[ver]). Incidentally, here are
the performance
tests for the split/join operations from the docs
<https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_split_join_timing_test.html>.
Please let me know if I can help out with anything.

>
> Howard
>
> --
>
> ---
> 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/.

--001a1149678065ecb605210caa02
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 Thu, Oct 1, 2015 at 6:20 PM, Howard Hinnant <span dir=3D"ltr">&lt;<a hre=
f=3D"mailto:howard.hinnant@gmail.com" target=3D"_blank">howard.hinnant@gmai=
l.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"m=
argin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=
=3D"">On Oct 1, 2015, at 11:08 AM, Ami Tavory &lt;<a href=3D"mailto:atavory=
@gmail.com">atavory@gmail.com</a>&gt; wrote:<br>
&gt;<br>
&gt;&gt; The authors of this proposal have no implementation experience for=
 your suggestion.=C2=A0 Perhaps you could propose this additional API.<br>
&gt;&gt;<br>
</span><span class=3D"">&gt;=C2=A0 =C2=A0I&#39;d like to point out again, t=
hat, unless I misunderstood something, this can be done, without exceptions=
 and in sublinear time, using well-known algorithms for balanced trees (det=
ails in my previous message).<br>
&gt;<br>
<br>
</span>Thank you.=C2=A0 The proposal process is like an open-source softwar=
e project.=C2=A0 Anyone willing to do the work can participate.=C2=A0 I enc=
ourage anyone with implementation experience to do so.<br></blockquote><div=
><br></div><div>=C2=A0 Sorry again if I&#39;m misunderstanding you, but I t=
ried to point out that I&#39;ve implemented this in a libstdc++ extension w=
hich I think has been bundled with g++ for the last decade (at least I alwa=
ys see it in the ext/pb_ds directory of /usr/include/c++/[ver]). Incidental=
ly, here are the <a href=3D"https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb=
_ds/tree_split_join_timing_test.html">performance tests for the split/join =
operations from the docs</a>. Please let me know if I can help out with any=
thing.</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex">
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
Howard<br>
</font></span><div class=3D"HOEnZb"><div class=3D"h5"><br>
--<br>
<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">std-propo=
sals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" rel=3D"noreferrer" target=3D"_blank">http://groups.google.c=
om/a/isocpp.org/group/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div></div>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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 />

--001a1149678065ecb605210caa02--

.

--Apple-Mail=_AF9F354E-CB75-4A90-8BCA-41CE81A3F4E7
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9310=E2=80=9301, at 11:26 PM, Ami Tavory <atavory@gmail.com=
> wrote:
>=20
> Sorry again if I'm misunderstanding you, but I tried to point out that I'=
ve implemented this in a libstdc++ extension which I think has been bundled=
 with g++ for the last decade (at least I always see it in the ext/pb_ds di=
rectory of /usr/include/c++/[ver]). Incidentally, here are the performance =
tests for the split/join operations from the docs <https://gcc.gnu.org/onli=
nedocs/libstdc++/ext/pb_ds/tree_split_join_timing_test.html>. Please let me=
 know if I can help out with anything.

Howard seems to be simply asking for a write-up which could be properly con=
sidered by the committee. Just looking at the documentation page (perhaps o=
verlooking source code comments), all I see is this:

> Additional Methods <>
> Tree-based containers support split and join methods. It is possible to s=
plit a tree so that it passes all nodes with keys larger than a given key t=
o a different tree. These methods have the following advantages over the al=
ternative of externally inserting to the destination tree and erasing from =
the source tree:
>=20
> These methods are efficient - red-black trees are split and joined in pol=
y-logarithmic complexity; ordered-vector trees are split and joined at line=
ar complexity. The alternatives have super-linear complexity.
> Aside from orders of growth, these operations perform few allocations and=
 de-allocations. For red-black trees, allocations are not performed, and th=
e methods are exception-free.=20

It looks very promising, but not yet actionable.

Just as I was sending this I got your last message, and though the graphs a=
re nice proof, they don=E2=80=99t seem to add any concepts.

A proposal should clearly state the interface you want to add, its complexi=
ty requirements, and its relation to the existing library and other proposa=
ls like extract.

Come back to this list with a draft and we=E2=80=99ll help to point out any=
 gaps.

For what it=E2=80=99s worth, I think extracting a unique_ptr (or unique_ptr=
-alike) and splitting a new container are orthogonal, and both would be nic=
e to have.

--=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/.

--Apple-Mail=_AF9F354E-CB75-4A90-8BCA-41CE81A3F4E7
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9310=
=E2=80=9301, at 11:26 PM, Ami Tavory &lt;<a href=3D"mailto:atavory@gmail.co=
m" class=3D"">atavory@gmail.com</a>&gt; wrote:</div><br class=3D"Apple-inte=
rchange-newline"><div class=3D""><div dir=3D"ltr" class=3D""><div class=3D"=
gmail_extra">Sorry again if I'm misunderstanding you, but I tried to point =
out that I've implemented this in a libstdc++ extension which I think has b=
een bundled with g++ for the last decade (at least I always see it in the e=
xt/pb_ds directory of /usr/include/c++/[ver]). Incidentally, here are the <=
a href=3D"https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_split_joi=
n_timing_test.html" class=3D"">performance tests for the split/join operati=
ons from the docs</a>. Please let me know if I can help out with anything.<=
/div></div></div></blockquote><br class=3D""></div><div><div class=3D"">How=
ard seems to be simply asking for a write-up which could be properly consid=
ered by the committee. Just looking at the documentation page (perhaps over=
looking source code comments), all I see is this:</div><div class=3D""><br =
class=3D""></div><div class=3D""><blockquote type=3D"cite" class=3D""><h2 c=
lass=3D""><a name=3D"add_methods" id=3D"add_methods" class=3D"">Additional =
Methods</a></h2><p class=3D"">Tree-based containers support split and join =
methods. It is possible to split a tree so that it passes all nodes with ke=
ys larger than a given key to a different tree. These methods have the foll=
owing advantages over the alternative of externally inserting to the destin=
ation tree and erasing from the source tree:</p><ol class=3D""><li class=3D=
"">These methods are efficient - red-black trees are split and joined in po=
ly-logarithmic complexity; ordered-vector trees are split and joined at lin=
ear complexity. The alternatives have super-linear complexity.</li><li clas=
s=3D"">Aside from orders of growth, these operations perform few allocation=
s and de-allocations. For red-black trees, allocations are not performed, a=
nd the methods are exception-free.&nbsp;</li></ol></blockquote><div class=
=3D""><br class=3D""></div></div><div class=3D"">It looks very promising, b=
ut not yet actionable.</div><div class=3D""><br class=3D""></div><div class=
=3D""><div class=3D"">Just as I was sending this I got your last message, a=
nd though the graphs are nice proof, they don=E2=80=99t seem to add any con=
cepts.</div></div><div class=3D""><br class=3D""></div><div class=3D"">A pr=
oposal should clearly state the interface you want to add, its complexity r=
equirements, and its relation to the existing library and other proposals l=
ike extract.</div><div class=3D""><br class=3D""></div><div class=3D"">Come=
 back to this list with a draft and we=E2=80=99ll help to point out any gap=
s.</div><div class=3D""><br class=3D""></div><div class=3D"">For what it=E2=
=80=99s worth, I think extracting a unique_ptr (or unique_ptr-alike) and sp=
litting a new container are orthogonal, and both would be nice to have.</di=
v><div class=3D""><br class=3D""></div></div></body></html>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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 />

--Apple-Mail=_AF9F354E-CB75-4A90-8BCA-41CE81A3F4E7--

.

------=_Part_8800_641251939.1443715852276
Content-Type: multipart/alternative;
 boundary="----=_Part_8801_1614634551.1443715852276"

------=_Part_8801_1614634551.1443715852276
Content-Type: text/plain; charset=UTF-8

I think this could be solved if we could apply common initial sequence in
that case.
e.g. `pair<Key const, T>&` can alias `pair<Key, T>&` based on this both
have same layout but only difference is constnes of members.
Only danger of that approach is that calling member function will have
different behavior because will work with different const version of
members:
template<typename A, typename B>
struct P
{
    A a;
    B b;
    int foo() { return a.bar() + b.bar(); }
};

struct T
{
    int bar() { return 0; }
    int bar() const { return 1; }
};

union
{
    P<T, T> f;
    P<const T, T> s;
    P<const T, const T> t;
    const P<T, T> r;
} a { P<T, T>{} };

assert(a.f.foo() == 0);
assert(a.s.foo() == 1);
assert(a.t.foo() == 2);
assert(a.r.foo() == 2);



Another example could be `std::move` that will only partially move objects.

On Wednesday, September 30, 2015 at 5:07:52 PM UTC+2, Edward Catmur wrote:
>
> On Wednesday, 30 September 2015 01:14:29 UTC+1, Howard Hinnant wrote:
>>
>>  And there is even more (and more powerful) functionality proposed.  For
>> example one can efficiently change the value of a key using this
>> functionality (with no deallocation/reallocation sequence).
>>
>
> How? *a.extract(k) would still return pair<Key const, T>& so there's no
> actual legal way to modify the key, notwithstanding that modifying it
> wouldn't break container invariants.
>
> I still think this is a great proposal, I just don't think it should be
> oversold.
>

--

---
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_8801_1614634551.1443715852276
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I think this could be solved if we could apply common init=
ial sequence in that case.<br>e.g. `pair&lt;Key const, T&gt;&amp;` can alia=
s `pair&lt;Key, T&gt;&amp;` based on this both have same layout but only di=
fference is constnes of members.<br>Only danger of that approach is that ca=
lling member function will have different behavior because will work with d=
ifferent const version of members:<br><div class=3D"prettyprint" style=3D"b=
ackground-color: rgb(250, 250, 250); border-color: rgb(187, 187, 187); bord=
er-style: solid; border-width: 1px; word-wrap: break-word;"><code class=3D"=
prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #008;" cla=
ss=3D"styled-by-prettify">template</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">&lt;</span><span style=3D"color: #008;" class=3D"st=
yled-by-prettify">typename</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> A</span><span style=3D"color: #660;" class=3D"styled-by-pr=
ettify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">typename</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> B</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">&gt;</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"=
color: #008;" class=3D"styled-by-prettify">struct</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"> P<br></span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 A a</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 B b</span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span><span style=3D"color=
: #008;" class=3D"styled-by-prettify">int</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> foo</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">()</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-pr=
ettify">{</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">return</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"> a</span><span=
 style=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify">bar</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">()</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">+</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> b</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">.</span><span style=3D"color: #000;" class=3D"styled-by-prettify">bar</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">();</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">}</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">};</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br><br></span><span style=3D"color: #008;" class=
=3D"styled-by-prettify">struct</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> T<br></span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">{</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"><br>=C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"style=
d-by-prettify">int</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"> bar</span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">()</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">{</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"c=
olor: #008;" class=3D"styled-by-prettify">return</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #066;" =
class=3D"styled-by-prettify">0</span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">}</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=
=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"styled-by-prettify"=
>int</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> bar</=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">()</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">const</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"style=
d-by-prettify">return</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> </span><span style=3D"color: #066;" class=3D"styled-by-prettify=
">1</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">}</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">};</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"><br><br></span><span style=3D"color: #008;" clas=
s=3D"styled-by-prettify">union</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"><br></span><span style=3D"color: #660;" class=3D"styled=
-by-prettify">{</span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"><br>=C2=A0 =C2=A0 P</span><span style=3D"color: #660;" class=3D"styled=
-by-prettify">&lt;</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify">T</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> T</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">&gt;</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"> f</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 P</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"color:=
 #008;" class=3D"styled-by-prettify">const</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"> T</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> T</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"=
> s</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=
=A0 P</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;<=
/span><span style=3D"color: #008;" class=3D"styled-by-prettify">const</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"> T</span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #00=
8;" class=3D"styled-by-prettify">const</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"> T</span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">&gt;</span><span style=3D"color: #000;" class=3D"styled=
-by-prettify"> t</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>=C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"styled-by-prett=
ify">const</span><span style=3D"color: #000;" class=3D"styled-by-prettify">=
 P</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify">T</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"> T</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">&gt;</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"> r</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"><br></span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">}</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> a =
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">{</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> P</span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify">T</span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> T</span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">&gt;{}</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">};</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br><=
br></span><span style=3D"color: #008;" class=3D"styled-by-prettify">assert<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify">a</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify">f</span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify">foo</span><span style=3D"color: #660;" class=3D"styled-=
by-prettify">()</span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D=
=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span=
><span style=3D"color: #066;" class=3D"styled-by-prettify">0</span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">);</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: =
#008;" class=3D"styled-by-prettify">assert</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify">a</span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">.</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify">s</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify">foo</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">()</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">=3D=3D</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #066;" cla=
ss=3D"styled-by-prettify">1</span><span style=3D"color: #660;" class=3D"sty=
led-by-prettify">);</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify"><br></span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">assert</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify">a</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">t</span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">.</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify">foo</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">()</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">=3D=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> </span><span style=3D"color: #066;" class=3D"styled-by-prettify">2</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">);</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">assert</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify">a</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify">r</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">.</span><span style=3D"color: #000;" class=3D"styled-by-prettify">fo=
o</span><span style=3D"color: #660;" class=3D"styled-by-prettify">()</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">=3D=3D</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #066;" class=3D"styled-by-prettify">2</span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">);</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"><br><br><br></span></div></code></div><br>Another exam=
ple could be `std::move` that will only partially move objects.<br><i></i><=
br>On Wednesday, September 30, 2015 at 5:07:52 PM UTC+2, Edward Catmur wrot=
e:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;b=
order-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">On Wednesda=
y, 30 September 2015 01:14:29 UTC+1, Howard Hinnant  wrote:<blockquote clas=
s=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc =
solid;padding-left:1ex">=C2=A0And there is even more (and more powerful) fu=
nctionality proposed. =C2=A0For example one can efficiently change the valu=
e of a key using this functionality (with no deallocation/reallocation sequ=
ence).
<br></blockquote><div><br></div><div>How? <font face=3D"courier new, monosp=
ace">*a.extract(k)</font> would still return <font face=3D"courier new, mon=
ospace">pair&lt;Key const, T&gt;&amp;</font> so there&#39;s no actual legal=
 way to modify the key, notwithstanding that modifying it wouldn&#39;t brea=
k container invariants.</div><div><br></div><div>I still think this is a gr=
eat proposal, I just don&#39;t think it should be oversold.</div></div></bl=
ockquote></div>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_8801_1614634551.1443715852276--
------=_Part_8800_641251939.1443715852276--

.

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

On Thu, Oct 1, 2015 at 6:37 PM, David Krauss <potswa@gmail.com> wrote:

>
> On 2015=E2=80=9310=E2=80=9301, at 11:26 PM, Ami Tavory <atavory@gmail.com=
> wrote:
>
> Sorry again if I'm misunderstanding you, but I tried to point out that
> I've implemented this in a libstdc++ extension which I think has been
> bundled with g++ for the last decade (at least I always see it in the
> ext/pb_ds directory of /usr/include/c++/[ver]). Incidentally, here are th=
e performance
> tests for the split/join operations from the docs
> <https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_split_join_timin=
g_test.html>.
> Please let me know if I can help out with anything.
>
>
> Howard seems to be simply asking for a write-up which could be properly
> considered by the committee. Just looking at the documentation page
> (perhaps overlooking source code comments), ...
>

  OK, thanks for the explanation. I'll try to phrase it precisely in the
terms you described.


>
> Additional Methods
>
> Tree-based containers support split and join methods. It is possible to
> split a tree so that it passes all nodes with keys larger than a given ke=
y
> to a different tree. These methods have the following advantages over the
> alternative of externally inserting to the destination tree and erasing
> from the source tree:
>
>    1. These methods are efficient - red-black trees are split and joined
>    in poly-logarithmic complexity; ordered-vector trees are split and joi=
ned
>    at linear complexity. The alternatives have super-linear complexity.
>    2. Aside from orders of growth, these operations perform few
>    allocations and de-allocations. For red-black trees, allocations are n=
ot
>    performed, and the methods are exception-free.
>
>
> It looks very promising, but not yet actionable.
>
> Just as I was sending this I got your last message, and though the graphs
> are nice proof, they don=E2=80=99t seem to add any concepts.
>
> A proposal should clearly state the interface you want to add, its
> complexity requirements, and its relation to the existing library and oth=
er
> proposals like extract.
>
> Come back to this list with a draft and we=E2=80=99ll help to point out a=
ny gaps.
>
> For what it=E2=80=99s worth, I think extracting a unique_ptr (or unique_p=
tr-alike)
> and splitting a new container are orthogonal, and both would be nice to
> have.
>
> --
>
> ---
> 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/.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Thu, Oct 1, 2015 at 6:37 PM, David Krauss <span dir=3D"ltr">&lt;<a h=
ref=3D"mailto:potswa@gmail.com" target=3D"_blank">potswa@gmail.com</a>&gt;<=
/span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div style=3D"word-wrap:bre=
ak-word"><span class=3D""><br><div><blockquote type=3D"cite"><div>On 2015=
=E2=80=9310=E2=80=9301, at 11:26 PM, Ami Tavory &lt;<a href=3D"mailto:atavo=
ry@gmail.com" target=3D"_blank">atavory@gmail.com</a>&gt; wrote:</div><br><=
div><div dir=3D"ltr"><div class=3D"gmail_extra">Sorry again if I&#39;m misu=
nderstanding you, but I tried to point out that I&#39;ve implemented this i=
n a libstdc++ extension which I think has been bundled with g++ for the las=
t decade (at least I always see it in the ext/pb_ds directory of /usr/inclu=
de/c++/[ver]). Incidentally, here are the <a href=3D"https://gcc.gnu.org/on=
linedocs/libstdc++/ext/pb_ds/tree_split_join_timing_test.html" target=3D"_b=
lank">performance tests for the split/join operations from the docs</a>. Pl=
ease let me know if I can help out with anything.</div></div></div></blockq=
uote><br></div></span><div><div>Howard seems to be simply asking for a writ=
e-up which could be properly considered by the committee. Just looking at t=
he documentation page (perhaps overlooking source code comments), ...</div>=
</div></div></blockquote><div><br></div><div>=C2=A0 OK, thanks for the expl=
anation. I&#39;ll try to phrase it precisely in the terms you described.</d=
iv><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 style=3D"word-wrap:=
break-word"><div><div><br></div><div><blockquote type=3D"cite"><h2><a name=
=3D"150240da08b16177_add_methods">Additional Methods</a></h2><p>Tree-based =
containers support split and join methods. It is possible to split a tree s=
o that it passes all nodes with keys larger than a given key to a different=
 tree. These methods have the following advantages over the alternative of =
externally inserting to the destination tree and erasing from the source tr=
ee:</p><ol><li>These methods are efficient - red-black trees are split and =
joined in poly-logarithmic complexity; ordered-vector trees are split and j=
oined at linear complexity. The alternatives have super-linear complexity.<=
/li><li>Aside from orders of growth, these operations perform few allocatio=
ns and de-allocations. For red-black trees, allocations are not performed, =
and the methods are exception-free.=C2=A0</li></ol></blockquote><div><br></=
div></div><div>It looks very promising, but not yet actionable.</div><div><=
br></div><div><div>Just as I was sending this I got your last message, and =
though the graphs are nice proof, they don=E2=80=99t seem to add any concep=
ts.</div></div><div><br></div><div>A proposal should clearly state the inte=
rface you want to add, its complexity requirements, and its relation to the=
 existing library and other proposals like extract.</div><div><br></div><di=
v>Come back to this list with a draft and we=E2=80=99ll help to point out a=
ny gaps.</div><div><br></div><div>For what it=E2=80=99s worth, I think extr=
acting a unique_ptr (or unique_ptr-alike) and splitting a new container are=
 orthogonal, and both would be nice to have.</div><div><br></div></div></di=
v><div class=3D"HOEnZb"><div class=3D"h5">

<p></p>

-- <br>
<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+unsubscribe@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 />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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 />

--001a1139bc1847eeb905210d607d--

.

On 10/1/2015 1:10 PM, inkwizytoryankes@gmail.com wrote:
> I think this could be solved if we could apply common initial sequence
> in that case.

The common initial sequence rule applies only to standard-layout unions,=20
so it would only work for standard-layout keys and values, giving=20
undefined behavior elsewhere. Furthermore, you are only allowed to read=20
from a member of the common initial sequence, not modify it.

Regards,
--=20
Agust=C3=ADn K-ballo Berg=C3=A9.-
http://talesofcpp.fusionfenix.com

--=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/.

.

On Oct 1, 2015, at 12:38 PM, Agust=C3=ADn K-ballo Berg=C3=A9 <kaballo86@hot=
mail.com> wrote:
>=20
> On 10/1/2015 1:10 PM, inkwizytoryankes@gmail.com wrote:
>> I think this could be solved if we could apply common initial sequence
>> in that case.
>=20
> The common initial sequence rule applies only to standard-layout unions, =
so it would only work for standard-layout keys and values, giving undefined=
 behavior elsewhere. Furthermore, you are only allowed to read from a membe=
r of the common initial sequence, not modify it.

Fortunately, just like <atomic>, <typeinfo>, and parts of several other lib=
raries such as <type_traits>, <mutex> and <locale>, there is no requirement=
 that <map> be implementable in portable C++.

The std::lib protects us from non-portable and undefined behavior by provid=
ing well-defined functionality that is otherwise unaccessible to us.  Somet=
imes this requires intimate cooperation with the compiler the std::lib ship=
s with.

Howard

--=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/.

.

On 10/1/2015 1:46 PM, Howard Hinnant wrote:
> On Oct 1, 2015, at 12:38 PM, Agust=C3=ADn K-ballo Berg=C3=A9 <kaballo86@h=
otmail.com> wrote:
>>
>> On 10/1/2015 1:10 PM, inkwizytoryankes@gmail.com wrote:
>>> I think this could be solved if we could apply common initial sequence
>>> in that case.
>>
>> The common initial sequence rule applies only to standard-layout unions,=
 so it would only work for standard-layout keys and values, giving undefine=
d behavior elsewhere. Furthermore, you are only allowed to read from a memb=
er of the common initial sequence, not modify it.
>
> Fortunately, just like <atomic>, <typeinfo>, and parts of several other l=
ibraries such as <type_traits>, <mutex> and <locale>, there is no requireme=
nt that <map> be implementable in portable C++.
>
> The std::lib protects us from non-portable and undefined behavior by prov=
iding well-defined functionality that is otherwise unaccessible to us.  Som=
etimes this requires intimate cooperation with the compiler the std::lib sh=
ips with.

Nod, we are saying the same thing, libc++'s implementation requires=20
compiler magic.

Regards,
--=20
Agust=C3=ADn K-ballo Berg=C3=A9.-
http://talesofcpp.fusionfenix.com

--=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/.

.

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

  I'd like to ask about the following alternative, which seems to me like
something between what the paper mentions as "Talbot's original idea" and
this version of the paper. IMHO, it offers improved performance for ordered
containers, natural operations for multi-key containers, and offers nearly
all of the benefits of node_ptr without introducing a new class.

It requires adding split and join methods to all associative containers.

*{map|set} methods:

    void split(iterator b, iterator e, container &other)

Input: takes a range given by two iterators to the object b, e, and another
*empty* object of the same type other;
Effect: transplants the range into other, removing it from the original
object.
Complexity: O( (log(n))^2 ), where n is the size of the object to begin
with.
Exception guarantees: those of the comparison functor (this method does not
allocate memory).

    void join(container &other)

Input: takes an object of same type other, whose keys may not be both
smaller-equal and larger with those of this object.
Effect: transplants the content of other into this object, emptying it.
Complexity: O( (log(max(m, n))^2 ), where m, n are the sizes of the objects
before the operation.
Exception guarantees: those of the comparison functor (this method must not
allocate memory).

unordered_*{map|set} have the following methods:

    void split(const key &k, container &other)

Input: takes a key reference k, and another *empty* object of the same type
other;
Effect: transplants the range of elements with key k, removing it from the
original object.
Complexity: expected O( n ), where n is the size of the range.
Exception guarantees: those of the hash & equality functors, as well as
those of inserting elements into other.

    void join(container &other)

Input: takes an object of same type other.
Effect: transplants the content of other into this object, emptying it.
Complexity: expected O( n ), where n is the size of other before the
operation.
Exception guarantees: none, but if an exception is thrown, the each element
must be in either this object or other.

-------------------------------------------------------------

This alternative has tradeoffs relative to the proposal. It has lower
complexity for ordered associative containers. It extends naturally to
multi-key containers. It unfortunately is not generic w.r.t.
ordered/unordered containers.

Another point is that an empty container can basically function as a
node_ptr (by splitting a single-size range into it), without introducing a
new class. For ordered containers, there are no disadvantages (no
exceptions can be thrown). For unordered containers, there is a
disadvantage in terms of exception safety, but it is less severe than might
be thought. It's possible to configure an empty unordered associative
container so that it will not throw on the first insert. Thus for a
sequence of movements between containers, a single object can be pre-built,
and then used repeatedly with no exception possibilities.



On Thu, Oct 1, 2015 at 6:37 PM, David Krauss <potswa@gmail.com> wrote:

>
> On 2015=E2=80=9310=E2=80=9301, at 11:26 PM, Ami Tavory <atavory@gmail.com=
> wrote:
>
> Sorry again if I'm misunderstanding you, but I tried to point out that
> I've implemented this in a libstdc++ extension which I think has been
> bundled with g++ for the last decade (at least I always see it in the
> ext/pb_ds directory of /usr/include/c++/[ver]). Incidentally, here are th=
e performance
> tests for the split/join operations from the docs
> <https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_split_join_timin=
g_test.html>.
> Please let me know if I can help out with anything.
>
>
> Howard seems to be simply asking for a write-up which could be properly
> considered by the committee. Just looking at the documentation page
> (perhaps overlooking source code comments), all I see is this:
>
> Additional Methods
>
> Tree-based containers support split and join methods. It is possible to
> split a tree so that it passes all nodes with keys larger than a given ke=
y
> to a different tree. These methods have the following advantages over the
> alternative of externally inserting to the destination tree and erasing
> from the source tree:
>
>    1. These methods are efficient - red-black trees are split and joined
>    in poly-logarithmic complexity; ordered-vector trees are split and joi=
ned
>    at linear complexity. The alternatives have super-linear complexity.
>    2. Aside from orders of growth, these operations perform few
>    allocations and de-allocations. For red-black trees, allocations are n=
ot
>    performed, and the methods are exception-free.
>
>
> It looks very promising, but not yet actionable.
>
> Just as I was sending this I got your last message, and though the graphs
> are nice proof, they don=E2=80=99t seem to add any concepts.
>
> A proposal should clearly state the interface you want to add, its
> complexity requirements, and its relation to the existing library and oth=
er
> proposals like extract.
>
> Come back to this list with a draft and we=E2=80=99ll help to point out a=
ny gaps.
>
> For what it=E2=80=99s worth, I think extracting a unique_ptr (or unique_p=
tr-alike)
> and splitting a new container are orthogonal, and both would be nice to
> have.
>
> --
>
> ---
> 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/.

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

<div dir=3D"ltr">=C2=A0 I&#39;d like to ask about the following alternative=
, which seems to me like something between what the paper mentions as &quot=
;Talbot&#39;s original idea&quot; and this version of the paper. IMHO, it o=
ffers improved performance for ordered containers, natural operations for m=
ulti-key containers, and offers nearly all of the benefits of <font face=3D=
"arial, helvetica, sans-serif">node_ptr</font> without introducing a new cl=
ass.<div><br></div><div>It requires adding <font face=3D"monospace, monospa=
ce">split</font> and <font face=3D"monospace, monospace">join</font> method=
s to all associative containers.=C2=A0<div><br></div><div><font face=3D"mon=
ospace, monospace">*{map|set}</font><font face=3D"arial, helvetica, sans-se=
rif">=C2=A0methods:</font></div></div><div><font face=3D"arial, helvetica, =
sans-serif"><br></font></div><div><font face=3D"arial, helvetica, sans-seri=
f">=C2=A0 =C2=A0 </font><font face=3D"monospace, monospace">void split(iter=
ator b, iterator e, container &amp;other)</font></div><div><font face=3D"ar=
ial, helvetica, sans-serif"><br></font></div><div><font face=3D"arial, helv=
etica, sans-serif">Input: takes a range given by two iterators to the objec=
t </font><font face=3D"monospace, monospace">b</font><font face=3D"arial, h=
elvetica, sans-serif">, </font><font face=3D"monospace, monospace">e,</font=
><font face=3D"arial, helvetica, sans-serif"> and another <u>empty</u>=C2=
=A0object of the same type </font><font face=3D"monospace, monospace">other=
</font><font face=3D"arial, helvetica, sans-serif">;=C2=A0</font></div><div=
><font face=3D"arial, helvetica, sans-serif">Effect: transplants the range =
into other, removing it from the original object.</font></div><div><font fa=
ce=3D"arial, helvetica, sans-serif">Complexity: O( (log(n))^2 ), where n is=
 the size of the object to begin with.</font></div><div><font face=3D"arial=
, helvetica, sans-serif">Exception guarantees: those of the comparison func=
tor (this method does not allocate memory).</font></div><div><font face=3D"=
arial, helvetica, sans-serif"><br></font></div><div><font face=3D"arial, he=
lvetica, sans-serif">=C2=A0 =C2=A0 </font><font face=3D"monospace, monospac=
e">void join(container &amp;other)</font></div><div><font face=3D"arial, he=
lvetica, sans-serif"><br></font></div><div><font face=3D"arial, helvetica, =
sans-serif">Input: takes an object of same type other, whose keys may not b=
e both smaller-equal and larger with those of this object.</font></div><div=
><font face=3D"arial, helvetica, sans-serif">Effect: transplants the conten=
t of other into this object, emptying it.</font></div><div><font face=3D"ar=
ial, helvetica, sans-serif">Complexity: O( (log(max(m, n))^2 ), where m, n =
are the sizes of the objects before the operation.</font></div><div><div><f=
ont face=3D"arial, helvetica, sans-serif">Exception guarantees: those of th=
e comparison functor (this method must not allocate memory).</font></div></=
div><div><font face=3D"arial, helvetica, sans-serif"><br></font></div><div>=
<font face=3D"monospace, monospace">unordered_*{map|set}</font><font face=
=3D"arial, helvetica, sans-serif"> have the following methods:</font></div>=
<div><font face=3D"arial, helvetica, sans-serif"><br></font></div><div><div=
><font face=3D"arial, helvetica, sans-serif">=C2=A0 =C2=A0=C2=A0</font><fon=
t face=3D"monospace, monospace">void split(const key &amp;k, container &amp=
;other)</font></div><div><font face=3D"arial, helvetica, sans-serif"><br></=
font></div><div><font face=3D"arial, helvetica, sans-serif">Input: takes a =
key reference </font><font face=3D"monospace, monospace">k,</font><font fac=
e=3D"arial, helvetica, sans-serif">=C2=A0and another=C2=A0<u>empty</u>=C2=
=A0object of the same type=C2=A0</font><font face=3D"monospace, monospace">=
other</font><font face=3D"arial, helvetica, sans-serif">;=C2=A0</font></div=
><div><font face=3D"arial, helvetica, sans-serif">Effect: transplants the r=
ange of elements with key </font><font face=3D"monospace, monospace">k</fon=
t><font face=3D"arial, helvetica, sans-serif">, removing it from the origin=
al object.</font></div><div><font face=3D"arial, helvetica, sans-serif">Com=
plexity: expected O( n ), where n is the size of the range.</font></div><di=
v><font face=3D"arial, helvetica, sans-serif">Exception guarantees: those o=
f the hash &amp; equality functors, as well as those of inserting elements =
into </font><font face=3D"monospace, monospace">other</font><font face=3D"a=
rial, helvetica, sans-serif">.</font></div><div><font face=3D"arial, helvet=
ica, sans-serif"><br></font></div><div><font face=3D"arial, helvetica, sans=
-serif">=C2=A0 =C2=A0=C2=A0</font><font face=3D"monospace, monospace">void =
join(container &amp;other)</font></div><div><font face=3D"arial, helvetica,=
 sans-serif"><br></font></div><div><font face=3D"arial, helvetica, sans-ser=
if">Input: takes an object of same type other.</font></div><div><font face=
=3D"arial, helvetica, sans-serif">Effect: transplants the content of other =
into this object, emptying it.</font></div><div><font face=3D"arial, helvet=
ica, sans-serif">Complexity: expected O( n ), where n is the size of other =
before the operation.</font></div><div><font face=3D"arial, helvetica, sans=
-serif">Exception guarantees: none, but if an exception is thrown, the each=
 element must be in either this object or </font><font face=3D"monospace, m=
onospace">other</font><font face=3D"arial, helvetica, sans-serif">.</font><=
/div></div><div><font face=3D"arial, helvetica, sans-serif"><br></font></di=
v><div><font face=3D"arial, helvetica, sans-serif">------------------------=
-------------------------------------</font></div><div><font face=3D"arial,=
 helvetica, sans-serif"><br></font></div><div><font face=3D"arial, helvetic=
a, sans-serif">This alternative has tradeoffs relative to the proposal. It =
has lower complexity for ordered associative containers. It extends natural=
ly to multi-key containers. It unfortunately is not generic w.r.t. ordered/=
unordered containers.</font></div><div><font face=3D"arial, helvetica, sans=
-serif"><br></font></div><div><font face=3D"arial, helvetica, sans-serif">A=
nother point is that an empty container can basically function as a node_pt=
r=C2=A0</font><span style=3D"font-family:arial,helvetica,sans-serif">(by sp=
litting a single-size range into it)</span><span style=3D"font-family:arial=
,helvetica,sans-serif">, without introducing a new class. For ordered conta=
iners, there are no disadvantages (no exceptions can be thrown). For unorde=
red containers, there is a disadvantage in terms of exception safety, but i=
t is less severe than might be thought. It&#39;s possible to configure an e=
mpty unordered associative container so that it will not throw on the first=
 insert. Thus for a sequence of movements between containers, a single obje=
ct can be pre-built, and then used repeatedly with no exception possibiliti=
es.=C2=A0</span></div><div><font face=3D"arial, helvetica, sans-serif"><br>=
</font></div><div><font face=3D"arial, helvetica, sans-serif"><br></font></=
div></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Thu,=
 Oct 1, 2015 at 6:37 PM, David Krauss <span dir=3D"ltr">&lt;<a href=3D"mail=
to:potswa@gmail.com" target=3D"_blank">potswa@gmail.com</a>&gt;</span> wrot=
e:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-l=
eft:1px #ccc solid;padding-left:1ex"><div style=3D"word-wrap:break-word"><s=
pan class=3D""><br><div><blockquote type=3D"cite"><div>On 2015=E2=80=9310=
=E2=80=9301, at 11:26 PM, Ami Tavory &lt;<a href=3D"mailto:atavory@gmail.co=
m" target=3D"_blank">atavory@gmail.com</a>&gt; wrote:</div><br><div><div di=
r=3D"ltr"><div class=3D"gmail_extra">Sorry again if I&#39;m misunderstandin=
g you, but I tried to point out that I&#39;ve implemented this in a libstdc=
++ extension which I think has been bundled with g++ for the last decade (a=
t least I always see it in the ext/pb_ds directory of /usr/include/c++/[ver=
]). Incidentally, here are the <a href=3D"https://gcc.gnu.org/onlinedocs/li=
bstdc++/ext/pb_ds/tree_split_join_timing_test.html" target=3D"_blank">perfo=
rmance tests for the split/join operations from the docs</a>. Please let me=
 know if I can help out with anything.</div></div></div></blockquote><br></=
div></span><div><div>Howard seems to be simply asking for a write-up which =
could be properly considered by the committee. Just looking at the document=
ation page (perhaps overlooking source code comments), all I see is this:</=
div><div><br></div><div><blockquote type=3D"cite"><h2><a name=3D"150240da08=
b16177_add_methods">Additional Methods</a></h2><p>Tree-based containers sup=
port split and join methods. It is possible to split a tree so that it pass=
es all nodes with keys larger than a given key to a different tree. These m=
ethods have the following advantages over the alternative of externally ins=
erting to the destination tree and erasing from the source tree:</p><ol><li=
>These methods are efficient - red-black trees are split and joined in poly=
-logarithmic complexity; ordered-vector trees are split and joined at linea=
r complexity. The alternatives have super-linear complexity.</li><li>Aside =
from orders of growth, these operations perform few allocations and de-allo=
cations. For red-black trees, allocations are not performed, and the method=
s are exception-free.=C2=A0</li></ol></blockquote><div><br></div></div><div=
>It looks very promising, but not yet actionable.</div><div><br></div><div>=
<div>Just as I was sending this I got your last message, and though the gra=
phs are nice proof, they don=E2=80=99t seem to add any concepts.</div></div=
><div><br></div><div>A proposal should clearly state the interface you want=
 to add, its complexity requirements, and its relation to the existing libr=
ary and other proposals like extract.</div><div><br></div><div>Come back to=
 this list with a draft and we=E2=80=99ll help to point out any gaps.</div>=
<div><br></div><div>For what it=E2=80=99s worth, I think extracting a uniqu=
e_ptr (or unique_ptr-alike) and splitting a new container are orthogonal, a=
nd both would be nice to have.</div><div><br></div></div></div><div class=
=3D"HOEnZb"><div class=3D"h5">

<p></p>

-- <br>
<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+unsubscribe@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>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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 />

--001a113a91c88a5fbc052112f62a--

.

--Apple-Mail=_288B0C2B-5F58-4263-AC76-543C5E9CF18C
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9310=E2=80=9302, at 6:56 AM, Ami Tavory <atavory@gmail.com>=
 wrote:
>=20
>   I'd like to ask about the following alternative, which seems to me like=
 something between what the paper mentions as "Talbot's original idea" and =
this version of the paper. IMHO, it offers improved performance for ordered=
 containers, natural operations for multi-key containers, and offers nearly=
 all of the benefits of node_ptr without introducing a new class.

I suspect that node_ptr should be a unique_ptr specialization. Its treatmen=
t of allocators (propagate_on_container_move_assignment etc) is unnecessary=
 and complex. Pointers are not containers. See P0043 <http://wg21.link/p004=
3>P004 <http://wg21.link/p0042>3 =C2=A71.1 for some tangential treatment.

> It requires adding split and join methods to all associative containers.=
=20
>=20
> *{map|set} methods:
>=20
>     void split(iterator b, iterator e, container &other)

Why does this not return by value? Is efficiency gained by passing a non-em=
pty other, as opposed to separate split and join operations?

Even so, I think that split-by-value should be provided.

> Input: takes a range given by two iterators to the object b, e, and anoth=
er empty object of the same type other;=20
> Effect: transplants the range into other, removing it from the original o=
bject.
> Complexity: O( (log(n))^2 ), where n is the size of the object to begin w=
ith.
> Exception guarantees: those of the comparison functor (this method does n=
ot allocate memory).
>=20
>     void join(container &other)

This should take an rvalue reference with move-from semantics. Also, it may=
 allocate memory when the source has an unequal allocator.

> Input: takes an object of same type other, whose keys may not be both sma=
ller-equal and larger with those of this object.
> Effect: transplants the content of other into this object, emptying it.
> Complexity: O( (log(max(m, n))^2 ), where m, n are the sizes of the objec=
ts before the operation.
> Exception guarantees: those of the comparison functor (this method must n=
ot allocate memory).
>=20
> unordered_*{map|set} have the following methods:
>=20
>     void split(const key &k, container &other)
>=20
> Input: takes a key reference k, and another empty object of the same type=
 other;=20

This should certainly return by value instead.

> Another point is that an empty container can basically function as a node=
_ptr (by splitting a single-size range into it), without introducing a new =
class.

I suspect that node_ptr is intended simply as an interface wrapper on a con=
tainer class. I=E2=80=99d presume that this solution was already considered=
..

> For ordered containers, there are no disadvantages (no exceptions can be =
thrown). For unordered containers, there is a disadvantage in terms of exce=
ption safety, but it is less severe than might be thought. It's possible to=
 configure an empty unordered associative container so that it will not thr=
ow on the first insert. Thus for a sequence of movements between containers=
, a single object can be pre-built, and then used repeatedly with no except=
ion possibilities.=20

No possible exception subsequent to populating that first object, right? Th=
is somewhat explains the reference parameters, but the difference seems uns=
ubstantial.

Altogether this looks pretty good, thanks for sharing!

--=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/.

--Apple-Mail=_288B0C2B-5F58-4263-AC76-543C5E9CF18C
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9310=
=E2=80=9302, at 6:56 AM, Ami Tavory &lt;<a href=3D"mailto:atavory@gmail.com=
" class=3D"">atavory@gmail.com</a>&gt; wrote:</div><br class=3D"Apple-inter=
change-newline"><div class=3D""><div dir=3D"ltr" class=3D"">&nbsp; I'd like=
 to ask about the following alternative, which seems to me like something b=
etween what the paper mentions as "Talbot's original idea" and this version=
 of the paper. IMHO, it offers improved performance for ordered containers,=
 natural operations for multi-key containers, and offers nearly all of the =
benefits of <font face=3D"arial, helvetica, sans-serif" class=3D"">node_ptr=
</font> without introducing a new class.<div class=3D""></div></div></div><=
/blockquote><div><br class=3D""></div><div>I suspect that <font face=3D"Cou=
rier" class=3D"">node_ptr</font> should be a <font face=3D"Courier" class=
=3D"">unique_ptr</font> specialization. Its treatment of allocators (<font =
face=3D"Courier" class=3D"">propagate_on_container_move_assignment</font> e=
tc) is unnecessary and complex. Pointers are not containers. See&nbsp;<a hr=
ef=3D"http://wg21.link/p0043" class=3D""><a href=3D"http://wg21.link/p0042"=
 class=3D"">P004</a>3</a>&nbsp;=C2=A71.1 for some tangential treatment.</di=
v><br class=3D""><blockquote type=3D"cite" class=3D""><div class=3D""><div =
dir=3D"ltr" class=3D""><div class=3D"">It requires adding <font face=3D"mon=
ospace, monospace" class=3D"">split</font> and <font face=3D"monospace, mon=
ospace" class=3D"">join</font> methods to all associative containers.&nbsp;=
<div class=3D""><br class=3D""></div><div class=3D""><font face=3D"monospac=
e, monospace" class=3D"">*{map|set}</font><font face=3D"arial, helvetica, s=
ans-serif" class=3D"">&nbsp;methods:</font></div></div><div class=3D""><fon=
t face=3D"arial, helvetica, sans-serif" class=3D""><br class=3D""></font></=
div><div class=3D""><font face=3D"arial, helvetica, sans-serif" class=3D"">=
&nbsp; &nbsp; </font><font face=3D"monospace, monospace" class=3D"">void sp=
lit(iterator b, iterator e, container &amp;other)</font></div><div class=3D=
""></div><div class=3D""></div></div></div></blockquote><div><br class=3D""=
></div><div>Why does this not return by value? Is efficiency gained by pass=
ing a non-empty other, as opposed to separate split and join operations?</d=
iv><div><br class=3D""></div><div>Even so, I think that split-by-value shou=
ld be provided.</div><br class=3D""><blockquote type=3D"cite" class=3D""><d=
iv class=3D""><div dir=3D"ltr" class=3D""><div class=3D""><font face=3D"ari=
al, helvetica, sans-serif" class=3D"">Input: takes a range given by two ite=
rators to the object </font><font face=3D"monospace, monospace" class=3D"">=
b</font><font face=3D"arial, helvetica, sans-serif" class=3D"">, </font><fo=
nt face=3D"monospace, monospace" class=3D"">e,</font><font face=3D"arial, h=
elvetica, sans-serif" class=3D""> and another <u class=3D"">empty</u>&nbsp;=
object of the same type </font><font face=3D"monospace, monospace" class=3D=
"">other</font><font face=3D"arial, helvetica, sans-serif" class=3D"">;&nbs=
p;</font></div><div class=3D""><font face=3D"arial, helvetica, sans-serif" =
class=3D"">Effect: transplants the range into other, removing it from the o=
riginal object.</font></div><div class=3D""><font face=3D"arial, helvetica,=
 sans-serif" class=3D"">Complexity: O( (log(n))^2 ), where n is the size of=
 the object to begin with.</font></div><div class=3D""><font face=3D"arial,=
 helvetica, sans-serif" class=3D"">Exception guarantees: those of the compa=
rison functor (this method does not allocate memory).</font></div><div clas=
s=3D""><font face=3D"arial, helvetica, sans-serif" class=3D""><br class=3D"=
"></font></div><div class=3D""><font face=3D"arial, helvetica, sans-serif" =
class=3D"">&nbsp; &nbsp; </font><font face=3D"monospace, monospace" class=
=3D"">void join(container &amp;other)</font></div><div class=3D""></div><di=
v class=3D""></div></div></div></blockquote><div><br class=3D""></div><div>=
This should take an rvalue reference with move-from semantics. Also, it may=
 allocate memory when the source has an unequal allocator.</div><br class=
=3D""><blockquote type=3D"cite" class=3D""><div class=3D""><div dir=3D"ltr"=
 class=3D""><div class=3D""><font face=3D"arial, helvetica, sans-serif" cla=
ss=3D"">Input: takes an object of same type other, whose keys may not be bo=
th smaller-equal and larger with those of this object.</font></div><div cla=
ss=3D""><font face=3D"arial, helvetica, sans-serif" class=3D"">Effect: tran=
splants the content of other into this object, emptying it.</font></div><di=
v class=3D""><font face=3D"arial, helvetica, sans-serif" class=3D"">Complex=
ity: O( (log(max(m, n))^2 ), where m, n are the sizes of the objects before=
 the operation.</font></div><div class=3D""><div class=3D""><font face=3D"a=
rial, helvetica, sans-serif" class=3D"">Exception guarantees: those of the =
comparison functor (this method must not allocate memory).</font></div></di=
v><div class=3D""><font face=3D"arial, helvetica, sans-serif" class=3D""><b=
r class=3D""></font></div><div class=3D""><font face=3D"monospace, monospac=
e" class=3D"">unordered_*{map|set}</font><font face=3D"arial, helvetica, sa=
ns-serif" class=3D""> have the following methods:</font></div><div class=3D=
""><font face=3D"arial, helvetica, sans-serif" class=3D""><br class=3D""></=
font></div><div class=3D""><div class=3D""><font face=3D"arial, helvetica, =
sans-serif" class=3D"">&nbsp; &nbsp;&nbsp;</font><font face=3D"monospace, m=
onospace" class=3D"">void split(const key &amp;k, container &amp;other)</fo=
nt></div><div class=3D""><font face=3D"arial, helvetica, sans-serif" class=
=3D""><br class=3D""></font></div><div class=3D""><font face=3D"arial, helv=
etica, sans-serif" class=3D"">Input: takes a key reference </font><font fac=
e=3D"monospace, monospace" class=3D"">k,</font><font face=3D"arial, helveti=
ca, sans-serif" class=3D"">&nbsp;and another&nbsp;<u class=3D"">empty</u>&n=
bsp;object of the same type&nbsp;</font><font face=3D"monospace, monospace"=
 class=3D"">other</font><font face=3D"arial, helvetica, sans-serif" class=
=3D"">;&nbsp;</font></div></div></div></div></blockquote><div><br class=3D"=
"></div><div>This should certainly return by value instead.</div><br class=
=3D""><blockquote type=3D"cite" class=3D""><div dir=3D"ltr" class=3D""><div=
 class=3D""><div class=3D""><font face=3D"arial, helvetica, sans-serif" cla=
ss=3D"">Another point is that an empty container can basically function as =
a node_ptr&nbsp;</font><span class=3D"" style=3D"font-family: arial, helvet=
ica, sans-serif;">(by splitting a single-size range into it)</span><span cl=
ass=3D"" style=3D"font-family: arial, helvetica, sans-serif;">, without int=
roducing a new class. </span></div></div></div></blockquote><div><br class=
=3D""></div><div>I suspect that <font face=3D"Courier" class=3D"">node_ptr<=
/font> is intended simply as an interface wrapper on a container class. I=
=E2=80=99d presume that this solution was already considered.</div><br clas=
s=3D""><blockquote type=3D"cite" class=3D""><div dir=3D"ltr" class=3D""><di=
v class=3D""><div class=3D""><span class=3D"" style=3D"font-family: arial, =
helvetica, sans-serif;">For ordered containers, there are no disadvantages =
(no exceptions can be thrown). For unordered containers, there is a disadva=
ntage in terms of exception safety, but it is less severe than might be tho=
ught. It's possible to configure an empty unordered associative container s=
o that it will not throw on the first insert. Thus for a sequence of moveme=
nts between containers, a single object can be pre-built, and then used rep=
eatedly with no exception possibilities.&nbsp;</span></div></div></div></bl=
ockquote></div><br class=3D""><div class=3D"">No possible exception subsequ=
ent to populating that first object, right? This somewhat explains the refe=
rence parameters, but the difference seems unsubstantial.</div><div class=
=3D""><br class=3D""></div><div class=3D"">Altogether this looks pretty goo=
d, thanks for sharing!</div><div class=3D""><br class=3D""></div></body></h=
tml>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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 />

--Apple-Mail=_288B0C2B-5F58-4263-AC76-543C5E9CF18C--

.

------=_Part_242_388027321.1443782748545
Content-Type: multipart/alternative;
 boundary="----=_Part_243_131686448.1443782748545"

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

My point was relaxing this rules to not standard layout types if difference=
=20
is only const.
If we don't change const type we have exactly same type and we could allow=
=20
writing to it from any union member.
If we change constnes then we can only read from that. Only rule here would=
=20
be that current active union member should not have const members.

union
{
    pair<A, B> a;
    pair<const A, B> b;
} u1, u2;

new (&u1.a) pair<A, B>();
u1.a.first.foo(); //current allowed
u1.b.first.foo(); //using IntSeqRul, different member type, only read=20
allowed
u1.b.second.bar(); //using IntSeqRul, same member type, write allowed

new (&u2.b) pair<A, B>();
u2.a.first.foo(); //illegal because it remove const



On Thursday, October 1, 2015 at 6:38:35 PM UTC+2, Agust=C3=ADn K-ballo Berg=
=C3=A9=20
wrote:
>
> On 10/1/2015 1:10 PM, inkwizyt...@gmail.com <javascript:> wrote:=20
> > I think this could be solved if we could apply common initial sequence=
=20
> > in that case.=20
>
> The common initial sequence rule applies only to standard-layout unions,=
=20
> so it would only work for standard-layout keys and values, giving=20
> undefined behavior elsewhere. Furthermore, you are only allowed to read=
=20
> from a member of the common initial sequence, not modify it.=20
>
> Regards,=20
> --=20
> Agust=C3=ADn K-ballo Berg=C3=A9.-=20
> http://talesofcpp.fusionfenix.com=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_243_131686448.1443782748545
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">My point was relaxing this rules to not standard layout ty=
pes if difference is only const.<br>If we don&#39;t change const type we ha=
ve exactly same type and we could allow writing to it from any union member=
..<br>If we change constnes then we can only read from that. Only rule here =
would be that current active union member should not have const members.<br=
><br><div class=3D"prettyprint" style=3D"background-color: rgb(250, 250, 25=
0); border-color: rgb(187, 187, 187); border-style: solid; border-width: 1p=
x; word-wrap: break-word;"><code class=3D"prettyprint"><div class=3D"subpre=
ttyprint">union<br>{<br>=C2=A0=C2=A0=C2=A0 pair&lt;A, B&gt; a;<br>=C2=A0=C2=
=A0=C2=A0 pair&lt;const A, B&gt; b;<br>} u1, u2;<br><br>new (&amp;u1.a) pai=
r&lt;A, B&gt;();<br>u1.a.first.foo(); //current allowed<br>u1.b.first.foo()=
; //using IntSeqRul, different member type, only read allowed<br>u1.b.secon=
d.bar(); //using IntSeqRul, same member type, write allowed<br><br>new (&am=
p;u2.b) pair&lt;A, B&gt;();<br>u2.a.first.foo(); //illegal because it remov=
e const<code class=3D"prettyprint"><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"><br></span></code></div></code></div><br><br><br>On Thurs=
day, October 1, 2015 at 6:38:35 PM UTC+2, Agust=C3=ADn K-ballo Berg=C3=A9 w=
rote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8e=
x;border-left: 1px #ccc solid;padding-left: 1ex;">On 10/1/2015 1:10 PM, <a =
href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"8OvkhkOiCgA=
J" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;javascript:&#39;;return=
 true;" onclick=3D"this.href=3D&#39;javascript:&#39;;return true;">inkwizyt=
....@gmail.com</a> wrote:
<br>&gt; I think this could be solved if we could apply common initial sequ=
ence
<br>&gt; in that case.
<br>
<br>The common initial sequence rule applies only to standard-layout unions=
,=20
<br>so it would only work for standard-layout keys and values, giving=20
<br>undefined behavior elsewhere. Furthermore, you are only allowed to read=
=20
<br>from a member of the common initial sequence, not modify it.
<br>
<br>Regards,
<br>--=20
<br>Agust=C3=ADn K-ballo Berg=C3=A9.-
<br><a href=3D"http://talesofcpp.fusionfenix.com" target=3D"_blank" rel=3D"=
nofollow" onmousedown=3D"this.href=3D&#39;http://www.google.com/url?q\75htt=
p%3A%2F%2Ftalesofcpp.fusionfenix.com\46sa\75D\46sntz\0751\46usg\75AFQjCNGrO=
c8fm1PhW0305mMc5XVd9NU-_Q&#39;;return true;" onclick=3D"this.href=3D&#39;ht=
tp://www.google.com/url?q\75http%3A%2F%2Ftalesofcpp.fusionfenix.com\46sa\75=
D\46sntz\0751\46usg\75AFQjCNGrOc8fm1PhW0305mMc5XVd9NU-_Q&#39;;return true;"=
>http://talesofcpp.fusionfenix.<wbr>com</a>
<br></blockquote></div>

<p></p>

-- <br />
<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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_243_131686448.1443782748545--
------=_Part_242_388027321.1443782748545--

.

------=_Part_987_1202216477.1459897058396
Content-Type: multipart/alternative;
 boundary="----=_Part_988_2962696.1459897058396"

------=_Part_988_2962696.1459897058396
Content-Type: text/plain; charset=UTF-8

Hello,
I just read the post-Jacksonville version of the paper (P0083R2) and I have
a question (hope this is the right place for it).
Why doesn't the paper propose adding the node_handle interface to
{forward_}list as well?
It will enable a uniform extraction API for all node-based containers in
the STL and I don't see any immediate problems.

On Wednesday, September 30, 2015 at 2:30:47 AM UTC+3, Aso Renji wrote:
>
> std::list contain splice method, that can move values from on list to
> another, but std::map - not. Why std::map don't have same functional? Very
> simple proposal - include splice method into std::map. If target map
> already have same keys as moved values, splice throw exception. In other
> case splice grant no-throw guarantee. Yes, i can move values through pair
> of map1.insert(*it) and map2.erase(it). But in this case my code can't
> grant any no-throw guarantee, because any call of std::map::insert can
> throw std::bad_alloc.
>

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/6bee2eeb-bd2b-4972-92d9-2a9ae07f2444%40isocpp.org.

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

<div dir=3D"ltr">Hello,<div>I just read the post-Jacksonville version of th=
e paper (P0083R2) and I have a question (hope this is the right place for i=
t).</div><div>Why doesn&#39;t the paper propose adding the node_handle inte=
rface to {forward_}list as well?</div><div>It will enable a uniform extract=
ion API for all node-based containers in the STL and I don&#39;t see any im=
mediate problems.</div><div><br>On Wednesday, September 30, 2015 at 2:30:47=
 AM UTC+3, Aso Renji wrote:<blockquote class=3D"gmail_quote" style=3D"margi=
n: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><di=
v dir=3D"ltr"><p>std::list contain splice method, that can move values from=
 on list to another, but std::map - not. Why std::map don&#39;t have same f=
unctional? Very simple proposal - include splice method into std::map. If t=
arget map already have same keys as moved values, splice throw exception. I=
n other case splice grant no-throw guarantee. Yes, i can move values throug=
h pair of map1.insert(*it) and map2.erase(it). But in this case my code can=
&#39;t grant any no-throw guarantee, because any call of std::map::insert c=
an throw std::bad_alloc.<br></p></div></blockquote></div></div>

<p></p>

-- <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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/6bee2eeb-bd2b-4972-92d9-2a9ae07f2444%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/6bee2eeb-bd2b-4972-92d9-2a9ae07f2444=
%40isocpp.org</a>.<br />

------=_Part_988_2962696.1459897058396--
------=_Part_987_1202216477.1459897058396--

.

------=_Part_1592_1725884290.1459929194217
Content-Type: multipart/alternative;
 boundary="----=_Part_1593_431327994.1459929194217"

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

My best guess is that it's not the problem that the paper is trying to=20
solve; having a uniform API would be interesting, but it's already possible=
=20
to splice lists.

I guess that if the std::map & std::set splicing proposal is accepted, then=
=20
a subsequent proposal could propose a similar interface for lists too, but=
=20
in this
case it would also be interesting to see how it plays with P0310=20
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0310r0.pdf) which=
=20
proposes
among other things to expose the node type of a list to users.

Le mercredi 6 avril 2016 00:57:38 UTC+2, Omer Rosler a =C3=A9crit :
>
> Hello,
> I just read the post-Jacksonville version of the paper (P0083R2) and I=20
> have a question (hope this is the right place for it).
> Why doesn't the paper propose adding the node_handle interface to=20
> {forward_}list as well?
> It will enable a uniform extraction API for all node-based containers in=
=20
> the STL and I don't see any immediate problems.
>
> On Wednesday, September 30, 2015 at 2:30:47 AM UTC+3, Aso Renji wrote:
>>
>> std::list contain splice method, that can move values from on list to=20
>> another, but std::map - not. Why std::map don't have same functional? Ve=
ry=20
>> simple proposal - include splice method into std::map. If target map=20
>> already have same keys as moved values, splice throw exception. In other=
=20
>> case splice grant no-throw guarantee. Yes, i can move values through pai=
r=20
>> of map1.insert(*it) and map2.erase(it). But in this case my code can't=
=20
>> grant any no-throw guarantee, because any call of std::map::insert can=
=20
>> throw std::bad_alloc.
>>
>

--=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.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/dc0cba53-22e3-4315-ae87-4615b034d925%40isocpp.or=
g.

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

<div dir=3D"ltr">My best guess is that it&#39;s not the problem that the pa=
per is trying to solve; having a uniform API would be interesting, but it&#=
39;s already possible to splice lists.<br><br>I guess that if the std::map =
&amp; std::set splicing proposal is accepted, then a subsequent proposal co=
uld propose a similar interface for lists too, but in this<br>case it would=
 also be interesting to see how it plays with P0310 (http://www.open-std.or=
g/jtc1/sc22/wg21/docs/papers/2016/p0310r0.pdf) which proposes<br>among othe=
r things to expose the node type of a list to users.<br><br>Le mercredi 6 a=
vril 2016 00:57:38 UTC+2, Omer Rosler a =C3=A9crit=C2=A0:<blockquote class=
=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #cc=
c solid;padding-left: 1ex;"><div dir=3D"ltr">Hello,<div>I just read the pos=
t-Jacksonville version of the paper (P0083R2) and I have a question (hope t=
his is the right place for it).</div><div>Why doesn&#39;t the paper propose=
 adding the node_handle interface to {forward_}list as well?</div><div>It w=
ill enable a uniform extraction API for all node-based containers in the ST=
L and I don&#39;t see any immediate problems.</div><div><br>On Wednesday, S=
eptember 30, 2015 at 2:30:47 AM UTC+3, Aso Renji wrote:<blockquote class=3D=
"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc soli=
d;padding-left:1ex"><div dir=3D"ltr"><p>std::list contain splice method, th=
at can move values from on list to another, but std::map - not. Why std::ma=
p don&#39;t have same functional? Very simple proposal - include splice met=
hod into std::map. If target map already have same keys as moved values, sp=
lice throw exception. In other case splice grant no-throw guarantee. Yes, i=
 can move values through pair of map1.insert(*it) and map2.erase(it). But i=
n this case my code can&#39;t grant any no-throw guarantee, because any cal=
l of std::map::insert can throw std::bad_alloc.<br></p></div></blockquote><=
/div></div></blockquote></div>

<p></p>

-- <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+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/dc0cba53-22e3-4315-ae87-4615b034d925%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/dc0cba53-22e3-4315-ae87-4615b034d925=
%40isocpp.org</a>.<br />

------=_Part_1593_431327994.1459929194217--
------=_Part_1592_1725884290.1459929194217--

.