Variable size bitset

Question

I am practicing a question on array in which I have to find unique elements. Now for this my logic is to find the max element in the array and define the bitset for that. But problem is bitset needs a constant value so how to overcome this, below are some of my question on this:

a) Can I, by any chance, define the bitset with a variable size?
b) If not, then what is the best approach to use vector<bool> or vector<char>?
c) I know boost has a dynamic bitset but as I am doing this for learning I want to know of alternate approaches.

Solution

The std::bitset<N> template requires a fixed size in advance. The std::vector<bool> is the C++ standard's way of providing a variable-length bitvector, and it offers functionality similar to a bitset that can grow and shrink.

As for whether it's better or worse to use vector<char> or vector<bool>: the vector<bool> is a much more direct way of accomplishing this goal. I would start off by using it, then switch to vector<char> if the performance is unacceptable. In general, it's good to try to write the cleanest, most straightforward implementation first, then to optimize later on.

Hope this helps!

Comments

[JackSparrow]

Thanks for quick reply ..:) ...okay that means bitset should only be used when size known beforehand ..?

[templatetypedef]

@Himank- It's a stronger claim - std::bitset can only be used when the size is known statically.

[JackSparrow]

Thanks again..! and one more doubt what would be the best approach in vector(bool) and vector(char) for this type of question when I just need to find unique when size not known..?

[templatetypedef]

@Himank- As mentioned in my answer, if you're planning on using a bit vector, the vector<bool> is a more reasonable starting point. I would switch to vector<char> only if you suspected that vector<bool> wasn't performant.

[borisbn]

Another thing, that you should know about vector< bool > is that & v[ n ] - & v[ 0 ] can be not equal to n, instead of any other type

[JackSparrow]

@borisbn thanks for this ...but why so ..alignment issue ?

[borisbn]

@Himank no. It's not because of alignment, but because of C++ standard (23.2.4 and 23.2.5) says: "The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size()". vector< bool > can store 8 values in one byte