15.11. A distance table with maps and sets¶

We can represent known routes with std::map<std::string, std::map<std::string, int>>. The outer map associates a city with its neighbors; each inner map associates a neighbor with a distance. A separate set keeps city names sorted for display.

For this example we assume distances are symmetric. Adding a route stores both directions. A later record for the same pair replaces both values. A route from a city to itself must have distance zero. Missing routes remain absent; we print a dash instead of inventing a distance or searching for an indirect route.

c192_routes.txt

"San Diego" "Los Angeles" 120
"Los Angeles" "San Francisco" 380
"Boston" "Chicago" 980

Example c192_distance_table

 1#include <fstream>
 2#include <iomanip>
 3#include <iostream>
 4#include <map>
 5#include <set>
 6#include <sstream>
 7#include <string>
 8using std::cout;
 9
10struct route_record {
11    std::string origin;
12    std::string destination;
13    int distance = 0;
14};
15
16bool parse_record(const std::string& line, route_record& record) {
17    std::istringstream input(line);
18    route_record parsed;
19    input >> std::ws;
20    if (input.peek() != '"' || !(input >> std::quoted(parsed.origin))) {
21        return false;
22    }
23    input >> std::ws;
24    if (input.peek() != '"' || !(input >> std::quoted(parsed.destination))) {
25        return false;
26    }
27    if (!(input >> parsed.distance) || parsed.distance < 0 ||
28        parsed.origin.empty() || parsed.destination.empty()) {
29        return false;
30    }
31    input >> std::ws;
32    if (!input.eof()) {
33        return false;
34    }
35    record = parsed;
36    return true;
37}
38
39
40using distance_table = std::map<std::string, std::map<std::string, int>>;
41
42void add_route(distance_table& routes, const route_record& record) {
43    routes[record.origin][record.destination] = record.distance;
44    routes[record.destination][record.origin] = record.distance;
45    routes[record.origin][record.origin] = 0;
46    routes[record.destination][record.destination] = 0;
47}
48
49int main() {
50    std::ifstream input("c192_routes.txt");
51    if (!input) {
52        std::cerr << "Unable to open routes\n";
53        return 1;
54    }
55    distance_table routes;
56    std::set<std::string> cities;
57    std::string line;
58    while (std::getline(input, line)) {
59        route_record record;
60        if (!parse_record(line, record) ||
61            (record.origin == record.destination && record.distance != 0)) {
62            std::cerr << "Invalid route: " << line << '\n';
63            return 1;
64        }
65        add_route(routes, record);
66        cities.insert(record.origin);
67        cities.insert(record.destination);
68    }
69    if (input.bad() || !input.eof()) {
70        std::cerr << "Read failed\n";
71        return 1;
72    }
73    cout << std::setw(16) << "";
74    for (const auto& city : cities) {
75        cout << std::setw(16) << city;
76    }
77    cout << '\n';
78    for (const auto& origin : cities) {
79        cout << std::setw(16) << origin;
80        const auto& neighbors = routes.at(origin);
81        for (const auto& destination : cities) {
82            auto position = neighbors.find(destination);
83            if (position == neighbors.end()) {
84                cout << std::setw(16) << "-";
85            } else {
86                cout << std::setw(16) << position->second;
87            }
88        }
89        cout << '\n';
90    }
91}

The display uses find and at, so printing does not insert missing routes. An empty input file produces an empty table without an invalid array access. Storage grows with the records we actually insert; there is no guessed limit of fifty cities and no custom resizing implementation.

For a dense numerical table with known dimensions, nested arrays or vectors may be more appropriate. Container choice follows the operations and meaning of the data, not the appearance of the printed table.