un bool ne fait quand même qu´un seul octet en mémoire (pas dans les registres, j´y reviens) quelle que soit la machine utilisé (enfin entre un x86 ou du IA64 ou affilié, le reste, je ne connais pas).
un "bool tableau[N];" n´est pas pire qu´un "char tableau[N]".
De plus, quand on le charge en mémoire, on peut (en tout cas sur des machines 32 bits) manipuler des morceaux de registre par paquets de 8 bits (AH,AL,BH,...) donc la encore dire qu´on manipule un int est faux, sans compter qu´il est tout à fait possible qu´un bon compilo puisse effectuer directement avec l´architecture du processeur (sans passer par des extensions) la même opération sur plusieurs bool (jusqu´à 4 donc sur une machine 32 bits) d´un coup (en chargeant 4 éléments d´un tableau de bool dans un registre par exemple).
Et enfin, il pourrait exister (et il existe peut-être) des architectures comme le MIX de Knuth qui peuvent manipuler les bit un à un (or le C++ est cencé est "portable", donc il faut écrire des programme aussi pour ces archi...).
La moralité de tout ça, c´est que d´après moi il faut utiliser les types disponible : en C un programmeur c´est qu´un booléen est codé dans un int (et encore, autant utiliser des typedef int BOOL), mais en C++, rien que pour la lisibilité il est plus logique d´utiliser des bool il me semble.