Alternative to vector<bool>

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

Otherwise use an alternative vector that doesn't specialize on bool, such as the one in Boost Container.

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

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.