how is std::map implemented

So it can be used to quickly implement a red-black tree!

In an STL map, insertion of key/value pair is in sorted order of key. It uses a tree to store values, which is why an O(log N) insert/lookup is required. There is also no need to handle collisions. An STL map works well for things like:
»»find min element
»»find max element
»»print elements in sorted order
»»find the exact element or, if the element is not found, find the next smallest number

example:


#include<map>
#include<string>
#include<iostream>

using namespace std;

int main()
{
map<string,int> p;
p["jan"]=1;
p["feb"]=2;
cout<<p["feb"]<<p["mar"]<<endl;
system("pause");
}

map is implemented using red-black tree.

Probably the two most common self balancing tree algorithms are Red-Black trees and AVL trees. To balance the tree after an insertion/update both algorithms use the notion of rotations where the nodes of the tree are rotated to perform the re-balancing.

While in both algorithms the insert/delete operations are O(log n), in the case of Red-Black tree re-balancing rotation is an O(1) operation while with AVL this is a O(log n) operation, making the Red-Black tree more efficient in this aspect of the re-balancing stage and one of the possible reasons that it is more commonly used.

Red-Black trees are used in most collection libraries, including the offerings from Java and Microsoft .NET Framework.

using namespace std;

typedef std::map<int,int>  MAP;
typedef std::pair<int,int> PAIR;

int main()
{

    MAP squares_map;

    squares_map.insert( PAIR(2,4) );
    squares_map.insert( PAIR(0,0) );
    squares_map.insert( PAIR(1,1) );
    squares_map.insert( PAIR(6,36) );
    squares_map.insert( PAIR(3,9) );

    if (!squares_map.empty())
    {
        MAP::iterator it_min = squares_map.begin();

        MAP::iterator it_max = squares_map.end();  // points to just past last element
        --it_max;                                  // points to last element

        cout << "min element : " << it_min->first << " " << it_min->second << "\n";
        cout << "max element : " << it_max->first << " " << it_max->second << "\n";
    }

    return 0;
}