Kleidemos wrote:
How map e std::sort() is implemented in the standard???
Except from "http://www.sgi.com/tech/stl/complexity.html":
STL Complexity Specifications
STL container, algorithm, and concept specifications include asymptotic
complexity specifications. For example, iterators are required to take
constant time, that is the time required by an iterator operation should be
no more than a fixed constant, independent of the size of the container to
which it refers.
Clearly programs will still function if a program component ignores the
complexity specifications. Nonetheless, these specifications are an
important part of the interface between STL components and code that uses
them. If they are ignored, the performance of the resulting program will
often render it useless.
[...]
Concept specifications (e.g. Forward Iterator or Container) specify
complexity requirements that should be met by all instances of the concept.
This is the minimum behavior required by operations (e.g. sort)
parameterized with respect to the concept. Any specific instance (e.g.
vector) is likely to perform better in at least some cases.
[...]
Algorithms specify either worst-case or average case performance, and
identify which. Unless otherwise stated, averages assume that container
elements are chosen from a finite type with more possible values than the
size of the container, and that container elements are independently
uniformly distributed.
[...]
Bye!
--
---
*************** | Have you ever retired a human by mystake?
*** Azathot *** |
*************** | To contact me, ask me gently. Thanks.
