Standard

A

Azathot

Kleidemos said:
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!
 
R

Roal Zanazzi

Kleidemos said:
How map e std::sort() is implemented in the standard???
Italian:
Hai gia' avuto la risposta su it.comp.lang.c++ :)

English:
AFAIK, C++ standard doesn't mandate a specific implementation for std
containers and algorithms, it only specifies the computational
complexity involved in operations.
If you want to know how the specific implementation of standard library
you are using is done, please check your library documentation or ask to
its specific NG or mailing list, if any, or directly to its producer.
 

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
474,183
Messages
2,570,967
Members
47,519
Latest member
OtisLucket

Latest Threads

Top