Topic: Destructive remove from containers
Author: Travis Gockel <travis@gockelhut.com>
Date: Sun, 12 Oct 2014 17:42:49 -0700 (PDT)
Raw View
------=_Part_2339_1889827912.1413160969586
Content-Type: text/plain; charset=UTF-8
There are a number of use cases where I want to entirely consume the
contents of an associative container and re-use the memory of the keys. If
I have an expensive to copy yet cheap to move key type, there is not a
supported way of moving my key to a new object, even though I am about to
erase said key from the container. I would love an operation that allowed
me to extract and re-use the key when I am moving it to another structure.
All associative containers could benefit from such an operation. The need
for this operation isn't terrifically common, but I think it is generic
enough to warrant a discussion.
In an std::map<Key, Value>, you might have member functions like so:
std::pair<iterator, std::optional<std::pair<Key, Value>>>
destroy(const Key& position);
std::pair<iterator, std::pair<Key, Value>>
destroy(const_iterator position);
For std::set<Key>:
std::pair<iterator, std::optional<Key>>
destroy(const Key& position);
std::pair<iterator, Key>
destroy(const_iterator position);
Forgive the poor naming...I can't think of a better one. I also can't
figure out a great way to make this scale to multimap/multiset.
The concept will feel familiar if you know Rust's container removal
operations (things like std::Vec<T>::pop return an Option<T> with the value
you popped moved into the Option).
--
---
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_2339_1889827912.1413160969586
Content-Type: text/html; charset=UTF-8
<div dir="ltr">There are a number of use cases where I want to entirely consume the
contents of an associative container and re-use the memory of the keys. If
I have an expensive to copy yet cheap to move key type, there is not a
supported way of moving my key to a new object, even though I am about to
erase said key from the container. I would love an operation that allowed
me to extract and re-use the key when I am moving it to another structure.
All associative containers could benefit from such an operation. The need
for this operation isn't terrifically common, but I think it is generic
enough to warrant a discussion.
<br>
<br>In an <span style="font-family: courier new,monospace;">std::map<Key, Value></span>, you might have member functions like so:
<br>
<br><span style="font-family: courier new,monospace;"> std::pair<iterator, std::optional<std::pair<Key, Value>>>
<br> destroy(const Key& position);
<br>
<br> std::pair<iterator, std::pair<Key, Value>>
<br> destroy(const_iterator position);
</span><br>
<br>For <span style="font-family: courier new,monospace;">std::set<Key></span>:
<br>
<br><span style="font-family: courier new,monospace;"> std::pair<iterator, std::optional<Key>>
<br> destroy(const Key& position);
<br>
<br> std::pair<iterator, Key>
<br> destroy(const_iterator position);
</span><br>
<br>Forgive the poor naming...I can't think of a better one. I also can't
figure out a great way to make this scale to multimap/multiset.
<br>
<br>The concept will feel familiar if you know Rust's container removal
operations (things like <span style="font-family: courier new,monospace;">std::Vec<T>::pop</span> return an <span style="font-family: courier new,monospace;">Option<T></span> with the value
you popped moved into the Option).
</div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:std-proposals+unsubscribe@isocpp.org">std-proposals+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href="mailto:std-proposals@isocpp.org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href="http://groups.google.com/a/isocpp.org/group/std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/</a>.<br />
------=_Part_2339_1889827912.1413160969586--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Mon, 13 Oct 2014 10:39:19 +0200
Raw View
On Sunday 12 October 2014 17:42:49 Travis Gockel wrote:
> I would love an operation that allowed
> me to extract and re-use the key when I am moving it to another structure.
> All associative containers could benefit from such an operation.
I think this was discussed two weeks or three ago.
The problem is that it can't be done exception-safely.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--
---
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/.
.
Author: Sean Middleditch <sean.middleditch@gmail.com>
Date: Mon, 13 Oct 2014 21:04:23 -0700 (PDT)
Raw View
------=_Part_3807_1596819911.1413259464145
Content-Type: text/plain; charset=UTF-8
On Monday, October 13, 2014 1:48:24 AM UTC-7, Thiago Macieira wrote:
>
> On Sunday 12 October 2014 17:42:49 Travis Gockel wrote:
> > I would love an operation that allowed
> > me to extract and re-use the key when I am moving it to another
> structure.
> > All associative containers could benefit from such an operation.
>
> I think this was discussed two weeks or three ago.
>
> The problem is that it can't be done exception-safely.
>
The number of compromises one has to make for exceptions does grow
wearisome.
Why not just make these members noexcept and only exist for
noexcept-movable keys/values?
--
---
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_3807_1596819911.1413259464145
Content-Type: text/html; charset=UTF-8
<div dir="ltr">On Monday, October 13, 2014 1:48:24 AM UTC-7, Thiago Macieira wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Sunday 12 October 2014 17:42:49 Travis Gockel wrote:
<br>> I would love an operation that allowed
<br>> me to extract and re-use the key when I am moving it to another structure.
<br>> All associative containers could benefit from such an operation.
<br>
<br>I think this was discussed two weeks or three ago.
<br>
<br>The problem is that it can't be done exception-safely.
<br></blockquote><div><br></div><div>The number of compromises one has to make for exceptions does grow wearisome.</div><div><br></div><div>Why not just make these members noexcept and only exist for noexcept-movable keys/values?</div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:std-proposals+unsubscribe@isocpp.org">std-proposals+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href="mailto:std-proposals@isocpp.org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href="http://groups.google.com/a/isocpp.org/group/std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/</a>.<br />
------=_Part_3807_1596819911.1413259464145--
.
Author: Travis Gockel <travis@gockelhut.com>
Date: Mon, 13 Oct 2014 22:17:18 -0600
Raw View
--001a1135ec948039af05055a4a6f
Content-Type: text/plain; charset=UTF-8
On Mon, Oct 13, 2014 at 10:04 PM, Sean Middleditch <
sean.middleditch@gmail.com> wrote:
> The number of compromises one has to make for exceptions does grow
> wearisome.
>
> Why not just make these members noexcept and only exist for
> noexcept-movable keys/values?
>
Are you thinking something to the tune of?
template <typename Container, typename Key, typename Value>
typename enable_if<is_nothrow_constructable<pair<Key, Value>, Key&&,
Value&&>::value,
pair<typename Container::iterator, pair<Key, Value>>
>::type
destroy(Container& c, typename Container::const_iterator position);
It would certainly fit my use case :-)
--
---
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/.
--001a1135ec948039af05055a4a6f
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On M=
on, Oct 13, 2014 at 10:04 PM, Sean Middleditch <span dir=3D"ltr"><<a hre=
f=3D"mailto:sean.middleditch@gmail.com" target=3D"_blank">sean.middleditch@=
gmail.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><div dir=3D"ltr"><span class=3D""></span><div>The number of comp=
romises one has to make for exceptions does grow wearisome.</div><div><br><=
/div><div>Why not just make these members noexcept and only exist for noexc=
ept-movable keys/values?</div></div></blockquote></div><br></div><div class=
=3D"gmail_extra">Are you thinking something to the tune of?<br><br></div><d=
iv class=3D"gmail_extra"><font face=3D"courier new,monospace">template <=
typename Container, typename Key, typename Value><br></font></div><div c=
lass=3D"gmail_extra"><font face=3D"courier new,monospace">typename enable_i=
f<is_nothrow_constructable<pair<Key, Value>, Key&&, Val=
ue&&>::value,<br></font></div><div class=3D"gmail_extra"><font f=
ace=3D"courier new,monospace">=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 pair<typ=
ename Container::iterator, </font><font face=3D"courier new,monospace">pair=
<Key, Value>><br></font></div><div class=3D"gmail_extra"><font fac=
e=3D"courier new,monospace">=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 >::type<br></f=
ont></div><div class=3D"gmail_extra"><font face=3D"courier new,monospace">d=
estroy(Container& c, typename Container::const_iterator position);<br><=
/font></div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra"=
>It would certainly fit my use case :-)<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" 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 />
--001a1135ec948039af05055a4a6f--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Tue, 14 Oct 2014 08:35:31 +0200
Raw View
On Monday 13 October 2014 21:04:23 Sean Middleditch wrote:
> On Monday, October 13, 2014 1:48:24 AM UTC-7, Thiago Macieira wrote:
> > On Sunday 12 October 2014 17:42:49 Travis Gockel wrote:
> > > I would love an operation that allowed
> > > me to extract and re-use the key when I am moving it to another
> >
> > structure.
> >
> > > All associative containers could benefit from such an operation.
> >
> > I think this was discussed two weeks or three ago.
> >
> > The problem is that it can't be done exception-safely.
>
> The number of compromises one has to make for exceptions does grow
> wearisome.
>
> Why not just make these members noexcept and only exist for
> noexcept-movable keys/values?
There's a workaround for your case.
Get a non-const reference to the item you want, and then swap it with an empty
(default-constructed) type. After that, remove it.
That way, you extract the item without copy and it's still exception-safe.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--
---
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/.
.
Author: David Krauss <potswa@gmail.com>
Date: Tue, 14 Oct 2014 14:59:05 +0800
Raw View
--Apple-Mail=_2BD7F028-E7C6-48E6-AA07-CF350997879B
Content-Type: text/plain; charset=ISO-8859-1
On 2014-10-14, at 2:35 PM, Thiago Macieira <thiago@macieira.org> wrote:
> Get a non-const reference to the item you want, and then swap it with an empty
> (default-constructed) type. After that, remove it.
>
> That way, you extract the item without copy and it's still exception-safe.
Getting a non-const reference into a std::set might not be UB per se, but it invalidates the invariants needed to safely remove the element.
--
---
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/.
--Apple-Mail=_2BD7F028-E7C6-48E6-AA07-CF350997879B
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=ISO-8859-1
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dwindows-1252"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-=
mode: space; -webkit-line-break: after-white-space;"><br><div><div>On 2014&=
ndash;10–14, at 2:35 PM, Thiago Macieira <<a href=3D"mailto:thiago=
@macieira.org">thiago@macieira.org</a>> wrote:</div><br class=3D"Apple-i=
nterchange-newline"><blockquote type=3D"cite"><div style=3D"font-size: 12px=
; font-style: normal; font-variant: normal; font-weight: normal; letter-spa=
cing: normal; line-height: normal; orphans: auto; text-align: start; text-i=
ndent: 0px; text-transform: none; white-space: normal; widows: auto; word-s=
pacing: 0px; -webkit-text-stroke-width: 0px;">Get a non-const reference to =
the item you want, and then swap it with an empty<span class=3D"Apple-conve=
rted-space"> </span><br>(default-constructed) type. After that, remove=
it.<br><br>That way, you extract the item without copy and it's still exce=
ption-safe.<br></div></blockquote><br></div><div>Getting a non-const refere=
nce into a std::set might not be UB per se, but it invalidates the invarian=
ts needed to safely remove the element.</div><div><br></div><br></body></ht=
ml>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" 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=_2BD7F028-E7C6-48E6-AA07-CF350997879B--
.
Author: Sean Middleditch <sean@middleditch.us>
Date: Tue, 14 Oct 2014 00:06:51 -0700
Raw View
On Mon, Oct 13, 2014 at 11:35 PM, Thiago Macieira <thiago@macieira.org> wrote:
> On Monday 13 October 2014 21:04:23 Sean Middleditch wrote:
>>
>> The number of compromises one has to make for exceptions does grow
>> wearisome.
>>
>> Why not just make these members noexcept and only exist for
>> noexcept-movable keys/values?
>
> There's a workaround for your case.
"workaround" being the operative word. :)
I'll restress a point that I made in a previous thread about a try-pop
interface being essential non-negotiable piece of some containers such
as concurrent queues. Exceptions can't keep being the excuse.
We have both conditional and unconditional noexcept; we don't have to
keep compromising on sensible user-friendly or high-efficiency
interfaces. If the user decides to make a type that can throw for
moves, they're going to have to deal with the consequences of opting
in to that design choice (which we can make into clear compile-time
errors rather than surprising run-time errors for new interfaces with
no fear of breaking existing code, at least).
--
Sean Middleditch
http://seanmiddleditch.com
--
---
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/.
.