trjhtr

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.

I have some specific places to get comments about:

1. taking and storing reference in VBOutputIterator constructor


2. should I DISALLOW_COPY_AND_ASSIGN in VBOutputIterator


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)
 = *_in;
 _n <<= 7;
 ++_in;
 
 _n 

 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] 

 // 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;
 // add to list
 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

Here are some things that may help you improve your code. I'll start with more general things and then address your specific questions.

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) :
 ptrptr,
 endend
 

 VBInputIterator &operator++() 
 for ( ; (ptr != end) && !(*ptr & 0x80) ; ++ptr) 
 
 if (ptr != end) 
 ++ptr;
 
 return *this; 
 
 unum operator*() const 
 unum val;
 for (auto pptr ; p != end; ++p) = (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) 0x80);
 for (n >>=7 ; n; n >>= 7) 
 temp.push_back(n & 0x7f);
 
 for (auto ittemp.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;
;