220 13538 <3e2c6bae-052e-4001-a407-8c69ae41e8cc@isocpp.org> article Path: news.gmane.org!not-for-mail From: Matthew Fioravante Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Proposal: Strongly Typed Bitset Date: Thu, 2 Oct 2014 08:25:47 -0700 (PDT) Lines: 211 Approved: news@gmane.org Message-ID: <3e2c6bae-052e-4001-a407-8c69ae41e8cc@isocpp.org> References: <113390b2-9c74-47e2-a943-5d27dd48bdf1@isocpp.org> <41983d24-efb2-4255-b09b-f84cff7bf56d@isocpp.org> <63de9d71-e3b0-4242-9698-bea3a307b3c7@isocpp.org> <9462C54C-E91B-4B66-AA8E-CAEA1F190FE6@gmail.com> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_6742_2027325697.1412263547681" X-Trace: ger.gmane.org 1412263556 20573 80.91.229.3 (2 Oct 2014 15:25:56 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 2 Oct 2014 15:25:56 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDELF54RTIGRB7G4WWQQKGQEX36MKYY@isocpp.org Thu Oct 02 17:25:50 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ob0-f198.google.com ([209.85.214.198]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XZiGL-0001sj-Tm for gclcip-std-proposals@m.gmane.org; Thu, 02 Oct 2014 17:25:50 +0200 Original-Received: by mail-ob0-f198.google.com with SMTP id wp4sf11356167obc.9 for ; Thu, 02 Oct 2014 08:25:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to: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=pmDKv5EWVhLzNungRmCnS8wU05x0pjeKW5xj5qs/Tfg=; b=AaAK8YjF1y3EbpWTzSt2jseYEf+P67Tndp/1U5BhS3oT2SzoLiShfxkKljmRDJ3III KNgomWfFI3rJSx/tqhvmQiVU6Nu3+YnfPccpaKyrM/+pPKBYnXpblsz8e00cHsa2Keka njmu4Z9IidhnxEZzLFhgP1OmOYoVedaUL2wEEOe2dqMZt5AGIc1UVwO+9J08yDmA99H7 M1y7E+GtDN4iSMntHu2iYqvFVKS/x932AH3aExBLpGNlcEu4/6OJ4SetWVqMeE4ALb+z /vMJhOrJEjCXXZAVG27hF5AYmrjT1K86euDiA7qzUqK+X+ejkaUUKAwNH5cZwZfa/HNy L4PA== 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: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=pmDKv5EWVhLzNungRmCnS8wU05x0pjeKW5xj5qs/Tfg=; b=gXvKJSkGXCyirqoTR9PS7ASd12A6qJkaiJupa2TWeEXiiq6RKzSlk50vfzloK8KyB1 Wf0oRxoMhb5XKN0S70nGA4XF3y/hRzl7ilOa6FRgsnkjUWrBHBSF5ako6iA6G81Ojhqj qN4aq24X+dxSudFuYQxYfn30UuaQgaI0P+MDgGDwphGt7B0n2Ne0hlAH4mpi7LhiCdqv rJ2iNJN85hMD2ndGiPvRmydCJW0fIwFVkl5to6/ttBjUHNC8dfxwgj//dmsAYNyf665X EFE/WXxb17jxGC0y5AIJWDauziSxirMKo8/6niIXZ6gAAtpw4Pnsn0j1OD51U31wYqj2 UIxg== X-Gm-Message-State: ALoCoQnmh5E/s+l1RKkQ0E/HIIyTAy2Nk7xKyvxW58FXQfKrvO/xCMd3InWC5/5LmLbjMZ4UXt6v X-Received: by 10.50.9.97 with SMTP id y1mr2819559iga.0.1412263548977; Thu, 02 Oct 2014 08:25:48 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.104.180 with SMTP id a49ls855541qgf.90.gmail; Thu, 02 Oct 2014 08:25:48 -0700 (PDT) X-Received: by 10.140.40.85 with SMTP id w79mr2757qgw.38.1412263548182; Thu, 02 Oct 2014 08:25:48 -0700 (PDT) In-Reply-To: <9462C54C-E91B-4B66-AA8E-CAEA1F190FE6@gmail.com> X-Original-Sender: fmatthew5876@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:13538 Archived-At: ------=_Part_6742_2027325697.1412263547681 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Thursday, October 2, 2014 9:59:32 AM UTC-4, Nicola Gigante wrote: > > > Il giorno 02/ott/2014, alle ore 15:38, Matthew Fioravante < > fmatth...@gmail.com > ha scritto: > > > > On Thursday, October 2, 2014 3:51:38 AM UTC-4, Nicola Gigante wrote: >> >> > It depends on how bitset_view is implemented. If its implemented on top o= f=20 > array_view (which I would recommend), this is a non-starter because the= =20 > object would contain 2 extra pointers. Defeating the entire purpose of my= =20 > current proposal. > > > My idea would be not to base the class on something specific (array_view= =20 > or something else), but to have the class to be wrapped > as a template parameter and include an object of such a class inside it. > > I=E2=80=99ve implemented once something related for a data structure we= =E2=80=99re=20 > developing at my university: > > https://github.com/nicola-gigante/bitvector/blob/master/include/bitview.h= =20 > > This kind of approach is very difficult to do generically. The devil is in= =20 the details. For one, you're assuming the underlying container has a single argument=20 constructor which takes an integral size. This works for std::vector but=20 not for std::array, a C array, or an array_view which already have an=20 implicit size and don't need any constructor arguments. You've got to=20 somehow detect and handle both concepts correctly. This also doesn't really support the full dynamic_bitset semantics. For=20 instance you cannot resize or push_back() into the underlying container if= =20 it is a dynamic one like a vector. Your bitview only models a fixed size=20 collection of bits. Again you've got to determine whether or not your=20 container can be resized and support this behavior if so. In order to do this kind of generic thing effectively you need to define=20 some concepts such as "fixed size buffer" (array_view) and "dynamically=20 growing buffer" (vector). Its better to modularize and outsource those=20 concepts to more pure interfaces designed only for them such as array_view= =20 and dynamic_array_view. The array_view handles all of the logic related to= =20 a fixed size buffer. Then built on top of that foundation, your bitset_view= =20 only needs to worry about manipulating the bits of that buffer. By=20 leveraging array_view, bitset_view works on any imaginable kind of fixed=20 size buffer for free. Its a better separation and encapsulation. Once you have those concepts, its better to make different bitview types=20 over them. If I have a bitset_view and a dynamic_bitset_view I know=20 immediately what to expect and don't have to know or care what the=20 underlying representation is. If I have a bitview, bitview,= =20 bitview, I don't know what the semanics of the=20 bitview is until I look at the underlying container. It also requires more= =20 template parameters to be passed around. I can pass a bitset_view to a=20 normal function. If I'm passing around a bitview, I have to use=20 templates everywhere. Now finally, you mentioned that one benefit of your approach is that=20 std::bitset and std::dynamic_bitset could just be implemented trivially=20 using the bitview. This is actually not a concern for us we generally don't= =20 care how things are implemented, as long as they fit the specification=20 efficiently. We hate our implementers and don't care how much work we=20 create for them ;). There's only 1 way to really do a fixed size bitset and that's just create= =20 an array and operate on the bits. We don't really need configurability=20 there. For a dynamic bitset, you could argue there are multiple=20 possibilities, just as there are many ways to implement the equivalent of= =20 std::vector. Or maybe someone wants dequeue or something else crazy. We=20 aren't talking about dynamic_bitset yet so I don't yet want to go there. I hope that made sense. Things get fuzzier when we go outside of bits and= =20 bytes and start talking design philosophies. --=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_6742_2027325697.1412263547681 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable


On Thursday, October 2, 2014 9:59:32 AM UTC-4, Nic= ola Gigante wrote:

Il giorno 02/ott/2014, alle ore 15:= 38, Matthew Fioravante <fmatth...@g= mail.com> ha scritto:



On Thursday, October 2, 2014 3:51:38 AM UTC-4, Nicola Gigante= wrote:

It depends on how bitset_view is implem= ented. If its implemented on top of array_view (which I would recommend), t= his is a non-starter because the object would contain 2 extra pointers. Def= eating the entire purpose of my current proposal.

My idea would be not to base the class on something = specific (array_view or something else), but to have the class to be wrappe= d
as a template parameter and include an object of such a class i= nside it.

I=E2=80=99ve implemented once something = related for a data structure we=E2=80=99re developing at my university:

This kind of approach is very difficult to do generically. The devil is i= n the details.

For one, you're assuming the underlying container has= a single argument constructor which takes an integral size. This works for= std::vector but not for std::array, a C array, or an array_view which alre= ady have an implicit size and don't need any constructor arguments. You've = got to somehow detect and handle both concepts correctly.

This also = doesn't really support the full dynamic_bitset semantics. For instance you = cannot resize or push_back() into the underlying container if it is a dynam= ic one like a vector. Your bitview only models a fixed size collection of b= its. Again you've got to determine whether or not your container can be res= ized and support this behavior if so.

In order to do this kind of ge= neric thing effectively you need to define some concepts such as "fixed siz= e buffer" (array_view) and "dynamically growing buffer" (vector). Its bette= r to modularize and outsource those concepts to more pure interfaces design= ed only for them such as array_view and dynamic_array_view. The array_view = handles all of the logic related to a fixed size buffer. Then built on top = of that foundation, your bitset_view only needs to worry about manipulating= the bits of that buffer. By leveraging array_view, bitset_view works on an= y imaginable kind of fixed size buffer for free. Its a better separation an= d encapsulation.

Once you have those concepts, its better to make di= fferent bitview types over them. If I have a bitset_view and a dynamic_bits= et_view I know immediately what to expect and don't have to know or care wh= at the underlying representation is. If I have a bitview<array>, bitv= iew<vector>, bitview<my_custom_array_class>, I don't know what = the semanics of the bitview is until I look at the underlying container. It= also requires more template parameters to be passed around. I can pass a b= itset_view to a normal function. If I'm passing around a bitview<T>, = I have to use templates everywhere.

Now finally, you mentioned that = one benefit of your approach is that std::bitset and std::dynamic_bitset co= uld just be implemented trivially using the bitview. This is actually not a= concern for us we generally don't care how things are implemented, as long= as they fit the specification efficiently. We hate our implementers and do= n't care how much work we create for them ;).

There's only 1 way to = really do a fixed size bitset and that's just create an array and operate o= n the bits. We don't really need configurability there. For a dynamic bitse= t, you could argue there are multiple possibilities, just as there are many= ways to implement the equivalent of std::vector. Or maybe someone wants de= queue or something else crazy. We aren't talking about dynamic_bitset yet s= o I don't yet want to go there.

I hope that made sense. Things get f= uzzier when we go outside of bits and bytes and start talking design philos= ophies.

--

---
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_6742_2027325697.1412263547681-- .