stl MAP what data structure?

[cppgans]

can anyone tell me what data structure is used in c++ to implement the map container

!with some explanation!

[Bazzy]

Try reading the documentation at http://www.cplusplus.com/reference/stl/map/

[cppgans]

sorry the link doesnt give me the answer i was looking for

but in some other link i found out that map in stl is implemented via red-black trees

is that true???

[Zaita]

AFAIK. Implementation would be compiler specific.

[helios]

The usual implementation is a self-balancing binary search tree (but any other data structure that respects the complexity constraints can be used, like a skip list).

Searching for an element takes O(log n) time
Inserting a new element takes O(log n) time
Incrementing/decrementing an iterator takes O(log n) time
Iterating through every element of a map takes O(n) time
Removing a single map element takes O(log n) time
Copying an entire map takes O(n log n) time.