C++ Reference documentation

[Lauke]

Hello guys,

Do you know if some kind of documentation for algorithm and data structure exists?
I mean, for example, does exists a documentation reporting that the "map" structure is implemented by a balanced tree? e so on for other algorithm/data structure.

Thank you

[keskiverto]

This? http://www.cplusplus.com/reference/


The standard how std::map should behave. The implementers of library are free to do whatever, as long as they fulfil that promise.

[Catfish4]

http://en.cppreference.com/w/cpp/container
http://en.wikipedia.org/wiki/List_of_data_structures

I mean, for example, does exists a documentation reporting that the "map" structure is implemented by a balanced tree?

As keskiverto said, the C++ standard describes how data structures (the containers) should behave. Then the implementers have freedom to do whatever they want internally, as long as the external behavior is respected.

[Lauke]

I don't understand why in http://en.cppreference.com/w/cpp/container/map is reported such sentence;

"Maps are usually implemented as red-black trees."

Moreover, please, can you indicate me some implementers?

Thank you guys.

[keskiverto]

Developers of Apple, GCC, Clang, MSVC, Cray, SGI, ...

[Catfish4]

http://en.wikipedia.org/wiki/Red-black_tree

Moreover, please, can you indicate me some implementers?

Some examples can be found here:
http://www.sgi.com/tech/stl/download.html
http://www.sgi.com/tech/stl/stl_map.h

[Lauke]

Another one than sgi?

But now... a doubt is arising in my head... what is STL?
I thought the STL was a kind of standard in the implementation too, instead i'm getting that there are several different implementation of such standard.

Am i wrong?

[keskiverto]

GCC is open source.

Android, Apple, and Windows phone users can call each other. Different phones, but an agreed standard on how they communicate. Standard defines an interface.

STL is Standard Template Library. There are non-template bits in libraries too. The C++ standard describes what its library must have. Different vendors are free to provide their own version, particularly when they have a special platform or business model.

[JLBorges]

> I thought the STL was a kind of standard in the implementation too,
> instead i'm getting that there are several different implementation of such standard.

Yes, there are several different implementations.

See: http://www.cplusplus.com/forum/lounge/110714/4/#msg607415
http://www.cplusplus.com/forum/general/114791/#msg626903

[Cubbi]

Lauke wrote:

a doubt is arising in my head... what is STL?

STL is a cool guy who works for Microsoft and maintains their C++ standard library.
STL was a general-purpose library for C++ developed at HP, moved to SGI when HP dropped financing, and abandoned over a decade ago (its website still remains, and was linked to earlier in this thread).
STL is an informal name sometimes used to describe the parts of the C++ standard that were originally inspired by parts of the STL (the HP/SGI library).