Пример добавления поддержка итераторов STL в пользовательский класс коллекции


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

В коллекции используется кольцевой буфер, это просто игрушка для того, чтобы помочь мне выучить соответствующих концепций. Когда у меня есть лучшее понимание этих понятий, я намерен ретро-фит схожее API к серии пользовательские классы коллекций в существующий большой объем кода.

/**
 * Name        : RingQueue.cpp
 * Author      : Some Guy
 * Version     :
 * Copyright   : Copyleft 2018 Some Guy. No rights reserved.
 * Description : A ring buffer with STL iterators in C++.
 */

#include <iostream>
#include <sstream>
#include <iterator>
#include <cassert>

template <typename T, int capacity> class RingIter;
template <typename T, int capacity> class RingIterConst;

template <typename T, int capacity> class RingQueue {
    friend class RingIter<T, capacity>;
    friend class RingIterConst<T, capacity>;
    typedef RingIter<T, capacity> iterator;
    typedef RingIterConst<T, capacity> const_iterator;
private:
    T buf[capacity];
    int begin_idx;
    int siz;

    int end_idx() { return (begin_idx + siz) % capacity; }
public:
    RingQueue() : begin_idx(0), siz(0) {}
    ~RingQueue() {}
    int size() const { return siz; }
    T &front() {
        if (siz) {
            return buf[begin_idx];
        } else {
            throw std::invalid_argument("RingQueue is empty");
        }
    }
    const T &front() const {
        if (siz) {
            return buf[begin_idx];
        } else {
            throw std::invalid_argument("RingQueue is empty");
        }
    }
    T &back() {
        if (siz) {
            return buf[end_idx()];
        } else {
            throw std::invalid_argument("RingQueue is empty");
        }
    }
    const T &back() const {
        if (siz) {
            return buf[end_idx()];
        } else {
            throw std::invalid_argument("RingQueue is empty");
        }
    }
    T &pop_front() {
        if (!siz) {
            throw std::invalid_argument("RingQueue is empty");
        }
        T &ret = buf[begin_idx];
        begin_idx++;
        begin_idx %= capacity;
        siz--;
        return ret;
    }
    void push_back(T val) {
        buf[end_idx()] = val;
        if (siz < capacity) {
            siz++;
        } else {
            begin_idx++;
            begin_idx %= capacity;
        }
    }
    iterator begin() { return iterator(*this, 0); }
    iterator end() { return iterator(*this, siz); }
    const_iterator cbegin() const { return const_iterator(*this, 0); }
    const_iterator cend() const { return const_iterator(*this, siz); }
    iterator rbegin() { return iterator(*this, siz - 1, -1); }
    iterator rend() { return iterator(*this, -1, -1); }
    const_iterator crbegin() const { return const_iterator(*this, siz - 1, -1); }
    const_iterator crend() const { return const_iterator(*this, -1, -1); }
};

template <typename T, int capacity> class RingIterConst {
    typedef RingIterConst<T, capacity> thisclass;
protected:
    const RingQueue<T, capacity> &rq;
    int off;
    int inc;
    inline const T& deref() { return rq.buf[(rq.begin_idx + off) % capacity]; }
public:
    RingIterConst(const RingQueue<T, capacity> &iterateOver, int offset, int increment = 1) : rq(iterateOver), off(offset), inc(increment) {}
    ~RingIterConst() {}
    bool operator==(const RingIterConst &i) {
        return &i.rq == &rq && i.off == off;
    }
    bool operator!=(const RingIterConst &i) {
        return !(*this == i);
    }
    thisclass & operator++()    { off += inc; return *this; }
    thisclass & operator++(int) { off += inc; return *this; }
    thisclass & operator--()    { off -= inc; return *this; }
    thisclass & operator--(int) { off -= inc; return *this; }
    typename std::iterator_traits<thisclass>::difference_type operator-(thisclass &sibling) const { return (off - sibling.off) / inc; }
    thisclass & operator+=(int amount) { off += (amount * inc); return *this; }
    thisclass & operator-=(int amount) { off -= (amount * inc); return *this; }
    thisclass & operator-() { return thisclass(rq, off, -inc); }
    bool operator<(thisclass &sibling) const { return (inc < 0) != (off < sibling.off);}
    bool operator<=(thisclass &sibling) const { return (inc < 0) != (off <= sibling.off); }
    bool operator>(thisclass &sibling) const { return (inc < 0) != (off > sibling.off); }
    bool operator>=(thisclass &sibling) const { return (inc < 0) != (off >= sibling.off); }
    const T& operator[](int index) {
        assert(index >= 0);
        assert(index < rq.siz);
        return rq.buf[(rq.begin_idx + off + (index * inc)) % capacity];
    }
    const T& operator*() { return deref(); }
};

