mannerofallthings mannerofallthings - 1 year ago 50
C++ Question

Dynamically allocating into a 2 dimensional std::unordered_map

I have a 2d map declared as

unordered_map< string, unordered_map<string, Road*>* > matrix;

That takes an instance of Road

class Road {
Road() : connected(0), weight(0) {}

bool connected;
int weight;

And I allocate as follows

void addPlace(string place) {
// error checking
if (placeExists(place)) {
cout << "Place already exists" << endl;

Road *road = new Road();
unordered_map<string, Road*> *newRelationship = new unordered_map<string, Road*>;
newRelationship->insert({ {place},{road} });

// add to network
matrix.insert({ { place },{ newRelationship } });

However, when I call

void connectPlace(string source, string dest, int w)
if (!placeExists(dest) || !placeExists(source)) {
cout << "Place(s) does not exists" << endl;
if (matrix.find(source)->second->find(dest)->second->connected)

I get an error: "List iterator is not dereferenceable", which suggests to me that I've gone somewhere wrong with my allocation? Thank you in advance.

Here is my call to placeExists, which returns true both calls from connectPlace:

bool placeExists(string place) {
if (matrix.find(place) == matrix.end()) {
return false;
return true;

I've broken it down to

auto a = matrix.find(source);
auto b = matrix.find(source)->second;
auto c = matrix.find(source)->second->find(dest); // (<Error reading characters of string.>, {connected=??? weight=??? })
auto d = matrix.find(source)->second->find(dest)->second; // stops here
auto e = matrix.find(source)->second->find(dest)->second->connected;

My function calls are as follows

Graph *road_network = new Graph(false);

road_network->addPlace("San Francisco");
road_network->addPlace("San Jose");
road_network->addPlace("Los Angelous");

road_network->connectPlace("Sacremento", "Antelope", 5); //<-- break
road_network->connectPlace("San Francisco", "San Jose", 2);
road_network->connectPlace("Los Angelous", "Davis", 10);
road_network->connectPlace("Davis", "Antelope", 4);
road_network->connectPlace("Roseville", "Davis", 5);
road_network->connectPlace("San Jose", "Antelope", 6);
road_network->connectPlace("Davis", "Los Angelous", 5);

Answer Source

Where things are going wrong is inside your addPlace() function. Your code:

Road *road = new Road();
unordered_map<string, Road*> *newRelationship = new unordered_map<string, Road*>;
newRelationship->insert({ {place},{road} });

// add to network
matrix.insert({ { place },{ newRelationship } });

creates a new road that could represent a link from the city to itself, but not to any of the others. For instance, after your call to


your matrix looks like:

  • "Sacremento"
    • "Sacremento": <Road>

And after your call to


it looks like:

  • "Sacremento"
    • "Sacremento": <Road>
  • "Antelope"
    • "Antelope": <Road>

So, later when you try to do road_network->connectPlace("Sacremento", "Antelope", 5); it is looking for an entry with the key "Antelope" in the unordered_map under the key "Sacremento" in the matrix map, which does not exist. So, when you try to dereference the iterator created by matrix.find(source)->second->find(dest) and access its second member, it throws an error because the iterator is not valid.

There are two ways you can fix this:

  1. When addPlace is called, add an entry to the newRelationship for every existing place in the matrix, and add an entry to the unordered_map of every existing place in the matrix for the new place. (This would be pretty inefficient with large datasets, for both storage and processing. Inefficient for storage because it would have to store (number of places)^2 entries, with many of them potentially being unused. Inefficient for processing because every time a new place is added, every single existing place has to be looped through)
  2. In addPlace simply add an empty unordered_map to the matrix under the key place. In connectPlace, if matrix.find(source)->second->find(dest) returns an invalid iterator (determined by if the value returned is equal to matrix.end()), then add a new entry to the unordered_map under the key source in matrix with key dest and the value being a new Road object with the given weight.