Problem
Follow-up: Array-like container for uints shorter than 8 bits (Rev 1)
First of all: yes, I need this kind of array to generate data for a piece of hardware, and it must be stored and manipulated somewhere. The general consensus regarding bit manipulation seems to be “if you need to do that, there’s something wrong”.
The array-like container (PackedBitfieldArray) I’m writing is for uintx_ts, where x = 2n (x is an integer power of two). No uintx_t crosses (or may cross) any word boundary of the actual underlying storage type. PackedBitfieldArray is templated with the number of Bits per element, number of Elements (just like std::array) and the default storage type V is uint8_t.
Elements are accessed by proxy and const_proxy objects, and I want to provide an iterator (already included below) and a const_iterator (not yet included because I want to avoid too much duplicate code), for use with algorithms.
Here’s the header:
#ifndef SFDD_PACKEDBITFIELDARRAY_H
#define SFDD_PACKEDBITFIELDARRAY_H
#include <array>
#include <cstdint>
template<size_t Bits, size_t Elements, typename V = uint8_t>
class PackedBitfieldArray
{
// array type for packable bitfields-kinda-types
public:
typedef V value_type;
static constexpr size_t value_bitwidth = 8*sizeof(value_type);
static_assert(Bits < value_bitwidth, "Bit size mut be smaller 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;
static constexpr size_t value_size = (Bits*Elements+(value_bitwidth-1))/value_bitwidth; // number of underlying storage elements
class proxy
{
public:
proxy(value_type& data, size_t offset) : data_(data), offset_(offset) {}
proxy& operator=(value_type value)
{
value_type orVal = ((value & arg_mask) << offset_);
data_ = (data_ & ~(arg_mask << offset_)) | orVal;
return *this;
}
operator value_type() const
{
return (data_ & (arg_mask << offset_)) >> offset_;
}
private:
value_type& data_;
size_t offset_;
};
class const_proxy
{
public:
const_proxy(value_type& data, size_t offset) : data_(data), offset_(offset) {}
operator value_type() const
{
return (data_ & (arg_mask << offset_)) >> offset_;
}
private:
const value_type& data_;
size_t offset_;
};
value_type* data() {return data_.data();}
const value_type* data() const {return data_.data();}
proxy operator[](size_t i)
{
size_t i_ = i*Bits/value_bitwidth;
uint8_t offset = i * Bits % value_bitwidth;
return proxy(data()[i_], offset);
}
class iterator : public std::iterator<std::forward_iterator_tag, proxy>
{
public:
iterator(value_type* data, size_t i)
{
size_t i_ = i*Bits/value_bitwidth;
offset_ = i * Bits % value_bitwidth;
data_ = &data[i_];
}
proxy operator*() const {return proxy(*data_, offset_);}
iterator& operator++()
{
offset_ += Bits;
if (offset_ == value_bitwidth)
{
offset_ = 0;
data_++;
}
return *this;
}
bool operator==(const iterator& rhs)
{
return ((data_ == rhs.data_) && (offset_ == rhs.offset_));
}
bool operator!=(const iterator& rhs) {return !(operator==(rhs));}
private:
value_type* data_;
size_t offset_;
};
iterator begin()
{
return iterator(data_.data(), 0);
}
iterator end()
{
return iterator(&data_.data()[value_size], 0); // WRONG
}
private:
std::array<value_type, value_size> data_;
};
#endif // SFDD_PACKEDBITFIELDARRAY_H
This is the first time I’ve written an iterator, and I basically just copied the implementation from this CR answer. Please do not suggest to use boost, as the environment I’m writing this for pollutes boost’s template parameter names with evil macros.
- Do the arguments for
iterator::iterator()make sense? Should I go for an index instead? - In cases where the upper bits of the last storage element are not used (e.g. with
Bits = 2,Elements = 3,V = uint8_t),PackedBitfieldArray::end()is not initialized correctly – this might influence the answer to the previous question (iterator constructor arguments). - Can I avoid duplicate code in
iterator::iterator()andPackedBitfieldArray::operator[]()? - I think a
forward_iteratoris sufficient in my case, are there any reasons to enhance it tobidirectionalorrandom_accessanyway?
This is the first time I’ve written an iterator of any kind. Is something essential missing? - Once I have a sufficiently well working iterator, how should I implement the const version from there without duplicating most of the code?
Usage examples:
#include <algorithm>
#include <bitset>
#include <iostream>
#include "packedBitfieldArray.h"
int main()
{
static const size_t bits = 2;
static const size_t n = 8;
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) << "nn";
/* 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[...] = " << (int)*it << " (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";
}
return 0;
}
Output:
bits = 2, n = 8, [a] = 2
a.arg_mask = 0b00000011
for loop, C-like element access:
a[0] = 0
a[1] = 1
a[2] = 2
a[3] = 3
a[4] = 0
a[5] = 1
a[6] = 2
a[7] = 3
for loop with iterators:
a[...] = 0 (0b00000000)
a[...] = 1 (0b00000001)
a[...] = 2 (0b00000010)
a[...] = 3 (0b00000011)
a[...] = 0 (0b00000000)
a[...] = 1 (0b00000001)
a[...] = 2 (0b00000010)
a[...] = 3 (0b00000011)
for_each with a lambda:
a[...] = 0 (0b00000000)
a[...] = 1 (0b00000001)
a[...] = 2 (0b00000010)
a[...] = 3 (0b00000011)
a[...] = 0 (0b00000000)
a[...] = 1 (0b00000001)
a[...] = 2 (0b00000010)
a[...] = 3 (0b00000011)
underlying data dump:
a[0_] = 228 (0b11100100)
a[1_] = 228 (0b11100100)
Solution
This will patch your code:
iterator end()
{
return iterator(data_.data(), Elements);
}
Now you can try e.g. this in your main():
static const size_t bits = 2;
static const size_t n = 5;
Output:
bits = 2, n = 5, [a] = 2 a.arg_mask = 0b00000011 for loop, C-like element access: a[0] = 0 a[1] = 1 a[2] = 2 a[3] = 3 a[4] = 0 for loop with iterators: a[...] = 0 (0b00000000) a[...] = 1 (0b00000001) a[...] = 2 (0b00000010) a[...] = 3 (0b00000011) a[...] = 0 (0b00000000) for_each with a lambda: a[...] = 0 (0b00000000) a[...] = 1 (0b00000001) a[...] = 2 (0b00000010) a[...] = 3 (0b00000011) a[...] = 0 (0b00000000) underlying data dump: a[0_] = 228 (0b11100100) a[1_] = 52 (0b00110100)
That should answer your first two questions: It is OK with this correction.
For the iterator you can use:
- Template (with some SFINEA for iterator->const_iterator)
- Inheritance (common base with the implementation)
- Composition (common struct to place inside as a member) to share some code.
For operator[] I would not worry about duplication, but you can solve it by const_proxy->proxy private constructor (and friend) and some const_cast to help you. Not nice, I would rather copy three lines and adapt. Again, some templated private helper could solve that as well.
It is your class, if you are fine with forward_iterator, then it is fine. If not, enhance it and use std category tag.