By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,411 Members | 1,030 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,411 IT Pros & Developers. It's quick & easy.

std::vector<bool> specialisation performance issue

P: n/a
On my platform I find that the std::vector<boolspecialisation incurs a
significant performance hit in some circumstances (when compared, say, to
std::vector<intprogrammed analagously). Is it possible to "spoof"
std::vector into implementing a "true" vector of bool rather than the
specialisation?

Say I do:

typedef bool boolreally;
std::vector<booleallybvec;

do I still get the std::vector<boolspecialisation? (I suspect the answer
is "yes", but I'm not sure how typedef-ed types are interpreted as
template parameters).

I can (and currently do) use std::vector<intat times, but I'd rather
not, when what I want really is "bool" rather than "int" (or anything else).

As I understand it, the justification for the std::vector<bool>
specialisation is to reduce the space overhead (possibly at the cost of
a time overhead). Personally I can't envisage many circumstances where one
mightn't use std::bitset rather than std::vector<boolif space were
an issue... I thus find the specialisation somewhat vexing. Am I
misunderstanding something here?

--
Lionel B
Dec 8 '06 #1
Share this Question
Share on Google+
8 Replies


P: n/a

Lionel B napsal:
On my platform I find that the std::vector<boolspecialisation incurs a
significant performance hit in some circumstances (when compared, say, to
std::vector<intprogrammed analagously). Is it possible to "spoof"
std::vector into implementing a "true" vector of bool rather than the
specialisation?

Say I do:

typedef bool boolreally;
std::vector<booleallybvec;

do I still get the std::vector<boolspecialisation? (I suspect the answer
is "yes", but I'm not sure how typedef-ed types are interpreted as
template parameters).
typedef'ed types are equivalent for template instantiation. You can
test it with following code:

#include <iostream>

template<typename T>
void Test()
{
std::cout << "Test<T>\n";
}

template<>
void Test<int>()
{
std::cout << "Test<int>\n";
}

int main(int argc, char* argv[])
{
typedef
int INT;

Test<INT>();
}
I can (and currently do) use std::vector<intat times, but I'd rather
not, when what I want really is "bool" rather than "int" (or anything else).

As I understand it, the justification for the std::vector<bool>
specialisation is to reduce the space overhead (possibly at the cost of
a time overhead). Personally I can't envisage many circumstances where one
mightn't use std::bitset rather than std::vector<boolif space were
an issue... I thus find the specialisation somewhat vexing. Am I
misunderstanding something here?
std::bitset has fixed size, std::vector<boolnot.

Dec 8 '06 #2

P: n/a
On Fri, 08 Dec 2006 05:59:14 -0800, Ondra Holub wrote:
Lionel B napsal:
>On my platform I find that the std::vector<boolspecialisation incurs a
significant performance hit in some circumstances (when compared, say, to
std::vector<intprogrammed analagously). Is it possible to "spoof"
std::vector into implementing a "true" vector of bool rather than the
specialisation?

Say I do:

typedef bool boolreally;
std::vector<booleallybvec;

do I still get the std::vector<boolspecialisation? (I suspect the answer
is "yes", but I'm not sure how typedef-ed types are interpreted as
template parameters).
typedef'ed types are equivalent for template instantiation. You can
test it with following code:

[snip]
Yup, thanks.
[snip]
>>
As I understand it, the justification for the std::vector<bool>
specialisation is to reduce the space overhead (possibly at the cost of
a time overhead). Personally I can't envisage many circumstances where one
mightn't use std::bitset rather than std::vector<boolif space were
an issue... I thus find the specialisation somewhat vexing. Am I
misunderstanding something here?

std::bitset has fixed size,
Oops, so it has.
std::vector<boolnot.
As it happens, I have just read an article suggesting that one way to spoof
std::vector<boolis to provide an explicit allocator, in which case the
non-specialised std::vector<boolwill be used... maybe overkill in my
case.

--
Lionel B
Dec 8 '06 #3

P: n/a

Lionel B wrote:
On my platform I find that the std::vector<boolspecialisation incurs a
significant performance hit in some circumstances (when compared, say, to
std::vector<intprogrammed analagously). Is it possible to "spoof"
std::vector into implementing a "true" vector of bool rather than the
specialisation?
struct Bool {
Bool(bool b) : b(b) { }
bool b;
operator bool() { return b; }
// etc...
};

