[C++] Standard Template Library Container: Map (ENG)

 

 

Creating Map

A map stores pairs of key and value. Keys cannot be duplicated. C++ maps are automatically sorted. It is based on the binary search tree (ascending order).

#include <map>

int main()
{
    std::map<std::string, int> simpleScoreMap;

    simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));
    simpleScoreMap.insert(std::pair<std::string, int>("Coco", 50));

    simpleScoreMap["Mocha"] = 0;

    std::cout << "Current size: " << simpleScoreMap.size() << std::endl;

    return 0;
}

 

// map<key_type, value_type> name;
// creates an empty map
std::map<std::string, int> simpleScoreMap;
std::map<StudentInfo, int> complexScoreMap;

// map<key_type, value_type> name(const map& x)
// creates a map that has same size and same data with map x
std::map<std::string, int> copiedSimpleScoreMap(simpleScoreMap);

 

 

 

Pair

// pair<first_type, second_type>
std::pair<std::string, int> student1("Coco", 10);

simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

 

A pair stores two data as one.

 

 

 

insert( )

// std::pair<iterator, bool> insert(const value_type& value)

// returns <iterator, true>
simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

// returns <iterator, false>
simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 0));

 

It inserts a new element to the map. It returns a pair of iterator and boolean. The iterator points the element, and the boolean shows the result of insertion. Keys can't be inserted in duplicate.

 

 

 

operator[ ]

// mapped_type& operator[](const Key& key);
std::map<std::string, int> simpleScoreMap;

simpleScoreMap["Coco"] = 10;  // inserts a new element
simpleScoreMap["Coco"] = 50;  // overwrites the value of "Coco"

 

It returns the value of the key by reference. If there isn't the key, it inserts a new element. If there is the key, it overwrites the value.

 

 

 

Auto Sort

simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));
simpleScoreMap.insert(std::pair<std::string, int>("Coco", 50));

for (std::map<std::string, int>::iterator it = simpleScoreMap.begin(); it != simpleScoreMap.end(); ++it)
{
    std::cout << "(" << it->first << ", " << it->second << ")" << std::endl;
}

 

("Coco", 50) ("Mocha", 100)

 

 

find( )

#include <map>

int main()
{
    std::map<std::string, int> simpleScoreMap;
    simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

    std::map<std::string, int>::iterator it = simpleScoreMap.find("Mocha");
    if (it != simpleScoreMap.end())
    {
        it->second = 80;
    }

    return 0;
}

 

// iterator find(const Key& key);
std::map<std::string, int>::iterator it = simpleScoreMap.find("Coco");

 

If it would find the key, it returns the value of the key by reference. If not, it returns end( ).

 

 

 

swap( ) and clear( )

std::map<std::string, int> scoreMap;         // ("Mocha", 10), ("Coco", 40)
std::map<std::string, int> anotherScoreMap;  // ("Nana", 100)

// void swap(map& other);
scoreMap.swap(anotherScoreMap);  // scoreMap: ("Nana", 100)
                                 // anotherScoreMap: ("Mocha", 10), ("Coco", 40)

// void clear();
anotherScoreMap.clear();         // anotherScoreMap: empty

 

 

erase( )

// void erase(iterator position);
// size_type erase(const key_type& key);
// void erase(iterator first, iterator last);

std::map<std::string, int>::iterator foundIt = simpleScoreMap.find("Coco");
simpleScoreMap.erase(foundIt);
simpleScoreMap.erase("Coco");

 

 

Using Objects as Keys

// StudentInfo.h
class StudentInfo
{
public:
    // constructors
private:
    std::string mName;
    std::string mStudentID;
};


// Main.cpp
int main()
{
    std::map<StudentInfo, int> scores;
    scores.insert(std::pair<StudentInfo, int>(StudentInfo("Poppy", "a556"), 30));
    scores.insert(std::pair<StudentInfo, int>(StudentInfo("Lulu:, "a112"), 70));
    // ...
}

// Error

 

STL maps are always sorted, so you have to make a function that compares two keys.

operator<( )

bool StudentInfo::operator<(const StudentInfo& other) const
{
    if (mName == other.mName)
    {
        return mStudentID < other.mStudentID;
    }

    return mName < other.mName;
}

 

If you can't access to the class, you can also put the comparer when you make a map.

struct StudentInfoComparer
{
    bool operator()(const StudentInfo& left, const StudentInfo& right) const
    {
        return (left.getName() < right.getName());
    }
};

// Main.cpp
std::map<StudentInfo, int, StudentInfoComparer> Scores;

 

 

 

Pros and Cons of Map

Pros

- Search speed of map is faster than std::list or std::vector.

 

Cons

- Map is sorted automatically.

- Map is not a hashmap. So it is not O(1). (There is a solution in C++11.)