Re: std::vector slow?
On Nov 8, 2:33 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
On 8 Nov, 10:14, David Klein <dkle...@gmail.com> wrote:
I wrote a simple template class Vec and when I compile with
optimization under Visual Studio 2005, std::vector takes 56% more
time. I would have thought that std::vector is much more optimized
than anything I could roll myself. Am I mis-using std::vector somehow?
Or is it really that inefficient?
You might want to have a look at
Bulka & Mayhew: "Efficient C++"
chapter 11 on the STL.
From the chapter introduction, page 156:
"The STL guarantees of the asymptotic complexity of the
algorithms is a good start. [...] However, we still must
explore the constant multipliers and low-order factors
that are ignored by the mathematicians."
I immediately quit reading an author who claims:
"However, we still must explore the constant multipliers and low-order
factors that are ignored by the mathematicians."
Who told him mathematicians "ignore" constant multipliers and low-
order factors? These are, in fact, ignored by the standard, which
makes claims on assimptotic computational complexity only (that big O
notation). This is done so to provide freedom for implementers choose
what they guess that will be the best algorithm to they target public
(there are trade-offs), while ensuring that users will not be using an
overly ill designed implementation.
Applied mathematicians do pay a lot of attention in coefficients and
low order factors, even though they know that the biggest exponent
will ultimately determine the applicability of such algorithms given
large enough problems.
Elias Salom?o Helou Neto.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]