220 19013 <477203ce-e59f-4198-8814-3335d4e01db6@isocpp.org> article Path: news.gmane.org!not-for-mail From: =?UTF-8?Q?Aymeric_Pell=C3=A9?= Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: vector unstable_erase Date: Fri, 10 Jul 2015 02:17:13 -0700 (PDT) Lines: 245 Approved: news@gmane.org Message-ID: <477203ce-e59f-4198-8814-3335d4e01db6@isocpp.org> References: <1235950b-a10c-4dc6-afe8-89ef8210a78a@isocpp.org> <559DD332.9020200@gmail.com> <01880b60-5e6c-4498-ae85-4d6097080143@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_1661_747144962.1436519833495" X-Trace: ger.gmane.org 1436519838 17333 80.91.229.3 (10 Jul 2015 09:17:18 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 10 Jul 2015 09:17:18 +0000 (UTC) Cc: dibeas@ieee.org To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDHZ5B6JWEGRBGU372WAKGQEEO6YR3I@isocpp.org Fri Jul 10 11:17:17 2015 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ob0-f199.google.com ([209.85.214.199]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZDUQm-0002ha-HZ for gclcip-std-proposals@m.gmane.org; Fri, 10 Jul 2015 11:17:16 +0200 Original-Received: by obbtu2 with SMTP id tu2sf408492253obb.1 for ; Fri, 10 Jul 2015 02:17:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:content-type:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=C4YF56iwNaLftyIfXuU1fpPLJiSU3f8Ere9TTdARMS0=; b=fAzwCUSqHUhe3ncm97sRkgJFZXjDjMc4DW3ZGoQVBrFF70YVQmIfmxTP9M0qTBd463 /H/0gDX+GXTlK+y8SZAIo+q9w/X44y3SW7cdN+gclCtdSxMrb/QX7k+7ZgNt5bVeEixd wdNsQH8W0u4X9cMwSsiwxw8JzQTYwg4JnW4exn1JuTq1ST/C8/3bok6vENl1SPI1xPC+ gnqAYa5489q8dICqcfL+bTw+raTpjsvWXc5r32R08fQjzUsGTG5TEUcIPjxOy22TL5yQ 7V5ypVe3259V3Zs8TMeYS+7I7K2nSHGwy2+rmlodLzHqS58uh6En1EGqMcXToMOxlGt5 30sQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:cc:message-id:in-reply-to :references:subject:mime-version:content-type:x-original-sender :reply-to:precedence:mailing-list:list-id:x-spam-checked-in-group :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=C4YF56iwNaLftyIfXuU1fpPLJiSU3f8Ere9TTdARMS0=; b=WWvuqxqPvd499oUzXOKX2HgJAYrZLkDH0yVql5zi2GuMKWc9dwyK9tBZfHO5n1Nsys X6ri8te2fkdT7BJ8jDwYzZRgFVz4Gx2J4LEWc+XiE+qJuuZWbhKVhsN/ACeMrvHi0OBC uoZBwpS3Apa+fp6U3e/Uf1ntWiawPZVDLOg8N9g/LZobaYuT3bwUxWMjPG3Z52OpWAiz qGweNoNVa2j5XlR1GTW9RqJnv6oZoo4Nf0gp9wyvyPTAcQHQJDajrQIbWYTusjc2VuQ8 CBkRxD6rtTZxPIoMbnx+0XVksEpn7aarstK3SDKPdIRHL+yFuU7yy+WTg+NnQHc1Gtmg UkYw== X-Gm-Message-State: ALoCoQl2ZQzqztm+htPgnT3NLIZg5jWDXSrmLecSMV1jB3YAm49Zo0jBG0rYqp0dJWWUXdzz1qD0 X-Received: by 10.182.103.131 with SMTP id fw3mr25641079obb.38.1436519835627; Fri, 10 Jul 2015 02:17:15 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.80.179 with SMTP id c48ls5189563qgd.93.gmail; Fri, 10 Jul 2015 02:17:14 -0700 (PDT) X-Received: by 10.140.102.172 with SMTP id w41mr289343qge.40.1436519834061; Fri, 10 Jul 2015 02:17:14 -0700 (PDT) In-Reply-To: <01880b60-5e6c-4498-ae85-4d6097080143@isocpp.org> X-Original-Sender: aymeric.pelle@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:19013 Archived-At: ------=_Part_1661_747144962.1436519833495 Content-Type: multipart/alternative; boundary="----=_Part_1662_913149977.1436519833495" ------=_Part_1662_913149977.1436519833495 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable > > It sounds like this function could be added to as follows... > > namespace std { > template > void unstable_erase(C& container, const It& elt) { > *elt =3D std::move(container.back()); // OOPS > container.pop_back(); > } > } // namespace std > > ...except that the line marked "OOPS" will invoke undefined behavior in= =20 > the case that iterator =3D=3D container.end()-1,=20 > There is no problem with this line. When you implement operator=3D (const T& t) for a class, you have to manage= =20 the case where &t =3D=3D this. It is the same with r-values, you have to manage this case anyway. You can= =20 imagine an algorithm where this can happen. Standard library types manage this case. From my part, the behavior is not undefined. If it is, the user did a=20 mistake. =20 > and as David pointed out, it will be pessimal in the case that C is=20 > std::list (so it needs a partial specialization, which means some=20 > additional hairiness in the implementation). > A specialization is necessary for std::list which simply calls=20 a_list.erase(an_iterator). =20 > In other words, the pattern here is "relatively simple algorithm, lots of= =20 > hairy little details" =E2=80=94 which is exactly the kind of thing we exp= ect the=20 > standard library to provide for us. Don't make everybody reinvent the hai= ry=20 > wheel; put a good implementation in the STL and give it to everybody for= =20 > free! > > A more traditional-STL interface for this function would be > > namespace std { > template > It unstable_remove(const It& begin, const It& end, const It& to_remove) { > if (to_remove !=3D end) { > *to_remove =3D std::move(*end); > } > return std::prev(to_remove); > } > } // namespace std > (This function should return std::prev(end).) I desapprove such a solution. remove functions of the standard take a value= =20 or a predicate not an iterator. It could be confusing. Moreover, this function should not test any condition on the input=20 parameters. I prefer a pre-condition as Zach Laine suggested. Such conditions exist in the standard, for example : 'Calling pop_back on= =20 an empty container is undefined.'=20 (http://en.cppreference.com/w/cpp/container/vector/pop_back) =20 > > to be used as > > auto it =3D v.find(...); > v.erase(std::unstable_remove(v.begin(), v.end(), it), v.end()); > In this case, I would prefer call : *it =3D std::move(v.back()); v.pop_back(); So, I prefer such an implementation for the generic case : namespace std { /** \pre !container.empty() */ template It unstable_erase(C& container, const It& iter) { *iter =3D std::move(container.back()); // No problem here container.pop_back(); return iter; } } // namespace std For the motivation of this feature, I think John Bytheway and Patrice Roy= =20 summarised what I had in mind. (Thank you.) (I have hesitated to submit it for a year. Then, two days ago, I met an=20 other developper in my company who decided to use a list instead of using a= =20 vector just because erase has O(1) as complexity for list and not for vector (the order didn't= =20 matter in his case). Of course, he was not the first developper I met who= =20 did this mistake.)=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_1662_913149977.1436519833495 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
It sound= s like this function could be added to <algorithm> as follows...

namespace std {<= /font>
template<typename= C, typename It>
void = unstable_erase(C& container, const It& elt) {
=C2=A0 =C2=A0 *elt =3D std::move(container.back= ()); =C2=A0// OOPS
= =C2=A0 =C2=A0 container.pop_back();
}
} //= namespace std

...except that the line marked &qu= ot;OOPS" will invoke undefined behavior in the case that iterator =3D=3D container.end()-1,

There is no problem with this line.When you implement op= erator=3D (const= T& t) for a class, you have to manage the case where &t =3D= =3D this.
It is the same with r-values, you have to manage this case any= way. You can imagine an algorithm where this can happen.
Standard librar= y types manage this case.
From my part, the behavior is not undefined. I= f it is, the user did a mistake.
=C2=A0
and as David pointed out,= it will be pessimal in the case that C is std::list (so it needs a partial= specialization, which means some additional hairiness in the implementatio= n).

A specialization is necess= ary for std::list which simply calls a_list.erase(an_iterator).
=C2=A0
<= blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bord= er-left: 1px #ccc solid;padding-left: 1ex;">
In other words, the pattern here is "relatively simple alg= orithm, lots of hairy little details" =E2=80=94 which is exactly the k= ind of thing we expect the standard library to provide for us. Don't ma= ke everybody reinvent the hairy wheel; put a good implementation in the STL= and give it to everybody for free!

A more traditi= onal-STL interface for this function would be

namespace std {
template<typename It>
= It unstable_remove(const It& begi= n, const It& end, const It& to_remove) {
=C2=A0 =C2=A0 if (to_remove !=3D end) {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 = *to_remove =3D std::move(*end);
=C2=A0 =C2=A0 }
=C2=A0 =C2=A0 return std::prev(to_remove);
}
} // namespace std
=

(This function should r= eturn std::prev(end).)
I desapprove such a solution. remove functions of the standard ta= ke a value or a predicate not an iterator. It could be confusing.
Moreov= er, this function should not test any condition on the input parameters. I = prefer a pre-condition as Zach Laine suggested.
Such conditions exist in= the standard, for example : 'Calling pop_back on an empty= container is undefined.' (http://en.cppreference.com/w/cpp/container/v= ector/pop_back)
=C2=A0

to be used as

=C2=A0 =C2=A0 auto it =3D v.find(...);
=C2=A0 =C2=A0 v.erase(std::unstable_= remove(v.begin(), v.end(), it), v.end());

In this case, I would prefer call :

*it =3D std::move(v.back());
v.= pop_back();

So, I prefer such an implementation for the gener= ic case :

namespace std {=
/**
= =C2=A0=C2=A0 \pre !container.empty()
*/
template<t= ypename C, typename It>
=C2=A0 =C2=A0 *iter =3D st= d::move(container.back()); =C2=A0// No problem here
=C2=A0 =C2=A0 container.pop_back();
= =C2=A0=C2=A0=C2=A0 return iter;
}
} // namespace= std

For the motivation of this feature, I think John Bytheway and Patrice Roy summarised what I= had in mind. (Thank you.)
(I have hesitated to submit it for a year. Th= en, two days ago, I met an other developper in my company who decided to us= e a list instead of using a vector just because
erase has O(1) as comple= xity for list and not for vector (the order didn't matter in his case).= Of course, he was not the first developper I met who did this mistake.)

--

---
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+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/<= /a>.
------=_Part_1662_913149977.1436519833495-- ------=_Part_1661_747144962.1436519833495-- .