Контейнер C++ — переменная байт кодированных чисел


Я пишу контейнера для беззнаковых целых чисел, которое использует переменную байт кода. Он работает, но некоторые решения я принимал выглядят некрасиво, поэтому я был бы рад, если бы вы дали мне несколько советов по улучшению дизайна.

У меня есть несколько конкретных мест, чтобы получить комментарии по поводу:

  1. отбор и хранение ссылок в VBOutputIterator конструктор
  2. я должен DISALLOW_COPY_AND_ASSIGN в VBOutputIterator
  3. == оператор в VBInputIterator
  4. с помощью функций malloc, realloc и free в VBList (не могу придумать СТД::вектор решения)

Но общие рекомендации тоже приветствуется)

Кроме того, недавно наткнулся на объявление, где они необходимы, чтобы "иметь возможность писать надежный и простой в сопровождении код". Как вы думаете, это мой код надежными или ремонтопригоден? Как я могу сделать его больше, так?

VBInputIterator.ч

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.ч

#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.ч

#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;
            }
        }
    };

главная

#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



Комментарии
1 ответ

Вот некоторые вещи, которые могут помочь вам улучшить ваш код. Я начну с более общих вещей, а затем решить ваши конкретные вопросы.

Исправить ошибку

В VBInputIterator по умолчанию второго шаблонного класса num_t=unsigned. Это не обязательно является проблемой, но его использование в VBList ошибка:

typedef VBInputIterator<char*> iterator;

Проблема в том, что если мы будем хранить unsigned long long int как в вашем примере, полученный итератор будет использовать только unsigned что вызывает очень большие числа, такие как 11122233344455566677ULL будет отображаться как 1967613269..

Это должно быть вот так:

typedef VBInputIterator<char*, num_t> iterator;

Я вижу небольшое преимущество (и много недостатков, как показывает этот баг!) для обеспечения класса по умолчанию, поэтому я сторонник опуская его.

Убедитесь, что у вас есть все необходимое #includeС

В VBList код использует VBInputIterator но не #include "VBInputIterator".

Использовать <cstdio> вместо <stdio.h>

Разница между двумя формами в том, что первый определяет вещи в std:: против имен в глобальное пространство имен. Язык юристов иметь много веселья с этим, но для ежедневного использования я рекомендую использовать <cstdio>. Вижу это так вопрос для деталей. Впрочем, см. Следующий пункт.

Используйте только необходимое #includeС

Код в VBList.h есть #includeчто не нужны. В частности, ни <stdio.h> ни <vector> требуются, поэтому они могут быть исключены. Стоит отметить, что free фактически, определенные в <cstdlib> а не <cstdio>так, если вы собираетесь использовать сырье malloc и freeкод должен #include <cstdlib>. Впрочем, см. Следующий пункт.

Не используйте подчеркиваниями в именах

Что-либо с символа подчеркивания в глобальном пространстве-это зарезервированное имя в C++ (и C). См. Этот вопрос для деталей. Если вы действительно знаете о правилах языка, я бы посоветовал избегать подчеркивания в именах. По аналогичным причинам, я бы тоже избежать num_t введите имя в шаблонах.

Не злоупотреблять using namespace std

Положить using namespace std в верхней части каждая программа-это плохая привычка , что вы могли бы сделать хорошо, чтобы избежать. Я не знаю, что ты на самом деле сделал это, но использование сырья cout и endl в вашем примере программа предполагает, что вы можете иметь.

Переосмыслить интерфейс

Рассмотрим интерфейс VBList. Имеются конструкторы и деструктор, но только открытые интерфейсы push_back(num_t n) и begin() и end(). Этого может быть достаточно для некоторых узких целей, но это не так, например, возможность удаления номера из списка, за исключением, уничтожив весь список.

Предпочитаю new и delete для malloc и free

Современный C++, как правило, используют new вместо malloc. Это позволит исключить необходимость <cstdlib> и это более идиоматические с++. В этом случае я был бы склонен использовать std::vector и не все четыре. Как частично работал пример:

#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;
};

3
ответ дан 4 марта 2018 в 06:03 Источник Поделиться