Also try std::deque<bool>. It does hold bools.

HTH,
Michiel Salters

Dec 8 '06 #4

P: n/a
On Fri, 8 Dec 2006 13:24:16 +0000 (UTC) in comp.lang.c++, "Lionel B"
<me@privacy.netwrote,
>Is it possible to "spoof"
std::vector into implementing a "true" vector of bool rather than the
specialisation?
Good question. I would be inclined to try a vector<unsigned charand
let default conversions take care of the rest.

Dec 8 '06 #5

P: n/a
On Fri, 08 Dec 2006 17:33:40 +0000, David Harmon wrote:
On Fri, 8 Dec 2006 13:24:16 +0000 (UTC) in comp.lang.c++, "Lionel B"
<me@privacy.netwrote,
>>Is it possible to "spoof"
std::vector into implementing a "true" vector of bool rather than the
specialisation?

Good question. I would be inclined to try a vector<unsigned charand
let default conversions take care of the rest.
I have done something like that before but it makes me - probably
unjustifiably - nervous... I can never somehow convince myself that
the default conversions will always do the "right thing"; i.e. at
the very least behave exactly like bool in all comparisons and assignments
with, to and from real bools as well as with, to and from the spoofed
bool (never mind with, to and from all other integer types...). Can this be
guaranteed?

--
Lionel B
Dec 8 '06 #6

P: n/a

Lionel B wrote:
On Fri, 08 Dec 2006 17:33:40 +0000, David Harmon wrote:
On Fri, 8 Dec 2006 13:24:16 +0000 (UTC) in comp.lang.c++, "Lionel B"
<me@privacy.netwrote,
>Is it possible to "spoof"
std::vector into implementing a "true" vector of bool rather than the
specialisation?
Good question. I would be inclined to try a vector<unsigned charand
let default conversions take care of the rest.

I have done something like that before but it makes me - probably
unjustifiably - nervous... I can never somehow convince myself that
the default conversions will always do the "right thing"; i.e. at
the very least behave exactly like bool in all comparisons and assignments
with, to and from real bools as well as with, to and from the spoofed
bool (never mind with, to and from all other integer types...). Can this be
guaranteed?
It probably doesnt help your code (if it needs to interact with old
code), but IMO bool would be better by far if it didnt have automatic
conversions from a large range of types. In fact it would be
interesting to try a bool UDT which didnt allow the conversions, except
by comparisons and so on. It may actually run faster than the original
code due to a reduction in the number of conversions and also may
clarify the code which again is good for speed. It would also solve
your problem ;-)

regards
Andy Little

Dec 8 '06 #7

P: n/a
"Lionel B" <me@privacy.netwrote in message
news:el**********@south.jnrs.ja.net...
As it happens, I have just read an article suggesting that one way to
spoof
std::vector<boolis to provide an explicit allocator, in which case the
non-specialised std::vector<boolwill be used... maybe overkill in my
case.
Bad article. vector<boolis partially specialized on its allocator type.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Dec 8 '06 #8

P: n/a

Lionel B wrote in message ...
>On Fri, 08 Dec 2006 05:59:14 -0800, Ondra Holub wrote:
>[snip]
std::bitset has fixed size,

Oops, so it has.
>std::vector<boolnot.

As it happens, I have just read an article suggesting that one way to spoof
std::vector<boolis to provide an explicit allocator, in which case the
non-specialised std::vector<boolwill be used... maybe overkill in my
case.
Well, if you are willing to 'overkill' anyway:

bool bl(true);
std::vector< std::bitset<1 VecBit( 7, 1 );
if( bl == VecBit.at(0)[0] ){
std::cout<<"VecBit.at(0)="<<VecBit.at(0)<<std::end l;
std::cout<<" ="<<std::boolalpha<<VecBit.at(0)[0]<<std::endl;
}
// out: VecBit.at(0)=1
// out: =true
<G>

[ seems I heard this was deprecated, I may be thinking of something else. ]
// Example (stl docs) // #include <vector>
std::bit_vector V(5);
V[0] = true;
V[1] = false;
V[2] = false;
V[3] = true;
V[4] = false;

for( std::bit_vector::iterator i(V.begin()); i < V.end(); ++i )
std::cout<<std::boolalpha<<(*i)<<std::endl;
/* - out -
true
false
false
true
false
*/

--
Bob R
POVrookie
Dec 8 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion.