Array-like container for uints shorter than 8 bits (Rev 1)

Question

This is a follow-up to Array-like container for uints shorter than 8 bits

In short: The PackedBitfieldArray should be a kind of container for packed (unsigned) ints shorter than 8 bits. It provides proxy objects for manipulation and iterators.

What I have changed:

• PackedBitfieldArray::end() now returns a correct past-the-end iterator (that was broken in the previous version). There also const versions of begin() and end().
• PackedBitfieldArray::operator[]() now has a const companion.
• The proxy objects proxy and const_proxy are now derived from a proxyT template that implements the const version. The non-const version adds an assignment operator.
• The iterators are now random_access_iterator (before: forward_iterator, I've added the necessary decrement and offset (is that their name?) operators.
• The iterators are now derived from a common template to minimize duplicate code (there is none, I think).
• The iterators now store an index where they stored an offset before. This might speed up everything related to random access, but slow down ++, -- and repeated access to the same location.

Here's the code, questions and things I'd like to know better are below that.

Header:

#ifndef SFDD_PACKEDBITFIELDARRAY_H
#define SFDD_PACKEDBITFIELDARRAY_H

#include <array>
#include <cstddef>
#include <cstdint>
#include <iterator>

template<size_t Bits, size_t Elements, typename V = uint8_t>
class PackedBitfieldArray
{
  public:
    typedef V value_type;

    static constexpr size_t value_bitwidth = 8*sizeof(value_type);
    static_assert(Bits <= value_bitwidth, "Bit size must not be greater than the underlying storage type's bit size");
    static_assert(value_bitwidth % Bits == 0, "Cannot pack this : (value_bitwidth % Bits per element) != 0");

    static constexpr value_type arg_mask = (1<< Bits)-1;
    // number of underlying storage elements
    static constexpr size_t value_size = (Bits*Elements+(value_bitwidth-1))/value_bitwidth;


  private:
    template<bool isConst>
    class proxyT
    {
      public:
        typedef typename std::conditional<isConst,
                                          const PackedBitfieldArray::value_type,
                                          PackedBitfieldArray::value_type>::type value_type;

        operator PackedBitfieldArray::value_type() const
        {
          return (data_ & (arg_mask << offset_)) >> offset_;
        }

      protected:
        proxyT(value_type& data, size_t offset) : data_(data), offset_(offset) {}
        value_type& data_;
        size_t offset_;
    };


  public:
    class proxy : public proxyT<false>
    {
      public:
        proxy(value_type& data, size_t offset) : proxyT<false>(data, offset) {}

        proxy& operator=(value_type value)
        {
          value_type orVal = ((value & arg_mask) << this->offset_);
          this->data_ = (this->data_ & ~(arg_mask << this->offset_)) | orVal;
          return *this;
        }

    };



    class const_proxy : public proxyT<true> {};

    value_type* data() {return data_.data();}
    const value_type* data() const {return data_.data();}
    void clear() {data_.fill(0);}

    proxy operator[](size_t i)
    {
      size_t i_ = i*Bits/value_bitwidth;
      uint8_t offset = i * Bits % value_bitwidth;
      return proxy(data()[i_], offset);
    }

    const_proxy operator[](size_t i) const
    {
      size_t i_ = i*Bits/value_bitwidth;
      uint8_t offset = i * Bits % value_bitwidth;
      return const_proxy(data()[i_], offset);
    }



    template<bool isConst>
    class iteratorT
    {
      public:
        typedef std::random_access_iterator_tag iterator_category;
        typedef typename std::conditional<isConst, const_proxy, proxy>::type value_type;
        typedef typename std::conditional<isConst, const PackedBitfieldArray::value_type, PackedBitfieldArray::value_type>::type storage_type;
        typedef value_type& reference;
        typedef value_type* pointer;
        typedef ptrdiff_t difference_type;

        /** Constructor **/
        iteratorT(storage_type* data, size_t i) : data_(data), i_(i) { }



        /**
          Input iterator, Forward Iterator
        **/
        iteratorT& operator++()// prefix increment
        {
          i_++;
          return *this;
        }

        iteratorT operator++(int)// postfix increment
        {
          iteratorT previous(*this);
          operator++();
          return previous;
        }

        bool operator==(const iteratorT& rhs) const
        {
          return ((data_ == rhs.data_) && (i_ == rhs.i_));
        }

        bool operator!=(const iteratorT& rhs) const {return !(operator==(rhs));}

        proxy operator*() const
        {
          size_t dataIndex = i_*Bits/value_bitwidth;
          uint8_t offset = i_ * Bits % value_bitwidth;
          return proxy(data_[dataIndex], offset);
        }



        /**
          Bidirectional iterator
        **/
        iteratorT& operator--()
        {
          i_--;
        }

        iteratorT operator--(int)
        {
          iteratorT previous(*this);
          operator--();
          return previous;
        }



        /**
          Random Access Iterator
        **/
        iteratorT& operator+=(size_t n)
        {
          i_ += n;
          return *this;
        }

        iteratorT operator+(size_t n) const
        {
          iteratorT result(*this);
          result+= n;
          return result;
        }

        iteratorT& operator-=(size_t n)
        {
          i_ -= n;
          return *this;
        }

        iteratorT operator-(size_t n) const
        {
          iteratorT result(*this);
          result-= n;
          return result;
        }



        /**
          Difference (do I need further comparisons?)
        **/
        typename iteratorT::difference_type operator-(const iteratorT& rhs) const
        {
          return i_ - rhs.i_;
        }

      private:
        storage_type* data_;
        size_t i_;
    };

    typedef iteratorT<false> iterator;
    typedef iteratorT<true> const_iterator;
    iterator begin()
    {
      return iterator(data_.data(), 0);
    }

    iterator end()
    {
      return iterator(data_.data(), Elements);
    }

    const_iterator begin() const
    {
      return const_iterator(data(), 0);
    }

    const_iterator end() const
    {
      return const_iterator(data_.data(), Elements);
    }

  private:
  std::array<value_type, value_size> data_;
};


#endif // SFDD_PACKEDBITFIELDARRAY_H

Usage Example

#include <algorithm>
#include <bitset>
#include <iostream>

#include "packedBitfieldArray.h"

int main()
{
  static const size_t bits = 2;
  static const size_t n = 9;
  typedef PackedBitfieldArray<bits, n, uint8_t> PackedBitfield;
  PackedBitfield a;

  using namespace std;

  cout << "bits = " << bits << ", n = " << n << ", [a] = " << sizeof(a) << "\n";
  cout << "a.arg_mask = 0b" << std::bitset<8*sizeof(PackedBitfield::value_type)>(a.arg_mask) << "\n\n";

  a.clear();

  /* Fill with indices */
  for (size_t i = 0; i < n; i++)
  {
    a[i] = i;
  }

  cout << "\nfor loop, C-like element access:\n";
  for (size_t i = 0; i < n; i++)
  {
    cout << "a[" << i << "] = " << (int)a[i] << "\n";
  }

  cout << "\nfor loop with iterators:\n";
  for (auto it = a.begin(); it != a.end(); ++it)
  {
    cout << "a[...] = " << *it;//(int)(uint8_t)*it;
    cout << " (0b" << std::bitset<8*sizeof(PackedBitfield::value_type)>(*it) << ")\n";
  }

  cout << "\nfor_each with a lambda:\n";
  std::for_each(a.begin(), a.end(), [](const PackedBitfield::proxy pr) {cout << "a[...] = " << (int)pr << " (0b" << std::bitset<8*sizeof(PackedBitfield::value_type)>(pr) << ")\n";});

  cout << "\nunderlying data dump:\n";
  for (size_t i = 0; i < a.value_size; i++)
  {
    cout << "a[" << i << "_] = " << (int)a.data()[i] << " (0b" << std::bitset<8*sizeof(PackedBitfield::value_type)>(a.data()[i]) << ")\n";
  }

  cout << "\nfor loop, random access offset:\n";
  for (size_t i = 0; i < n; i++)
  {
    auto it = a.begin() + i;
    cout << "a[" << i << "] = " << (int)*it << "\n";
  }

  size_t start = 2;
  cout << "\nfor loop, random access offset from " << start << ":\n";
  auto iStart = a.begin() + start;
  for (size_t i = start; i < n; i++)
  {
    auto it = iStart + (i - start);
    cout << "a[" << i << "] = " << (int)*it << "\n";
  }

  const PackedBitfield b = a;
  auto icStart = b.begin();

  return 0;
}

Questions and Problems

Source

• Are the comments ok (amount, type, and quality)?
• Is the formatting ok?

PackedBitfieldArray

• I have defined a value_type which is the underlying storage type, see PackedBitfieldArray::data_, which is a std::array). Should I add a second typedef for read/write access using proxies? This would add some flexibility, but make it harder to understand/use. The names would then be storage_type and value_type.

proxyT

• this class is private to PackedBitfieldArray and has a protected constructor. It can only be constructed by proxy and const_proxy, which derive from it.
• I don't know how well the operator value_type() behaves when other int-like types must be assigned the proxy's value. When I run into problems with that, should I add a template conversion operator that handles integers or would that create even more problems?
• I will most probably have statements like bool b = somePackedBitfieldArray[i]. Implicit conversion to bool is said (! I have no real experience with that) to be dangerous. What should I prepare for regarding implicit conversions to bool?

const_proxy

• derived from proxyT, but doesn't refine anything. A typedef proxyT<true> const_proxy wouldn't work here, because it couldn't be constructed: the base constructor is protected. Is that particularly bad?

proxy

• Similar to the proxyT conversion operator, will I run into problems with the assignment operator here?

iteratorT

• The internal types seem to work, but I can't see any sense for reference and pointer types, because the interface uses the proxy objects. However, containers should allow references and pointers to the objects they store, right?
• is proxy/const_proxy the correct value_type in the first place?
• Do I need more comparison operators, such as <, >, <=, >=?

Testing

• How do I test this (the container, the iterators) without too much trial and error?

Answer 1

I would like to see some extra comments or some brief description before the proxy and proxyT member types. Their implementations are not trivial either, involving some unclear bit-shifts. So I think some explanation of what their methods do is proper.

A brief header description of what the PackedBitfieldArray does, what are its most remarkable features, etc, is also nice. Place such comment just before the class declaration. It should be brief but summarise the purposes of the class. Adding a short usage example in the comment is also valid.

The only comment I currently find useless is this one:

/** Constructor **/
iteratorT(storage_type* data, size_t i) : data_(data), i_(i) { }

---

If you want to be more pedantic, you can use std::size_t/std::uint8_t. Personally, I'm fine with just size_t/uint8_t though.

---

Currently, you have interface and implementation together in the header file. For inline classes and template classes, I usually separate the code in two files.

In the header file (.h/.hpp) I keep just the class declaration, as if it were a normal class. This makes easier for someone who is just looking for the name or signature of a method and does not wish to be bothered by the implementation details.

The template implementation is place inside an .inl (inline) file. This extension is recognised by most IDEs and text editors. Then the .inl is included at the end of the header. It looks something like this:

Class.hpp:

// include guards...

template<class T> class Class {
public:
    void methodA();
    void methodB();
};

#include "Class.inl"

Class.inl:

template<class T>
void Class<T>::methodA()
{
    // implementation ...
}

template<class T>
void Class<T>::methodB()
{
    // implementation ...
}

...

Answer 2

Typedefs on the container

typedef proxy reference             // this one is fine
typedef const_proxy const_reference // this is problematic

or you can rename them completely. Look at std::bitset::reference or std::vector<bool> for some inspiration, but the const_reference = bool there in vector<bool> is considered unlucky choice (violates the common rules about containers). The problem is, that const_reference can be used for both return type (where it should be real reference) and as argument (where it should be value_type in this case).

proxyT

I was at first worried if the code can even compile, having public base class which is private to the container, but it seems to work. Conversion operator value_type() should be fine and you can specialize it (or use SFINAE) if you wish to use bool for Bits=1:

typedef V storage_type
typedef conditional_t<Bits==1,bool,V> value_type

Note that I have just used C++14 conditional_t which is defined as

template< bool B, class T, class F >
using conditional_t = typename conditional<B,T,F>::type;

You can bring it to your C++11 code as well (and I am using it this way) and make your code a bit nicer and more readable.

const_proxy

Well, you could possibly use other SFINAE trics to allow simple typedef proxyT<false> reference; typedef proxyT<true> const_reference, but I would not worry that much here.

iteratorT

I think that value_type and reference should be the same as on the container here. Pointer could in fact be the iterator itself, but I would rather not define it. I hope somebody more experienced will address this, because this is getting opinion-based and touches the problems about vector<bool> - vector<bool>::iterator is derived from std::iterator<std::random_access_iterator_tag, bool>.

---

Comments about this topic (vector<bool>::const_reference and such) appriciated, I will gladly edit the answer, if somebody can shed some more light at it.