# C++ container — variable byte coded numbers list

I'm writing a container for unsigned integers, which uses variable byte coding. It works but some decisions I took look ugly so I would be glad if you gave me some hints for improving the design.

1. taking and storing reference in VBOutputIterator constructor
3. == operator in VBInputIterator
4. using of malloc, realloc and free in VBList (couldn't come up with a std::vector solution)

But general advice is welcome as well)

Also, recently came across a job ad where they required to "be able to write robust and maintainable code". How do you think, is my code robust or maintainable? How can I make it more so?

VBInputIterator.h

template <class ForwardIterator_t, class num_t=unsigned>
class VBInputIterator
{
public:
typedef num_t value_type;
typedef num_t& reference;
typedef num_t* pointer;
typedef std::forward_iterator_tag iterator_category;

// default gives the end
// see operator==
VBInputIterator()
: _end(true)
{
}
VBInputIterator(VBInputIterator const & other) = default;
VBInputIterator & operator=(VBInputIterator &) = default;

explicit
VBInputIterator(ForwardIterator_t const & arr)
: _in (arr)
, _end(false)
{
++*this;
}
~VBInputIterator()
{
}

//    void swap(VBInputIterator& other) noexcept {
//        using std::swap;
//        swap(_in, other._in);
//    }

VBInputIterator&
operator++ ()
{
_n = 0;
// if the first char == 128, it's the end of the stream
if (static_cast<unsigned char>(*_in) == 0x80)
{
_end = true;
return *this;
}

// while char < 128

// lol
// you can choose any variant
// or even leave both))
while ((*_in & 0x80) != 0x80)
while (*_in & 0x80 ^ 0x80)
{
_n |= *_in;
_n <<= 7;
++_in;
}
_n |= *_in & 0x7F;
++_in;

return *this;
}

VBInputIterator
operator++ (int)
{
VBInputIterator r (*this);
++*this;
return r;
}

// This part is what I would like to hear some suggestions about.
//
// to allow constructions such as while (iter != end)
// I implemented operator==. But how do I construct
// end iterator on default constructor, if I'm not
// even given the iterator (in default constructor that is)
// So I decided to keep a private boolean _end,
// and assign it to true when I meet the termination character.
// in ==, I just return _end.
// this allows some great constructions such as
// (iter != iter) that work perfectly fine.
//
// maybe I should have some static instance of that iterator
// denoting the end and return it every time, and then
// if I'm comparing with that end iter I just return _end
// and if not, I would compare underlying _in iterators or something
bool
operator== (VBInputIterator const & other) const
{
return _end;
}

bool
operator!= (VBInputIterator const & other) const
{
return ! (*this == other);
}

num_t const
operator* () const
{
return _n;
}

private:
num_t _n; // current number iterator points to
ForwardIterator_t _in;
bool _end; // see operator==
};


VBOutputIterator.h

#define DISALLOW_COPY_AND_ASSIGN(TypeName) \
TypeName(TypeName&) = delete;              \
void operator=(TypeName) = delete;

// bool terminating template argument:
// if true, we terminate the stream after each written number
// (and at the very beginning, in the constructor) and then
// overwrite the terminating character when writing a new number.
// can be set to false if OutputIterator_t doesn't support overwriting
// same elements.
// I put it in template parameters because then in the generated bytecode
// there is no checking, it's as if i used #ifdef or something.
// moreover, if you create a VBOutputIterator for some iterator,
// the iterator either supports overwriting or doesn't, so this boolean
// is a one-time decision, totally ok to hold it in template parameters.
// looks ugly though.
template <class OutputIterator_t, class num_t=unsigned, bool terminating=true>
class VBOutputIterator
{
public:
typedef num_t value_type;
typedef num_t& reference;
typedef num_t* pointer;
typedef std::output_iterator_tag iterator_category;

// note that I'm taking &out as a parameter, and _out is & as well
// this is done so that I can take, for example, ostreambuf_iterator
// which is noncopyable. But I don't really like the solution
explicit
VBOutputIterator(OutputIterator_t & out)
: _out(out)
{
// so far there are no elements, so terminate the "stream"
if (terminating) terminate();
}

VBOutputIterator&
operator=(num_t n)
{
if (n == 0) throw std::invalid_argument("we don't store zeros here");

// "you are not expected to understand this"
char _arr_buf[sizeof(num_t)*8/7 + 1];
char* i = _arr_buf;
do  {
*i = n & 0x7F;
++i;
n >>= 7;
} while (n > 0);
// now i points to the one past end character of our sequence

_arr_buf[0] |= 0x80;

// write bytes in reverse order to the out stream
while (i != _arr_buf)
{
--i;
*_out = *i;
++_out;
}

if (terminating) terminate();

return *this;
}

// my stream of bytes is terminated by 0x80 character
// , it's like null-terminated string
inline
void
terminate()
{
*_out = 0x80;
}

// these are no-op, as they are in ostreambuf_iterator
// hey, and how can make them a no-op?
// I don't know how long the next number would be,
// so I can't reserve space for them, so I can't
// increment iterator without writing a number.
VBOutputIterator&
operator*()
{
return *this;
}
VBOutputIterator&
operator++()
{
return *this;
}
VBOutputIterator&
operator++(int)
{
return *this;
}

private:
// most such restrictions are due to
// ostreambuf_iterator and alike iterators
// that can't be copied. But maybe I should
// that class so that it works with char arrays
// (which can be copied, where you can overwrite
// one location several times) and then if
// my class client wants to pass ostreambuf_iterator
// and decides to take a copy, it won't compile or
// maybe some bug will be introduced, but that's
// just his problem.
//
// so what should I do: restrict or let the user decide?
DISALLOW_COPY_AND_ASSIGN(VBOutputIterator);

// this is where the output goes
OutputIterator_t & _out;
};


VBList.h

#include "VBInputIterator.h"
#include "VBOutputIterator.h"

template <typename num_t>
class VBList
{
public:
typedef VBInputIterator<char*> iterator;
VBList()
: VBList(max_vb_size)
{
}
VBList(size_t capacity)
: _size(0)
, _capacity(capacity)
, _arr_start(static_cast<char*>(malloc(_capacity)))
, _arr_iter(_arr_start)
, _output(_arr_iter)
{
ensure_capacity();
}
~VBList()
{
free(_arr_start);
}
void
push_back(num_t n)
{
ensure_capacity();
_output = n;
++_size;
}

iterator
begin()
{
return iterator(_arr_start);
}
iterator
end()
{
return iterator();
}

private:
static size_t const max_vb_size = sizeof(num_t)*8/7 + 1;
size_t _size;
size_t _capacity;
char * _arr_start;
char * _arr_iter;
VBOutputIterator<char*, num_t> _output;

// =====================
// note how I store char* _arr_iter,
// I initialize VBOutputIterator with it,
// but VBOutputIterator takes a reference, not a copy.
// so it changes where _arr_iter points to.
// when I ensure_capacity, I create a new array (realloc)
// and assign _arr_iter to a new value,
// and VBOutputIterator starts writing to a new place
// because it holds a reference to _arr_iter!
// looks creepy but I couldn't find better solution.
// Does anyone have any suggestions?
// =====================

void
ensure_capacity()
{
size_t const arr_size = _arr_iter - _arr_start;
if (_capacity - arr_size  <  max_vb_size)
{
_capacity = _capacity*2 + max_vb_size;
_arr_start = static_cast<char*>(realloc(_arr_start, _capacity));
_arr_iter = _arr_start + arr_size;
}
}
};


main

#include <iostream>
#include <fstream>
#include "VBList.h"

int main()
{
using namespace std;
VBList<unsigned long long> l;
l.push_back(12);
l.push_back(1223233);
// iterate the list
for (auto i: l)
cout << i << endl;

// write to file
ofstream fout("file");
ostreambuf_iterator<char> ofstr_iter (fout.rdbuf());
VBOutputIterator<ostreambuf_iterator<char>, unsigned, false> out(ofstr_iter);
out = 1;
out = 333;
out = 18;
out.terminate();
fout.flush();

// read back from the file
ifstream fin("file");
VBInputIterator<istreambuf_iterator<char>, unsigned> in(fin.rdbuf());
VBInputIterator<istreambuf_iterator<char>, unsigned> end;
while (in != end)
{
cout << *in << endl;
++in;
}

return 0;
}


https://github.com/jazzandrock/VBNumberList

• Any specific reason you're using malloc in a C++ project instead of new? – yuri Mar 3 '18 at 20:41
• @yuri I really liked realloc, which copies the array on resize. The question is more like, why do I use raw arrays. I first tried to use back_insert_iterator<vector<char>>, but it doesn't allow writing a character and then overwriting it. Maybe in STL there is such iterator that allows that and also takes care of resizing? – jazzandrock Mar 3 '18 at 21:14
• Why do you pretend VB to each type name instead of using a namespace? – Cris Luengo Mar 3 '18 at 23:46
• @yuri You should not even be using new in C++ really; make_shared and make_unique are the best in 90% of cases. Moreover even when using smart pointers there should be no raw new (this subtetly occurs when considering exceptions). – JNS Mar 8 '18 at 10:56

## Fix the bug

The VBInputIterator has a default second templated class num_t=unsigned. That's not necessarily a problem, but its use in VBList is a bug:

typedef VBInputIterator<char*> iterator;


The problem is that if we're storing an unsigned long long int as in your example, the resulting iterator will only use unsigned which causes very large numbers such as 11122233344455566677ULL to be displayed as 1967613269..

It should be this:

typedef VBInputIterator<char*, num_t> iterator;


I see little advantage (and plenty of disadvantage, as illustrated by this bug!) to providing a default class, so I'd advocate omitting it.

## Make sure you have all required #includes

The VBList code uses VBInputIterator but doesn't #include "VBInputIterator".

## Use <cstdio> instead of <stdio.h>

The difference between the two forms is that the former defines things within the std:: namespace versus into the global namespace. Language lawyers have lots of fun with this, but for daily use I'd recommend using <cstdio>. See this SO question for details. However, see the next item.

## Use only required #includes

The code in VBList.h has #includes that are not needed. Specifically, neither <stdio.h> nor <vector> are required, so these may both be eliminated. It's worth noting that free is actually defined in <cstdlib> rather than <cstdio>, so if you're going to use raw malloc and free, the code should #include <cstdlib>. However, see the next item.

## Don't use leading underscores in names

Anything with a leading underscore in global space is a reserved name in C++ (and in C). See this question for details. Unless you're really sure about the language rules, I'd suggest avoiding leading underscore in names. For similar reasons, I'd also avoid the num_t type name in the templates.

## Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. I don't know that you've actually done that, but the use of raw cout and endl in your example program suggests that you may have.

## Rethink the interface

Consider the interface to the VBList. It has constructors and a destructor, but the only public interfaces are push_back(num_t n) and begin() and end(). This may be sufficient for some narrow purposes, but it doesn't, for example, allow the removal of numbers from the list, except by destroying the entire list.

## Prefer new and delete to malloc and free

Modern C++ tends to use new instead of malloc. Doing so would eliminate the need for <cstdlib> and is more idiomatic C++. In this case, I'd be inclined to use std::vector and avoid all four. As a partially worked example:

#include <vector>
#include <cstdint>

template<typename unum>
class VBInputIterator {
public:
typedef unum value_type;
typedef unum& reference;
typedef unum* pointer;
typedef std::forward_iterator_tag iterator_category;

explicit VBInputIterator(std::vector<uint8_t>::iterator ptr, std::vector<uint8_t>::iterator end) :
ptr{ptr},
end{end}
{}

VBInputIterator &operator++() {
for ( ; (ptr != end) && !(*ptr & 0x80) ; ++ptr) {
}
if (ptr != end) {
++ptr;
}
return *this;
}
unum operator*() const {
unum val{};
for (auto p{ptr} ; p != end; ++p) {
uint8_t c = *p;
val |= (c & 0x7f);
if (c & 0x80)
break;
val <<= 7;
}
return val;
}
bool operator!=(const VBInputIterator<unum> &two) const {
return ptr != two.ptr;
}
private:
std::vector<uint8_t>::iterator ptr;
std::vector<uint8_t>::iterator end;
};

template <typename unum>
class VBList {
public:
VBList() :
vec{}
{}
void push_back(unum n) {
if (n == 0) {
return;
}
std::vector<uint8_t> temp;
temp.reserve(sizeof(n));
temp.push_back((n & 0x7f) | 0x80);
for (n >>=7 ; n; n >>= 7) {
temp.push_back(n & 0x7f);
}
for (auto it{temp.rbegin()}; it != temp.rend(); ++it) {
vec.push_back(*it);
}
}
unum front() {
return *(begin());
}
VBInputIterator<unum> begin() {
return VBInputIterator<unum>{vec.begin(), vec.end()};
}
VBInputIterator<unum> end() {
return VBInputIterator<unum>(vec.end(), vec.end());
}
private:
std::vector<uint8_t> vec;
};

• Why naked pointers at all? This seems to go against 'robust and maintainable'. – David Mar 4 '18 at 9:19
• Apart from being reserved, prepending things to distinguish member variables (like "<underscore>" or "m<underscore>") only generates more work for you imo as it takes longer for autocomplete to be helpful. – yuri Mar 4 '18 at 10:09
• @David, Good point; it's why the rewritten version uses no pointers. – Edward Mar 4 '18 at 13:07