On Fri, 19 Jan 2007 17:34:42 GMT, Gennaro Prota wrote:

>I have rewritten most of boost::dynamic_bitset but haven't changed its
>design (there have been some changes which broke backwards
>compatibility, e.g. in the stream extractor, and most of the
>implementation has changed, but the original design is there, and
>clearly visible). When I began working on it, mimicking std::bitset<>
>looked like a good idea. Over time however I've realized that we just
>inherited a schizophrenic design from a class template which attempts
>to do something of at least two different abstractions (bit sequence
>and mathematical set), without being complete for either of them. Not
>to talk about string conversions, and lack of iterators (think of the
>new categories). As I said, I'll try posting more details in the next
>week.

Sorry for the late reply; hopefully these notes will repay your wait
:-)

I had a comprehensive summary of changes planned for a new
bit_sequence facility, but it is among my old Yahoo account mails,
which I can't access. Anyhow, off the top of my head, this is a list
of fixes/issues I consider very important:

* exception safety guarantees: I don't think I have to explain why we
need these :-)

* rules for invalidation of references: they were not documented in
boost::dynamic_bitset; I'm oriented towards the guarantees of
std::deque... in any case this requires some coordination with the new
iterator categories proposal

* again about references, I've never liked the idea that
const_reference=3Dbool; and I was experimenting with making operator&
applied to a reference return an iterator (quite a new idea in the
context of standard containers, though, so I guess low hope to be
adopted)

* removing (i.e. not introducing :-)) the clumsy from/to string
conversions: those are design errors in std::bitset<> that we should
finally get rid of. Summarizing some excellent points raised by James
Kanze long ago:

 If one needs a "textual" representation of the data stored in
 a bitset object there are the stream operators, which are the
 standard C++ convention for formatting data. By using << and >>
 you have a neat separation of concerns between the class that
 stores the data (dynamic_bitset, bit_sequence, whatever) and
 the one that stores their textual representation (basic_string),
 a generic name, operator>> or operator <<, for the free function
 that connects them (which is important for template programming)
 and none of the two classes encumbered with knowledge of the other.
 Also, you can easily deal with locale-related issues.

Note that lexical_cast has also been proposed for TR2. FWIW, I'm using
an analogous facility I called textual_cast for long time, and I don't
have string conversions in none of my classes and class templates. It
works for me very well.

* to_ulong (or to_ulonglong or...) shouldn't enforce "preconditions"
via exceptions

* other, perhaps minor, point you might find about by googling old
group discussions for "dynamic_bitset" (there was something related to
lib issue 434, for instance)


This is a summary from a follow-up to N2050 I was working on; last
rev. date is August 10, 2006.

                           Abstract

This paper proposes two new libraries concerned with manipulation of
bit sequences and mathematical sets. The goal is to improve language
library support in two notably lacking areas, and remove a
long-standing embarrassment about vector<bool>.

The suggestions in this proposal build on previous work and experience
=97in particular on boost::dynamic_bitset, a stable and largely used
facility of the Boost library collection.

                          Motivation

Bit manipulation is a recurring task in system and application
programming, for a variety of problem domains: representation of sets
and their operations or relations (union, difference, intersection,
complement, inclusion), graph algorithms, cyclic redundancy checksums,
big integer arithmetic, look-ahead character calculation in parsers
and compilers, and many others.

On the basis of the abstraction being involved we identify three big
areas:
 1. mathematical sets
 2. =93bit arrays=94 or generally bit sequences
 3. big integers

The standard currently offers two libraries related to bit
manipulation, namely std::bitset<> and std::vector<bool>.
Unfortunately, the former is not suitable for bit structures whose
size can change dynamically. The latter does not meet requirements for
being a standard container, and the committee has already expressed a
desire to deprecate it in favor of a cleaner solution.
[N2050] proposes a class template closely modeled after
boost::dynamic_bitset, which partially covers needs 1. and 2. This
partial coverage comes in fact from std::bitset, on which
dynamic_bitset is in turn based. The Boost experience however has
highlighted that this =93dual=94 design has no practical benefit and
effectively confuses users: in short it does not separate concerns,
and doesn't cover either of 1. and 2. in depth. It is worth noticing
that [N0220 =96 Allison, 1993] was already clear on recognizing this
limitation: "Neither of these classes [bits<>, later become
std::bitset<>, and bitstring, not standardized] attempts to provide
complete semantics for mathematical sets, but member functions exist
that provide the equivalent of union, intersection, and symmetric
difference as well as insert, remove and test for membership."=20
What we propose here is two distinct templates for needs (1) and (2).
A separate proposal will likely be submitted for big integers (3).

--
Genny.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"Gennaro Prota"  wrote

>The standard currently offers two libraries related to bit
>manipulation, namely std::bitset<> and std::vector<bool>.
>Unfortunately, the former is not suitable for bit structures whose
>size can change dynamically. The latter does not meet requirements for
>being a standard container, and the committee has already expressed a
>desire to deprecate it in favor of a cleaner solution.

If I understand N2160 correctly, only the vector<bool> specialization will
be deprecated, but vector<bool> itself will still exist as a "normal"
container of bools, taking one sizeof(bool) per bool. So when a user wants a
normal container of bools, he can still choose vector<bool>. In my opinion
the dynamic bitset however is not a container at all, neither is bitset.

>[N2050] proposes a class template closely modeled after
>boost::dynamic_bitset, which partially covers needs 1. and 2. This
>partial coverage comes in fact from std::bitset, on which
>dynamic_bitset is in turn based. The Boost experience however has
>highlighted that this "dual" design has no practical benefit and
>effectively confuses users: in short it does not separate concerns,
>and doesn't cover either of 1. and 2. in depth. It is worth noticing
>that [N0220 - Allison, 1993] was already clear on recognizing this
>limitation: "Neither of these classes [bits<>, later become
>std::bitset<>, and bitstring, not standardized] attempts to provide
>complete semantics for mathematical sets, but member functions exist
>that provide the equivalent of union, intersection, and symmetric
>difference as well as insert, remove and test for membership."
>What we propose here is two distinct templates for needs (1) and (2).
>A separate proposal will likely be submitted for big integers (3).

In my opinion the infinite precision integer is neither a container nor a
dynamic bitset, see N2143. However a dynamic bitset can be defined re-using
the infinite precision integer, but perhaps we should call that an
integer_bitset, existing next to the dynamic_bitset.
Regards, Maarten.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Fri,  9 Feb 2007 18:52:25 GMT, "Maarten Kronenburg" wrote:

>If I understand N2160 correctly, only the vector<bool> specialization will
>be deprecated, but vector<bool> itself will still exist as a "normal"
>container of bools, taking one sizeof(bool) per bool. So when a user wants a
>normal container of bools, he can still choose vector<bool>. In my opinion
>the dynamic bitset however is not a container at all, neither is bitset.

Yes, none of them is a container. Lack of iterators is the main reason
why I said dynamic_bitset is an experiment that failed: as soon as you
begin to use it in real applications you need lot of algorithms which
are in the standard library, but can't be applied to dynamic_bitset
(find_first/find_next are probably the most often required, which is
why I introduced them, but where do you stop? And how do you allow
user-defined algorithms...)

>In my opinion the infinite precision integer is neither a container nor a
>dynamic bitset, see N2143. However a dynamic bitset can be defined re-using
>the infinite precision integer, but perhaps we should call that an
>integer_bitset, existing next to the dynamic_bitset.

I'm not familiar with the infinite precision integer proposal, so I
can't comment on that. What I had in mind was to refine an interface
for a "bit sequence" which a) exposed iterators (of the new
categories) b) was implementable in terms of deque< bool >. But I
never went beyond the mere intent.

Another area I wanted to experiment more on is the one I hint at in
the final part of this post (special formatting):

  <http://preview.tinyurl.com/35vwlc>

Cheers,
Genny.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

In article <j4hps2h1avad3hb6bm88ud80f2e25ku6kq@4ax.com>, Gennaro Prota
<gennaro.prota@yahoo.com> wrote:

> On Fri,  9 Feb 2007 18:52:25 GMT, "Maarten Kronenburg" wrote:
>
> >If I understand N2160 correctly, only the vector<bool> specialization will
> >be deprecated, but vector<bool> itself will still exist as a "normal"
> >container of bools, taking one sizeof(bool) per bool. So when a user wants a
> >normal container of bools, he can still choose vector<bool>. In my opinion
> >the dynamic bitset however is not a container at all, neither is bitset.
>
> Yes, none of them is a container. Lack of iterators is the main reason
> why I said dynamic_bitset is an experiment that failed: as soon as you
> begin to use it in real applications you need lot of algorithms which
> are in the standard library, but can't be applied to dynamic_bitset
> (find_first/find_next are probably the most often required, which is
> why I introduced them, but where do you stop? And how do you allow
> user-defined algorithms...)
>
   Perhaps what needs experimenting is a finer division of iterator
categeries:)   Using a finer grained iterator category the iterators
for
vector<bool>, bitset<N>, dynamic_bitset, [assuming the interface is
same as bitset<N> but the size is determined at construction , not
compile time], can be written with a proxy to read/write via operator
*(). [not legal currently for forward or 'better' iterators...].

