deque VS vector
todd niec
but I though Herb Sutter propsed treating deque as the default since
it is often faster and more memory efficient. And that vector should
be used only when the data needs to be in a contiquous array in
memory. But I've been told that his latest books says to use vector
as the default. true? not true? arguments on either side?
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Aaron Isotton
> Which should be the "default" container. The standard says vector,
> but I though Herb Sutter propsed treating deque as the default since
> it is often faster and more memory efficient. And that vector should
> be used only when the data needs to be in a contiquous array in
> memory. But I've been told that his latest books says to use vector
> as the default. true? not true? arguments on either side?
I haven't read any of Herb Sutter's books, so I don't know what he said.
IMHO, there is no "default" container because there is no default use
for it. Each container has its own advantages and disadvantages, and
should be used in situations where its advantages prevail over its
disadvantages. I mostly use vectors and lists because vectors are the
fastest to iterate over and lists are the fastest for insertions and
deletions.
With nowadays' computers memory is often (not always, though) not a
problem if the data sets are small. So I don't see what's wrong with
vectors.
Aaron
Herb Sutter
>Which should be the "default" container. The standard says vector,
>but I though Herb Sutter propsed treating deque as the default since
>it is often faster and more memory efficient. And that vector should
>be used only when the data needs to be in a contiquous array in
>memory. But I've been told that his latest books says to use vector
>as the default. true? not true? arguments on either side?
Yes, I changed that advice from the column to the book. I originally
recommended that you consider using deque by default, unless you needed the
extra performance at the cost of potentially slightly more user code
complexity. The book still presents deque in a good light and encourages you
to know about it and consider it, but it returns to recommending using
vector by default.
I continue to believe that deque is simpler to use from the point of view
that you don't need to know about reserve() -- forgetting about that won't
hurt you the way it can with vector. Granted, that may be a fairly small
advantage for most people. Deque is also somewhat slower than vector for
many operations, because it's a somewhat more complicated representation
under the covers, as described and measured in the column and in the book.
A major concern (unstated in the book) that caused me to change the advice
was that there are C++ bashers who still write phony efficiency comparisons
to make C++ look bad compared to, say, C. It was feared in some quarters
that such phony comparisons might be abetted by comparing C arrays to C++
deques (with the illegitimate excuse of "well, popular C++ books recommend
using deque by default, so this is an idiomatic comparison" -- illegitimate
because my advice said not to use it if indeed performance was an issue) and
make C++ look that much worse with further phony comparisons. Also, I'd been
getting intermittent feedback from people encouraging me to go back to
recommending vector by default. So that was that: The material in the book
covers similar tradeoffs and information as in the original article (plus
updates and enhancements), but changes the end recommendation in this case.
Herb
---
Herb Sutter (www.gotw.ca)
Secretary, ISO WG21/ANSI J16 (C++) standards committee (www.gotw.ca/iso)
Contributing Editor, C/C++ Users Journal (www.cuj.com)
Check out "THE C++ Seminar" - Boston, March 2002 (www.gotw.ca/cpp_seminar)
Stephen Howe
"todd niec" <nie...@journey.com> wrote in message
news:4f336e92.0202...@posting.google.com...
> Which should be the "default" container. The standard says vector,
> but I though Herb Sutter propsed treating deque as the default since
> it is often faster and more memory efficient.
How can there be a default container? Each container has strengths and
weaknesses in terms of its complexity guarantees and its memeber functions.
You should choose the container that best fits the problem you are trying to
solve. That coudl be any of them: set, map, deque vector, list etc.
> And that vector should
> be used only when the data needs to be in a contiquous array in
> memory. But I've been told that his latest books says to use vector
> as the default. true? not true?
Herb probably said something. I would go back and read Exceptional C++/More
Exceptional C++ and find out _exactly_ what he said. Herb might have added
qualifiers and conditions as well. Make sure you understand these as well in
the context presented.
Stephen Howe
Paul Braman
>
> Which should be the "default" container. The standard says vector,
> but I though Herb Sutter propsed treating deque as the default since
> it is often faster and more memory efficient. And that vector should
> be used only when the data needs to be in a contiquous array in
> memory. But I've been told that his latest books says to use vector
> as the default. true? not true? arguments on either side?
The three sequence containers dequeue, list, and vector are optimized
for different access patterns.
vector is optimized for operating on the end of the array. dequeue is
optimized for operating on both ends of the array. list is optimized
for operating on any point withing the "array".
Only vector and dequeue, however, store elements in a C-compatible
array.
Paul Braman
Paul_Braman @ tvratings . com
Witold K
"Paul Braman" <Paul_...@tvratings.com> wrote in message
news:87202387.02022...@posting.google.com...
> nie...@journey.com (todd niec) wrote:
> >
> > Which should be the "default" container. The standard says vector,
> > but I though Herb Sutter propsed treating deque as the default since
> > it is often faster and more memory efficient. And that vector should
> > be used only when the data needs to be in a contiquous array in
> > memory. But I've been told that his latest books says to use vector
> > as the default. true? not true? arguments on either side?
>
> The three sequence containers dequeue, list, and vector are optimized
> for different access patterns.
>
> vector is optimized for operating on the end of the array. dequeue is
> optimized for operating on both ends of the array. list is optimized
> for operating on any point withing the "array".
>
> Only vector and dequeue, however, store elements in a C-compatible
> array.
I always thought that of the three only vector stores elements in a
C-compatible array.
How could push_front() be a constant time operation if deque was
implemented as a C-compatible array?
Witold Kuzminski
Herb Sutter
wrote:
>Only vector and dequeue, however, store elements in a C-compatible
>array.
Only vector, actually. Deque storage is by definition not contiguous (except
for very small deques that fit on a single internal page, and there's no
portable way to detect that short of inspecting the address of every
contained object).
Herb
---
Herb Sutter (www.gotw.ca)
Secretary, ISO WG21/ANSI J16 (C++) standards committee (www.gotw.ca/iso)
Contributing Editor, C/C++ Users Journal (www.cuj.com)
Check out "THE C++ Seminar" - Boston, March 2002 (www.gotw.ca/cpp_seminar)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
todd niec
I haven't even seen More Exceptional C++ yet. but Exceptional C++ is
great. I put it on the must read list just behind Scott Meyer's
Effective C++ and More Effective C++. (Sorry, Herb, you got the
bronze, but if you complain about the judge you can probably get a 2nd
gold metal.)
> IMHO, there is no "default" container because there is no default use
> for it. Each container has its own advantages and disadvantages, and
> should be used in situations where its advantages prevail over its
> disadvantages.
The "default" is a basically the starting point for analyzing what
contaner to use. i.e. start with the default. Then consider your
needs. if X applies, use container a, if Y applies use container b
and so on. (like if you need to be able to add and delete in the
container and not invalidate iterators, you need to use list<>). If
there are no specific requirements in your needs you will still end up
with the default container, so its important what that was.
> I mostly use vectors and lists because vectors are the
> fastest to iterate over and lists are the fastest for insertions and
> deletions.
For randoem access vectors are the fastest. When it comes to
sequential iteration I doubt there is a significant difference between
vectors and list. You might consider deque. deque has most of
vector's advantages but like list it is fairly fast at inserstions and
deletions at nearly any point in the sequence. (not likely to be as
good as list, but much better than vector). So in many ways deque is
a compromize container. its not the best in many things, but its very
good at most things.
todd niec
I still like your original advice though. I found deque to be faster
ovarall. The random access operations were very slightly slower, but
adding oeprations, even at the end, were considerably faster (without
reserving space in the vector). Unless I'm prepared to do some actual
profiling on a particular case--and we know how likely that is--I
think I;ll tend to use deque.
James Kanze
news:<87202387.02022...@posting.google.com>...
> nie...@journey.com (todd niec) wrote:
> > Which should be the "default" container. The standard says
> > vector, but I though Herb Sutter propsed treating deque as the
> > default since it is often faster and more memory efficient. And
> > that vector should be used only when the data needs to be in a
> > contiquous array in memory. But I've been told that his latest
> > books says to use vector as the default. true? not true?
> > arguments on either side?
> The three sequence containers dequeue, list, and vector are
> optimized for different access patterns.
> vector is optimized for operating on the end of the array. dequeue
> is optimized for operating on both ends of the array. list is
> optimized for operating on any point withing the "array".
It depends on what operations. For accessing with an index, nothing
beats vector, no matter where you're accessing. My tendancy would be
to say that if the size is fixed, then vector is the default; in all
other cases, consider where the growth can take place.
> Only vector and dequeue, however, store elements in a C-compatible
> array.
The original standard didn't guarantee that any store their elements
in a C-compatible array. It has been ammended (or corrected, or
something) to say that vector does. I don't know of any dequeue
implementation that does, however, and I suspect that it would not be
possible.
--
James Kanze mailto:ka...@gabi-soft.de
Beratung in objektorientierer Datenverarbeitung --
-- Conseils en informatique orientée objet
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany, Tél.: +49 (0)69 19 86 27
Michiel Salters
> The three sequence containers dequeue, list, and vector are optimized
> for different access patterns.
>
> vector is optimized for operating on the end of the array. dequeue is
> optimized for operating on both ends of the array. list is optimized
> for operating on any point withing the "array".
>
> Only vector and dequeue, however, store elements in a C-compatible
> array.
Two points :
1) It's std::deque, not dequeue
2) std::deque isn't a "C-compatible array.". It's segmented.
Regards,
--
Michiel Salters
Paul Braman
>
> "Paul Braman" <Paul_...@tvratings.com> wrote:
> >
> > Only vector and dequeue, however, store elements in a C-compatible
> > array.
>
> I always thought that of the three only vector stores elements in a
> C-compatible array.
Bleh...you are correct. (I had been thinking about "chunks" and
mistakenly made the internal conversion to "contiguous".)
Disregard what I said about the internal storage of dequeue. Mea
culpa.
Paul Braman
Paul_Braman @ tvratings . com
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Bill Wade
"todd niec" <nie...@journey.com> wrote
> ... I found deque to be faster
> ovarall.
> adding oeprations, even at the end, were considerably faster [for deque]
(without
> reserving space in the vector).
That may be an implementation detail. Herb's grow test (GOTW 54) where T is
int, had deque about 30% faster with MSVC++5, even with vector.reserve(),
Running the same test with studio.net, I see that vector with reserve is
about three times as fast as deque. vector without reserve is about 50%
faster than deque.
YMMV