Created
December 20, 2021 03:08
-
-
Save TonyDecvA180XN/2fdca671d3b7f264ddbea6e14816bf7d to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <utility> | |
| #include <optional> | |
| #include <cassert> | |
| // Сделать класс шаблонным для любых типов данных | |
| template <class T, class Allocator = std::allocator<T>> | |
| class CyclicBufferRanged | |
| { | |
| public: | |
| // Запретить создание буфера если не указана вместимость | |
| CyclicBufferRanged() = delete; | |
| // Создать буфер указанного размера. Аллокатор автоматически выделит необходимое место | |
| CyclicBufferRanged(size_t capacity) : | |
| Capacity(capacity), | |
| Buffer(ContainerAllocator.allocate(capacity)) | |
| {} | |
| ~CyclicBufferRanged() | |
| { | |
| ContainerAllocator.deallocate(Buffer, Capacity); | |
| Buffer = nullptr; | |
| } | |
| // Поместить елемент в буфер вернуть true. Если буфер заполнен, вернуть false | |
| bool Insert(T element) | |
| { | |
| if (GetSize() >= Capacity) return false; | |
| // Нормализовать индекс головы буфера и переместить в него элемент | |
| Buffer[Head % Capacity] = std::move(element); | |
| // Передвинуть голову буфера | |
| ++Head; | |
| return true; | |
| } | |
| // Попытаться извлечь эелемент из буффера и вернуть его. Если буфер пуст, вернуть std::nullopt | |
| std::optional<T> Extract() | |
| { | |
| if (GetSize()) // Буфер не пустой? | |
| { | |
| T element = std::move(Buffer[Tail]);// Извлечь элемент из буфера | |
| ++Tail; // Передвинуть хвост | |
| // Сдвинуть голову и хвост на один буфер вниз | |
| if (Tail >= Capacity) | |
| { | |
| Tail -= Capacity; | |
| Head -= Capacity; | |
| } | |
| return std::make_optional(element); | |
| } | |
| else | |
| { | |
| return std::nullopt; | |
| } | |
| } | |
| // Количество хранимых элементов равно разнице индексов головы и хвоста | |
| size_t GetSize() { return Head - Tail; } | |
| size_t GetCapacity() { return Capacity; } | |
| private: | |
| Allocator ContainerAllocator{}; | |
| T* Buffer{ nullptr }; | |
| size_t Capacity; | |
| size_t Head{ 0 }, Tail{ 0 }; | |
| }; | |
| // Сделать класс шаблонным для любых типов данных | |
| template <class T, class Allocator = std::allocator<T>> | |
| class CyclicBufferSized | |
| { | |
| public: | |
| // Запретить создание буфера если не указана вместимость | |
| CyclicBufferSized() = delete; | |
| // Создать буфер указанного размера. Аллокатор автоматически выделит необходимое место | |
| CyclicBufferSized(size_t capacity) : | |
| Capacity(capacity), | |
| Buffer(ContainerAllocator.allocate(capacity)) | |
| {} | |
| ~CyclicBufferSized() | |
| { | |
| ContainerAllocator.deallocate(Buffer, Capacity); | |
| Buffer = nullptr; | |
| } | |
| // Поместить елемент в буфер вернуть true. Если буфер заполнен, вернуть false | |
| bool Insert(T element) | |
| { | |
| if (Size >= Capacity) return false; | |
| // Найти конец очереди и поместить в него эелемент | |
| Buffer[(Start + Size) % Capacity] = std::move(element); | |
| ++Size; | |
| return true; | |
| } | |
| // Попытаться извлечь эелемент из буффера и вернуть его. Если буфер пуст, вернуть std::nullopt | |
| std::optional<T> Extract() | |
| { | |
| if (GetSize()) | |
| { | |
| T element = std::move(Buffer[Start]); // Извлечь елемент из буффера | |
| --Size; // Уменьшить размер буфера | |
| ++Start; // Передвинуть начало очереди | |
| Start %= Capacity; // Циклически сбросить начало очереди если оно достигло конца массива | |
| return std::make_optional(element); | |
| } | |
| else | |
| { | |
| return std::nullopt; | |
| } | |
| } | |
| // Размер просто хранится как переменная | |
| size_t GetSize() { return Size; } | |
| size_t GetCapacity() { return Capacity; } | |
| private: | |
| Allocator ContainerAllocator{}; | |
| T* Buffer{ nullptr }; | |
| size_t Capacity; | |
| size_t Start{ 0 }, Size{ 0 }; | |
| }; | |
| int main() | |
| { | |
| // Тестирование. Раскомментировать один из буфферов | |
| //CyclicBufferRanged<int> b{ 4 }; | |
| CyclicBufferSized<int> b{ 4 }; | |
| assert(!b.Extract().has_value()); | |
| assert(b.Insert(3)); | |
| assert(b.Insert(5)); | |
| assert(b.Insert(42)); | |
| assert(b.Insert(42)); | |
| assert(!b.Insert(999)); | |
| assert(b.Extract().value_or(-1) == 3); | |
| assert(b.Extract().value_or(-1) == 5); | |
| assert(b.Insert(77)); | |
| assert(b.Insert(84)); | |
| assert(!b.Insert(111)); | |
| assert(b.Extract().value_or(-1) == 42); | |
| assert(b.Extract().value_or(-1) == 42); | |
| assert(b.Extract().value_or(-1) == 77); | |
| assert(b.Extract().value_or(-1) == 84); | |
| for (size_t i = 0; i < 30; i++) | |
| { | |
| assert(b.Insert(11)); | |
| assert(b.Extract().has_value()); | |
| } | |
| assert(!b.Extract().has_value()); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment