Категория итератора для циклического буфера

Question

Я попытался реализовать циклический буфер следующего вида.

Для простоты я предполагаю, что циклический буфер - это просто адаптер контейнера (например, std::stack) для контейнеров, имеющих RandomAccessIterator . Контейнер изменял размер / заполнял значения каким-либо образом, затем вставлял в адаптер. После этого размер нижележащего контейнера не должен изменяться.

Очевидно c.begin() == c.end() для циклического буфера. Некоторые алгоритмы (скажем, диапазон на основе l oop) не работают должным образом для циклического буфера (вместо for (;;) можно использовать assert(!c.empty()); auto beg = std::begin(c), it = beg; do { f(it); } while (++it != beg); для обхода циклического буфера).

Основная проблема возникла, когда я Попробуйте отсортировать циклический буфер, используя std::sort. Наследование категории итераторов из нижележащего контейнера не справедливо для циклических буферных итераторов. Итератор циклического буфера должен быть почти RandomAccessIterator , но не строго по порядку (<, >, <=, >= не определены). Реализация std::sort может использовать operator < внутри (и делает).

Я не могу определить свою собственную категорию итераторов (скажем, ModularIterator ) и вставить ее между существующими категориями (например, что std::is_base_of_v<std::bidirectional_iterator_tag, my_iterator_tag> и std::is_base_of_v<my_iterator_tag, std::random_access_iterator_tag>). Также алгоритмы не являются точками настройки.

Я не хочу устанавливать iterator_category в std::bidirectional_iterator_tag, потому что std::equal_range не будет работать в логарифмическом c времени.

строгое общее упорядочение RandomAccessIterator действительно необходимо где-то в алгоритмах или его можно избежать?

Есть ли способ заставить <algorithm> s работать для циклического буфера?

в Стандарте упущено, что не существует категории итераторов, подходящей для неупорядоченных итераторов, которая может быть продвинута для любого шага для O(1)?

Пример: https://wandbox.org/permlink/GH1JF4WK2IUUCRHg

Answer 1

Очевидно c.begin() == c.end() для циклического буфера. Некоторые алгоритмы (скажем, диапазон на основе l oop) не работают должным образом для циклического буфера

Исправление: никакой алгоритм на основе диапазона не работает (значимо) для такого диапазона, потому что диапазон, где начинается и конечные итераторы одинаковые пустые. Это определение пустого диапазона.

Вам нужен итератор, который знает не только, какая позиция находится в буфере, но и какая цикл это на. Начальный итератор может находиться в позиционном индексе 0, цикл 0, в то время как конечный итератор находится в позиционном индексе 0, цикл 1. Два итератора будут не сравниваться равными. И когда вы увеличиваете итератор за границу цикла, он увеличивает счетчик циклов на 1. Обратное происходит для уменьшения значения за границей цикла.

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

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