So the basic sequenced C++ containers are
vector - holds data in a contiguous memory block that has the same memory footprint as a classical array. Expensive to insert or delete at the front or in the middle as it involves copying to maintain the memory layout, can be expensive to append to the end if it involves reallocating memory, never releases memory once allocated without user intervention. Has random access and therefore random access iterators. Should be the default container of choice unless a specific design decision can be found to use another container type.
deque - holds data in blocks of allocated memory, quick to insert or delete and beginning or end, deletion/insertion in the middle is slow. Has random access and therefore random access iterators.
list - holds data in individually allocated blocks of memory, quick to insert or delete and beginning, end or in the middle also quick to sort/reorder as these just involve swapping pointer values not objects. Does not have random access and therefore does not have random access iterators only sequential iterators.
The derived sequential contains, queue, priority_queue and stack are all implemented as adaptors of one of the basic sequential containers as follows
queue adapts deque
priority_queue adapts vector
stack adapts deque
Note that these adaptions are not fixed but are actually passed as template parameters.
So my question boils down to the queue adaption of deque.
queue interface member functions are
empty Test whether container is empty
size Return size
front Access next element
back Access last element
push Insert element implemented as push_back
pop Delete next element implemented as pop_front
In fact both deque and list have the correct members to be able to implement the queue adaptor. They also both seem to have good efficiency for the operations required. So the question is (finally after that long post :D )...
Why is the default queue implemented as an adaption of deque rather than an adaption of list? What is the design decision that makes deque the better choice in this case?
vector - holds data in a contiguous memory block that has the same memory footprint as a classical array. Expensive to insert or delete at the front or in the middle as it involves copying to maintain the memory layout, can be expensive to append to the end if it involves reallocating memory, never releases memory once allocated without user intervention. Has random access and therefore random access iterators. Should be the default container of choice unless a specific design decision can be found to use another container type.
deque - holds data in blocks of allocated memory, quick to insert or delete and beginning or end, deletion/insertion in the middle is slow. Has random access and therefore random access iterators.
list - holds data in individually allocated blocks of memory, quick to insert or delete and beginning, end or in the middle also quick to sort/reorder as these just involve swapping pointer values not objects. Does not have random access and therefore does not have random access iterators only sequential iterators.
The derived sequential contains, queue, priority_queue and stack are all implemented as adaptors of one of the basic sequential containers as follows
queue adapts deque
priority_queue adapts vector
stack adapts deque
Note that these adaptions are not fixed but are actually passed as template parameters.
So my question boils down to the queue adaption of deque.
queue interface member functions are
empty Test whether container is empty
size Return size
front Access next element
back Access last element
push Insert element implemented as push_back
pop Delete next element implemented as pop_front
In fact both deque and list have the correct members to be able to implement the queue adaptor. They also both seem to have good efficiency for the operations required. So the question is (finally after that long post :D )...
Why is the default queue implemented as an adaption of deque rather than an adaption of list? What is the design decision that makes deque the better choice in this case?
Comment