Operating through data container map>

Question

I need to find the fastest way from one city to other using djikstra algorithm (working on directed graph with weights), but i have to use this specific container. I have a problem with saving data properly to this map, here is part of my code.

    fstream file;
    string fromThisCity, toThisCity;
    int distance;
    file.open("drogi.txt", ios::in);

    if (file.good())
    {
        while (!file.eof())
        {
            file >> fromThisCity;
            file >> toThisCity;
            file  >> distance;

            map<string, int> inGraph;
            inGraph[toThisCity] = distance;
            graph[fromThisCity] = inGraph;



            for (map<string, map<string, int>>::iterator element = graph.begin(); element != graph.end(); element++)
            {
                for (map<string, int>::iterator i = inGraph.begin(); i != inGraph.end(); i++)
                {
                    cout << element->first << " " << i -> first << " " << i -> second << endl;
                }
            }
        }

    }
    else
    {
        cout << "file couldnt be opened" << endl;
    }

    file.close();

Please be more specifc than "I have a problem with saving data properly". (Read about the [mcve].) — molbdnilo, Jan 19 '22 at 09:40
Also, [Why is iostream::eof inside a loop condition (i.e. `while (!stream.eof())`) considered wrong?](https://stackoverflow.com/questions/5605125/why-is-iostreameof-inside-a-loop-condition-i-e-while-stream-eof-cons). — molbdnilo, Jan 19 '22 at 09:41
Aside from the actual problem, I'd recommend that you use a more simple structure than a map. Thing is, comparing hashed strings is far more costly than using indices, and I presume that your algorithm is meant to be highly efficient, for the case that you end up with several million cities. Store the actual city names separately. Consider using a container specifically written for matrices, maybe even specifically for symmetric matrices. — Aziuth, Jan 19 '22 at 10:05

molbdnilo · Answer 1 · 2022-01-19T10:16:59.470

Every time you read a fromThisCity, you set that key's value in graph to a new single-value map<string,int>, discarding any mapping you already had.

You want to modify the map graph[fromThisCity], not replace it, i.e. graph[fromThisCity][toThisCity] = distance;.

Fixing some other problems, you might end up with

ifstream file("drogi.txt"); // Use ifstream for reading, open on initialization.
if (file.good())
{
    // Declare variables as near to use as possible.
    string fromThisCity, toThisCity;
    int distance;
    // This is the "standard" and least surprising read loop.
    while (file >> fromThisCity >> toThisCity >> distance)
    {
        // Update the graph.
        graph[fromThisCity][toThisCity] = distance;
        // Since you're apparently in C++17, use modern loops.
        for (const auto& from: graph)
        {
            for (const auto& to: from.second)
            {
                cout << from.first << " " << to.first << " " << to.second << endl;
            }
        }
    }
}
else
{
    cout << "File couldn't be opened" << endl;
}
// You don't need to explicitly close fstreams; the destructor does it if appropriate.

Marek R · Answer 2 · 2022-01-19T12:55:03.283

Having this kind of map is wasteful.

Note that for the problem itself you do not need to have city names.

Also learn to split code into small functions to make it easier to maintain.

Take a look on that:

struct Data {
    std::map<std::string, int> namesToIds;
    std::vector<std::string> names;
    std::vector<std::vector<int>> distances;

    int addCity(const std::string& city) {
        auto cityIdCandidate = static_cast<int>(namesToIds.size());
        auto [it, newInsert] =
            namesToIds.insert(std::pair{city, cityIdCandidate});
        if (newInsert) {
            names.push_back(city);
            updateDistancesSize();
        }

        assert(names.size() == namesToIds.size());
        return it->second;
    }

    void addRoute(int src, int dst, int dist) {
        distances[src][dst] = dist;
    }

    void addRoute(const std::string& src, const std::string& dst, int dist) {
        addRoute(addCity(src), addCity(dst), dist);
    }

    void updateDistancesSize() {
        auto newSize = names.size();
        distances.resize(newSize, std::vector(newSize, -1));
        for(auto& row : distances) {
            row.resize(newSize, -1);
        }
    }
};

std::istream& operator>>(std::istream& in, Data& data) {
    std::string src, dst;
    int dist;

    while (in >> src >> dst >> dist) {
        data.addRoute(src, dst, dist);
    }
    return in;
}

void loadData(std::filesystem::path name, Data& data) {
    std::ifstream stream{name};
    stream >> data;
}

https://godbolt.org/z/q194a9dG6

Concerns are spited, use of file is not obligatory, city names are kept separately from adjacency matrix. Code is easy to read and maintain.

Operating through data container map>

2 Answers2