Alternative to vector<bool>

Question

As (hopefully) we all know, vector<bool> is totally broken and can't be treated as a c array. What is the best way to get this functionality? So far, the ideas I have thought of are:

• Use a vector<char> instead, or
• Use a wrapper class and have vector<bool_wrapper>

How do you guys handle this problem? I need the c_array() functionality.

As a side question, if I don't need the c_array() method, what is the best way to approach this problem if I need random access? Should I use a deque or something else?

Edit:

• I do need dynamic sizing.
• For those who don't know, vector<bool> is specialized so that each bool takes 1 bit. Thus you can't convert it to a c-style array.
• I guess "wrapper" is a bit of a misnomer. I was thinking something like this:

Of course, then I have to read into a my_bool due to possible alignment issues :(

struct my_bool
{
    bool the_bool;
};
vector<my_bool> haha_i_tricked_you;

Answer 1

Use std::deque if you don't need the array, yes.

Otherwise I think you're best off writing a minimal equivalent class of your own - internally allocates a C array of bool, and has the usual constructor, operators, destructor, swap, [], size, c_array, etc.

Answer 2

Depends on your needs. I would go for either std::vector<unsigned char>. Writting a wrapper can be fine if you only use a subset of the functionality, else it will become a nightmare.

Answer 3

You may want to check your compiler/library suite. There was a way to get vector to behave "sanely" (albeit not according to the standard) using a compiler flag in CodeWarrior, if I recall correctly.

Answer 4

That's an interesting problem.

If you need what would have been a std::vector if it was not specialized, then maybe something like that would work fine with your case :

#include <vector>
#include <iostream> 
#include <algorithm>

class Bool
{
public:

    Bool(): m_value(){}
    Bool( bool value ) : m_value(value){}

    operator bool() const { return m_value;}

    // the following operators are to allow bool* b = &v[0]; (v is a vector here).
    bool* operator& () { return &m_value; }
const bool * const operator& () const { return &m_value; }

private:

    bool m_value;

};




int main()
{
    std::vector<Bool> working_solution(10, false);


    working_solution[5] = true;
    working_solution[7] = true;


    for( int i = 0; i < working_solution.size(); ++i )
    {
     std::cout<< "Id " << i << " = " << working_solution[i] << "(" <<(working_solution[i] ? "true" : "false") << ")" <<std::endl; // i used ? : to be sure the boolean evaluation is correct
    }

    std::sort( working_solution.begin(), working_solution.end());
    std::cout<< "--- SORTED! ---" << std::endl;

    for( int i = 0; i < working_solution.size(); ++i )
    {
            bool* b = &working_solution[i]; // this works!

     std::cout<< "Id " << i << " = " << working_solution[i] << "(" << (working_solution[i] ? "true" : "false") << ")" <<std::endl; // i used ? : to be sure the boolean evaluation is correct
    }

    std::cin.get();
    return 0;
}

I tried this with VC9 and it seems to work fine. The idea of the Bool class is to simulate the bool type by providing the same behavior and size (but not the same type). Almost all the work is done by the bool operator and the default copy constructors here. I added a sort to be sure it react as assumed when using algorithms.

Not sure it would suit all cases. If it's right for your needs, it would be less work than rewriting a vector-like class...

Answer 5

this problem was already discussed on comp.lang.c++.moderated (http://groups.google.ru/group/comp.lang.c++.moderated/browse_thread/thread/b8d6dd59dfb295c0/e23e0f606d64550a)
proposed solutions:

• your own allocator (based on std::allocator) and own vector specialization;
• use std::deque (as early was recommended in one of books S. Mayers ) - but this not for your requirements;
• make POD bool wrapper;
• use something (char/int/etc) with same size as bool instead bool;

also early I saw proposal for standard commitette - introduce macro (something like STD_VECTOR_BOOL_SPECIAL) for dissallow this specialization - but afaik this proposal was not implemented in stl implementations and wasn't approoved.

it seems that your problem has no ways to do this nicely.. maybe in C++0x

Answer 6

Consider using a vector< int >. Once you get past compilation and type checking, bool and int are both just machine words (edit: apparently this is not always true; but will be true on many PC architectures). In those cases where you want to convert without a warning, use "bool foo = !!bar", which converts zero to false and non-zero to true.

A vector< char > or similar will use less space, though it also has the potential to take a (very small) speed hit in some circumstances, because characters are less than the machine word size. This is, I believe, the main reason that bools are implemented using ints instead of chars.

If you really want clean semantics, I also like the suggestion of making your own boolean class -- looks like a bool, acts like a bool, but fools the template specialization.

Also, welcome to the club of people who want the vector< bool > specialization dropped from the C++ standard (with bit_vector to replace it). It's where all the cool kids hang out :).