nibble vector, iterators?

[bnolsen]

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 ?

[Cubbi]

Such iterator would have to dereference into a proxy object, just like vector<bool> -- you could look at a few implementations of that.

[andywestken]

vector<bool>

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.

From : dynamic_bitset<Block, Allocator>
http://www.boost.org/doc/libs/1_53_0/libs/dynamic_bitset/dynamic_bitset.html
Also see:

So I don't think vector<bool> should be seen as a good example.

A bit of information about how you want to use your "nibble collection" might be of use?

Andy

Also see:

When Is a Container Not a Container?
http://www.gotw.ca/publications/mill09.htm

Alternative to vector<bool>
http://stackoverflow.com/questions/670308/alternative-to-vectorbool

Edit: in the pro-vector<bool> camp, this post seems to be arguing that it might be possible. But I've only just come across this particular thread, so I haven't even begun to digest it.

Could multiple proxy classes make up a STL-proof bitvector?
http://stackoverflow.com/questions/14061694/could-multiple-proxy-classes-make-up-a-stl-proof-bitvector

[bnolsen]

Theoretically it doesn't quite fit c++ containers but *most* operations work just fine. Things like &vecbool[index] don't work but the basic paradigm works.

Unfortunately I don't consider the c++ headers to be very readable and my first attempt at copy resulted in problems with iterator errors with std::equal, etc.

When working with actual vectors of uint8_t uint16_t, float, etc I find std::copy/std::transform adaptability to be invaluable for things like applying alpha bit masks, etc.

[Cubbi]

Nibbles aren't addressable either, so the expression &vecnibble[0] 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.

[bnolsen]

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.

namespace std
{
  template <> struct
    iterator_traits<ns::vectornibble::const_iterator>
      { typedef uint8_t value_type; };
  template <> struct
    iterator_traits<ns::vectornibble::iterator>
      { typedef uint8_t value_type; };
}