How does a std::deque achieve O(1) time complexity when inserting at the front of the queue?

Question

std::deque in C++ internally uses a segmented array, so how does it maintain O(1) time complexity when inserting at the front of the deque?

Segmented arrays break down the big array into smaller ones, but inserting at the front in the segmented array can also be a time-consuming task. I am unsure how does std::deque maintains O(1) time. Or it take segmented size time?

Exarchate

Big-O is about asymptotic behaviour at infinity. A segment of a fixed size is nothing compared to infinity. – Illconsidered

Real answer? It doesn’t. For details see the comment discussion at https://mcmap.net/q/109492/-what-really-is-a-deque-in-stl. – Communicative

@KonradRudolph this answer details a scheme where it is (amortized) O(1): https://mcmap.net/q/109492/-what-really-is-a-deque-in-stl Are you implying that there are implementations that don't meet the requirements? – Esquiline

@Esquiline Actually my own answer’s graphic shows exactly that implementation. But somehow I hadn’t thought about (or forgot) it in the subsequent discussion, and assumed that the map (“outer vector”) was filled from index 0 rather than growing from the middle out. I’d need to think about this more carefully and don’t have the time now. But it does sound as if this strategy would achieve amortised O(1) runtime for both growth directions, and would maintain O(1) index access time. – Communicative

@KonradRudolph In the standard, complexity is stated in terms of operations on T (so in this case, construction, destruction, copying and moving) see. Other operations, such as copying pointers to T, do not count. – Illconsidered

@n.m.couldbeanAI I’m aware, in fact this is also being discussed in the linked comments. – Communicative

A similar question: #22307449 – Miter