Hi,

Whenever I find myself using std::list, I do so because of slice(). Yet
a typical slice() call like

    std::list<~~~> local;
    local.splice(local.begin(), tasks, tasks.begin());

is quite a mouthful and even long-time C++ developers (incl. myself)
need to look up what this call does. In C++17, and with std::set, this
could be written as:

    auto local = tasks.extract(tasks.begin());

which is self-documenting, even if you don't remember the exact
semantics of extract() - at least it's clear what is being extracted. We
also don't need to duplicate the type of 'tasks', thanks to auto.

Now, surely when extract() was added to the associative containers,
adding it to std::list was discussed, too. P0083R3 as written suggests
that extract() is the replacement for slice(), which, according to the
proposal, is not applicable for associative containers, which must
maintain ordering. It does not contain any thoughts on adding it to
list, too, apparently deeming splice() fit for the task (which it is,
technically).

It turns out, however, that the API eventually designed turned out much
nicer than the catch-all slice() we have on list, and that developers
(incl. myself) expected extract() on list, too, what with list also
being node-based.

So, would a proposal to add node_handle functionality to std::list and
std::forward_list be welcome?

Thanks,
Marc

--
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/2110e62883efa2e21e3d7f31c94e66f8%40kdab.com.

.

------=_Part_11745_212855065.1518536984136
Content-Type: multipart/alternative;
 boundary="----=_Part_11746_270139029.1518536984136"

------=_Part_11746_270139029.1518536984136
Content-Type: text/plain; charset="UTF-8"

On Tuesday, February 13, 2018 at 5:38:08 AM UTC-5, Mutz, Marc wrote:
>
> Hi,
>
> Whenever I find myself using std::list, I do so because of slice(). Yet
> a typical slice() call like
>
>     std::list<~~~> local;
>     local.splice(local.begin(), tasks, tasks.begin());
>
> is quite a mouthful and even long-time C++ developers (incl. myself)
> need to look up what this call does. In C++17, and with std::set, this
> could be written as:
>
>     auto local = tasks.extract(tasks.begin());
>
> which is self-documenting, even if you don't remember the exact
> semantics of extract() - at least it's clear what is being extracted. We
> also don't need to duplicate the type of 'tasks', thanks to auto.
>
> Now, surely when extract() was added to the associative containers,
> adding it to std::list was discussed, too. P0083R3 as written suggests
> that extract() is the replacement for slice(), which, according to the
> proposal, is not applicable for associative containers, which must
> maintain ordering. It does not contain any thoughts on adding it to
> list, too, apparently deeming splice() fit for the task (which it is,
> technically).
>
> It turns out, however, that the API eventually designed turned out much
> nicer than the catch-all slice() we have on list, and that developers
> (incl. myself) expected extract() on list, too, what with list also
> being node-based.
>
> So, would a proposal to add node_handle functionality to std::list and
> std::forward_list be welcome?
>

Why? What's the point of exposing `node_handle` and that sort of thing on
`std::list`? `list` already has splicing functionality, and splicing
multiple nodes at once is a very fast operation in lists.

Your principle problem is that the current API for it is difficult to work
with, since you have to have an already existing `list` type to do the
splicing. So, just make an API that creates a new `list` that gets spliced
into. It will be no less efficient than the node_type version.

--
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/63cf0359-c783-48e0-bb41-6f4d263f7840%40isocpp.org.

------=_Part_11746_270139029.1518536984136
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Tuesday, February 13, 2018 at 5:38:08 AM UTC-5, Mutz, M=
arc wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left:=
 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Hi,
<br>
<br>Whenever I find myself using std::list, I do so because of slice(). Yet=
=20
<br>a typical slice() call like
<br>
<br>=C2=A0 =C2=A0 std::list&lt;~~~&gt; local;
<br>=C2=A0 =C2=A0 local.splice(local.begin(), tasks, tasks.begin());
<br>
<br>is quite a mouthful and even long-time C++ developers (incl. myself)=20
<br>need to look up what this call does. In C++17, and with std::set, this=
=20
<br>could be written as:
<br>
<br>=C2=A0 =C2=A0 auto local =3D tasks.extract(tasks.begin());
<br>
<br>which is self-documenting, even if you don&#39;t remember the exact=20
<br>semantics of extract() - at least it&#39;s clear what is being extracte=
d. We=20
<br>also don&#39;t need to duplicate the type of &#39;tasks&#39;, thanks to=
 auto.
<br>
<br>Now, surely when extract() was added to the associative containers,=20
<br>adding it to std::list was discussed, too. P0083R3 as written suggests=
=20
<br>that extract() is the replacement for slice(), which, according to the=
=20
<br>proposal, is not applicable for associative containers, which must=20
<br>maintain ordering. It does not contain any thoughts on adding it to=20
<br>list, too, apparently deeming splice() fit for the task (which it is,=
=20
<br>technically).
<br>
<br>It turns out, however, that the API eventually designed turned out much=
=20
<br>nicer than the catch-all slice() we have on list, and that developers=
=20
<br>(incl. myself) expected extract() on list, too, what with list also=20
<br>being node-based.
<br>
<br>So, would a proposal to add node_handle functionality to std::list and=
=20
<br>std::forward_list be welcome?
<br></blockquote><div><br>Why? What&#39;s the point of exposing `node_handl=
e` and that sort of thing on `std::list`? `list` already has splicing funct=
ionality, and splicing multiple nodes at once is a very fast operation in l=
ists.<br><br>Your principle problem is that the current API for it is diffi=
cult to work with, since you have to have an already existing `list` type t=
o do the splicing. So, just make an API that creates a new `list` that gets=
 spliced into. It will be no less efficient than the node_type version.<br>=
</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/63cf0359-c783-48e0-bb41-6f4d263f7840%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/63cf0359-c783-48e0-bb41-6f4d263f7840=
%40isocpp.org</a>.<br />

------=_Part_11746_270139029.1518536984136--

------=_Part_11745_212855065.1518536984136--

.

On 2018-02-13 16:49, Nicol Bolas wrote:
[...]
> Why? What's the point of exposing `node_handle` and that sort of thing
> on `std::list`?

Consistency, for one.

> `list` already has splicing functionality, and
> splicing multiple nodes at once is a very fast operation in lists.
>
> Your principle problem is that the current API for it is difficult to
> work with, since you have to have an already existing `list` type to
> do the splicing. So, just make an API that creates a new `list` that
> gets spliced into. It will be no less efficient than the node_type
> version.

extract() and node-insert make sense on std::list, so for consistency
they should be there. That's one part, the one I'm interested in.
Whether there's another API that could be added to std::list that
returns a list instead of a node_handle is another topic, and orthogonal
to whether node_handle-API should be on list, too.

Thanks,
Marc

--
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/7e59ecff5263d7a7ae8dff84f654c773%40kdab.com.

.

------=_Part_9172_1378162946.1518564189176
Content-Type: multipart/alternative;
 boundary="----=_Part_9173_847883271.1518564189177"

------=_Part_9173_847883271.1518564189177
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Tuesday, February 13, 2018 at 2:38:08 AM UTC-8, Mutz, Marc wrote:
>
> Hi,=20
>
> Whenever I find myself using std::list, I do so because of slice(). Yet=
=20
> a typical slice() call like=20
>
>     std::list<~~~> local;=20
>     local.splice(local.begin(), tasks, tasks.begin());=20
>

For reference, the above two-liner is equivalent to this three-liner...
    decltype(tasks) local;
    local.push_back(std::move(tasks.front()));
    tasks.pop_front();

is quite a mouthful and even long-time C++ developers (incl. myself)=20
> need to look up what this call does. In C++17, and with std::set, this=20
> could be written as:=20
>
>     auto local =3D tasks.extract(tasks.begin());=20
>

No, that's incorrect. In C++17, the `extract` method returns a "node=20
handle", which is not at all the same thing as a list. What you'd actually=
=20
write in a hypothetical `extract`-enabled std::list implementation would=20
be...

    decltype(tasks) local;
    auto nh =3D tasks.extract(tasks.begin());
    local.insert(std::move(nh));

or simply

    decltype(tasks) local;
    local.insert(tasks.extract(tasks.begin()));

Now unfortunately we hit a snag. `std::list`, being a sequence container=20
(not an associative container), *does not have* a position-agnostic=20
`insert` method!
So we end up having to tell the list exactly *where* we want to insert the=
=20
new item:

    decltype(tasks) local;
    local.insert(local.begin(), tasks.extract(tasks.begin()));

Compare this to the version you didn't like:

    decltype(tasks) local;
    local.insert(local.begin(), tasks, tasks.begin());

Isn't the version you didn't like *better* than the version you're=20
proposing?

HTH,
=E2=80=93Arthur

--=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/4e92e355-39cc-4acd-9e47-951d0ba79ab5%40isocpp.or=
g.

------=_Part_9173_847883271.1518564189177
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Tuesday, February 13, 2018 at 2:38:08 AM UTC-8, Mutz, M=
arc wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left:=
 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Hi,
<br>
<br>Whenever I find myself using std::list, I do so because of slice(). Yet=
=20
<br>a typical slice() call like
<br>
<br>=C2=A0 =C2=A0 std::list&lt;~~~&gt; local;
<br>=C2=A0 =C2=A0 local.splice(local.begin(), tasks, tasks.begin());
<br></blockquote><div><br></div><div>For reference, the above two-liner is =
equivalent to this three-liner...</div><div>=C2=A0 =C2=A0 decltype(tasks) l=
ocal;</div><div>=C2=A0 =C2=A0 local.push_back(std::move(tasks.front()));</d=
iv><div>=C2=A0 =C2=A0 tasks.pop_front();</div><div><br></div><blockquote cl=
ass=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px =
#ccc solid;padding-left: 1ex;">is quite a mouthful and even long-time C++ d=
evelopers (incl. myself)=20
<br>need to look up what this call does. In C++17, and with std::set, this=
=20
<br>could be written as:
<br>
<br>=C2=A0 =C2=A0 auto local =3D tasks.extract(tasks.begin());
<br></blockquote><div><br></div><div>No, that&#39;s incorrect. In C++17, th=
e `extract` method returns a &quot;node handle&quot;, which is not at all t=
he same thing as a list. What you&#39;d actually write in a hypothetical `e=
xtract`-enabled std::list implementation would be...</div><div><br></div><d=
iv>=C2=A0 =C2=A0 decltype(tasks) local;</div><div>=C2=A0 =C2=A0 auto nh =3D=
 tasks.extract(tasks.begin());</div><div>=C2=A0 =C2=A0 local.insert(std::mo=
ve(nh));</div><div><br></div><div>or simply</div><div><br></div><div><div>=
=C2=A0 =C2=A0 decltype(tasks) local;</div><div>=C2=A0 =C2=A0 local.insert(t=
asks.extract(tasks.begin()));</div></div><div><br></div><div>Now unfortunat=
ely we hit a snag. `std::list`, being a sequence container (not an associat=
ive container), <i>does not have</i> a position-agnostic `insert` method!</=
div><div>So we end up having to tell the list exactly <i>where</i> we want =
to insert the new item:</div><div><br></div><div><div>=C2=A0 =C2=A0 decltyp=
e(tasks) local;</div><div>=C2=A0 =C2=A0 local.insert(local.begin(), tasks.e=
xtract(tasks.begin()));</div></div><div><br></div><div>Compare this to the =
version you didn&#39;t like:</div><div><br></div><div><div><div>=C2=A0 =C2=
=A0 decltype(tasks) local;</div><div>=C2=A0 =C2=A0 local.insert(local.begin=
(), tasks, tasks.begin());</div></div></div><div><br></div><div>Isn&#39;t t=
he version you didn&#39;t like <i><b>better</b></i> than the version you&#3=
9;re proposing?</div><div><br></div><div>HTH,</div><div>=E2=80=93Arthur</di=
v></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/4e92e355-39cc-4acd-9e47-951d0ba79ab5%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/4e92e355-39cc-4acd-9e47-951d0ba79ab5=
%40isocpp.org</a>.<br />

------=_Part_9173_847883271.1518564189177--

------=_Part_9172_1378162946.1518564189176--

.

------=_Part_7085_1364397076.1518578259254
Content-Type: multipart/alternative;
 boundary="----=_Part_7086_104753759.1518578259254"

------=_Part_7086_104753759.1518578259254
Content-Type: text/plain; charset="UTF-8"

On Tuesday, February 13, 2018 at 6:17:28 PM UTC-5, Mutz, Marc wrote:
>
> On 2018-02-13 16:49, Nicol Bolas wrote:
> [...]
> > Why? What's the point of exposing `node_handle` and that sort of thing
> > on `std::list`?
>
> Consistency, for one.
>

Different kinds of things are not expected to be consistent with each other
because they're *different*. Sequence containers don't have the same
interfaces as associative containers and vice-versa.

For example, `list` can handle splicing with arbitrary numbers of nodes, so
long as they're all in a range. Associative containers cannot;
`node_handle` only contains a single element. So their API only supports
one-by-one element transfers.

So how would you extend the `extract` interface to handle ranges of nodes?
Well, you'd have to have some object to store the range of nodes,
obviously. And since it's a range, maybe it'd be nice to be able to add
more elements to the range. Or perhaps remove some.

And we just reinvented `std::list`.

Adding `node_handle` functionality to `list` is like adding `operator[]` to
`list`. Sure you can do it, but that doesn't mean you should. It serves no
useful purpose and is fundamentally inferior to what we already can do at
present.

--
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/7d44b9d6-1538-4fbf-a971-dd141667039e%40isocpp.org.

------=_Part_7086_104753759.1518578259254
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Tuesday, February 13, 2018 at 6:17:28 PM UTC-5, Mutz, M=
arc wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left:=
 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On 2018-02-13 16:49,=
 Nicol Bolas wrote:
<br>[...]
<br>&gt; Why? What&#39;s the point of exposing `node_handle` and that sort =
of thing
<br>&gt; on `std::list`?
<br>
<br>Consistency, for one.
<br></blockquote><div><br>Different kinds of things are not expected to be =
consistent with each other because they&#39;re <i>different</i>. Sequence c=
ontainers don&#39;t have the same interfaces as associative containers and =
vice-versa.<br><br>For example, `list` can handle splicing with arbitrary n=
umbers of nodes,
 so long as they&#39;re all in a range. Associative containers cannot; `nod=