template <typename T, int capacity> class RingIter : public RingIterConst<T, capacity> {
public:
    RingIter(RingQueue<T, capacity> &iterateOver, int offset) : RingIterConst<T, capacity>(iterateOver, offset) {}
    ~RingIter() {}
    T& operator[](int index) { return this->rq.buf[(this->rq.begin_idx + this->off + (index * this->inc)) % this->capacity]; }
    T &operator*() { return this->deref(); }
};

// FIXME: Do not pollute namespace 'std'.
namespace std {
template<typename T, int capacity> class iterator_traits<RingIterConst<T, capacity> > {
public:
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef std::random_access_iterator_tag iterator_category;
};
template<typename T, int capacity> class iterator_traits<RingIter<T, capacity> > : public iterator_traits<RingIterConst<T, capacity> > {
    typedef const T value_type;
    typedef const T* pointer;
    typedef const T& reference;
};
}

int main(void) {
    RingQueue<int, 4> rq;
    for (int i = 0; i < 10; i++) {
        rq.push_back(i * i);
    }
    assert(rq.size() == 4);
    std::ostringstream s;
    std::copy(rq.cbegin(), rq.cend(), std::ostream_iterator<const int>(s, " "));
    assert(s.str() == "36 49 64 81 ");
    s.str("");
    std::copy(rq.crbegin(), rq.crend(), std::ostream_iterator<const int>(s, " "));
    assert(s.str() == "81 64 49 36 ");
    return 0;
}


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

Быть последовательным с back()

end_idx() должны соответствовать следующим ввода установки или последнего ввода позиции. Простой тест push_back() и back() показывает, как они не последовательны.

Это может быть исправлено путем внесения end_idx ссылаться на последний элемент добавлен, и перед приращением перед установкой.

Обеспечить begin()/end()/rbegin()/rend() для постоянной коллекции.

Вы хотите быть в состоянии написать функцию вроде

template<typename T, std::size_t Capacity>
std::string to_string(const RingIter<T,Capacity>& ring)
{
std::ostringstream s;
std::copy(ring.begin(), ring.end(), std::ostream_iterator<const T>(s, " "));
return s.str();
}

и вы хотите быть в состоянии написать for (auto& element: ring) без прыжки через обручи.

Постинкремент и postdecrement неправильно реализован

++ и ++(int) не должна же здесь (и g++ -Weffc++ предупреждает об этом):

thisclass & operator++()    { off += inc; return *this; }
thisclass & operator++(int) { off += inc; return *this; }
thisclass & operator--() { off -= inc; return *this; }
thisclass & operator--(int) { off -= inc; return *this; }

Я ожидал

thisclass & operator++()    { off += inc; return *this; }
thisclass operator++(int) { auto t = *this; off += inc; return t; }
thisclass & operator--() { off -= inc; return *this; }
thisclass operator--(int) { auto t = *this; off -= inc; return t; }

Конечно, возвращаясь по стоимости будет включать нарезки для неконстантной подкласс, так что потребуется (разумеется) перегрузки есть.

Реляционные операторы не должны принимать изменяемые аргументы Реф

Вместо

bool operator<(thisclass &sibling) const;

Я ожидал

bool operator<(thisclass const& sibling) const;

То же самое касается operator-() что делает еще thisclass.

Оператор индексирования

Я не видел оператор индексирования на итератор раньше, но вы могли бы упростить это только с помощью ожидания программиста:

const T& operator[](int index) {
return *(*this + index);
}

Обратите внимание, что assert() это нормально для документирования инварианты, но очень плохой аргумент для проверки.

Использовать std::size_t для размеров и индексов

Кто хочет набор ограничен диапазоном int?

