Re: Whats going onto the stack here?
Ben Voigt <rbv@nospam.nospam> wrote:
"Igor Tandetnik" <itandetnik@mvps.org> wrote in message
news:%236nTumBYHHA.2556@TK2MSFTNGP02.phx.gbl...
Ben Voigt <rbv@nospam.nospam> wrote:
Where in the STL or Standard C++ Library documentation are any
performance guarantees made?
Pretty much everywhere. For example:
23.2.2.4 list operations
void sort();
template <class Compare> void sort(Compare comp);
32 Complexity: Approximately NlogN comparisons, where N == size().
I see semantics discussed, with a correctness guarantee in the case
that no exceptions are thrown by the user-defined ordering. There's
also a complexity statement.
From the context of your original statement, it seems clear that you
weren't using the word performance in the sense of correctness, but
in the sense of throughput. I see no throughput guarantees. I don't
even see mention of what inputs cause best-case or worst-case
throughput.
What is the distinction, in your opinion, between "complexity" and
"throughput" ?
Sorting algorithms have performance that is highly data-dependent.
There is no one-size-fits-all algorithm for fast sorting, which is
what you appear to be claiming when you state that the STL (which
implementation not specified) is better for the task than a
hand-picked algorithm.
I'm not sure where you see this claim. Tim Roberts claimed that STL
provides a performance guarantee - an upper boundary on the running time
of its algorithms. In the example above, the claim is that, whatever the
underlying algorithm, it won't make more than O(N log N) comparisons,
regardless of the data it is applied to. Nobody claims that STL
implements the best possible algorithm for every possible problem.
You seem to have a different definition of "performance guarantee" than
me and Tim Roberts. What exactly do you mean by this term?
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925