Re: std::deque typically faster then std::list for push_back(), front(), pop_front()?
Victor V. Terber ha scritto:
In existing sources I found a std::list using only methods
push_back(), front() and pop_front(). I'm considering to replace the
list by std::deque.
The usual rule of thumb to use the simplest container that does the
job seems to apply here. I'm aware that the standard doesn't say much
about performance behavior, but due to various restrictions (client's
site, varying compilers, STLs, OS) actual measuring is very hard in
this case.
Does such a replacement of list by deque seem reasonable? Would you
typically expect real-world performance changes?
Of course, the only definitive answer comes from actual profiling, but
if all modifying operation you need are push_back() and pop_front() I
would expect deque to be more performant. Typically, the most expensive
operation in containers is the dynamic allocation/deallocation of memory
from the heap, while other book-keeping overhead can be almost
negligible. A list requires a dynamic allocation/deallocation for each
item inserted/extracted, while deque allocates memory in chunks suitable
to accommodate several objects. The chunk size is usually small enough
so that allocating a chunk nearly takes the same time as allocating a
single item, therefore having a smaller number of heap operations to
perform is definitely a plus.
HTH,
Ganesh
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]