Hierarchical data structures with vectors in c++, that can be traversed bottom-up and top-bottom

Question

I have a hierarchical structures of few levels. I have the following:

RawSheet = vector<Country>
Country = vector<City>
City = vector<Building>

and the classes besides the vectors contain some other useful stuff. The problem is I can only go top to bottom in the whole structure, that is, starting from a RawSheet I can get its countries, and then for each Country I can get the cities, and for each City I can get its buildings. But I also need to be able to do this: given a Building, get its City, then for the City get its Country, and finally get the RawSheet for that country. What I have now is basically a tree with links top-bottom, but not bottom to top. Can you suggest me ways to do this, and then also how do I manage those links? For example each city can keep a reference to a country, its own. Same for the others... Keep a reference to your parent.

Thanks

Answer 1

I would define a base class Layer that has a pointer to a parent layer and a name that you can print. Then you can define all the layers in your hierarchy by simply inheriting from this Layer and using the new C++11 inheriting constructor feature to avoid code repetition (in C++98 you would have to define the constructor in every concrete layer).

I would not store the children inside the layer but in a std::multimap<Layer*, Layer*> instead, so that you can use the convenient member function equal_range to get all children of any concrete layer inside your application (I called this data structure Atlas).

#include <map>
#include <string>
#include <utility>
#include <vector>
#include <iostream>

class Layer
{
public:
    explicit Layer(std::string n, Layer* p = nullptr): name_(n), parent_(p) {}
    std::string name() { return name_; }
    Layer* parent() { return parent_; }
private:
    std::string name_;
    Layer* parent_;
};

// inheriting constructrors (C++11 only, retype constructors for C++98)
class City   : public Layer { using Layer::Layer; };
class Country: public Layer { using Layer::Layer; };
class Planet : public Layer { using Layer::Layer; };

typedef std::multimap<Layer*, Layer*> Atlas;

int main()
{
    Planet Earth("Earth");

    Country USA("United States of America", &Earth);
    Country FRA("France", &Earth);

    std::vector<City> USA_cities = { City("Los Angeles", &USA), City("New York", &USA) };
    std::vector<City> FRA_cities = { City("Bordeaux", &FRA), City("Paris", &FRA) };

    Atlas a;

    a.insert(std::make_pair(&Earth, &USA));
    a.insert(std::make_pair(&Earth, &FRA));

    for (auto& city: USA_cities)
        a.insert(std::make_pair(&USA, &city));

    for (auto& city: FRA_cities)
        a.insert(std::make_pair(&FRA, &city));

    auto countries = a.equal_range(&Earth);
    std::cout << "Countries on planet " << countries.first->first->name() << " :\n";
    for (auto it = countries.first; it != countries.second; ++it) {
         auto country = it->second;
         std::cout << country->name() << " (located on planet " << country->parent()->name() << "), with cities:\n";
         auto cities = a.equal_range(country);
         for (auto jt = cities.first; jt != cities.second; ++jt) { 
              auto city = jt->second;
              std::cout << "     " << city->name() << " (located in country " << city->parent()->name() << ")\n";
         }
         std::cout << "\n";
    }
}

Live Example with the following output:

Countries on planet Earth :
United States of America (located on planet Earth), with cities:
     Los Angeles (located in country United States of America)
     New York (located in country United States of America)

France (located on planet Earth), with cities:
     Bordeaux (located in country France)
     Paris (located in country France)

As you can see, you can iterate up and down this hierarchy.

You can critique this solution on several points. There is no enforcement on the class hierarchy: a Planet can have a list of Cities without intermediate Country layer, etc. You could enforce such things through either compile-time checking or through runtime type information. This is a tradeoff between flexibility and safety.

There is also no virtual destructor in the base class Layer. As long as you don't try to delete any concrete layer objects through Layer*, there is no problem with that. There are also no smart pointers because all the Layer* are non-owning pointers. If you ever want to move or copy buildings around (it happens sometimes), you could extend it easily.

Answer 2

There are several approaches to this problem. I'm just exposing one.

You can encapsulate each element of the container with a reference to the container. Something like:

class Country;

class City {
public:
    City(Country& c): country(c) {
    }

private:
    string      name;
    size_t      population;
    Country&    country;
};

class Country {
    string          name;
    vector<City>    cities;
};

You could use a pointer instead a reference to container, of course. But if you want to force each city is owned by just one Country, use a reference. In this case, you have to supply a constructor to City class, as seen in the example.

Extend this sample to the other levels of the hierarchy is easy too.