220 6233 <6c98fd58-4225-4904-85de-d14a9e77bc01@isocpp.org> article Path: news.gmane.org!not-for-mail From: inkwizytoryankes@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Re: Specialization of std::stack for std::forward_list Date: Sat, 7 Sep 2013 06:53:47 -0700 (PDT) Lines: 233 Approved: news@gmane.org Message-ID: <6c98fd58-4225-4904-85de-d14a9e77bc01@isocpp.org> References: <5b046beb-f0c0-4cd2-96bb-bc7007da13e9@isocpp.org> <1111d35d-1a91-47b3-a2a4-01c2b91a6527@isocpp.org> <5ad3d618-fb43-4ceb-90a2-2d7c0b9bfffd@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_506_25686563.1378562027296" X-Trace: ger.gmane.org 1378562027 10209 80.91.229.3 (7 Sep 2013 13:53:47 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 7 Sep 2013 13:53:47 +0000 (UTC) Cc: inkwizytoryankes@gmail.com To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDDLTAGNTIBBB267VSIQKGQEPDJW5OQ@isocpp.org Sat Sep 07 15:53:50 2013 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yh0-f69.google.com ([209.85.213.69]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VIIxR-0002be-IA for gclcip-std-proposals@m.gmane.org; Sat, 07 Sep 2013 15:53:49 +0200 Original-Received: by mail-yh0-f69.google.com with SMTP id c41sf2111087yho.0 for ; Sat, 07 Sep 2013 06:53:48 -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:x-original-sender:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe:content-type; bh=mgdG/QOfjgfGn37YGw+Xk4IiIpF7ybyXtFc2XrUfld4=; b=o2H1GB8I/YYkxVvBbAWpxtpD61cN57pMH24VOoHr/H3qoGGiM79sVd3Mt3xOfqwW4h /GD1Lh5CWSsX+2wlDAExtgy2hJqDQ4QPQzhx2XabseJPzq6aOx2laAQ6i1FLGVfDfrbr JWGrngmRCPOhrGO+8+VPrXg62ldiBRywTbA4q72XCKHClR2J2IuPkTgCkZFrlt5S/cFa x07gKsOph2BLei1oTuT0wkuk+fvDrYZcgs0+43y2VeuQVd3JNYrg2GhGOyvohyIrzReQ CH9Ts3VcpR4KeEqXj7oUKjgBv6nKf4bFPV0Vx7MUP/NLaudMa1KCbqjIiI97HivQt5Tb mpLQ== X-Received: by 10.236.69.35 with SMTP id m23mr2738182yhd.6.1378562028321; Sat, 07 Sep 2013 06:53:48 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.49.3.169 with SMTP id d9ls1448353qed.61.gmail; Sat, 07 Sep 2013 06:53:47 -0700 (PDT) X-Received: by 10.49.83.199 with SMTP id s7mr36796qey.11.1378562027852; Sat, 07 Sep 2013 06:53:47 -0700 (PDT) In-Reply-To: X-Original-Sender: inkwizytoryankes@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: 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:6233 Archived-At: ------=_Part_506_25686563.1378562027296 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable After this discussion I end up with conclusion that your solution is=20 correct one. Its simples and requare no changes in `std::stack` or in=20 `std::forward_list`. Another thing is that if any problems would occur it will be during=20 compilation not in execution (you cant remove anything from `std::forward_list` without using this=20 warper, therefore `size()` will always return correct value). On Saturday, September 7, 2013 1:02:30 PM UTC+2, Daniel Kr=FCgler wrote: > > 2013/9/7 Vlad from Moscow > > >> What you demonstarted is not a stack. You dealt with a container. So=20 >> there is nothing suprising that the elements are outputed in the reverse= =20 >> order. It was your decision to use std::forward_list as a container.=20 >> > > It is not clear whose decision it will be, because the std::stack might b= e=20 > used as an implementation detail of another template, so it the effects a= re=20 > very unexpected and not aware of the implementer of the "outer2 template.= =20 > > Keep also in mind that the protected member 'c' is part of the API, so=20 > someone who derives from stack can expect that the member functions of c= =20 > required in the std::stack specification do exist. In case of your=20 > hypothetical specialization of std::stack the derived template would brea= k=20 > when trying to refer to push_back(), back(), etc. > > I also think that your assertion that stack "is a some sort of an abstrac= t=20 > class" is misleading. This type as an *adaptor* type, so like other=20 > adaptors its specification relies on a well-defined set of operations fro= m=20 > the adapteed type. The standard library support user-defined=20 > specializations of library templates ([namespace.std]), if specialization= =20 > meets the standard library requirements for the original template. This i= s=20 > not satisfied for std::forward_list, because the difference is observable= ,=20 > *because* the member c is part of its API. > > =20 > >> It is the same as you would use std::list and then decided to change it= =20 >> to std::vector and now you wonder that std::vector has no member functio= n=20 >> push_front. >> > > No, this example does not match here for std::stack, because std::stack= =20 > does not depend on any operation named push_front(). > =20 > >> Your example demonstrates that the specialization of std::stack for=20 >> std::forward_list is very useful! Because it allows to output elements o= f a=20 >> stack in the natural order in which they are stored in it that is in th= e=20 >> order FILO. =20 >> > > Again I repeat that this can already be realized by providing an adaptor= =20 > of forward_list, that provides the required operations needed for=20 > std::stack. There is no reason to assume that such an adaptor would cause= =20 > any time overhead. There would be a small space overhead to provide the= =20 > size() member, but obviously this idea was accepted when using std::stack= =20 > based on forward_list. I also consider this kind of adaptor as an=20 > interesting one that is similar to reverse_iterator for iterators. I'm no= t=20 > sure that reverse_container is the right name for it, but here the rough= =20 > idea of such a template: > > template > > class reverse_container { > public: > typedef typename Container::value_type value_type; > typedef typename Container::reference reference; > typedef typename Container::const_reference const_reference; > typedef typename Container::size_type size_type; > typedef Container container_type;=20 > [..] // constructors > bool empty() const { return c.empty(); } > size_type size() const { return c.size(); } > reference back() { return c.front(); } > const_reference back() const { return c.front(); } > =20 > void push_back(const value_type& x) { c.push_front(x); } > void push_back(value_type&& x) { c.push_front(std::move(x)); } > template void emplace_back(Args&&... args) > { c.emplace_front(std::forward(args)...); } > void pop_back() { c.pop_font(); } > void swap(stack& s) noexcept(noexcept(swap(c, s.c))) > { using std::swap; swap(c, s.c); } > private: > Container c; // For exposition only > }; > > I'm leaving the decision open here, there are several ways to handle that= .. > > - Daniel > > --=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_506_25686563.1378562027296 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
After this discussion I end up with conclusion that your s= olution is correct one. Its simples and requare no changes in `std::stack` = or in `std::forward_list`.
Another thing is that if any problems would o= ccur it will be during compilation not in execution
(you cant remove any= thing from `std::forward_list` without using this warper, therefore `size()= ` will always return correct value).

On Saturday, September 7, 2013 = 1:02:30 PM UTC+2, Daniel Kr=FCgler wrote:
2013/9/7 Vlad from Moscow <= ;vlad....@mail.ru>
<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex">
What you demonstarted is not a stack. You dealt with = a container. So there is nothing suprising that the elements are outputed i= n the reverse order. It was your decision to use std::forward_list as a con= tainer. 

It is not clear whose decision it wi= ll be, because the std::stack might be used as an implementation detail of = another template, so it the effects are very unexpected and not aware of th= e implementer of the "outer2 template.

Keep also in mind that the protected member 'c' is part of the API, so = someone who derives from stack can expect that the member functions of c re= quired in the std::stack specification do exist. In case of your hypothetic= al specialization of std::stack the derived template would break when tryin= g to refer to push_back(), back(), etc.

I also think that your assertion that stack "is a some sort = of an abstract class" is misleading. This type as an *adaptor* type, so lik= e other adaptors its specification relies on a well-defined set of operatio= ns from the adapteed type. The standard library support  user-defined = specializations of library templates ([namespace.std]), if specialization m= eets the standard library requirements for the original template. This is n= ot satisfied for std::forward_list, because the difference is observable, *= because* the member c is part of its API.

 
It is the same as you would use std::list and then= decided to change it to std::vector and now you wonder that std::vector ha= s no member function push_front.

No, this example does not match here= for std::stack, because std::stack does not depend on any operation named = push_front().
 
 Your example demonstrates that the specializati= on of std::stack for std::forward_list is very useful! Because it allows to= output elements of a stack in the natural order in which th= ey are  stored in it that is in the order FILO.  <= /div>

Again I repeat that this can already= be realized by providing an adaptor of forward_list, that provides the req= uired operations needed for std::stack. There is no reason to assume that s= uch an adaptor would cause any time overhead. There would be a small space = overhead to provide the size() member, but obviously this idea was accepted= when using std::stack based on forward_list. I also consider this kind of = adaptor as an interesting one that is similar to reverse_iterator for itera= tors. I'm not sure that reverse_container is the right name for it, but her= e the rough idea of such a template:

template <class T, class Container =3D deque<T> >
class = reverse_container {
public:
  typedef typename Container::value_= type value_type;
  typedef typename Container::reference reference;=
  typedef typename Container::const_reference const_reference;
  typedef typename Container::size_type size_type;
  typedef C= ontainer container_type;
  [..] // constructors
&nbs= p; bool empty() const { return c.empty(); }
  size_type size() cons= t { return c.size(); }
  reference back() { return c.front(); }
  const_reference ba= ck() const { return c.front(); }
 
  void push_back(const = value_type& x) { c.push_front(x); }
  void push_back(value_type= && x) { c.push_front(std::move(x)); }
  template <class... Args> void emplace_back(Args&&... a= rgs)
  { c.emplace_front(std::forward<Args>(args)...); }=
  void pop_back() { c.pop_font(); }
  void swap(stack&= s) noexcept(noexcept(swap(c, s.c)))
  { using std::swap; swap(c, s.c); }
private:
<= div>  Container c; // For exposition only
};

I'm leaving the decision open here, there are several ways to handle= that.

- Daniel

--
 
---
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-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/<= /a>.
------=_Part_506_25686563.1378562027296-- .