std::deque typically faster then std::list for push_back(), front(), pop_front()?
in [C++]
|
Prev: std::deque typically faster then std::list for push_back(), front(), pop_front()?
Next: std::deque typically faster then std::list for push_back(), front(), pop_front()?
From: Alberto Ganesh Barbati on 10 Jan 2008 05:07 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! ] |