C++ Map : manipulate map inside map

Question

I'm more used to a single map and not to nested map. So I have serious difficulty understanding how to deal with this.

Remark: Please don't request me to use multimap or boost,I'm restricted to use this structure

In C++ STL map, i have a definition like this

map<string, map<string, string>> exploration; // country --> state --> city

The first map represent a pair of key(country) and value as tree structure map<string, string> which represent there respective state and city.

I know how to populate this structure manually (hard coding) like so:

exploration["Canada"]["Ontario"] = "Toronto";

Problem :

Later the data showed above will be entred by the user :

> Canada Ontario Toronto

> Canada Alberta Edmonton

> USA Washington Seatle

> USA Nevada Las-Vegas

So if I apply this logic to my example above, this is wrong since map does not accept duplicate keys

Illustration (wrong) :

exploration["Canada"]["Ontario"] = "Toronto";
exploration["Canada"]["Alberta"] = "Edmonton";

Illustration (What I'm looking for) :

exploration["Canada"]["Ontario"] = "Toronto";
                     ["Alberta"] = "Edmonton";

        Canada
          **
         *  *     
        *    *
     Ontario Alberta
       *        *
      *          *
   Toronto     Edmonton  

My hypothetical solution,

> Canada Ontario Toronto

1 case: If the country(Canada) does not exist in exploration structure,I add it as well as the province and its city.

2 case: If the country(Canada) exist, so I add Ontario and Toronto a long side the data entered before.

Any indications, ideas or hints are welcomed.

Answer 1

Your example is quite right. Looking at the code below (in C++11 but the same reasoning applies to previous versions), you can see that each country is only inserted once in the exploration map.

Code:

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, map <string, string> > exploration;
    exploration["Canada"]["Ontario"] = "Toronto";
    exploration["Canada"]["Alberta"] = "Edmonton";
    exploration["USA"]["Washington"] = "Seattle";
    exploration["USA"]["Nevada"] = "Las Vegas";

    cout << "Number of keys: " << exploration.size() << endl;

    for (auto country : exploration) {
        for (auto city : country.second)
            cout << country.first << ":" << city.first << " -> " << city.second << endl;
    }

    return 0;
}

Output:

Number of keys: 2
Canada:Alberta -> Edmonton
Canada:Ontario -> Toronto
USA:Nevada -> Las Vegas
USA:Washington -> Seattle

Let's go step by step to understand what is going on:

1. map<string, map <string, string> > exploration: Defines a map whose keys are strings and its values are other maps. It is empty so far.
2. exploration["Canada"]["Ontario"] = "Toronto": First it checks that Canada does not exist in the exploration map. Hence a mapping is created linking Canada to an empty map. Now, a mapping from Ontario to Toronto is created inside the exploration["Canada"] map.
3. exploration["Canada"]["Alberta"] = "Edmonton": Since the Canada key already exists in exploration, no need to create it again. It will just map Alberta to Edmonton in the already created map.

The same reasoning applies to the USA map. This way, there will be no duplicated keys even with nested maps. C++ is great.

Answer 2

You can have two cities in the same state, so you really need map<string, map<string, set<string>>>

But what you have before that will already work. For example:

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

int main() {

    std::map<std::string, std::map<std::string, std::set<std::string>>> countries;

    countries["Canada"]["Ontario"].insert("Toronto");
    countries["Canada"]["Ontario"].insert("Something else");
    countries["Canada"]["Alberta"].insert("Edmonton");


    for (const auto& country : countries) {
        std::cout << "Country: " << country.first << "\n";
        for (const auto& statePair : country.second) {
            std::cout << "State: " << statePair.first << "\n";
            for (const auto& city : statePair.second) {
                std::cout << "City: " << city << "\n";
            }
        }
    }

    return 0;
}

Will output

Country: Canada
State: Alberta
City: Edmonton 
State: Ontario
City: Something else
City: Toronto

EDIT:

In relation to your follow up question, this should get you there:

using CountryMap = std::map<std::string, std::map<std::string, std::set<std::string>>>;
bool countryContainsCity(const CountryMap& countryMap, const std::string& country, const std::string& city)
{
    for (const auto& country : countryMap[country]) {
        for (const auto& statePair : country.second) {
            if (statePair.second.find(city)
            {
                return true;
            }
        }
    }

    return false;
}