I've read STL deque accessing by index is O(1)? and how does random access of an element in deque gives constant time complexity? and it still doesn't seem clear to me why O(1) random access is guaranteed.
I understand a deque in STL is implemented as an array of pointers to contiguous fixed size chunks. So I understand looping over a fixed size chunk is O(1) because it is independent of the size of the deque. But to find which chunk to loop over, we need to loop over an array of pointers, which I don't believe is an O(1) operation because the array of pointers is proportional to the size of the deque?
For example, if we have an n sized deque and the fixed chunk size is say, m, our array of pointers would be size ceiling(n/m), which is O(n)? Am I misunderstanding something?