e_handle` only contains a single element. So their API only supports one-by=
-one element transfers.<br><br>So how would you extend the `extract` interf=
ace to handle ranges of nodes? Well, you&#39;d have to have some object to =
store the range of nodes, obviously. And since it&#39;s a range, maybe it&#=
39;d be nice to be able to add more elements to the range. Or perhaps remov=
e some.<br><br>And we just reinvented `std::list`.<br><br>Adding `node_hand=
le` functionality to `list` is like adding `operator[]` to `list`. Sure you=
 can do it, but that doesn&#39;t mean you should. It serves no useful purpo=
se and is fundamentally inferior to what we already can do at present.</div=
><br></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/7d44b9d6-1538-4fbf-a971-dd141667039e%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/7d44b9d6-1538-4fbf-a971-dd141667039e=
%40isocpp.org</a>.<br />

------=_Part_7086_104753759.1518578259254--

------=_Part_7085_1364397076.1518578259254--

.

Hi,

On 2018-02-14 00:23, Arthur O'Dwyer wrote:
[...]
>> std::list<~~~> local;
>> local.splice(local.begin(), tasks, tasks.begin());
>
> For reference, the above two-liner is equivalent to this
> three-liner...
>     decltype(tasks) local;
>     local.push_back(std::move(tasks.front()));
>     tasks.pop_front();

No, it is not. In the splice() call, the value_type is neither copied
nor moved. The list node is simple re-linked. In the three-liner, the
value_type is moved, a new node is allocated, and the old one destroyed.

[...]
>> auto local = tasks.extract(tasks.begin());
>
> No, that's incorrect. In C++17, the `extract` method returns a "node
> handle", which is not at all the same thing as a list.

A node_handle gives me access to the element already (cf.
std::set::node_type::value()). My specific use-case was extracting a
single element from a list (think work-queue of a thread-pool, which is
100% of my use-cases for std::list over 15 years of professional C++
development). Right now, for ownership reasons, I need to use a local
std::list. But with node_handle, which is an owner, too, I don't need
that:

   auto local = tasks.extract(tasks.begin());
   do_something_with(local.value());
   // at end of scope: 'local' deletes 'local.value()'
   // alternatively, I can insert the node into some outgoing queue:
   // out.insert(out.end(), std::move(local));

The benefit here is that the extraction and insertion of the work item
does not involve memory (de)allocations.

As for ranges: splice() is ok there, since the iterator pair
unambiguously identifies the source and the single iterator the target.
It's the one-element case where the splice() call is overly opaque.


Taking a step back, I appreciate that map::extract() was conceived as
the corresponding API to list::splice(), and that therefore,
feature-wise, list::extract() is not strictly necessary. But for me, not
having followed the standardisation process of this feature, extract()
et al were a way to allow access to nodes of node-based containers.
Splicing being just one of them. Taking a cue from Herb, let's look at
use-cases for splice() and ways to make them simpler: I showed node
extraction above, but node creation is another example:

You may want to separate node allocation from insertion into a (probably
shared) container: If you want the memory allocation outside the
critical section, what do you do? You create a std::list with one
element outside the critical section, and then splice the list into the
shared container under mutex protection.

So, there's even a use-case for a std::Container::node_type::create()
(or, rather, static container::create_node() b/c of allocators)
function!

Thanks,
Marc

--
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/beef6850afe148c357cca399baf94220%40kdab.com.

.

------=_Part_13428_328973329.1518620229670
Content-Type: multipart/alternative;
 boundary="----=_Part_13429_1001619930.1518620229670"

------=_Part_13429_1001619930.1518620229670
Content-Type: text/plain; charset="UTF-8"

On Wednesday, February 14, 2018 at 7:37:41 AM UTC-5, Mutz, Marc wrote:
>
> Hi,
>
> On 2018-02-14 00:23, Arthur O'Dwyer wrote:
> [...]
> >> std::list<~~~> local;
> >> local.splice(local.begin(), tasks, tasks.begin());
> >
> > For reference, the above two-liner is equivalent to this
> > three-liner...
> >     decltype(tasks) local;
> >     local.push_back(std::move(tasks.front()));
> >     tasks.pop_front();
>
> No, it is not. In the splice() call, the value_type is neither copied
> nor moved. The list node is simple re-linked. In the three-liner, the
> value_type is moved, a new node is allocated, and the old one destroyed.
>
> [...]
> >> auto local = tasks.extract(tasks.begin());
> >
> > No, that's incorrect. In C++17, the `extract` method returns a "node
> > handle", which is not at all the same thing as a list.
>
> A node_handle gives me access to the element already (cf.
> std::set::node_type::value()). My specific use-case was extracting a
> single element from a list (think work-queue of a thread-pool, which is
> 100% of my use-cases for std::list over 15 years of professional C++
> development). Right now, for ownership reasons, I need to use a local
> std::list. But with node_handle, which is an owner, too, I don't need
> that:
>
>    auto local = tasks.extract(tasks.begin());
>    do_something_with(local.value());
>    // at end of scope: 'local' deletes 'local.value()'
>    // alternatively, I can insert the node into some outgoing queue:
>    // out.insert(out.end(), std::move(local));
>
> The benefit here is that the extraction and insertion of the work item
> does not involve memory (de)allocations.
>
> As for ranges: splice() is ok there, since the iterator pair
> unambiguously identifies the source and the single iterator the target.
> It's the one-element case where the splice() call is overly opaque.
>

We don't need a special API for the case of one element. If an API is fine
for many elements, then it works just as well for a single one. Let's not
forget the Zero/One/Infinity rule. Some types can only handle One, so they
use  `node_handle`. Splice is for types that can handle Infinity.

If you're making a thread work-queue, you wouldn't want to write that code
differently for the "pop one item" operation vs. "pop many items". One item
is just a special case.

Taking a step back, I appreciate that map::extract() was conceived as
> the corresponding API to list::splice(), and that therefore,
> feature-wise, list::extract() is not strictly necessary. But for me, not
> having followed the standardisation process of this feature, extract()
> et al were a way to allow access to nodes of node-based containers.
> Splicing being just one of them. Taking a cue from Herb, let's look at
> use-cases for splice() and ways to make them simpler: I showed node
> extraction above, but node creation is another example:
>
> You may want to separate node allocation from insertion into a (probably
> shared) container: If you want the memory allocation outside the
> critical section, what do you do? You create a std::list with one
> element outside the critical section, and then splice the list into the
> shared container under mutex protection.
>
> So, there's even a use-case for a std::Container::node_type::create()
> (or, rather, static container::create_node() b/c of allocators)
> function!
>

.... how is that a use-case? You use a container to do that. Node handles
don't need to have creation functionality. Node handles are nothing more
than intermediaries. They allow some slight value manipulation, but they
aren't meant to be single-element containers. You create a node in a
container, extract it, and then insert it somewhere else. That's the usage
pattern.

I don't know why it is that you want to treat `node_handle`s as real
objects rather than intermediaries, but that's not their function. We use
containers; that's the way the system is designed, and it works quite well
this way.

If there was some design deficiency in this process, something that is
otherwise genuinely impossible with this design, that would be one thing.
But everything you want to do can be done, just not the *way* you want to
do it. Containers have good support for node creation as it is. They
already have allocators and ways to manipulate them. They already have
`emplace` and similar functions. And so forth.

There's no reason beyond personal preference to duplicate all of these APIs
in `node_handle`s.

--
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/fe1e128d-fee6-4a34-9b32-5df93bba8cf1%40isocpp.org.

------=_Part_13429_1001619930.1518620229670
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Wednesday, February 14, 2018 at 7:37:41 AM UTC-5, Mutz,=
 Marc wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Hi,
<br>
<br>On 2018-02-14 00:23, Arthur O&#39;Dwyer wrote:
<br>[...]
<br>&gt;&gt; std::list&lt;~~~&gt; local;
<br>&gt;&gt; local.splice(local.begin(), tasks, tasks.begin());
<br>&gt;=20
<br>&gt; For reference, the above two-liner is equivalent to this
<br>&gt; three-liner...
<br>&gt; =C2=A0 =C2=A0 decltype(tasks) local;
<br>&gt; =C2=A0 =C2=A0 local.push_back(std::move(<wbr>tasks.front()));
<br>&gt; =C2=A0 =C2=A0 tasks.pop_front();
<br>
<br>No, it is not. In the splice() call, the value_type is neither copied=
=20
<br>nor moved. The list node is simple re-linked. In the three-liner, the=
=20
<br>value_type is moved, a new node is allocated, and the old one destroyed=
..
<br>
<br>[...]
<br>&gt;&gt; auto local =3D tasks.extract(tasks.begin());
<br>&gt;=20
<br>&gt; No, that&#39;s incorrect. In C++17, the `extract` method returns a=
 &quot;node
<br>&gt; handle&quot;, which is not at all the same thing as a list.
<br>
<br>A node_handle gives me access to the element already (cf.=20
<br>std::set::node_type::value()). My specific use-case was extracting a=20
<br>single element from a list (think work-queue of a thread-pool, which is=
=20
<br>100% of my use-cases for std::list over 15 years of professional C++=20
<br>development). Right now, for ownership reasons, I need to use a local=
=20
<br>std::list. But with node_handle, which is an owner, too, I don&#39;t ne=
ed=20
<br>that:
<br>
<br>=C2=A0 =C2=A0auto local =3D tasks.extract(tasks.begin());
<br>=C2=A0 =C2=A0do_something_with(local.<wbr>value());
<br>=C2=A0 =C2=A0// at end of scope: &#39;local&#39; deletes &#39;local.val=
ue()&#39;
<br>=C2=A0 =C2=A0// alternatively, I can insert the node into some outgoing=
 queue:
<br>=C2=A0 =C2=A0// out.insert(out.end(), std::move(local));
<br>
<br>The benefit here is that the extraction and insertion of the work item=
=20
<br>does not involve memory (de)allocations.
<br>
<br>As for ranges: splice() is ok there, since the iterator pair=20
<br>unambiguously identifies the source and the single iterator the target.=
=20
<br>It&#39;s the one-element case where the splice() call is overly opaque.=
<br></blockquote><div><br>We don&#39;t need a special API for the case of o=
ne element. If an API is fine for many elements, then it works just as well=
 for a single one. Let&#39;s not forget the Zero/One/Infinity rule. Some ty=
pes can only handle One, so they use=C2=A0 `node_handle`. Splice is for typ=
es that can handle Infinity.<br><br>If you&#39;re making a thread work-queu=
e, you wouldn&#39;t want to write that code differently for the &quot;pop o=
ne item&quot; operation vs. &quot;pop many items&quot;. One item is just a =
special case.<br><br></div><blockquote class=3D"gmail_quote" style=3D"margi=
n: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
Taking a step back, I appreciate that map::extract() was conceived as=20
<br>the corresponding API to list::splice(), and that therefore,=20
<br>feature-wise, list::extract() is not strictly necessary. But for me, no=
t=20
<br>having followed the standardisation process of this feature, extract()=
=20
<br>et al were a way to allow access to nodes of node-based containers.=20
<br>Splicing being just one of them. Taking a cue from Herb, let&#39;s look=
 at=20
<br>use-cases for splice() and ways to make them simpler: I showed node=20
<br>extraction above, but node creation is another example:
<br>
<br>You may want to separate node allocation from insertion into a (probabl=
y=20
<br>shared) container: If you want the memory allocation outside the=20
<br>critical section, what do you do? You create a std::list with one=20
<br>element outside the critical section, and then splice the list into the=
=20
<br>shared container under mutex protection.
<br>
<br>So, there&#39;s even a use-case for a std::Container::node_type::<wbr>c=
reate()=20
<br>(or, rather, static container::create_node() b/c of allocators)=20
<br>function!<br></blockquote><div><br>... how is that a use-case? You use =
a container to do that. Node handles don&#39;t need to have creation functi=
onality. Node handles are nothing more than intermediaries. They allow some=
 slight value manipulation, but they aren&#39;t meant to be single-element =
containers. You create a node in a container, extract it, and then insert i=
t somewhere else. That&#39;s the usage pattern.<br><br>I don&#39;t know why=
 it is that you want to treat `node_handle`s as real objects rather than in=
termediaries, but that&#39;s not their function. We use containers; that&#3=
9;s the way the system is designed, and it works quite well this way.<br><b=
r>If there was some design deficiency in this process, something that is ot=
herwise genuinely impossible with this design, that would be one thing. But=
 everything you want to do can be done, just not the <i>way</i> you want to=
 do it. Containers have good support for node creation as it is. They alrea=
dy have allocators and ways to manipulate them. They already have `emplace`=
 and similar functions. And so forth.<br><br>There&#39;s no reason beyond p=
ersonal preference to duplicate all of these APIs in `node_handle`s.<br></d=
iv></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/fe1e128d-fee6-4a34-9b32-5df93bba8cf1%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/fe1e128d-fee6-4a34-9b32-5df93bba8cf1=
%40isocpp.org</a>.<br />

------=_Part_13429_1001619930.1518620229670--

------=_Part_13428_328973329.1518620229670--

.

------=_Part_13412_1868266826.1518622195435
Content-Type: multipart/alternative;
 boundary="----=_Part_13413_35401087.1518622195435"

------=_Part_13413_35401087.1518622195435
Content-Type: text/plain; charset="UTF-8"



On Wednesday, February 14, 2018 at 9:57:09 AM UTC-5, Nicol Bolas wrote:
>
> On Wednesday, February 14, 2018 at 7:37:41 AM UTC-5, Mutz, Marc wrote:
>>
>> Hi,
>>
>> On 2018-02-14 00:23, Arthur O'Dwyer wrote:
>> [...]
>> >> std::list<~~~> local;
>> >> local.splice(local.begin(), tasks, tasks.begin());
>> >
>> > For reference, the above two-liner is equivalent to this
>> > three-liner...
>> >     decltype(tasks) local;
>> >     local.push_back(std::move(tasks.front()));
>> >     tasks.pop_front();
>>
>> No, it is not. In the splice() call, the value_type is neither copied
>> nor moved. The list node is simple re-linked. In the three-liner, the
>> value_type is moved, a new node is allocated, and the old one destroyed.
>>
>> [...]
>> >> auto local = tasks.extract(tasks.begin());
>> >
>> > No, that's incorrect. In C++17, the `extract` method returns a "node
>> > handle", which is not at all the same thing as a list.
>>
>> A node_handle gives me access to the element already (cf.
>> std::set::node_type::value()). My specific use-case was extracting a
>> single element from a list (think work-queue of a thread-pool, which is
>> 100% of my use-cases for std::list over 15 years of professional C++
>> development). Right now, for ownership reasons, I need to use a local
>> std::list. But with node_handle, which is an owner, too, I don't need
>> that:
>>
>>    auto local = tasks.extract(tasks.begin());
>>    do_something_with(local.value());
>>    // at end of scope: 'local' deletes 'local.value()'
>>    // alternatively, I can insert the node into some outgoing queue:
>>    // out.insert(out.end(), std::move(local));
>>
>> The benefit here is that the extraction and insertion of the work item
>> does not involve memory (de)allocations.
>>
>> As for ranges: splice() is ok there, since the iterator pair
>> unambiguously identifies the source and the single iterator the target.
>> It's the one-element case where the splice() call is overly opaque.
>>
>
> We don't need a special API for the case of one element. If an API is fine
> for many elements, then it works just as well for a single one. Let's not
> forget the Zero/One/Infinity rule. Some types can only handle One, so they
> use  `node_handle`. Splice is for types that can handle Infinity.
>
> If you're making a thread work-queue, you wouldn't want to write that code
> differently for the "pop one item" operation vs. "pop many items". One item
> is just a special case.
>

To me, the principle need for a `list::extract` is to avoid having to do
this:

decltype(source) lst(source.get_allocator());
lst.splice(lst.begin(), begin, end);

It'd be much easier to be able to do:

auto lst = source.extract(begin, end);

It should just be a convenience wrapper around `splice` functionality.

--
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/7887eb28-8cab-432e-a339-b146ee328663%40isocpp.org.

------=_Part_13413_35401087.1518622195435
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Wednesday, February 14, 2018 at 9:57:09 AM UTC-=
5, Nicol Bolas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;m=
argin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr">On Wednesday, February 14, 2018 at 7:37:41 AM UTC-5, Mutz, Marc wr=
ote:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;b=
order-left:1px #ccc solid;padding-left:1ex">Hi,
<br>
<br>On 2018-02-14 00:23, Arthur O&#39;Dwyer wrote:
<br>[...]
<br>&gt;&gt; std::list&lt;~~~&gt; local;
<br>&gt;&gt; local.splice(local.begin(), tasks, tasks.begin());
<br>&gt;=20
<br>&gt; For reference, the above two-liner is equivalent to this
<br>&gt; three-liner...
<br>&gt; =C2=A0 =C2=A0 decltype(tasks) local;
<br>&gt; =C2=A0 =C2=A0 local.push_back(std::move(<wbr>tasks.front()));
<br>&gt; =C2=A0 =C2=A0 tasks.pop_front();
<br>
<br>No, it is not. In the splice() call, the value_type is neither copied=
=20
<br>nor moved. The list node is simple re-linked. In the three-liner, the=
=20
<br>value_type is moved, a new node is allocated, and the old one destroyed=
..
<br>
<br>[...]
<br>&gt;&gt; auto local =3D tasks.extract(tasks.begin());
<br>&gt;=20
<br>&gt; No, that&#39;s incorrect. In C++17, the `extract` method returns a=
 &quot;node
<br>&gt; handle&quot;, which is not at all the same thing as a list.
<br>
<br>A node_handle gives me access to the element already (cf.=20
<br>std::set::node_type::value()). My specific use-case was extracting a=20
<br>single element from a list (think work-queue of a thread-pool, which is=
=20
<br>100% of my use-cases for std::list over 15 years of professional C++=20
<br>development). Right now, for ownership reasons, I need to use a local=
=20
<br>std::list. But with node_handle, which is an owner, too, I don&#39;t ne=
ed=20
<br>that:
<br>
<br>=C2=A0 =C2=A0auto local =3D tasks.extract(tasks.begin());
<br>=C2=A0 =C2=A0do_something_with(local.<wbr>value());
<br>=C2=A0 =C2=A0// at end of scope: &#39;local&#39; deletes &#39;local.val=
ue()&#39;
<br>=C2=A0 =C2=A0// alternatively, I can insert the node into some outgoing=
 queue:
<br>=C2=A0 =C2=A0// out.insert(out.end(), std::move(local));
<br>
<br>The benefit here is that the extraction and insertion of the work item=
=20
<br>does not involve memory (de)allocations.
<br>
<br>As for ranges: splice() is ok there, since the iterator pair=20
<br>unambiguously identifies the source and the single iterator the target.=
=20
<br>It&#39;s the one-element case where the splice() call is overly opaque.=
<br></blockquote><div><br>We don&#39;t need a special API for the case of o=
ne element. If an API is fine for many elements, then it works just as well=
 for a single one. Let&#39;s not forget the Zero/One/Infinity rule. Some ty=
pes can only handle One, so they use=C2=A0 `node_handle`. Splice is for typ=
es that can handle Infinity.<br><br>If you&#39;re making a thread work-queu=
e, you wouldn&#39;t want to write that code differently for the &quot;pop o=
ne item&quot; operation vs. &quot;pop many items&quot;. One item is just a =
special case.<br></div></div></blockquote><div><br>To me, the principle nee=
d for a `list::extract` is to avoid having to do this:<br><br><div style=3D=
"background-color: rgb(250, 250, 250); border-color: rgb(187, 187, 187); bo=
rder-style: solid; border-width: 1px; overflow-wrap: break-word;" class=3D"=
prettyprint"><code class=3D"prettyprint"><div class=3D"subprettyprint"><spa=
n style=3D"color: #008;" class=3D"styled-by-prettify">decltype</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify">source</span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify"> lst</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">source</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">.</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
">get_allocator</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">());</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><=
br>lst</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify">splice</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify">lst</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">.</span><span style=3D"color: #00=
8;" class=3D"styled-by-prettify">begin</span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">(),</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-b=
y-prettify">begin</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <=
/span><span style=3D"color: #008;" class=3D"styled-by-prettify">end</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">);</span></div></c=
ode></div><br>It&#39;d be much easier to be able to do:<br><br><div style=
=3D"background-color: rgb(250, 250, 250); border-color: rgb(187, 187, 187);=
 border-style: solid; border-width: 1px; overflow-wrap: break-word;" class=
=3D"prettyprint"><code class=3D"prettyprint"><div class=3D"subprettyprint">=
<span style=3D"color: #008;" class=3D"styled-by-prettify">auto</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"> lst </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> source</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">.</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify">extract</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">(</span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">begin</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: #008;" class=3D"styled-by-prettify">end</sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">);</span></div=
></code></div><br>It should just be a convenience wrapper around `splice` f=
unctionality.</div><br></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/7887eb28-8cab-432e-a339-b146ee328663%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/7887eb28-8cab-432e-a339-b146ee328663=
%40isocpp.org</a>.<br />

------=_Part_13413_35401087.1518622195435--

------=_Part_13412_1868266826.1518622195435--

.

On 2018-02-14 16:29, Nicol Bolas wrote:
[...]
> To me, the principle need for a `list::extract` is to avoid having to
> do this:
>
> decltype(source) lst(source.get_allocator());
> lst.splice(lst.begin(), begin, end);
> It'd be much easier to be able to do:
>
> auto lst = source.extract(begin, end);
> It should just be a convenience wrapper around `splice` functionality.

Right. It's a bit weird that list::extract returns a list while
map::extract returns a node_handle, but I guess that's ok, since map
does not have an extract(it, it) overload.

Now, what about the one-element case? Saying

    auto lst = source.extract(source.begin(), ++source.begin());

is clearly wasteful, since you need to increment an iterator for no good
reason (even C++98 splice() is overloaded for range/single-element). So,
assume we also add

    auto extracted = source.extract(source.begin());

or even

    auto extracted = source.extract_front();

what's the decltype of 'extracted'? A list? Or something compatible with
a std::set::node_type?

Also: if we add list::extract(it, it) -> list, should we add
map::extract(it, it) -> map? After all, a sub-range of a map is properly
ordered for becoming a new map, both in the RB-tree and the hash-map
implementations.

Thanks,
Marc

--
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/25ee9d747af520bb27d4a3b957207aae%40kdab.com.

.

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

On Thu, Feb 15, 2018 at 12:27 AM, Mutz, Marc <marc@kdab.com> wrote:

> On 2018-02-14 16:29, Nicol Bolas wrote:
> [...]
>
>> To me, the principle need for a `list::extract` is to avoid having to
>> do this:
>>
>> decltype(source) lst(source.get_allocator());
>> lst.splice(lst.begin(), begin, end);
>> It'd be much easier to be able to do:
>>
>> auto lst =3D source.extract(begin, end);
>> It should just be a convenience wrapper around `splice` functionality.
>>
>
> Right. It's a bit weird that list::extract returns a list while
> map::extract returns a node_handle, but I guess that's ok, since map does
> not have an extract(it, it) overload.
>

Okay, I'm convinced that Marc has a use-case for "moveless popping" an
element off of a std::list (which could be used to shorten a critical
section, for example).
However, `extract` is not the right name for this thing unless it returns a
node_handle, which it apparently does not.
Marc, the name for "snip a range of elements out of a larger sequence"
would be more like "sublist", analogous to "substr". However, "substr" is
copying, whereas you want something that mutates the original container
too; therefore the name should include a verb. Perhaps "extract_sublist" or
"pop_sublist" or "snip_sublist". Perhaps just "snip", actually =E2=80=94 it=
's
sufficiently different from the already-taken "extract", and pleasingly
similar to the existing verb "splice".

You'll have to decide how this is going to work with allocators (grrr, what
a mess the committee has made here). The "snip" algorithm itself does not
allocate or deallocate any memory, but it does cause the creation of a
brand-new container (the returned list) which must come with an allocator
suitable for deallocating the node(s) that you've snipped out. This means
that the "snip" algorithm must *copy* the list's existing allocator =E2=80=
=94 but
it *must not* use select_on_container_copy_construction. You should specify
this precisely, and think about whether there are any corner cases that
might matter here.

Since list iterators are non-random-access iterators, I believe there will
be a desire for

    auto lst =3D source.snip(source.begin(), 42);

as that is implementable much more efficiently than

    auto lst =3D source.snip(source.begin(), std::next(source.begin(), 42))=
;

This eliminates your concern about the one-element case; it becomes simply

    auto lst =3D source.snip(source.begin(), 1);

with no special coding necessary.
However, there is still a use-case for

    auto lst =3D source.snip(first, last);

as well; I would tentatively expect both signatures to be provided.

Notice that source.snip(first, last) cannot possibly be an O(1) operation,
because it needs to walk the entire sublist to decide on the value of
lst.size() and the value to subtract from source.size().
Consider whether `forward_list::snip_after` should exist. It could probably
be O(1) because forward_list does not track its own size.

Also: if we add list::extract(it, it) -> list, should we add
> map::extract(it, it) -> map? After all, a sub-range of a map is properly
> ordered for becoming a new map, both in the RB-tree and the hash-map
> implementations.
>

Proper sequential ordering isn't sufficient to become a brand-new map
(AFAIK); you also need proper tree structure. Snipping a subtree into a new
tree is possible, but detecting whether a range makes up a subtree
structure isn't possible at the moment, and snipping out a subtree would
tend to leave the source tree unbalanced.
Is it actually possible to snip out a range from an RB-tree, turn the range
into a balanced RB-tree, and rebalance the source RB-tree, and do it all
*faster* than if you just transferred the node-handles one at a time?

=E2=80=93Arthur

--=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/CADvuK0KAcuFc0J4WLr98zGMeBPuoAvATEkBY0QHENjUq7mT=
sxQ%40mail.gmail.com.

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

<div dir=3D"ltr">On Thu, Feb 15, 2018 at 12:27 AM, Mutz, Marc <span dir=3D"=
ltr">&lt;<a href=3D"mailto:marc@kdab.com" target=3D"_blank">marc@kdab.com</=
a>&gt;</span> wrote:<br><div class=3D"gmail_extra"><div class=3D"gmail_quot=
e"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bord=
er-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204=
);padding-left:1ex">On 2018-02-14 16:29, Nicol Bolas wrote:<br>
[...]<span class=3D"gmail-"><br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);p=
adding-left:1ex">
To me, the principle need for a `list::extract` is to avoid having to<br>
do this:<br>
<br>
decltype(source) lst(source.get_allocator());<br>
lst.splice(lst.begin(), begin, end);<br>
It&#39;d be much easier to be able to do:<br>
<br>
auto lst =3D source.extract(begin, end);<br>
It should just be a convenience wrapper around `splice` functionality.<br>
</blockquote>
<br></span>
Right. It&#39;s a bit weird that list::extract returns a list while map::ex=
tract returns a node_handle, but I guess that&#39;s ok, since map does not =
have an extract(it, it) overload.<br></blockquote><div><br></div><div>Okay,=
 I&#39;m convinced that Marc has a use-case for &quot;moveless popping&quot=
; an element off of a std::list (which could be used to shorten a critical =
section, for example).</div><div>However, `extract` is not the right name f=
or this thing unless it returns a node_handle, which it apparently does not=
..</div><div>Marc, the name for &quot;snip a range of elements out of a larg=
er sequence&quot; would be more like &quot;sublist&quot;, analogous to &quo=
t;substr&quot;. However, &quot;substr&quot; is copying, whereas you want so=
mething that mutates the original container too; therefore the name should =
include a verb. Perhaps &quot;extract_sublist&quot; or &quot;pop_sublist&qu=
ot; or &quot;snip_sublist&quot;. Perhaps just &quot;snip&quot;, actually =
=E2=80=94 it&#39;s sufficiently different from the already-taken &quot;extr=
act&quot;, and pleasingly similar to the existing verb &quot;splice&quot;.<=
/div><div><br></div><div>You&#39;ll have to decide how this is going to wor=
k with allocators (grrr, what a mess the committee has made here). The &quo=
t;snip&quot; algorithm itself does not allocate or deallocate any memory, b=
ut it does cause the creation of a brand-new container (the returned list) =
which must come with an allocator suitable for deallocating the node(s) tha=
t you&#39;ve snipped out. This means that the &quot;snip&quot; algorithm mu=
st <i>copy</i> the list&#39;s existing allocator =E2=80=94 but it <i>must n=
ot</i> use select_on_container_copy_construction. You should specify this p=
recisely, and think about whether there are any corner cases that might mat=
ter here.</div><div><br></div><div>Since list iterators are non-random-acce=
ss iterators, I believe there will be a desire for</div><div><br></div><div=
>=C2=A0 =C2=A0 auto lst =3D source.snip(source.begin(), 42);</div><div><br>=
</div><div>as that is implementable much more efficiently than</div><div><b=
r></div><div><div>=C2=A0 =C2=A0 auto lst =3D source.snip(source.begin(), st=
d::next(source.begin(), 42));</div></div><div><br></div><div>This eliminate=
s your concern about the one-element case; it becomes simply</div><div><br>=
</div><div><div>=C2=A0 =C2=A0 auto lst =3D source.snip(source.begin(), 1);<=
/div></div><div><br></div><div>with no special coding necessary.</div><div>=
However, there is still a use-case for<br></div><div><div><br></div><div>=
=C2=A0 =C2=A0 auto lst =3D source.snip(first, last);</div></div><div><br></=
div><div>as well; I would tentatively expect both signatures to be provided=
..</div><div><br></div><div>Notice that source.snip(first, last) cannot poss=
ibly be an O(1) operation, because it needs to walk the entire sublist to d=
ecide on the value of lst.size() and the value to subtract from source.size=
().</div><div>Consider whether `forward_list::snip_after` should exist. It =
could probably be O(1) because forward_list does not track its own size.</d=
iv><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px=
 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:=
rgb(204,204,204);padding-left:1ex">Also: if we add list::extract(it, it) -&=
gt; list, should we add map::extract(it, it) -&gt; map? After all, a sub-ra=
nge of a map is properly ordered for becoming a new map, both in the RB-tre=
e and the hash-map implementations.<br></blockquote><div><br></div><div>Pro=
per sequential ordering isn&#39;t sufficient to become a brand-new map (AFA=
IK); you also need proper tree structure. Snipping a subtree into a new tre=
e is possible, but detecting whether a range makes up a subtree structure i=
sn&#39;t possible at the moment, and snipping out a subtree would tend to l=
eave the source tree unbalanced.</div><div>Is it actually possible to snip =
out a range from an RB-tree, turn the range into a balanced RB-tree, and re=
balance the source RB-tree, and do it all <i>faster</i> than if you just tr=
ansferred the node-handles one at a time?</div><div><br></div><div>=E2=80=
=93Arthur</div></div></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/CADvuK0KAcuFc0J4WLr98zGMeBPuoAvATEkBY=
0QHENjUq7mTsxQ%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">htt=
ps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CADvuK0KAcuFc0J4W=
Lr98zGMeBPuoAvATEkBY0QHENjUq7mTsxQ%40mail.gmail.com</a>.<br />

--001a114714dabe63fd05654455c9--

.

------=_Part_1959_953387243.1518723683444
Content-Type: multipart/alternative;
 boundary="----=_Part_1960_133623231.1518723683444"

------=_Part_1960_133623231.1518723683444
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable



On Thursday, February 15, 2018 at 1:24:16 PM UTC-5, Arthur O'Dwyer wrote:
>
> On Thu, Feb 15, 2018 at 12:27 AM, Mutz, Marc <ma...@kdab.com <javascript:=
>
> > wrote:
>
>> On 2018-02-14 16:29, Nicol Bolas wrote:
>> [...]
>>
>>> To me, the principle need for a `list::extract` is to avoid having to
>>> do this:
>>>
>>> decltype(source) lst(source.get_allocator());
>>> lst.splice(lst.begin(), begin, end);
>>> It'd be much easier to be able to do:
>>>
>>> auto lst =3D source.extract(begin, end);
>>> It should just be a convenience wrapper around `splice` functionality.
>>>
>>
>> Right. It's a bit weird that list::extract returns a list while=20
>> map::extract returns a node_handle, but I guess that's ok, since map doe=
s=20
>> not have an extract(it, it) overload.
>>
>
> Okay, I'm convinced that Marc has a use-case for "moveless popping" an=20
> element off of a std::list (which could be used to shorten a critical=20
> section, for example).
> However, `extract` is not the right name for this thing unless it returns=
=20
> a node_handle, which it apparently does not.
>

Fair enough.

Marc, the name for "snip a range of elements out of a larger sequence"=20
> would be more like "sublist", analogous to "substr". However, "substr" is=
=20
> copying, whereas you want something that mutates the original container=
=20
> too; therefore the name should include a verb. Perhaps "extract_sublist" =
or=20
> "pop_sublist" or "snip_sublist". Perhaps just "snip", actually =E2=80=94 =
it's=20
> sufficiently different from the already-taken "extract", and pleasingly=
=20
> similar to the existing verb "splice".
>
>
Since list iterators are non-random-access iterators, I believe there will=
=20
> be a desire for
>
>     auto lst =3D source.snip(source.begin(), 42);
>
> as that is implementable much more efficiently than
>
>     auto lst =3D source.snip(source.begin(), std::next(source.begin(), 42=
));
>

If you only have a size rather than an iterator, yes this will be faster.=
=20
But if it's a choice between a size and an iterator you already have,=20
neither is going to be faster.

In any case, if we're going to add sized `snip`, then we should also add=20
sized `splice`, for the same reasons.

This eliminates your concern about the one-element case; it becomes simply
>
>     auto lst =3D source.snip(source.begin(), 1);
>
> with no special coding necessary.
> However, there is still a use-case for
>
>     auto lst =3D source.snip(first, last);
>
> as well; I would tentatively expect both signatures to be provided.
>
> Notice that source.snip(first, last) cannot possibly be an O(1) operation=
,=20
> because it needs to walk the entire sublist to decide on the value of=20
> lst.size() and the value to subtract from source.size().
>

Whether this is problematic or not depends entirely on what you do with the=
=20
extracted elements. If you splice the entire snipped list into some other=
=20
`list`, then that can be an O(1) operation, because you already have its=20
size. If you had instead returned some specialized, unsized=20
snipped-node-sequence object, then you would have to compute the new size=
=20
at `splice` time. So whether at snip or splice time, you're computing a=20
size.

But really, this is an argument for having an un-sized/non-O(1)-sized=20
`list`. We have to deal with what we've got.

Consider whether `forward_list::snip_after` should exist. It could probably=
=20
> be O(1) because forward_list does not track its own size.
>

> Also: if we add list::extract(it, it) -> list, should we add=20
>> map::extract(it, it) -> map? After all, a sub-range of a map is properly=
=20
>> ordered for becoming a new map, both in the RB-tree and the hash-map=20
>> implementations.
>>
>
> Proper sequential ordering isn't sufficient to become a brand-new map=20
> (AFAIK); you also need proper tree structure. Snipping a subtree into a n=
ew=20
> tree is possible, but detecting whether a range makes up a subtree=20
> structure isn't possible at the moment, and snipping out a subtree would=
=20
> tend to leave the source tree unbalanced.
> Is it actually possible to snip out a range from an RB-tree, turn the=20
> range into a balanced RB-tree, and rebalance the source RB-tree, and do i=
t=20
> all *faster* than if you just transferred the node-handles one at a time?
>
> =E2=80=93Arthur
>

--=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/5e05b030-5b4a-4113-b676-b6a5f212c4b7%40isocpp.or=
g.

------=_Part_1960_133623231.1518723683444
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Thursday, February 15, 2018 at 1:24:16 PM UTC-5=
, Arthur O&#39;Dwyer 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">On Thu, Feb 15, 2018 at 12:27 AM, Mutz, Marc <span dir=3D"ltr=
">&lt;<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"63=
nM4E3nCgAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;javascript:&#3=
9;;return true;" onclick=3D"this.href=3D&#39;javascript:&#39;;return true;"=
>ma...@kdab.com</a>&gt;</span> wrote:<br><div><div class=3D"gmail_quote"><b=
lockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-le=
ft-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);pad=
ding-left:1ex">On 2018-02-14 16:29, Nicol Bolas wrote:<br>
[...]<span><br>
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);p=
adding-left:1ex">
To me, the principle need for a `list::extract` is to avoid having to<br>
do this:<br>
<br>
decltype(source) lst(source.get_allocator());<br>
lst.splice(lst.begin(), begin, end);<br>
It&#39;d be much easier to be able to do:<br>
<br>
auto lst =3D source.extract(begin, end);<br>
It should just be a convenience wrapper around `splice` functionality.<br>
</blockquote>
<br></span>
Right. It&#39;s a bit weird that list::extract returns a list while map::ex=
tract returns a node_handle, but I guess that&#39;s ok, since map does not =
have an extract(it, it) overload.<br></blockquote><div><br></div><div>Okay,=
 I&#39;m convinced that Marc has a use-case for &quot;moveless popping&quot=
; an element off of a std::list (which could be used to shorten a critical =
section, for example).</div><div>However, `extract` is not the right name f=
or this thing unless it returns a node_handle, which it apparently does not=
..</div></div></div></div></blockquote><div><br>Fair enough.<br><br></div><b=
lockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;borde=
r-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=
=3D"gmail_quote"><div>Marc, the name for &quot;snip a range of elements out=
 of a larger sequence&quot; would be more like &quot;sublist&quot;, analogo=
us to &quot;substr&quot;. However, &quot;substr&quot; is copying, whereas y=
ou want something that mutates the original container too; therefore the na=
me should include a verb. Perhaps &quot;extract_sublist&quot; or &quot;pop_=
sublist&quot; or &quot;snip_sublist&quot;. Perhaps just &quot;snip&quot;, a=
ctually =E2=80=94 it&#39;s sufficiently different from the already-taken &q=
uot;extract&quot;, and pleasingly similar to the existing verb &quot;splice=
&quot;.</div><div><br></div></div></div></div></blockquote><br><div></div><=
blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bord=
er-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div clas=
s=3D"gmail_quote"><div></div><div>Since list iterators are non-random-acces=
s iterators, I believe there will be a desire for</div><div><br></div><div>=
=C2=A0 =C2=A0 auto lst =3D source.snip(source.begin(), 42);</div><div><br><=
/div><div>as that is implementable much more efficiently than</div><div><br=
></div><div><div>=C2=A0 =C2=A0 auto lst =3D source.snip(source.begin(), std=
::next(source.begin(), 42));</div></div></div></div></div></blockquote><div=
><br>If you only have a size rather than an iterator, yes this will be fast=
er. But if it&#39;s a choice between a size and an iterator you already hav=
e, neither is going to be faster.<br><br>In any case, if we&#39;re going to=
 add sized `snip`, then we should also add sized `splice`, for the same rea=
sons.<br><br></div><div></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">=
<div dir=3D"ltr"><div><div class=3D"gmail_quote"><div></div><div>This elimi=
nates your concern about the one-element case; it becomes simply</div><div>=
<br></div><div><div>=C2=A0 =C2=A0 auto lst =3D source.snip(source.begin(), =
1);</div></div><div><br></div><div>with no special coding necessary.</div><=
div>However, there is still a use-case for<br></div><div><div><br></div><di=
v>=C2=A0 =C2=A0 auto lst =3D source.snip(first, last);</div></div><div><br>=
</div><div>as well; I would tentatively expect both signatures to be provid=
ed.</div><div><br></div><div>Notice that source.snip(first, last) cannot po=
ssibly be an O(1) operation, because it needs to walk the entire sublist to=
 decide on the value of lst.size() and the value to subtract from source.si=
ze().</div></div></div></div></blockquote><div><br>Whether this is problema=
tic or not depends entirely on what you do with the extracted elements. If =
you splice the entire snipped list into some other `list`, then that can be=
 an O(1) operation, because you already have its size. If you had instead r=
eturned some specialized, unsized snipped-node-sequence object, then you wo=
uld have to compute the new size at `splice` time. So whether at snip or sp=
lice time, you&#39;re computing a size.<br><br>But really, this is an argum=
ent for having an un-sized/non-O(1)-sized `list`. We have to deal with what=
 we&#39;ve got.<br><br></div><blockquote class=3D"gmail_quote" style=3D"mar=
gin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><=
div dir=3D"ltr"><div><div class=3D"gmail_quote"><div>Consider whether `forw=
ard_list::snip_after` should exist. It could probably be O(1) because forwa=
rd_list does not track its own size.</div></div></div></div></blockquote><d=
iv></div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: =
0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div=
><div class=3D"gmail_quote"><div><br></div><blockquote class=3D"gmail_quote=
" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style=
:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Also: if we add=
 list::extract(it, it) -&gt; list, should we add map::extract(it, it) -&gt;=
 map? After all, a sub-range of a map is properly ordered for becoming a ne=
w map, both in the RB-tree and the hash-map implementations.<br></blockquot=
e><div><br></div><div>Proper sequential ordering isn&#39;t sufficient to be=
come a brand-new map (AFAIK); you also need proper tree structure. Snipping=
 a subtree into a new tree is possible, but detecting whether a range makes=
 up a subtree structure isn&#39;t possible at the moment, and snipping out =
a subtree would tend to leave the source tree unbalanced.</div><div>Is it a=
ctually possible to snip out a range from an RB-tree, turn the range into a=
 balanced RB-tree, and rebalance the source RB-tree, and do it all <i>faste=
r</i> than if you just transferred the node-handles one at a time?</div><di=
v><br></div><div>=E2=80=93Arthur</div></div></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/5e05b030-5b4a-4113-b676-b6a5f212c4b7%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/5e05b030-5b4a-4113-b676-b6a5f212c4b7=
%40isocpp.org</a>.<br />

------=_Part_1960_133623231.1518723683444--

------=_Part_1959_953387243.1518723683444--

.