29

I'm working with a user-defined quantity of bits (I'm holding a three-dimensional array of bits, so the size increases cubically - assume no less then 512 bits), and need to flip them each individually. Right now, just on a computer, I'm using the bool type, since memory isn't an issue. I do plan to move the code to a microcontroller in the future, and so processing power and memory requirements may be an issue. Right now though, I just want speed.

I then found the std::bitset object from the C++ STL, but I can't define a bitset's size at runtime. I then found that the std::vector<bool> has a special initializer to store them as bits (instead of entire bytes, or 4 bytes) but then found this section in Wikipedia:

The Standard Library defines a specialization of the vector template for bool. The description of this specialization indicates that the implementation should pack the elements so that every bool only uses one bit of memory. This is widely considered a mistake. [...] There is a general consensus among the C++ Standard Committee and the Library Working Group that vector<bool> should be deprecated and subsequently removed from the standard library, while the functionality will be reintroduced under a different name.

Now, you can probably see my want for using a vector<bool> object, but after reading that, I'm considering using something else. The only problem is that I'm not sure what to use. I was curious though why they state that the functionality should be re-introduced (albeit under a different name).

So, my question is, would the use of vector<bool> objects be acceptable (being that they are a part of the STL)? Are they a part of the C++ standard?

If their use is not acceptable, is there an acceptable, alternative solution (outside me defining a special container myself)? I have a few ideas myself, but I'm just curious if anyone has a better solution. Also, I would like to avoid using large libraries (again, I want to eventually port this code to a microcontroller).

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Breakthrough
  • 2,444
  • 2
  • 23
  • 37
  • 1
    What are the problems of just using for example `vec[bit>>3] |= (1<<(bit&7));` with an `std::vector`? – 6502 Jul 21 '11 at 20:07
  • 1
    Related: Howard Hinnant's blog article [On `vector`](https://isocpp.org/blog/2012/11/on-vectorbool) - terrible name for a useful data structure. With appropriate specializations for `std::find`, `std::count`, and so on, a standard library can even expose fast system-specific optimizations. – Peter Cordes Jun 23 '22 at 20:02

6 Answers6

28

In "Effective STL," Item 18, Scott Meyers recommended: "Avoid using vector< bool >.":

As an STL container, there are really only two things wrong with vector< bool >. First, it's not an STL container. Second, it doesn't hold bools. Other than that, there's not much to object to.

Rob Hruska
  • 118,520
  • 32
  • 167
  • 192
Gnawme
  • 2,321
  • 1
  • 15
  • 21
23

There's nothing wrong with vector<bool>, except that it isn't equivalent to a vector<T> were T is the integer type equivalent to bool. This only shows in performance (CPUs only access bytes at a time, where in a vector<bool> every element is stored in one bit) and memory access (a reference to a first element of a vector<bool> is not equivalent to an array like with any other vector<T>.

It is part of the Standard, unfortunately: see section 23.3.7 (C++0x FDIS).

rubenvb
  • 74,642
  • 33
  • 187
  • 332
  • 12
    vector is optimized for space not speed. Also it does not confirm to container semantics exactly like the vector does. – Martin York Jul 21 '11 at 20:09
14

The critique is that vector<bool> is the only standard container that doesn't fully conform to the standard's container requirements. That's a bit of a surprise.

Another point is that vector<bool> forces a space optimization on everyone (by storing bits), when perhaps some users would have preferred a speed optimization.

Other than that, the major deviation is that the container cannot return a reference to its members, because it doesn't store any bools. That will make the odd standard library algorithm fail to compile for vector<bool>.

If you can live with that, and it fits your needs for everything else, it is quite ok to use it.

Bo Persson
  • 90,663
  • 31
  • 146
  • 203
11

There is boost.dynamic_bitset which is nearly identical to std::bitset, except that its size is given at runtime. If you're not interested in boost dependency, its source code (which is entirely contained in its header file) could at least give more ideas on how such container could be written.

Cubbi
  • 46,567
  • 13
  • 103
  • 169
  • thank you for your response, I changed my question to more accurately reflect why I chose 512 (the grid *I'm working with* is 8x8x8, but it can be defined as any size, and so the number of elements [and thus memory requirements] increase cubically). – Breakthrough Jul 21 '11 at 20:06
  • @Breakthrough Nevermind my note on 512, but is there any sort of internal structure to the data in that potentially large 3D array? Perhaps there are other data structures that could make use of that, like http://en.wikipedia.org/wiki/K-d_tree http://en.wikipedia.org/wiki/Octree and friends? – Cubbi Jul 21 '11 at 20:19
  • +1, and there is nothing wrong with your answer, and I really appreciate those alternate data types, but @rubenvb posted an answer that is more fitting to what I was looking for. I don't think trees are the way to go in this case, since I'm not performing any binary searches whatsoever. I do, however, need access to any element in this array nearly instantly in no particular order... – Breakthrough Jul 21 '11 at 21:45
2

There's nothing wrong with correct usage of vector<bool>, just like there's nothing wrong with auto_ptr- as long as you know the drawbacks and the surprises before going on.

Puppy
  • 144,682
  • 38
  • 256
  • 465
  • 2
    Indeed. If `vector` works for you, use it. It's part of the standard. If used safely, the worst that will happen when the specialization is removed in the future is not that your code will break, but that it will suddenly use a lot more RAM. – Cory Nelson Jul 21 '11 at 20:10
  • 1
    Do not use [`auto_ptr`](https://en.cppreference.com/w/cpp/memory/auto_ptr). It was deprecated in C++11 and removed in C++17. – John McFarlane Sep 26 '19 at 09:00
1

An alternative could be BitMagic although I'm not sure it works on any other architecture than x86(it's heavily optimized using SIMD).

celavek
  • 5,575
  • 6
  • 41
  • 69