frankzhu_2001 wrote: > I know STL's deque has O(1) in insert/delete and access. How is it > implemented? I don't quite follow the source code. >
Without looking at the source (and really only the interface is dictated by the standard, implementations may vary), I would say a linked list. Access is constant because both the front and the back have references in the container, so this is simply following a pointer. Insert and delete are also constant because of these direct accesses, and because the nodes may be anywhere in memory: this differs from an array where modifications on one end (index 0) would require reallocation. -- John Gaughan http://www.jtgprogramming.org/
