<yancheng.cheok@gmail.comwrote in message
news:1158229557.206084.224760@k70g2000cwa.googlegr oups.com...
: after reading
http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp,
:
: i realize that deque has its own speed advantage over vector in all
the
: aspect (except for memory deallocation).
When reading that article, you should pay attention to two things:
- its focus is really on collection creation and disposal.
- it studies collections of hundreds of thousands of items.
- it says nothing about how the code was compiled: were
optimizations enabled? I expect that std::vector will
perform better in optimized mode than std::deque.
[ this will be especially true if the author used
the debug-enabled standard library of Visual Studio ]
For small object collection, std::vector is just simpler.
It inter-operates more easily with legacy code or libraries
that expect contiguous arrays of data. Contiguous storage
also tends to provide better performance when processing
collections of numeric data.
std::deque might waste large amounts of memory when it stores
a small collection (some implementations may allocate chunks of
hundreds of items at a time, even when only 1 element is stored).
Iterators for std::deque typically cause a performance overhead
(both in space and time).
Maybe more importantly, any insert/erase anywhere in a deque
(even push/pop at either end) will invalidate all iterators.
std::vector is more controllable and predictable in terms
of iterator invalidation.
: does it mean that we should
: prefer deque over vector? (in contrast with c++ standard, which
: recommence vector over deque)
The real point is: you should care in the first place for the
operations that are supported by the container, not for "speed"
is some random benchmark. Most C++ developers still tend to think
in terms of arrays when they use sequence containers, and
std::vector is the simplest container that fulfills this need.
In practice, I only use std::deque:
- when I need to implement a queue / fifo buffer
(that's what deque is best at).
- for stack-like buffers that I know will be very large,
and when testing has demonstrated that deque does
indeed tend to perform better than std::vector.
- possibly as well want push_back to never invalidate
item references (this is guaranteed by deque if only
push/pop_front/back are used).
hth -Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
