5
\$\begingroup\$

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)
            {
            _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;
    // 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

\$\endgroup\$
  • \$\begingroup\$ Any specific reason you're using malloc in a C++ project instead of new? \$\endgroup\$ – yuri Mar 3 '18 at 20:41
  • \$\begingroup\$ @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? \$\endgroup\$ – jazzandrock Mar 3 '18 at 21:14
  • \$\begingroup\$ Why do you pretend VB to each type name instead of using a namespace? \$\endgroup\$ – Cris Luengo Mar 3 '18 at 23:46
  • \$\begingroup\$ @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). \$\endgroup\$ – JNS Mar 8 '18 at 10:56
3
\$\begingroup\$

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) :
        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;
};
\$\endgroup\$
  • 1
    \$\begingroup\$ Why naked pointers at all? This seems to go against 'robust and maintainable'. \$\endgroup\$ – David Mar 4 '18 at 9:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – yuri Mar 4 '18 at 10:09
  • 1
    \$\begingroup\$ @David, Good point; it's why the rewritten version uses no pointers. \$\endgroup\$ – Edward Mar 4 '18 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.