should we prefer deque over vector

[yancheng.cheok]

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). does it mean that we should
prefer deque over vector? (in contrast with c++ standard, which
recommence vector over deque)

thanks!

[Earl Purple]

ya************@ gmail.com wrote:

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). does it mean that we should
prefer deque over vector? (in contrast with c++ standard, which
recommence vector over deque)

deque is better if you are going to do inserts or removes at both ends.
vector is better is better if you only insert and remove at the back.

[peter koch]

Earl Purple wrote:

ya************@ gmail.com wrote:

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). does it mean that we should
prefer deque over vector? (in contrast with c++ standard, which
recommence vector over deque)

deque is better if you are going to do inserts or removes at both ends.

Also much nicer behaviour in case capacity needs to change and lower
memory requirements.

vector is better is better if you only insert and remove at the back.

In what way? You mean to say that indexing is faster?

[peter koch]

Earl Purple wrote:

ya************@ gmail.com wrote:

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). does it mean that we should
prefer deque over vector? (in contrast with c++ standard, which
recommence vector over deque)

deque is better if you are going to do inserts or removes at both ends.

Also much nicer behaviour in case capacity needs to change and lower
memory requirements.

vector is better is better if you only insert and remove at the back.

In what way? You mean to say that indexing is faster?
Peter

[peter koch]

Earl Purple wrote:

ya************@ gmail.com wrote:

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). does it mean that we should
prefer deque over vector? (in contrast with c++ standard, which
recommence vector over deque)

deque is better if you are going to do inserts or removes at both ends.

Also much nicer behaviour in case capacity needs to change and lower
memory requirements.

vector is better is better if you only insert and remove at the back.

In what way? You mean to say that indexing is faster?

/Peter

[Ivan Vecerina]

<ya************ @gmail.comwrote in message
news:11******** **************@ k70g2000cwa.goo glegroups.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