Thread: What is a Map/Table? How is it Implemented?

The standard map is usually implemented as a red-black tree. You can find an implementation and description here.

Example use of a map:

Code:

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

using namespace std;

int main(void)
{
    typedef map<string,float> StrFltMap;
    StrFltMap FruitPrices;
    StrFltMap::iterator it;
    string search;

    FruitPrices["Pear"] = 0.66f;
    FruitPrices["Apple"] = 0.89f;
    FruitPrices["Kiwi"] = 1.19f;
    FruitPrices["Banana"] = 0.59f;

    cout << "Welcome to Bob's Produce Market" << endl;
    cout << "Available fruits and their prices:" << endl;
    for( it = FruitPrices.begin(); it != FruitPrices.end(); ++it )
        cout << it->first << " costs " << it->second << "/lb." << endl;

    cout << "\nEnter in a fruit to search for: ";
    getline(cin,search);
    while( search.length() )
    {
        if( (it = FruitPrices.find(search)) != FruitPrices.end() )
            cout << "That fruit costs " << it->second << "/lb." << endl;
        else
            cout << "Sorry, we do not have that fruit in stock." << endl;

        cout << "\nEnter in a fruit to search for: ";
        getline(cin,search);
    }

    cout << "Goodbye!" << endl;
    cin.get();
}

Notice in the output below that the map container automatically sorts its entries according to the key value regardless of the order in which they were inserted into the map. I.e. Apple comes before Banana which comes before Kiwi which comes before Pear:

Code:

Welcome to Bob's Produce Market
Available fruits and their prices:
Apple costs 0.89/lb.
Banana costs 0.59/lb.
Kiwi costs 1.19/lb.
Pear costs 0.66/lb.

Enter in a fruit to search for: Banana
That fruit costs 0.59/lb.

Enter in a fruit to search for: Pear
That fruit costs 0.66/lb.

Enter in a fruit to search for: Apple
That fruit costs 0.89/lb.

Enter in a fruit to search for: blah
Sorry, we do not have that fruit in stock.

Enter in a fruit to search for: 
Goodbye!

>>A Binary Tree is a map then?
A map is an abstract concept of a collection of items that are accessed by a key. It just happens that a binary search tree is a very close match to that concept without any tweaking. If you wanted you could implement a map as a hash table, or a simple array.

>>How are the values in the Hex base Number system maped to the Values they should be?
It's all binary.

>>I sthere a map it uses to check it or something?
That's totally up to the system, but it could be implemented that way.