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: Ulrich Eckhardt on 10 Jan 2008 05:05 Victor V. Terber wrote: > 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. It seems to be used as a FIFO. For that, there is std::queue<>, which is itself a wrapper around a container. This doesn't change the code per se (except that you write push() and pop() instead of push_back() and pop_front()) but it documents the intention. > 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. With std::list<>, you typically have a doubly-linked list. With std::deque<>, you typically have a vector of pointers to chunks of N elements. So, when inserting a single element, you need to allocate a single node for the list while chances are good (1-1/N) that the actual chunk of the deque still has one element free. Now, in both cases you have two costs: A for the allocation and C for copying the element to the new location. Assuming the time it takes to allocate memory doesn't depend on the size, the cost for adding an element to a list is A+C while the average cost of adding it to a deque is A/N+C, because you only need to allocate every N times. > Does such a replacement of list by deque seem reasonable? Would you > typically expect real-world performance changes? Yes. Whether you can measure those changes is another question though. If the elements that are stored themselves require dynamic allocation (e.g. non-refcounted std::string) this will soon dwarf the overhead of the container's allocation. Uli -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |