我不明白我可能做错了什么，导致不断出现此 valgrind 错误。我没有泄漏任何记忆..
在我的项目中，我必须实现一个图（一种基本图算法），并拥有一个可以在实际数据中查找路径的工作地图应用程序。我不能在这个项目中使用new，也不能编辑公共成员函数的签名，也不能添加图类的公共成员变量。我可以添加私有成员变量和函数。我不能修改其他函数的签名。不过，我可能会添加额外的辅助函数。我可能只修改graph.h和application.cpp。
我的图形类表示具有以下所有属性的图形：
有向 – 边有起点和终点。
简单 – 对于任意两个节点 A 和 B，从 A 到 B 至多有一条有向边。
目标是使用图表来表示地图。顶点代表人们可以存在的地方，顶点之间的边表明人们如何在这些地方之间移动。 OSM（OpenStreetMaps）中的节点是现实世界中的单个点，由我们关心的3个值组成：
ID（很长很长，唯一标识符）
纬度（双）
经度（双）
OSM的数据告诉我，起始节点和结束节点恰好是其他路的一部分。这就是我将人行道连接到其他人行道并构建整个图表的方法。我感兴趣的另一种方式是建筑。 OSM 通过其周边的节点来定义建筑物。例如，一个大学校园可能由 13 个节点组成，尽管看起来是矩形的。为了简化我的导航问题，我必须通过平均其周边节点的坐标，将每个建筑物转换为单个节点。因为这些节点没有通过人行道连接到图表，所以我必须添加从建筑中心到附近人行道节点的新边。
我只能修改graph.h和application.cpp。
我的图表.h：
#pragma once
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;
/// @brief Simple directed graph using an adjacency list.
/// @tparam VertexT vertex type
/// @tparam WeightT edge weight type
template <typename VertexT, typename WeightT>
class graph {
private:
// TODO_STUDENT
/*We are dealing with an adjacency list representation. The elements
are not required to be sorted based on keys*/
unordered_map<VertexT, unordered_map<VertexT, WeightT> > adjacencyList;
public:
/// Default constructor
graph() {
// No initialization needed for the adjacency list
}
/// @brief Add the vertex `v` to the graph, must run in at most O(log |V|).
/// @param v
/// @return true if successfully added; false if it existed already
bool addVertex(VertexT v) {
// TODO_STUDENT
return adjacencyList.emplace(v, unordered_map<VertexT, WeightT>()).second;
}
/// @brief Add or overwrite directed edge in the graph, must run in at most O(log |V|).
/// @param from starting vertex
/// @param to ending vertex
/// @param weight edge weight / label
/// @return true if successfully added or overwritten;
/// false if either vertices isn't in graph
bool addEdge(VertexT from, VertexT to, WeightT weight) {
// TODO_STUDENT
if (adjacencyList.find(from) != adjacencyList.end() && adjacencyList.find(to)
!= adjacencyList.end()) {
adjacencyList[from][to] = weight;
return true;
}
return false;
}
/// @brief Maybe get the weight associated with a given edge, must run in at most O(log |V|).
/// @param from starting vertex
/// @param to ending vertex
/// @param weight output parameter
/// @return true if the edge exists, and `weight` is set;
/// false if the edge does not exist
bool getWeight(VertexT from, VertexT to, WeightT& weight) const {
// TODO_STUDENT
auto fromIt = adjacencyList.find(from);
if (fromIt != adjacencyList.end()) {
auto toIt = fromIt->second.find(to);
if (toIt != fromIt->second.end()) {
weight = toIt->second;
return true;
}
}
return false;
}
/// @brief Get the out-neighbors of `v`. Must run in at most O(|V|).
/// @param v
/// @return vertices that v has an edge to
set<VertexT> neighbors(VertexT v) const {
set<VertexT> S; //A set that will store the out-neighbors of the vertex v
// TODO_STUDENT
auto it = adjacencyList.find(v);
if (it != adjacencyList.end()) {
for (const auto& neighbor : it->second) {
S.insert(neighbor.first);
}
}
return S; //Returns the out-neighbors of the vertex
}
/// @brief Return a vector containing all vertices in the graph
vector<VertexT> getVertices() const {
// TODO_STUDENT
vector<VertexT> vertices; //Vector that will store all vertices present in the graph
for (const auto& pair : adjacencyList) {
vertices.push_back(pair.first);
}
return vertices;
}
/// @brief Get the number of vertices in the graph. Runs in O(1).
size_t NumVertices() const {
return adjacencyList.size();
}
/// @brief Get the number of directed edges in the graph. Runs in at most O(|V|).
size_t NumEdges() const {
size_t numEdges = 0;
for (const auto& pair : adjacencyList) {
numEdges += pair.second.size(); // Increment by the number of outgoing edges for each vertex
}
return numEdges;
}
};
我的应用程序.cpp：
#include "application.h"
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iomanip> /*setprecision*/
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include "dist.h"
#include "graph.h"
#include "osm.h"
#include "tinyxml2.h"
using namespace std;
using namespace tinyxml2;
double INF = numeric_limits<double>::max();
graph<long long, double> buildGraph(
const map<long long, Coordinates>& Nodes,
const vector<FootwayInfo>& Footways,
const vector<BuildingInfo>& Buildings) {
graph<long long, double> G;
// TODO_STUDENT
for (const auto& node : Nodes) {
G.addVertex(node.first);
}
for (const auto& footway : Footways) { //For each footway
for (size_t i = 0; i + 1 < nodes.size(); ++i) {
long long from = nodes.at(i);
long long to = nodes.at(i + 1);
double distance = distBetween2Points(Nodes.at(from).Lat, Nodes.at(from).Lon,
Nodes.at(to).Lat, Nodes.at(to).Lon);
G.addEdge(from, to, distance);
G.addEdge(to, from, distance);
}
}
for (const auto& building : Buildings) {
G.addVertex(building.Coords.ID);
for (const auto& node : Nodes) {
if (node.second.OnFootway && distBetween2Points(building.Coords.Lat, building.Coords.Lon, node.second.Lat, node.second.Lon) < 0.041) {
G.addEdge(building.Coords.ID, node.first, distBetween2Points(building.Coords.Lat, building.Coords.Lon, node.second.Lat, node.second.Lon));
G.addEdge(node.first, building.Coords.ID, distBetween2Points(building.Coords.Lat, building.Coords.Lon, node.second.Lat, node.second.Lon)); // Bidirectional edge
}
}
}
return G;
}
class prioritize {
public:
bool operator()(const pair<double, long long>& p1, const pair<double, long long>& p2) const {
return p1.first > p2.first; // Compare based on the first element (distance)
}
};
vector<long long> dijkstra(
const graph<long long, double>& G,
long long start,
long long target,
const set<long long>& ignoreNodes) {
vector<long long> path; //Vector to sore the shortest path
// TODO_STUDENT
/*Priority queue to store vertices with their respective distances*/
priority_queue<pair<double, long long>, vector<pair<double, long long> >, prioritize> worklist;
unordered_map<long long, double> distances;
unordered_map<long long, long long> previous;
set<long long> visited;
if (start == target) {
return {start};
}
for (long long vertex : G.getVertices()) {
distances[vertex] = INF; // Set initial distance to
}
distances[start] = 0; //Sets distance to start the vertex to 0
worklist.push(make_pair(0, start)); //Push the start vertex to the priority queue
while (!worklist.empty()) {
long long current = worklist.top().second;
double distance = distances.at(current);
worklist.pop(); // Pops the vertex with the smallest distance
if(current == target) { break; }
if (visited.count(current)) continue;
visited.insert(current);
// Update distances of neighbors
for (long long neighbor : G.neighbors(current)) {
// Skip ignored nodes
if (ignoreNodes.count(neighbor) && neighbor != target) continue;
double weight = 0.0;
double edgeExists = G.getWeight(current, neighbor, weight);
if (!edgeExists) continue;
if (distance + weight < distances[neighbor] || distances.count(neighbor) == 0) {
distances[neighbor] = distance + weight;
previous[neighbor] = current; // Update previous vertex
worklist.push(make_pair(distances[neighbor], neighbor));
}
}
}
long long current = target;
while (current != start) {
path.push_back(current);
current = previous[current];
}
path.push_back(start);
reverse(path.begin(), path.end()); // Reverse the path to get the correct order
return path;
}
double pathLength(const graph<long long, double>& G, const vector<long long>& path) {
double length = 0.0;
double weight = 0.0;
for (size_t i = 0; i + 1 < path.size(); i++) {
bool res = G.getWeight(path.at(i), path.at(i + 1), weight);
assert(res);
length += weight;
}
return length;
}
void outputPath(const vector<long long>& path) {
for (size_t i = 0; i < path.size(); i++) {
cout << path.at(i);
if (i != path.size() - 1) {
cout << "->";
}
}
cout << endl;
}
void application(
const vector<BuildingInfo>& Buildings,
const graph<long long, double>& G) {
string person1Building, person2Building;
set<long long> buildingNodes;
for (const auto& building : Buildings) {
buildingNodes.insert(building.Coords.ID);
}
cout << endl;
cout << "Enter person 1's building (partial name or abbreviation), or #> ";
getline(cin, person1Building);
while (person1Building != "#") {
cout << "Enter person 2's building (partial name or abbreviation)> ";
getline(cin, person2Building);
//
// find the building coordinates
//
bool foundP1 = false;
bool foundP2 = false;
Coordinates P1Coords, P2Coords;
string P1Name, P2Name;
for (const BuildingInfo& building : Buildings) {
if (building.Abbrev == person1Building) {
foundP1 = true;
P1Name = building.Fullname;
P1Coords = building.Coords;
}
if (building.Abbrev == person2Building) {
foundP2 = true;
P2Name = building.Fullname;
P2Coords = building.Coords;
}
}
for (const BuildingInfo& building : Buildings) {
if (!foundP1 &&
building.Fullname.find(person1Building) != string::npos) {
foundP1 = true;
P1Name = building.Fullname;
P1Coords = building.Coords;
}
if (!foundP2 && building.Fullname.find(person2Building) != string::npos) {
foundP2 = true;
P2Name = building.Fullname;
P2Coords = building.Coords;
}
}
if (!foundP1) {
cout << "Person 1's building not found" << endl;
} else if (!foundP2) {
cout << "Person 2's building not found" << endl;
} else {
cout << endl;
cout << "Person 1's point:" << endl;
cout << " " << P1Name << endl << " " << P1Coords.ID << endl;
cout << " (" << P1Coords.Lat << ", " << P1Coords.Lon << ")" << endl;
cout << "Person 2's point:" << endl;
cout << " " << P2Name << endl << " " << P2Coords.ID << endl;
cout << " (" << P2Coords.Lat << ", " << P2Coords.Lon << ")" << endl;
string destName = "";
Coordinates destCoords;
Coordinates centerCoords = centerBetween2Points(
P1Coords.Lat, P1Coords.Lon, P2Coords.Lat, P2Coords.Lon);
double minDestDist = numeric_limits<double>::max();
for (const BuildingInfo& building : Buildings) {
double dist = distBetween2Points(
centerCoords.Lat, centerCoords.Lon,
building.Coords.Lat, building.Coords.Lon);
if (dist < minDestDist) {
minDestDist = dist;
destCoords = building.Coords;
destName = building.Fullname;
}
}
cout << "Destination Building:" << endl;
cout << " " << destName << endl;
cout << " " << destCoords.ID << endl;
cout << " (" << destCoords.Lat << ", " << destCoords.Lon << ")" << endl;
vector<long long> P1Path = dijkstra(G, P1Coords.ID, destCoords.ID, buildingNodes);
vector<long long> P2Path = dijkstra(G, P2Coords.ID, destCoords.ID, buildingNodes);
// This should NEVER happen with how the graph is built
if (P1Path.empty() || P2Path.empty()) {
cout << endl;
cout << "At least one person was unable to reach the destination building. Is an edge missing?" << endl;
cout << endl;
} else {
cout << endl;
cout << "Person 1's distance to dest: " << pathLength(G, P1Path);
cout << " miles" << endl;
cout << "Path: ";
outputPath(P1Path);
cout << endl;
cout << "Person 2's distance to dest: " << pathLength(G, P2Path);
cout << " miles" << endl;
cout << "Path: ";
outputPath(P2Path);
}
}
//
// another navigation?
//
cout << endl;
cout << "Enter person 1's building (partial name or abbreviation), or #> ";
getline(cin, person1Building);
}
}
我的osm.h：
/*osm.h*/
#pragma once
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include "tinyxml2.h"
using namespace std;
using namespace tinyxml2;
//
// Coordinates:
//
// the triple (ID, lat, lon)
//
struct Coordinates {
long long ID;
double Lat;
double Lon;
bool OnFootway;
Coordinates() {
ID = 0;
Lat = 0.0;
Lon = 0.0;
OnFootway = false;
}
Coordinates(long long id, double lat, double lon) {
ID = id;
Lat = lat;
Lon = lon;
OnFootway = false;
}
};
//
// FootwayInfo
//
// Stores info about one footway in the map. The ID uniquely identifies
// the footway. The vector defines points (Nodes) along the footway; the
// vector always contains at least two points.
//
// Example: think of a footway as a sidewalk, with points n1, n2, ...,
// nx, ny. n1 and ny denote the endpoints of the sidewalk, and the points
// n2, ..., nx are intermediate points along the sidewalk.
//
struct FootwayInfo {
long long ID;
vector<long long> Nodes;
FootwayInfo() {
ID = 0;
}
FootwayInfo(long long id) {
ID = id;
}
};
//
// BuildingInfo
//
// Defines a campus building with a fullname, an abbreviation (e.g. SEO),
// and the coordinates of the building (id, lat, lon).
//
struct BuildingInfo {
string Fullname;
string Abbrev;
Coordinates Coords;
BuildingInfo() {
Fullname = "";
Abbrev = "";
Coords = Coordinates();
}
BuildingInfo(string fullname, string abbrev, long long id, double lat, double lon) {
Fullname = fullname;
Abbrev = abbrev;
Coords = Coordinates(id, lat, lon);
}
};
//
// Functions:
//
bool LoadOpenStreetMap(string filename, XMLDocument& xmldoc);
int ReadMapNodes(XMLDocument& xmldoc, map<long long, Coordinates>& Nodes);
int ReadFootways(XMLDocument& xmldoc,
map<long long, Coordinates>& Nodes,
vector<FootwayInfo>& Footways);
int ReadUniversityBuildings(XMLDocument& xmldoc,
const map<long long, Coordinates>& Nodes,
vector<BuildingInfo>& Buildings);
我的main.cpp：
#include <iostream>
#include <iomanip> /*setprecision*/
#include <string>
#include <vector>
#include <map>
#include <cstdlib>
#include <cassert>
#include "tinyxml2.h"
#include "graph.h"
#include "osm.h"
#include "application.h"
using namespace std;
using namespace tinyxml2;
int main() {
// maps a Node ID to it's coordinates (lat, lon)
map<long long, Coordinates> Nodes;
// info about each footway, in no particular order
vector<FootwayInfo> Footways;
// info about each building, in no particular order
vector<BuildingInfo> Buildings;
XMLDocument xmldoc;
cout << "** Navigating UIC open street map **" << endl;
// cout << endl;
cout << std::setprecision(8);
string default_filename = "uic-2024.osm";
string filename;
// cout << "Enter map filename> ";
// getline(cin, filename);
if (filename == "") {
filename = default_filename;
}
// Load XML-based map file
if (!LoadOpenStreetMap(filename, xmldoc)) {
cout << "**Error: unable to load open street map." << endl;
cout << endl;
return 0;
}
// Read the nodes, which are the various known positions on the map:
int nodeCount = ReadMapNodes(xmldoc, Nodes);
// Read the footways, which are the walking paths:
int footwayCount = ReadFootways(xmldoc, Nodes, Footways);
// Read the university buildings:
int buildingCount = ReadUniversityBuildings(xmldoc, Nodes, Buildings);
// Stats
assert(nodeCount == (int)Nodes.size());
assert(footwayCount == (int)Footways.size());
assert(buildingCount == (int)Buildings.size());
// cout << endl;
cout << "# of nodes: " << Nodes.size() << endl;
cout << "# of footways: " << Footways.size() << endl;
cout << "# of buildings: " << Buildings.size() << endl;
// Build graph from input data
graph<long long, double> G = buildGraph(Nodes, Footways, Buildings);
// More stats
cout << "# of vertices: " << G.NumVertices() << endl;
cout << "# of edges: " << G.NumEdges() << endl;
application(Buildings, G);
cout << "** Done **" << endl;
return 0;
}
我的预期输出（我有）：
第一个人的观点：
UIC 学术及住宅综合体 (ARC)
664275388
(41.87478,-87.650866)
2号人的观点：
科学与工程办公室（SEO）
151960667
(41.870851,-87.650375)
目的地大楼：
史蒂文森厅（上海）
151676521
(41.872875,-87.650468)
人 1 到目的地的距离：0.13975891 英里
路径：664275388->2412572929->1645208827->464345369->463814052->464748194->462010750->462010751->9862302685->9870872111-> 151676521
第 2 个人到目的地的距离：0.16077909 英里
路径：151960667->1647971930->462010746->462010758->11257988853->464345492->462010740->9870872102->462010759->151676521
您的问题不包含有关 valgrind 方面的大量详细信息（例如，缺少 valgrind 的版本、生成的确切警告以及您正在使用的选项）。 但在 valgrind 的最新版本中，当 valgrind 观察到大小 > 256 MB 的内存区域的分配或映射时，会生成与字符串“set address range perms”匹配的唯一警告。
这只是一个警告，仅在 valgrind 详细程度 > 0 时显示。
因此，请仔细检查您的代码分配或映射这么大的内存区域是否正常，然后就一切正常了。