Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Comparing two vectors of bools

Reply
Thread Tools

Comparing two vectors of bools

 
 
James Kanze
Guest
Posts: n/a
 
      08-02-2008
On Aug 2, 12:13 pm, "Bo Persson" <(E-Mail Removed)> wrote:
> Juha Nieminen wrote:
> > Rafal wrote:
> >> (E-Mail Removed) wrote:


> >>> I know that std::vector<bool> is specialized to store individual
> >>> bools as single bits.


> >> Actually this is considered a bit of "hack" and AFAIR it will be
> >> removed soon (in C++0x?).


> > Exactly how is it a "hack" and why should it be removed? Has a
> > better alternative been suggested?


> It's strange because it is the only container that does not
> store elements of the contained type.


But it does. At least as far as client code can tell. And
bitset is in a similar situation. It's strange because it's
called std::vector<bool>, but it doesn't conform to the
documented contract of std::vector.

> It also uses a proxy class for vector<bool>::reference, which
> is not allowed by the standard for any other container.


Again: bitset.

The problem isn't that it's there. The problem is that it is
called std::vector< bool >, and not something else. (Or
alternatively, the problem is that the contract for std::vector
is too constraining. You can argue it both ways. But if you
take this second approach, you're going to have to change some
of the basic principles of the STL.)

> The real hack is that the standard assumes that everyone
> benefits from a space optimization for vector<bool> and speed
> optimizations for vector<everything_else>. Why?


In many cases, the space optimization may also be a speed
optimization (because of reduced cache misses). The difference
is that this optimization only applies to vector<bool>, and that
it isn't transparent, and that there's no way of making it
transparent, given the design of the STL and the integration of
std::vector into the STL.

> It hasn't been removed so far, and as its section has actually
> been edited in the latest draft for the next standard, it is
> unlikely to go away anytime soon. We have also seen that other
> containers, like std::string and std::array, are allowed to
> somewhat deviate from the general container requirements, so
> why not?


Because the name std::vector gives, or should give, certain
guarantees. std::bitset has a different name, and you don't
expect it to define the same contract as std::vector, so there's
no problem with it, and there'd be no problem with an
std::dynamic_bitset, either.

> > I certainly would like to have some kind of bool data
> > container where each bool indeed takes only one bit, to save
> > memory.


> Always, or sometimes?


Well, if it's not in a container, a normal bool is fine.

My own experience is that I've never needed a vector of bool
(with the interface of vector, or something similar), but if I
did, I'd want it to behave like vector. My own experience is
that I often need something like bitset (with the interface of
bitset), but with dynamic length. Except that there is a lot
more functionality which is useful: isSubsetOf( other ), etc.;
bitset doesn't seem to be able to make up its mind what it
really is either. The result is that I still use (and actively
maintain) my pre-standard implementations, even today.

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
 
 
 
Bo Persson
Guest
Posts: n/a
 
      08-03-2008
James Kanze wrote:
> On Aug 2, 12:13 pm, "Bo Persson" <(E-Mail Removed)> wrote:
>> Juha Nieminen wrote:
>>> Rafal wrote:
>>>> (E-Mail Removed) wrote:

>
>>>>> I know that std::vector<bool> is specialized to store individual
>>>>> bools as single bits.

>
>>>> Actually this is considered a bit of "hack" and AFAIR it will be
>>>> removed soon (in C++0x?).

>
>>> Exactly how is it a "hack" and why should it be removed? Has a
>>> better alternative been suggested?

>
>> It's strange because it is the only container that does not
>> store elements of the contained type.

>
> But it does. At least as far as client code can tell. And
> bitset is in a similar situation. It's strange because it's
> called std::vector<bool>, but it doesn't conform to the
> documented contract of std::vector.
>
>> It also uses a proxy class for vector<bool>::reference, which
>> is not allowed by the standard for any other container.

>
> Again: bitset.


Yes, I forgot about that one.

It claims to be an associative container, but doesn't have the
required interface.

I should have written that the general container requirements (section
23.1) doesn't allow for this (reference as a proxy). On the other hand
it is still required in some places...

>
> The problem isn't that it's there. The problem is that it is
> called std::vector< bool >, and not something else. (Or
> alternatively, the problem is that the contract for std::vector
> is too constraining. You can argue it both ways. But if you
> take this second approach, you're going to have to change some
> of the basic principles of the STL.)


The contract is cracking up anyway, as the revisions for the next
standard introduces new containers and new requirements that just
don't go well together.

Just like bitset is (supposedly) an associative container with a fixed
size (and therefore has a non-conforming different interface), C++0x
introduces a std::array as a fixed size sequence container which
cannot implement insert and erase, for example. We also have
basic_string claiming to be a sequence container, but falling short.

