3 ms·
There are actually implementations of deque which can store elements contiguously: imagine a vector where the "first element" is placed in the middle of the vec
by jemfinch 16y ago
There are actually implementations of deque which can store elements contiguously: imagine a vector where the "first element" is placed in the middle of the vector, and push_{front,back} reallocate whenever either end is reached. It wastes more memory than the typical deque implementation, but the elements are contiguous.
- georgecmu 16y agoYou still don't get O(1) insertions/deletions of arbitrary elements with this implementation. Insertions and deletions at either end are O(1), but inserting/deleting in the middle is costly.