220 6218 <87e679e7-d932-41e5-bbb3-244e7f28d260@isocpp.org> article Path: news.gmane.org!not-for-mail From: Vlad from Moscow Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Re: Specialization of std::stack for std::forward_list Date: Sat, 7 Sep 2013 05:15:04 -0700 (PDT) Lines: 255 Approved: news@gmane.org Message-ID: <87e679e7-d932-41e5-bbb3-244e7f28d260@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_566_8743719.1378556104126" X-Trace: ger.gmane.org 1378556103 2540 80.91.229.3 (7 Sep 2013 12:15:03 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 7 Sep 2013 12:15:03 +0000 (UTC) Cc: inkwizytoryankes@gmail.com To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBCXLLRHD7IDRBSFRVSIQKGQEXUOK6MI@isocpp.org Sat Sep 07 14:15:06 2013 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-qc0-f198.google.com ([209.85.216.198]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VIHPu-0001SK-5I for gclcip-std-proposals@m.gmane.org; Sat, 07 Sep 2013 14:15:06 +0200 Original-Received: by mail-qc0-f198.google.com with SMTP id l13sf587010qcy.5 for ; Sat, 07 Sep 2013 05:15:05 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; 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=FfNU7lToIPReVww6P+a45rsojlszwf0ExQ70slq4O8k=; b=dDWF4ZzKCj7sItyV66YIVCbakA5ACkVu2j/NsG/w2SE3HoCMa1Ny/pPaSbmJY/7rfC oAta2iT7ZYqewJ1acaUeWJNvmstKpWgRzGCKTabhz9qkfamhq0HfBJX+mI3rHfI3wZOD fQxnLir05rHlyedE/oHOwb/+oFyJtc/DNTYnK2d4MU6yQ/CW7x0m9Kp8R0wlSgbw3WAF 1MGBW8CRvk3Xb1CuSoCxCZ6DmKzeD52Ek8rBB0VNaCXIbR4F+ET9i2XmyPjE7NCXybLY mS+RTSb2huaVfy1rWZPzQQVmeWi1nn2NCEn4/GFTJUH++WdQClGWIT0jEFfQjj4xPWvU wE0w== X-Received: by 10.224.223.198 with SMTP id il6mr8802807qab.7.1378556105293; Sat, 07 Sep 2013 05:15:05 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.49.71.83 with SMTP id s19ls1218568qeu.7.gmail; Sat, 07 Sep 2013 05:15:04 -0700 (PDT) X-Received: by 10.49.64.72 with SMTP id m8mr1700qes.20.1378556104585; Sat, 07 Sep 2013 05:15:04 -0700 (PDT) In-Reply-To: X-Original-Sender: vlad.moscow@mail.ru 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:6218 Archived-At: ------=_Part_566_8743719.1378556104126 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable =20 By the way when std:;stack was adopted there was no such a container as=20 std:;forward_list. It is the only std::vector that among other sequantial= =20 containers has no member function push_front. =20 So all sequantial containers can be split into two groups.=20 =20 The one that contains std::vector, std::deque and std::list may use=20 push_back and back() methods that to simulate the stack. =20 The other group contains std:;deque, std::list and std:;forward_list that= =20 canuse methods push_front and front to simulate the stack. =20 I think no one group should be discriminated.=20 =D1=81=D1=83=D0=B1=D0=B1=D0=BE=D1=82=D0=B0, 7 =D1=81=D0=B5=D0=BD=D1=82=D1= =8F=D0=B1=D1=80=D1=8F 2013 =D0=B3., 15:02:30 UTC+4 =D0=BF=D0=BE=D0=BB=D1=8C= =D0=B7=D0=BE=D0=B2=D0=B0=D1=82=D0=B5=D0=BB=D1=8C Daniel Kr=C3=BCgler=20 =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB: > 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_566_8743719.1378556104126 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
 
By the way when std:;stack was adopt= ed there was no such a container as std:;forward_list. It is the only std::= vector that among other sequantial containers has no member function push_f= ront.
 
So all sequantial containers can be split = into two groups.
 
The one that contains std::vec= tor, std::deque and std::list may use push_back and back() methods tha= t to simulate the stack.
 
The other group co= ntains std:;deque, std::list and std:;forward_list that canuse methods= push_front and front to simulate the stack.
 
I think no one group should be discriminated. 

= =D1=81=D1=83=D0=B1=D0=B1=D0=BE=D1=82=D0=B0, 7 =D1=81=D0=B5=D0=BD=D1=82=D1= =8F=D0=B1=D1=80=D1=8F 2013 =D0=B3., 15:02:30 UTC+4 =D0=BF=D0=BE=D0=BB= =D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=D1=82=D0=B5=D0=BB=D1=8C Daniel Kr=C3=BCgler = =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:
2013/9/7 Vlad from Moscow <v= lad....@mail.ru>
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 has 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_566_8743719.1378556104126-- .