D
Digital Puer
I am trying to implement some graph algorithms, and I need
to manage a typical weighted adjacency data structure,
such that A[v1, v2] = w, where w is the weight of the
directed edge that connects vertex v1 to vertex v2.
I know the standard implementations of this data structure,
namely the adjacency matrix and the adjacency list.
http://en.wikipedia.org/wiki/Adjacency_matrix
http://en.wikipedia.org/wiki/Adjacency_list
Then I got to thinking how C++ STL would handle the following:
map<vector<int>, int> A;
int v1, v2, w;
vector<int> edge;
edge.push_back(v1);
edge.push_back(v2);
A[edge] = w;
Yes, I know that I can use pair<int, int> instead of vector<int>.
How does STL internally manage map<vector<int>, int>
or map<pair<int, int>, int>?
How well does they compare in memory and lookup time to
an adjacency matrix and an adjacency list?
to manage a typical weighted adjacency data structure,
such that A[v1, v2] = w, where w is the weight of the
directed edge that connects vertex v1 to vertex v2.
I know the standard implementations of this data structure,
namely the adjacency matrix and the adjacency list.
http://en.wikipedia.org/wiki/Adjacency_matrix
http://en.wikipedia.org/wiki/Adjacency_list
Then I got to thinking how C++ STL would handle the following:
map<vector<int>, int> A;
int v1, v2, w;
vector<int> edge;
edge.push_back(v1);
edge.push_back(v2);
A[edge] = w;
Yes, I know that I can use pair<int, int> instead of vector<int>.
How does STL internally manage map<vector<int>, int>
or map<pair<int, int>, int>?
How well does they compare in memory and lookup time to
an adjacency matrix and an adjacency list?