«

I know that std::vector<bool> is specialized to store individual bools
as single bits. I have a question about the comparison operation on a
pair of vector<bool>s.

Is the comparison done bit by bit? That would be slow. In theory it's
possible to just do a bit-wise XOR on all bits and then OR it all
together and compare the single bit right? That would make it O(1)
instead of O(n). What's bad about this method?

Does the size of the vector matter here? For instance if the vectors
are <= 32bits they can fit into two registers and it's easy to do the
XOR. But if they are more than that then it's more complicated

What about comparison on std::bitset? Does compare work the same way
for it?

And what about boost::dynamic_bitset? Any difference for that?

Thanks.

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?).

On Aug 1, 10:00*pm, Sam <s...@email-scan.com> wrote:
> fgh.vbn....@gmail.com writes:
> > I know that std::vector<bool> is specialized to store individual bools
> > as single bits. I have a question about the comparison operation on a
> > pair of vector<bool>s.
>
> > Is the comparison done bit by bit? That would be slow. In theory it's
> > possible to just do a bit-wise XOR on all bits and then OR it all
> > together and compare the single bit right? That would make it O(1)
> > instead of O(n). What's bad about this method?
>
> No, it wouldn't be O(1). It's still O(n). This would be faster, of course,
> but the complexity is still linear, since the number of XOR operations is
> linearly proportional to the vector's size.
>

Hmm, if we have a 32-bit ALU then we could load both vectors into a
pair of registers and use the comparator to get the result in "one
cycle" right? In other words, we are doing all XORs in parallel
followed by one OR. Please correct me if I'm wrong here.

Of course, I have no idea if the compiler would actually do this.

Thanks.

In article <g70loa$4tb$>, lid
says...
> 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?).

I doubt it. The current draft (N2691) still includes it, with minor
changes from C++ 03. It now explicitly recommends: "a space optimized
representation of bits...", whereas C++ 03 merely described the class as
being provided: "To optimize space allocation..."

--
Later,
Jerry.

The universe is a figment of its own imagination.

On Aug 2, 6:51 am, fgh.vbn....@gmail.com wrote:
> On Aug 1, 10:00 pm, Sam <s...@email-scan.com> wrote:

> > fgh.vbn....@gmail.com writes:
> > > I know that std::vector<bool> is specialized to store
> > > individual bools as single bits. I have a question about
> > > the comparison operation on a pair of vector<bool>s.

> > > Is the comparison done bit by bit? That would be slow. In
> > > theory it's possible to just do a bit-wise XOR on all bits
> > > and then OR it all together and compare the single bit
> > > right? That would make it O(1) instead of O(n). What's bad
> > > about this method?

The library is free to implement the function however it wants.
From a QoI point of view, of course, it would be a very poor
library that does the comparison bit by bit.

> > No, it wouldn't be O(1). It's still O(n). This would be
> > faster, of course, but the complexity is still linear, since
> > the number of XOR operations is linearly proportional to the
> > vector's size.

> Hmm, if we have a 32-bit ALU then we could load both vectors
> into a pair of registers and use the comparator to get the
> result in "one cycle" right? In other words, we are doing all
> XORs in parallel followed by one OR. Please correct me if I'm
> wrong here.

I'm not sure I understand. How can the code load both vectors
into a pair of registers, if, say, the vectors each contain
several thousand bits.

What I would expect is that the bits are actually kept in an
array of unsigned, and that the library compare this. Something
like:

return lhs.size() == rhs.size()
&& std::equal( lhs.buffer_start,
lhs.buffer_end,
rhs.buffer_start ) ;

(Some additional logic is necessary to ensure that a possible
partial word at the end doesn't compare unequal, even though all
of the significant bits are equal.)

The algorithm remains O(N), but:

-- is O(1) is the lengths are different, and
-- only actually loops N/32 (or whatever) times, rather than N
(but this doesn't change the complexity, of course).

> Of course, I have no idea if the compiler would actually do
> this.

Typicallyl, the compiler will do whatever the code in the
library implementation tells it to do. (It doesn't have to;
it's allowed to build in knowledge of std::vector<bool>, and use
that knowledge to generate special code. But I don't know of
any compiler which does this.)

--
James Kanze (GABI Software) email:
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

wrote:
> Hmm, if we have a 32-bit ALU then we could load both vectors into a
> pair of registers and use the comparator to get the result in "one
> cycle" right? In other words, we are doing all XORs in parallel
> followed by one OR. Please correct me if I'm wrong here.

If the std::vector<bool> has a size of 1 million, how do you suppose
it can load all at once into the ALU?

Btw, what do you need the xors and ors for? If you are comparing for
equality or inequality, just compare the array elements (eg. if they are
for example size_t elements) for equality of inequality. If any bit
differs, the results will be unequal.

Rafał wrote:
> 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?

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

(OTOH, I assume the dynamic bitvector in boost is more of the kind of
data container people like rather than std::vector<bool>? I would be
fine with that too, but will such a data container be included in the
next standard?)

Juha Nieminen wrote:
> Rafal wrote:
>> 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. It also uses a proxy class for
vector<bool>::reference, which is not allowed by the standard for any
other container.

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?


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?


>
> 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?

>
> (OTOH, I assume the dynamic bitvector in boost is more of the kind
> of data container people like rather than std::vector<bool>? I
> would be fine with that too, but will such a data container be
> included in the next standard?)

Doesn't seem so (yet).


Bo Persson

On Aug 2, 3:10*am, James Kanze <james.ka...@gmail.com> wrote:
> On Aug 2, 6:51 am, fgh.vbn....@gmail.com wrote:
>
>
> > > No, it wouldn't be O(1). It's still O(n). This would be
> > > faster, of course, but the complexity is still linear, since
> > > the number of XOR operations is linearly proportional to the
> > > vector's size.
> > Hmm, if we have a 32-bit ALU then we could load both vectors
> > into a pair of registers and use the comparator to get the
> > result in "one cycle" right? In other words, we are doing all
> > XORs in parallel followed by one OR. Please correct me if I'm
> > wrong here.
>
> I'm not sure I understand. *How can the code load both vectors
> into a pair of registers, if, say, the vectors each contain
> several thousand bits.

I was only referring to the case when size <= 32. If it is more than
that then clearly, the N/32 factor that you have mentioned will come
in.

Thanks.

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.

#include <vector>

template <typename T> void Test() {
std::vector<T> V(3);
T& third = V.at(2);
}

int main() {
Test<int>();
Test<bool>();
}

Works for int,
but for bool:
x.cpp:5: error: invalid initialization of non-const reference of
type ‘bool&’ from a temporary of type ‘std::_Bit_reference

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

Yes, but this should be separate object - because it does not behave like a
vector<>