I'd like to cook up a nibble vector (packed vector with datatype 4 bits). I need this to be memory efficient so taking the low bits of a vector<uchar> isn't desired. I'm having some trouble finding good examples of how to properly cook up iterators for this. Any suggestions where to find something a good clear example of this ?
Isn't it problems with proxy objects that led to the call for vector<bool> to be removed from the C++ standard as it is a "nonconforming container"?
Boost have this say on why their dynamic_bitset, which uses bit packing like vector<bool>, does not support iterators. The same arguments should hold for nibbles?
dynamic_bitset is not a Container and does not provide iterators for the following reason:
A container with a proxy reference type can not fulfill the container requirements as specified in the C++ standard (unless one resorts to strange iterator semantics). std::vector<bool> has a proxy reference type and does not fulfill the container requirements and as a result has caused many problems. One common problem is when people try to use iterators from std::vector<bool> with a Standard algorithm such as std::search. The std::search requirements say that the iterator must be a Forward Iterator, but the std::vector<bool>::iterator does not meet this requirement because of the proxy reference. Depending on the implementation, they may or not be a compile error or even a run-time error due to this misuse. For further discussion of the problem see Effective STL by Scott Meyers). So dynamic_bitset tries to avoid these problems by not pretending to be a container.
Nibbles aren't addressable either, so the expression &vecnibble would have to either fail or return a proxy (like in the last SO link posted by @andywestken).
And yes, containers with non-addressable elements violate current standard requirements so the standard algorithms may not work with them (unless the author of the library made sure it was possible). You can have the iterators, but you might need to specialize the algorithms. Or, indeed, go the dynamic_bitset way and make a dynamic_nibbleset without iterators.
Ummm, for my use i have zero problem with &vecnibble[index] working. Just because some operations don't follow std::vector doesn't mean the whole concept of fitting iterators is invalid. In my opinion &vec[index] is itself a hack that should never have been used. It just so happens a subset of elements that can be packed in a vector also match up with a common native machine size (some multiple of an 8 bit byte).
Okay so the problem I run into is this:
error: no type named ‘value_type’ in ‘struct std::iterator_traits<vectornibble::const_iterator>
I'm not even sure how to deal with this. I start deriving from std::iterator and i get tons of wierd errors from manipulating the proxy. "typedef unsigned char value_type" inside the iterator class or the container seems to do nothing as well.
okay, update. Partial template speciailzation is always yuk.