Circular Buffer

1.

Circular buffer
Буфер фиксированного значения, который перебирает свои элементы по
циклу.
Презентацию оформил: Артем Быстров

2.

Пример использования на языке C++
Выход текущий программы:
34567
Циклический буфер работает
с добавлением новых записей в конец
за O(1) .Как только буфер достигнет фикси рованного значения старые записи
начнут удаляться за O(1).
Этот буфер занимает статическое
место в памяти, и очень полезен для
создания журналов, буферов хранения временной информации

3.

Пример реализации класса контейнера
Использованы специальные методы
для совместимости с range-based.
Использованы базовые методы для
работы с классом. end() begin() итераторы. size_all_data() размер
всех данных проходящих через буфер
за все время.
operator[] приватный, так как при
использовании цикла без итерации
ломается вся логика.

4.

Пример реализации класса итератора над ним
Имеет базовые функции
итератора:
разыменование,
сравнение итераторов.
Если пройти по
итератору: b.begin() <
b.begin() + 8 при Size=5
Вывод такой итерации:
12345123
При b.begin() < b. end():
12345 ( без повтора )

5.

Примеры использования
Логирование записей в журнал, для дальнешего мониторинга:
uid
name
data
4
5
6
7
8
Jane
Bill
Bill
MIke
Cristian
entry 871428989
entry 871429000
exit 871429002
entry 871429023
entry 871429029

6.

Оценка временной сложности
push_back(T&&)
Перемещение rvalue
Копирования lvalue
Сложность O(1)
pop_front()
Сложность О(1)
*вызывается автоматически*
back() top()
Сложность О(1)
operator[]
Сложность O(1)
*вызывается автоматически*
Итерация по N
элементов
O(N)

7.

Альтернативы
Pool Object (Пул объектов) - в этом случае задействован также статический
массив, но можно удалять любой элемент, и перезапись идёт именно в
свободную ячейку памяти от старого элемента либо в новую. Таким образ
работает запись на электронные носители на низком уровне, где статическая
память не сдвигается а использует занятые и незанятые ячейки памяти, там
где пусто хранится мусор от прошлых использований, и лишь при
добавлении элементов пул перезаписывается. Это позволяет удалять
элементы за O(1) а добавлять за O(1-N) в зависимости сколько будет
искаться пустая ячейка памяти.