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

Я создал простой кольцевой буфер, унаследовав std :: vector и перегрузив его operator [], чтобы модулировать желаемый индекс с размером вектора:

template <typename T>
class circvector : public std::vector<T> {
public:
    T& operator[](size_t index) { return *(this->data() + index%this->size()); };       // modulo index by vector size when accessing with [] operator
};

int main()
{
    circvector<int> buffer;                         // create a circvector
    buffer.resize(10);                              // resize it
    std::iota(buffer.begin(), buffer.end(), 0);     // fill with monotonically increasing integers

    for (int i = 0; i < buffer.size() * 2; i++)
        std::cout << buffer[i] << " ";              // access elements with [] beyond the circvector size is safe
}

который правильно производит вывод:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

Я также хотел бы создать «умный» итератор прямого ввода, который поддерживает оператор ++ (приращение) и оператор * (разыменование) и который автоматически «оборачивается» при продвижении мимо последнего элемента в векторе назад к началу базового вектора, с которым он связан.

Этот гипотетический итератор позволит, например, упростить выполнение некоторых функций в библиотеке алгоритмов (которые часто принимают итераторы в качестве аргументов) на подмножестве кругового вектора без добавления логики для проверки, а затем разделить на два отдельных вызова, когда желаемое подмножество охватывает конец-> начало обтекания кругового вектора.

Я читал о создании пользовательских итераторов, но описания становятся довольно запутанными с информацией, которая, по-видимому, удовлетворяет требованиям, которые я не думаю, которые мне нужны. Добавьте к этому обсуждение недавнего отказа от std :: iterator, и я не уверен, где даже начать создавать свой собственный итератор или связывать его с моим классом circvector.

Может ли кто-нибудь помочь мне начать работу с минимально работоспособным шаблоном?


c++ iterator stdvector circular-buffer
person NKatUT    schedule 16.11.2019    source источник
comment
Я предполагаю, что итератор над кольцевым буфером противоречит самой идее кольцевого буфера. Есть ли у std::stack begin и end? Кроме того, если он завершится, как некоторые алгоритмы узнают, где находится конец?   -  person zdf    schedule 16.11.2019
comment
Не теряйте время, используйте уже сделанный, например boost.org/doc/libs/1_71_0/doc/html/ round_buffer.html   -  person 4xy    schedule 16.11.2019
comment
@ZDF Я не понимаю, почему это противоречит идее. Что было бы так неправильно, если бы итерация выполнялась от элемента begin () + 8 до begin () + 12 и позволяла итератору автоматически получать доступ к базовым векторным элементам в начале вектора, даже если +12 в противном случае увеличился бы после последнего элемента в вектор? Кроме того, почему бы не разрешить итерацию от begin () до begin () + 100, если нужно выполнить итерацию по буферу 10 раз? Я согласен, что итератор end () не имеет большого смысла.   -  person NKatUT    schedule 17.11.2019
comment
@ 4xy Спасибо, я уже сталкивался с boost :: round_buffer раньше и решил, что могу просто подключить его и попробовать, но я также надеялся использовать это как возможность узнать больше о настраиваемых интеллектуальных итераторах, а также получить решение, которое только минимально изменено из std: vector, с которым я уже знаком.   -  person NKatUT    schedule 17.11.2019
comment
Практической пользы не вижу. Клиенту нужны push_back и pop_front.   -  person zdf    schedule 17.11.2019
comment
@ZDF Это определенно практическое применение ... Я выделяю весь буфер вначале с помощью .resize () или .assign (), и мне не нужно добавлять или удалять элементы, только заменяю их или получаю к ним доступ с помощью оператора [] или с моим (гипотетическим) итератором, если я хочу перейти с N-го элемента на N + M-й элемент. Методы push_back () и pop_front () просто вызовут базовые методы std :: vector по умолчанию и фактически изменят размер буфера, вместо того, чтобы добавлять или вычитать из него круговым способом, который предоставляет перегруженный оператор [].   -  person NKatUT    schedule 17.11.2019
comment
@ 4xy Похоже, итераторы boost :: round_buffer не демонстрируют требуемого мне поведения. Если вы продвинете boost :: round_buffer ‹› :: iterator за пределы размера round_buffer, он выйдет из строя с нарушением доступа для чтения.   -  person NKatUT    schedule 17.11.2019

Ответы (1)


arrow_upward
0
arrow_downward

Этот класс, похоже, обеспечивает желаемое поведение, хотя он наследуется от устаревшего класса std :: iterator:


template <typename T>
class circvector: public std::vector<T> {
public:
    T& operator[](size_t index_) { return *(this->data() + index_%this->size()); };     // modulo index_ by vector size when accessing with [] operator

    class iterator; // forward declaration

    iterator begin() { return circvector<T>::iterator(*this, 0); }
    iterator end() { return circvector<T>::iterator(*this, this->size()); } // will be same as begin() due to modulo in iterator constructor initializer list

private:

    class iterator : public std::iterator<std::output_iterator_tag, T> {
    private:
        circvector<T>& container_;      // NOTE: ORDER MATTERS! // dependency injection
        size_t index_{ 0 };         // NOTE: ORDER MATTERS! // state of iterator

    public:
        T& operator*() const { return container_[index_]; }                                     // this uses the overloaded operator[] which includes modulo
        iterator& operator+(int N) { index_ = (index_ + N) % container_.size(); return *this; } // random increment by N
        iterator& operator++() { index_ = (index_ + 1) % container_.size(); return *this; }     // increment with modulo
        iterator operator++(int) { return ++(*this); }                                              // just calls prefix increment: operator++()
        bool operator!=(const iterator & right) const { return index_ != right.index_ % container_.size(); }
        bool operator==(const iterator & right) const { return index_ == right.index_ % container_.size(); }
        explicit iterator(circvector<T>& container, size_t index_ = 0) : container_(container), index_(index_ % container_.size()) {}       // constructor
    };
};

Он был изменен с https://lorenzotoso.wordpress.com/2016/01/13/defining-a-custom-iterator-in-c/

Программа тестирования:

int main()
{
    circvector<int> buffer;
    buffer.assign({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });

    auto start_offset{ 8 };
    auto end_offset{ start_offset + 5 };

    for (int i = 0; i < buffer.size(); i++) std::cout << buffer[i] << " ";
    std::cout << "\n";
    std::for_each(buffer.begin() + start_offset, buffer.begin() + end_offset, [](auto& i) { i = 42; });
    for (int i = 0; i < buffer.size(); i++) std::cout << buffer[i] << " ";
}

создание вывода:

0 1 2 3 4 5 6 7 8 9
42 42 42 3 4 5 6 7 42 42

Использование алгоритмов от begin () до end (), конечно, больше не работает, поскольку begin () == end (). Но вы можете работать с частичными сегментами буфера, используя алгоритмы (например, std :: for_each, как показано), пока их длина на 1 меньше, чем полный размер буфера.

person NKatUT    schedule 17.11.2019