Comparing two vectors of bools

[fgh.vbn.rty@gmail.com]

I know that std::vector<boo lis 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.

[Sam]

Re: Comparing two vectors of bools

fgh.vbn.rty@gma il.com writes:

I know that std::vector<boo lis 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.

>
Does the size of the vector matter here? For instance if the vectors

That would be implementation defined. It makes sense that an implementation
would provide an optimization comparison operator, if possible.

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

You'll need to read the implementation of your compiler's std::vector<boo l>
to determine how it's done.


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAki TzeAACgkQx9p3GY HlUOI/2gCdG7CLnV8rXSq ol2mRDz1k9w75
38gAmgKzqUQpVZ2 +uPZ3+UWcx0DEZ5 fN
=9Qpt
-----END PGP SIGNATURE-----

[=?UTF-8?B?UmFmYcWC?=]

Re: Comparing two vectors of bools

fgh.vbn.rty@gma il.com wrote:

I know that std::vector<boo lis 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?).

[fgh.vbn.rty@gmail.com]

Re: Comparing two vectors of bools

On Aug 1, 10:00 pm, Sam <s...@email-scan.comwrote:

fgh.vbn....@gma il.com writes:

I know that std::vector<boo lis 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.

[Jerry Coffin]

Re: Comparing two vectors of bools

In article <g70loa$4tb$1@i news.gazeta.pl> , newsgroup@limco re.com.invalid
says...

fgh.vbn.rty@gma il.com wrote:
>

I know that std::vector<boo lis 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.

[James Kanze]

Re: Comparing two vectors of bools

On Aug 2, 6:51 am, fgh.vbn....@gma il.com wrote:

On Aug 1, 10:00 pm, Sam <s...@email-scan.comwrote:

fgh.vbn....@gma il.com writes:

I know that std::vector<boo lis 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_star t,
lhs.buffer_end,
rhs.buffer_star t ) ;

(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<boo l>, and use
that knowledge to generate special code. But I don't know of
any compiler which does this.)

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Juha Nieminen]

Re: Comparing two vectors of bools

fgh.vbn.rty@gma il.com 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<boo lhas 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.

[Juha Nieminen]

Re: Comparing two vectors of bools

Rafał wrote:

fgh.vbn.rty@gma il.com wrote:
>

>I know that std::vector<boo lis 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<boo l>? I would be
fine with that too, but will such a data container be included in the
next standard?)

[Bo Persson]

Re: Comparing two vectors of bools

Juha Nieminen wrote:

Rafal wrote:

>fgh.vbn.rty@gma il.com wrote:
>>

>>I know that std::vector<boo lis 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>::r eference, 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<booland speed optimizations for
vector<everythi ng_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<boo l>? 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

[fgh.vbn.rty@gmail.com]

Re: Comparing two vectors of bools

On Aug 2, 3:10 am, James Kanze <james.ka...@gm ail.comwrote:

On Aug 2, 6:51 am, fgh.vbn....@gma il.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.

[Pete Becker]

Re: Comparing two vectors of bools

On 2008-08-02 08:36:24 -0400, fgh.vbn.rty@gma il.com said:

On Aug 2, 3:10 am, James Kanze <james.ka...@gm ail.comwrote:

>On Aug 2, 6:51 am, fgh.vbn....@gma il.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.
>

O(whatever) is about how performance changes with increasing size. If
you have a known size limit it's simply not applicable. You don't need
to talk about asymptotic behavior, because you can analyze your problem
exactly.

For example, if you have 32 bits packed into four 8-bit fields, you
need four comparisons. If they're stored in thirty-two 8-bit fields you
need thirty-two comparisons.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[=?UTF-8?B?UmFmYcWC?=]

Re: Comparing two vectors of bools

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 Tvoid Test() {
std::vector<TV( 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_re ference

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

[James Kanze]

Re: Comparing two vectors of bools

On Aug 2, 12:13 pm, "Bo Persson" <b...@gmb.dkwro te:

Juha Nieminen wrote:

Rafal wrote:

fgh.vbn....@gma il.com wrote:

>I know that std::vector<boo lis 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<boo l>, but it doesn't conform to the
documented contract of std::vector.

It also uses a proxy class for vector<bool>::r eference, 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<booland speed
optimizations for vector<everythi ng_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_bi tset, 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:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Bo Persson]

Re: Comparing two vectors of bools

James Kanze wrote:

On Aug 2, 12:13 pm, "Bo Persson" <b...@gmb.dkwro te:

>Juha Nieminen wrote:

>>Rafal wrote:
>>>fgh.vbn....@ gmail.com wrote:

>

>>>>I know that std::vector<boo lis 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<boo l>, but it doesn't conform to the
documented contract of std::vector.
>

>It also uses a proxy class for vector<bool>::r eference, 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<boolseem s like a minor problem. .-)


Bo Persson

[Juha Nieminen]

Re: Comparing two vectors of bools

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<boo lnot 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...)