Re: How is map<vector<int>, int> stored? (for graph algorithms)
On Nov 8, 12:55 pm, Digital Puer <digital_p...@hotmail.com> wrote:
On Nov 7, 11:51 pm, Vaclav Haisman <v.hais...@sh.cvut.cz> wrote:
Digital Puer wrote, On 8.11.2009 6:34:
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?
Using std::vector<> as a key for two integere elements is very suboptim=
al.
There is extra indirection, which means its copy ctor and other operati=
ons
have lots more overhead than that of std::pair<>. Also,
sizeof(std::vector<int>) > sizeof(std::pair<int,int>). The access to th=
e
elements is harder, too.
Instead of std::vector<>, use either the std::pair<> or your own Edge c=
lass.
How does STL hash pair<int, int> for use as a map key?
std::map uses the operator<() (less than) function to order it's
elements. The term hash does not apply. std::pair defines this as:
template<class Ty1, class Ty2>
bool operator<(const pair<Ty1, Ty2>& left, const pair<Ty1, Ty2>&
right)
{
return left.first < right.first || !(right.first < left.first) &&
left.second < right.second;
}
which is right from the dinkumware.com website. That is, the first
element is the high order part of the key, and the second element is
the low order part of the key.
HTH