Menu
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<byte> 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
vectortemplate forbool. The description of this specialization indicates that the implementation should pack the elements so that everyboolonly 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 thatvector<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).
437
If you need a "dynamic" array, then std::vector is the natural solution. It should in general be the default container for everything. But if you want a statically sized array created at time of compilation (like a C-style array is) but wrapped in a nice C++ object then std::array might be a better choice.
A std::vector can never be faster than an array, as it has (a pointer to the first element of) an array as one of its data members. But the difference in run-time speed is slim and absent in any non-trivial program. One reason for this myth to persist, are examples that compare raw arrays with mis-used std::vectors.
The time complexity for the insertion of a new element is O(log N). Vector is faster for insertion and deletion of elements at the end of the container. Set is faster for insertion and deletion of elements at the middle of the container.
The vector<bool> class is a partial specialization of vector for elements of type bool . It has an allocator for the underlying type that's used by the specialization, which provides space optimization by storing one bool value per bit.
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.
88
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).
41
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