Итератор направление никогда не меняется

Мы можем объявить inc чтобы быть постоянным. Это не влияет на нашу способность присваивать значения, как мы уже содержать эталонный элемент.

Не нужно объявлять деструктор

Деструкторы итераторы' ничего не делать, так просто пусть компилятор по умолчанию их.

Неконстантный итератор вполне непроверен

Мы никогда не компилировать любой код, используя не-const версия итератора. Даже его конструктор нарушается:

189380.cpp:83:32: error: no matching function for call to ‘RingIter<int, 4>::RingIter(RingQueue<int, 4>&, int, int)’
iterator rbegin() { return iterator(*this, siz - 1, -1); }
^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Нам нужно, чтобы добавить последний аргумент

RingIter(RingQueue<T, capacity> &iterateOver, int offset, int increment = 1)
: RingIterConst<T, capacity>(iterateOver, offset, increment)
{}

Его iterator_traits членами Совета являются все частные, поэтому непригодным.

Гипс является обязательным в operator*:

T &operator*() { return const_cast<T&>(this->deref()); }


Альтернативная реализация

Вместо того, чтобы держать ссылку на контейнер, мы можем более просто держать указатель/ссылку на ее буфера в итераторе. Мы должны провести фактический индекс (мод capacity), а не смещение от контейнера текущей конечной точки, но это не сложно:

template <typename T, int capacity>
class RingIter
{
T *const buf;
int off;
int const inc;

public:
RingIter(T *buf, int offset, int increment = 1)
: buf(buf), off(offset), inc(increment)
{}
//...
};

Мы можем повторно использовать для обоих const и неconst итераторы такой:

template <typename T, int capacity>
class RingQueue
{
public:
typedef RingIter<T, capacity> iterator;
typedef RingIter<const T, capacity> const_iterator;

iterator begin() { return {buf, begin_idx}; }
iterator end() { return {buf, begin_idx + siz}; }
const_iterator cbegin() const { return {buf, begin_idx}; }
const_iterator cend() const { return {buf, begin_idx + siz}; }
iterator rbegin() { return {buf, begin_idx + siz - 1, -1}; }
iterator rend() { return {buf, begin_idx - 1, -1}; }
const_iterator crbegin() const { return {buf, begin_idx + siz - 1, -1}; }
const_iterator crend() const { return {buf, begin_idx - 1, -1}; }
};

Теперь итератор не надо быть friend (но при этом необходимо сотрудничество с контейнера, который должен выдать указатель на внутренний буфер), и мы должны поддерживать только один итератор шаблон (который может одинаково хорошо пункт const или неconst тип T).

Рассмотрим std::reverse_iterator

Упростить итератора с помощью std::reverse_iterator<RingIter<...>> адаптировать свой произвольного доступа итератор для обратной операции, в качестве стандартной библиотеки реализаций. Это означает, что итераторы не нужны inc члены указывают их направление.


Полный пример

#include <iterator>

template <typename T, std::size_t Capacity>
class RingIter;

template <typename T, std::size_t Capacity>
class RingQueue
{
private:
T buf[Capacity];
std::size_t begin_idx;
std::size_t siz;

T& last_val() { return buf[(begin_idx + siz - 1) % Capacity]; }

public:
using iterator = RingIter<T, Capacity>;
using const_iterator = RingIter<const T, Capacity>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

RingQueue()
: begin_idx(0), siz(0)
{}

std::size_t size() const { return siz; }
bool empty() const { return siz; }
T &front() { return buf[begin_idx]; }
const T &front() const { return buf[begin_idx]; }
T &back() { return last_val(); }
const T &back() const { return last_val(); }

T &pop_front() {
T &ret = buf[begin_idx++];
begin_idx %= Capacity;
--siz;
return ret;
}
void push_back(const T& val) {
if (siz < Capacity) {
++siz;
} else {
++begin_idx %= Capacity;
}
last_val() = val;
}
void push_back(T&& val) {
if (siz < Capacity) {
++siz;
} else {
++begin_idx %= Capacity;
}
last_val() = std::move(val);
}

iterator begin() { return { buf, begin_idx }; }
iterator end() { return {buf, begin_idx + siz}; }
const_iterator begin() const { return {buf, begin_idx}; }
const_iterator end() const { return {buf, begin_idx + siz}; }
const_iterator cbegin() const { return begin(); }
const_iterator cend() const { return end(); }

reverse_iterator rbegin() { return reverse_iterator{end()}; }
reverse_iterator rend() { return reverse_iterator{begin()}; }
const_reverse_iterator rbegin() const { return const_reverse_iterator{end()}; }
const_reverse_iterator rend() const { return const_reverse_iterator{begin()}; }
const_reverse_iterator crbegin() const { return rbegin(); }
const_reverse_iterator crend() const { return rend(); }
};

