18

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.

Alexis Wilke
  • 19,179
  • 10
  • 84
  • 156
JackSparrow
  • 707
  • 2
  • 10
  • 24

1 Answers1

21

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Thanks for quick reply ..:) ...okay that means bitset should only be used when size known beforehand ..? – JackSparrow Jan 21 '13 at 06:55
  • 3
    @Himank- It's a stronger claim - `std::bitset` *can* only be used when the size is known statically. – templatetypedef Jan 21 '13 at 06:57
  • 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..? – JackSparrow Jan 21 '13 at 06:59
  • @Himank- As mentioned in my answer, if you're planning on using a bit vector, the `vector` is a more reasonable starting point. I would switch to `vector` only if you suspected that `vector` wasn't performant. – templatetypedef Jan 21 '13 at 07:00
  • 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 – borisbn Jan 21 '13 at 07:17
  • @borisbn thanks for this ...but why so ..alignment issue ? – JackSparrow Jan 21 '13 at 07:22
  • @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 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 – borisbn Jan 21 '13 at 07:33