should we prefer deque over vector

E

Earl Purple

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.
 
P

peter koch

Earl said:
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?
 
P

peter koch

Earl said:
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
 
P

peter koch

Earl said:
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
 
I

Ivan Vecerina

: 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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top