template <typename T, std::size_t Capacity>
class RingIter
{
T *const buf;
std::size_t off;
public:
RingIter(T *buf, std::size_t offset)
: buf(buf), off(offset)
{}
bool operator==(const RingIter &i) {
return &i.buf == &buf && i.off == off;
}
bool operator!=(const RingIter &i) {
return !(*this == i);
}
RingIter & operator++() { ++off; return *this; }
RingIter operator++(int) { auto t = *this; ++off; return t; }
RingIter & operator--() { --off; return *this; }
RingIter operator--(int) { auto t = *this; --off; return t; }
std::ptrdiff_t operator-(RingIter const& sibling) const { return off - sibling.off; }
RingIter & operator+=(int amount) { off += amount; return *this; }
RingIter & operator-=(int amount) { off -= amount; return *this; }
bool operator<(RingIter const&sibling) const { return off < sibling.off;}
bool operator<=(RingIter const&sibling) const { return off <= sibling.off; }
bool operator>(RingIter const&sibling) const { return off > sibling.off; }
bool operator>=(RingIter const&sibling) const { return off >= sibling.off; }
T& operator[](int index) const { return *(*this + index); }
T& operator*() const { return buf[off % Capacity]; }
};

namespace std {
template<typename T, std::size_t Capacity>
class iterator_traits<RingIter<T,Capacity> >
{
public:
using difference_type = std::ptrdiff_t;
using size_type = std::size_t;
using value_type = T;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
};
}

#include <cassert>
#include <iostream>
#include <sstream>
int main(void) {
RingQueue<int, 4> ring;
for (int i = 0; i < 10; i++) {
ring.push_back(i * i);
}
assert(ring.size() == 4);
assert(ring.front() == 36);
assert(ring.back() == 81);
std::ostringstream s;
std::copy(ring.cbegin(), ring.cend(), std::ostream_iterator<const int>(s, " "));
assert(s.str() == "36 49 64 81 ");
s.str("");
std::copy(ring.rbegin(), ring.rend(), std::ostream_iterator<const int>(s, " "));
assert(s.str() == "81 64 49 36 ");

auto const& ro_ring = ring;
s.str("");
std::copy(ro_ring.cbegin(), ro_ring.cend(), std::ostream_iterator<const int>(s, " "));
assert(s.str() == "36 49 64 81 ");
s.str("");
std::copy(ro_ring.rbegin(), ro_ring.rend(), std::ostream_iterator<const int>(s, " "));
assert(s.str() == "81 64 49 36 ");
return 0;
}

2
ответ дан 12 марта 2018 в 02:03 Источник Поделиться

Избежать повторения себя

По моим подсчетам у вас 5 повторений кода, чтобы гарантировать, что коллекция не пуста, прежде чем делать что функция предназначена, чтобы сделать.

Я бы двигаться, что код в одну функцию, а другие называют это:

void assure_non_empty() const { 
if (siz == 0)
throw std::invalid_argument("RingQueue is empty");
}

const T &back() const {
assure_non_empty();
return buf[end_idx()];
}

const T &front() const {
assure_non_empty();
return buf[begin_idx];
}

// and so on

Выбор исключений

Я тоже немного меньше, чем уверен, что std::invalid_argument правильное исключение, чтобы бросить в этих обстоятельствах. Вы можете возразить, что участвуют действительно недопустимый аргумент (с this передается как скрытый аргумент в функцию-член), но, по крайней мере для меня он "чувствует" неправильно, чтобы бросить invalid_argument из функции, которая на самом деле не брать явный аргумент.

2
ответ дан 12 марта 2018 в 01:03 Источник Поделиться