У очереди на обоих концах появилась обрезка с начала — за постоянное время

У очереди на обоих концах появилась обрезка с начала до заданной длины. Метод стабилен и работает за постоянное время для простых типов элементов.

Чем обходились раньше

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

Для простых типов элементов пересчёт сводится к сдвигу начала, то есть к одной операции. Но общий метод обрезки так не работает — он обязан поддерживать и конец, где элементы надо освобождать.

Что даёт

Отдельный метод для начала очереди, который не трогает конец. То есть удаление устаревших элементов из очереди — самая частая операция в очереди с ограничением по длине — становится операцией без обхода.

Оригинал

stabilize VecDeque::retain_back from truncate_front