In comparison, vector<bool> seems like a minor problem. .-)


Bo Persson



 
Reply With Quote
 
 
 
 
Juha Nieminen
Guest
Posts: n/a
 
      08-03-2008
Rafał wrote:
> Juha Nieminen wrote:
>
>> Exactly how is it a "hack" and why should it be removed?

>
> This container do not act like a container, it has other semantics.
> For example, taking address of N-th element will not work.


Ok, that's *one* example. You write as if there were numerous. Any
other examples of std::vector<bool> not behaving like other types of
std::vector?

(One could argue that not being able to get a pointer to a bool value
inside the vector is not such a big of a loss...)
 
Reply With Quote
 
Erik Wikström
Guest
Posts: n/a
 
      08-03-2008
On 2008-08-03 12:37, Juha Nieminen wrote:
> Rafał wrote:
>> Juha Nieminen wrote:
>>
>>> Exactly how is it a "hack" and why should it be removed?

>>
>> This container do not act like a container, it has other semantics.
>> For example, taking address of N-th element will not work.

>
> Ok, that's *one* example. You write as if there were numerous. Any
> other examples of std::vector<bool> not behaving like other types of
> std::vector?
>
> (One could argue that not being able to get a pointer to a bool value
> inside the vector is not such a big of a loss...)


The loss is quite small until you try to use vector<bool> just like any
other vector in one of your nice parametrised libraries and stuff no
longer works and you are forced to rewrite half the library just to get
it working with vector<bool>.

--
Erik Wikström
 
Reply With Quote
 
Rafał
Guest
Posts: n/a
 
      08-03-2008
Juha Nieminen wrote:

> Ok, that's *one* example. You write as if there were numerous. Any
> other examples of std::vector<bool> not behaving like other types of
> std::vector?
>
> (One could argue that not being able to get a pointer to a bool value
> inside the vector is not such a big of a loss...)


Well, vector claims to allow to do T& x = &V.at(n); yet it brakes that
promise.

This is not USA government, but an official standardized language, so I
would expect it to keep such "promises".

It's unfortunate that some programs do rely on this behavior, and now it
will not be change therefore.

IMHO they should right away start with some vector_packed class.




 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      08-03-2008
On Aug 3, 12:27 pm, "Bo Persson" <(E-Mail Removed)> wrote:
> James Kanze wrote:
> > On Aug 2, 12:13 pm, "Bo Persson" <(E-Mail Removed)> wrote:
> >> It also uses a proxy class for vector<bool>::reference,
> >> which is not allowed by the standard for any other
> >> container.


> > Again: bitset.


> Yes, I forgot about that one.


> It claims to be an associative container, but doesn't have the
> required interface.


And shouldn't have. Basically, the requirements for containers
don't really mean anything; it doesn't start becoming serious
until you consider the requirements for sequence.

[...]
> The contract is cracking up anyway, as the revisions for the
> next standard introduces new containers and new requirements
> that just don't go well together.


The problem is that the original specifications aren't really
well designed. They work (more or less) for the containers that
were present in the original standard (with the exception of
bitset), but they aren't nearly flexible enough to cover all, or
even most, of the useful cases.

> Just like bitset is (supposedly) an associative container with
> a fixed size (and therefore has a non-conforming different
> interface), C++0x introduces a std::array as a fixed size
> sequence container which cannot implement insert and erase,
> for example. We also have basic_string claiming to be a
> sequence container, but falling short.


basic_string should be fixed so that it is a sequence.
Otherwise, however, I don't see anything wrong with introducing
containers which aren't sequences, and it seems obvious (to me,
anyways) that the basic concepts need working on: ) there should
be a distinction in the notion of mutable---you need containers
whose values can be modified, but whose topology is fixed (like
tr1::array), for example, and there are more than a few problems
with the iterators: why, for example, should an iterator into a
non-mutable sequence still require operator* to return a
reference, rather than a value? Or for that matter, why not
rework the concepts to allow proxies in general?

> In comparison, vector<bool> seems like a minor problem. .-)


The problem isn't that it exists. The problem is that it is an
std::vector, and not something else.

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Style guidance with checking bools Angus C++ 20 06-26-2009 11:20 AM
Comparing the values of two vectors utab C++ 6 04-07-2006 09:48 AM
Linker error LNK2001 with bools Mike C++ 3 10-12-2004 11:46 AM
An array of bools ccs C++ 5 06-13-2004 03:05 AM
Python style of accessing bools? Jonathon McKitrick Python 3 04-15-2004 02:15 PM



Advertisments