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 Deque maintains O(1) time. Or it take segmented size time?