Требования к сложности для std::deque::push_back/front

В результате этого вопроса, заданного несколько дней назад, есть несколько вещей, которые не дают мне покоя в отношении требований к сложности для std::deque::push_back/push_front по сравнению с реальными std::deque реализациями в природе.

Итогом предыдущего вопроса было то, что эти операции должны иметь O(1) сложность в худшем случае. Я убедился, что это действительно так в c++11:

из 23.3.3.4 модификаторы deque, относящиеся к insert, push/emplace front/back

Сложность: Сложность линейна в количестве вставленных элементов плюс меньшее из расстояний до начала и конца deque. Вставка одного элемента в начало или конец deque всегда занимает постоянное время и

Это сочетается с O(1) требованием сложности для индексации, через operator[] и т.д.

Проблема в том, что реализации не строго удовлетворяют этим требованиям.

С точки зрения msvc и gcc реализация std::deque представляет собой блокированную структуру данных, состоящую из динамического массива указателей на блоки (фиксированного размера), где каждый блок хранит некоторое количество элементов данных.

В худшем случае, push_back/front и т.д. может потребовать выделения дополнительного блока (что нормально - выделение блоков фиксированного размера - это O(1)), но это также может потребовать изменения размера динамического массива указателей блоков - это не нормально, поскольку это O(m), где m - количество блоков, что в конечном итоге O(n).

Очевидно, что это все еще амортизированная O(1) сложность, и поскольку в общем случае m , на практике это будет довольно быстро. Но, похоже, есть проблема с соответствием?

В качестве дальнейшего пункта, я не вижу, как можно спроектировать структуру данных, которая строго удовлетворяет O(1) сложности как для push_back/front etc, так и для operator[]. Можно иметь связанный список блочных указателей, но это не дает желаемого поведения operator[]. Можно ли это сделать?