I see the problem with forward or better iterators disallowing a
different read and write operation via operator *() that is x = *i
and *i = x must generate the same code for *i. while an input iterator,
that is also an output iterator can differentiate between *i=x, and x =
*i, via a proxy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Sat, 10 Feb 2007 02:51:29 GMT, Carl Barron wrote:

>   Perhaps what needs experimenting is a finer division of iterator
>categeries:)   Using a finer grained iterator category the iterators
>for vector<bool>, bitset<N>, dynamic_bitset, [assuming the interface is
>same as bitset<N> but the size is determined at construction , not
>compile time], can be written with a proxy to read/write via operator
>*(). [not legal currently for forward or 'better' iterators...].

Hmm, I'm not sure I understand (er, let's face it: I'm almost sure I
do not understand :-))... are you thinking to a different
categorization than the one originally proposed by Jeremy Siek?

  <http://www.boost.org/libs/iterator/doc/new-iter-concepts.html>

Genny.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

I strongly welcome the newly proposed dynamic_bitset, but would like
to discuss some notable differences with the current class template
bitset or other deviations from other parts of the library
specifications:

1) The proposal should use template parameter names according to
existing std naming convention, i.e. charT instead of CharT, traits
instead of Traits (even if these sometimes demonstrate annoying
case-inconsistencies ;-).

2) Existing throws clauses only mention std::bad_alloc and
std::overflow_error. In constrast to this, std::bitset also throws
std::out_of_range and std::invalid_argument under specified
circumstances (e.g. during construction from string or using the
set() function). Is this change in behaviour by design or an
oversight?
If it is by design, it would be better, to mention this difference in
the introductory parts, e.g. in the chapters "1 Introduction" or
"2 Constructing dynamic_bitsets using strings". My personal
tendency is to favour exceptions at least for the string-related
c'tors and operations, which matches the behaviour of
std::basic_string itself.

3) There exist good chances, that std::bitset::bitset(unsigned long)
will be confused with std::dynamic_bitset::dynamic_bitset(size_type,
unsigned long long = 0, const Allocator& = Allocator())
- regrettably with a very different meaning. Also note that due to
this inconsistency the first example on page 12 is wrong, which
says, that:

"dynamic_bitset(string("11011100")) is the same as
dynamic_bitset(220ul)"

which should be changed to

"dynamic_bitset(string("11011100")) is the same as dynamic_bitset(8,
220ull)"

or to the simpler

"dynamic_bitset(string("11011100")) is the same as dynamic_bitset(8,
220)"

I'm aware that due to the existence of this c'tor the equivalent
bitset::bitset() and bitset::bitset(unsigned long) are produced,
but with the mentioned disadvantage. What do others think about
this issue?

4) Member function get_allocator() has a throws clause, which is
unique for the whole C++ standard. I recommend to follow a uniform
specification strategy (My proposal: Remove this throws clause).
On the other hand operator=(const dynamic_bitset&) explicitely says
that it will throw nothing, which is most probably an error.

5) Operator<<(std::basic_ostream<charT, traits>& os,
const dynamic_bitset<Block, Allocator>& x) says:

"Throws: std::ios_base::failure if there is a problem writing to the
stream."

which contradicts the usual wording and behaviour of inserters. I
recommend to remove this clause, because the effects clause
already characterizes any throw behaviour indirectly via delegation
to the string insertion.
For similar reasons the throws clause of the corresponding extractor
should be removed. Another point is the no-throw guarantee specified
by operator<<(std::basic_ostream<charT, traits>& os,
const set_bit_order&), which looks very suspicious to me - typical
implementations might have difficulties to fulfill that. IIRC, no other

std manipulator does say such strong words. It seems more
reasonable to remove the throws clause and to guarantee no more
than usual inserters do (as specified by 27.6.2.5.1 Common
requirements).

6) Member function to_ulonglong() described on page 19 should
return "unsigned long long" instead of the current "unsigned long".

7) The first example on page is written as:

"If *this == dynamic_bitset(string("11101101"),false)and x ==
dynamic_bitset(string("101111011010"),false) then,[...]"

I assume, the boolean value false has to be replaced by lsb_first
at both positions.

8) It is unclear which template arguments are valid for the parameter
StringT in to_string() are legal, because the effects clause does
not specify any equivalent code. Is the assignment pattern
specified? Has StringT to be an instance of std::basic_string?

Finally the question: Is it ok, to discuss such items in the public?
Mostly I have *only* contacted authors of such papers personally,
so I would like to ask if others consider that as the more polite
approach? I'm totally aware how much personal commitment is
involved in writing such papers and that it's very much easier to
point on some tiny errors than to write a better one.

Greetings from Bremen,

Daniel Kr   gler


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Thu, 18 Jan 2007 15:09:27 CST, Daniel Kr   gler wrote:

>I strongly welcome the newly proposed dynamic_bitset,

I don't. I consider boost::dynamic_bitset an experiment that failed
(and as such useful) and was slowly working on a different proposal,
but without too much motivation :-( I don't have time right now but if
there's interest I could try posting something about it next week.

Genny.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

"Gennaro Prota"  wrote
> On Thu, 18 Jan 2007 15:09:27 CST, Daniel Kr=FCgler wrote:
>
> >I strongly welcome the newly proposed dynamic_bitset,
>
> I don't. I consider boost::dynamic_bitset an experiment that failed
> (and as such useful) and was slowly working on a different proposal,
> but without too much motivation :-( I don't have time right now but if
> there's interest I could try posting something about it next week.
>

There is another possible option: once the infinite precision integer (se=
e
N2143) would be accepted, the dynamic_bitset class could be defined with
data members an integer and a bit size. The integer bit access member
functions get_bit and set_bit would be reused in the dynamic_bitset bit
access member functions, but with adding bounds checking. Appending two
bitsets would be adding the bit sizes and shifting/or-ing the integers. T=
he
proxy class reference would be copied as the proxy to bool. But such a cl=
ass
would not be a container, and would not have the block and allocator
template parameters. But neither has bitset.
Regards, Maarten.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:
> On Thu, 18 Jan 2007 15:09:27 CST, Daniel Kr   gler wrote:
>
> >I strongly welcome the newly proposed dynamic_bitset,
>
> I don't. I consider boost::dynamic_bitset an experiment that failed
> (and as such useful) and was slowly working on a different proposal,
> but without too much motivation :-(

Ooops, these are harsh words from one of the authors himself!
I hope they where not caused by my comments to N2050?  ;-)

>I don't have time right now but if
> there's interest I could try posting something about it next week.

Yes, I'm strongly interested to hear about the reasonings of that
failed experiment. From my point of view, I see no such failure.
Especially in the context of the comment "We now have: N2050"
at the end of the active, open issue

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#96

the dynamic_bitset proposal looks promising to me. So what
does that failure (if it really is one) imply for the chances of a
replacement of std::vector<bool>?

Greetings,

Daniel


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Fri, 19 Jan 2007 09:58:10 CST, Daniel Kr=FCgler wrote:

>Gennaro Prota wrote:
>> On Thu, 18 Jan 2007 15:09:27 CST, Daniel Kr=FCgler wrote:
>>
>> >I strongly welcome the newly proposed dynamic_bitset,
>>
>> I don't. I consider boost::dynamic_bitset an experiment that failed
>> (and as such useful) and was slowly working on a different proposal,
>> but without too much motivation :-(
>
>Ooops, these are harsh words from one of the authors himself!
>I hope they where not caused by my comments to N2050?  ;-)

No no :-) To date I haven't received any committee comment about the
proposal. But I hadn't aroused lively interest on the boost list
either, which might have been the real cause: what would you do after
posting several messages like this with no meaningful reply?

  <http://aspn.activestate.com/ASPN/Mail/Message/2049405>

But, of course, if there's no interest there's no interest. Nothing we
can do about that :-)

Note that I'm not an author of the paper. I was informed of its
existence the same day it was submitted. As a courtesy, my address was
added to the reply-to section.

I have rewritten most of boost::dynamic_bitset but haven't changed its
design (there have been some changes which broke backwards
compatibility, e.g. in the stream extractor, and most of the
implementation has changed, but the original design is there, and
clearly visible). When I began working on it, mimicking std::bitset<>
looked like a good idea. Over time however I've realized that we just
inherited a schizophrenic design from a class template which attempts
to do something of at least two different abstractions (bit sequence
and mathematical set), without being complete for either of them. Not
to talk about string conversions, and lack of iterators (think of the
new categories). As I said, I'll try posting more details in the next
week.

Genny.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Fri, 19 Jan 2007 09:58:10 CST, Daniel Kr=FCgler wrote:

>Gennaro Prota wrote:
>> On Thu, 18 Jan 2007 15:09:27 CST, Daniel Kr=FCgler wrote:
>>
>> >I strongly welcome the newly proposed dynamic_bitset,
>>
>> I don't. I consider boost::dynamic_bitset an experiment that failed
>> (and as such useful) and was slowly working on a different proposal,
>> but without too much motivation :-(
>
>Ooops, these are harsh words from one of the authors himself!
>I hope they where not caused by my comments to N2050?  ;-)

Ah, sorry: I had missed the word "my" in your last sentence, so I
interpreted it as "I hope they where not caused by [committee]
comments to N2050" (hence what I say in my other reply). No, I'm not
bothered at all by your comments. On the contrary you seem to have
reviewed everything with care and interest. Thanks for that :-)

Genny.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]