stl MAP what data structure?

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

!with some explanation!


Try reading the documentation at http://www.cplusplus.com/reference/stl/map/
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???
Last edited on
AFAIK. Implementation would be compiler specific.
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.
Topic archived. No new replies allowed.