Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > How is map<vector<int>, int> stored? (for graph algorithms)

Reply
Thread Tools

How is map<vector<int>, int> stored? (for graph algorithms)

 
 
Digital Puer
Guest
Posts: n/a
 
      11-08-2009
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?


 
Reply With Quote
 
 
 
 
Vaclav Haisman
Guest
Posts: n/a
 
      11-08-2009
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 suboptimal.
There is extra indirection, which means its copy ctor and other operations
have lots more overhead than that of std:air<>. Also,
sizeof(std::vector<int>) > sizeof(std:air<int,int>). The access to the
elements is harder, too.

Instead of std::vector<>, use either the std:air<> or your own Edge class.

--
VH
 
Reply With Quote
 
 
 
 
Digital Puer
Guest
Posts: n/a
 
      11-08-2009
On Nov 7, 11:51*pm, Vaclav Haisman <(E-Mail Removed)> 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 suboptimal..
> There is extra indirection, which means its copy ctor and other operations
> have lots more overhead than that of std:air<>. Also,
> sizeof(std::vector<int>) > sizeof(std:air<int,int>). The access to the
> elements is harder, too.
>
> Instead of std::vector<>, use either the std:air<> or your own Edge class.
>



How does STL hash pair<int, int> for use as a map key?
 
Reply With Quote
 
AnonMail2005@gmail.com
Guest
Posts: n/a
 
      11-08-2009
On Nov 8, 12:55*pm, Digital Puer <(E-Mail Removed)> wrote:
> On Nov 7, 11:51*pm, Vaclav Haisman <(E-Mail Removed)> 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 suboptimal.
> > There is extra indirection, which means its copy ctor and other operations
> > have lots more overhead than that of std:air<>. Also,
> > sizeof(std::vector<int>) > sizeof(std:air<int,int>). The access to the
> > elements is harder, too.

>
> > Instead of std::vector<>, use either the std:air<> or your own Edge class.

>
> 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:air 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

 
Reply With Quote
 
Joshua Maurice
Guest
Posts: n/a
 
      11-08-2009
On Nov 8, 10:19*am, "(E-Mail Removed)" <(E-Mail Removed)>
wrote:
> On Nov 8, 12:55*pm, Digital Puer <(E-Mail Removed)> wrote:
>
>
>
> > On Nov 7, 11:51*pm, Vaclav Haisman <(E-Mail Removed)> 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 suboptimal.
> > > There is extra indirection, which means its copy ctor and other operations
> > > have lots more overhead than that of std:air<>. Also,
> > > sizeof(std::vector<int>) > sizeof(std:air<int,int>). The access to the
> > > elements is harder, too.

>
> > > Instead of std::vector<>, use either the std:air<> or your own Edge class.

>
> > 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:air defines this as:


Well, C++03 the term hash does not apply. For TR2 or C++0x, we're
getting hash sets and hash maps, so it does apply in these cases.
However, the OP is still wrong as he implied that std::map is a hash
map. It is not. It is a red-black binary tree (or at least almost
certainly is because of the complexity requirements in the standard).
 
Reply With Quote
 
Digital Puer
Guest
Posts: n/a
 
      11-08-2009
On Nov 8, 1:11*pm, Joshua Maurice <(E-Mail Removed)> wrote:
> On Nov 8, 10:19*am, "(E-Mail Removed)" <(E-Mail Removed)>
> wrote:
>
>
>
>
>
> > On Nov 8, 12:55*pm, Digital Puer <(E-Mail Removed)> wrote:

>
> > > On Nov 7, 11:51*pm, Vaclav Haisman <(E-Mail Removed)> 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 suboptimal.
> > > > There is extra indirection, which means its copy ctor and other operations
> > > > have lots more overhead than that of std:air<>. Also,
> > > > sizeof(std::vector<int>) > sizeof(std:air<int,int>). The access to the
> > > > elements is harder, too.

>
> > > > Instead of std::vector<>, use either the std:air<> or your own Edge class.

>
> > > 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:air defines this as:

>
> Well, C++03 the term hash does not apply. For TR2 or C++0x, we're
> getting hash sets and hash maps, so it does apply in these cases.
> However, the OP is still wrong as he implied that std::map is a hash
> map. It is not. It is a red-black binary tree (or at least almost
> certainly is because of the complexity requirements in the standard).


By "hash", I meant to ask how are the keys compared? For a
map<vector<int>, int>, how would the keys be compared? I assume the
comparer must walk down both vectors and do element-wise comparison,
and if two vectors are the same through N elements but one vector
is longer, then the shorter one wins the comparison?

 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      11-09-2009
On Nov 8, 10:35 pm, Digital Puer <(E-Mail Removed)> wrote:
> On Nov 8, 1:11 pm, Joshua Maurice <(E-Mail Removed)> wrote:
> > On Nov 8, 10:19 am, "(E-Mail Removed)" <(E-Mail Removed)>
> > wrote:
> > > On Nov 8, 12:55 pm, Digital Puer <(E-Mail Removed)> wrote:
> > > > On Nov 7, 11:51 pm, Vaclav Haisman <(E-Mail Removed)> 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>.


More logical than either would be to define an Edge class. But
vector is a very poor approximation of an edge, since it can
have any number of values, not just exactly two.

> > > > > > 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 suboptimal. There is extra indirection, which
> > > > > means its copy ctor and other operations have lots
> > > > > more overhead than that of std:air<>. Also,
> > > > > sizeof(std::vector<int>) > sizeof(std:air<int,int>).
> > > > > The access to the elements is harder, too.


> > > > > Instead of std::vector<>, use either the std:air<>
> > > > > or your own Edge class.


> > > > 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:air defines this as:


> > Well, C++03 the term hash does not apply. For TR2 or C++0x,
> > we're getting hash sets and hash maps, so it does apply in
> > these cases. However, the OP is still wrong as he implied
> > that std::map is a hash map. It is not. It is a red-black
> > binary tree (or at least almost certainly is because of the
> > complexity requirements in the standard).


It's not necessarily a red-black tree, but in practice, it must
be some form of more or less balanced tree to meet the
complexity requirements.

> By "hash", I meant to ask how are the keys compared? For a
> map<vector<int>, int>, how would the keys be compared?


Straightforward lexographical comparison.

> I assume the comparer must walk down both vectors and do
> element-wise comparison, and if two vectors are the same
> through N elements but one vector is longer, then the shorter
> one wins the comparison?


Exactly.

Note that that's more or less what std:air does as well.
Except that one pair will never be longer than the other, and
since the class knows the length, and the length is small, it
won't bother with a loop, but will simply do the two
comparisons.

--
James Kanze
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
[Boost.Graph] graph.vertices property creates new objects George Sakkis Python 1 01-29-2007 11:09 PM
Help with initialization of graph (Boost Graph Library) Jef Driesen C++ 3 01-24-2006 01:44 PM
Missing Graph.h and (Graph.lib) woes - any help Dr Ann Huxtable C Programming 6 12-21-2004 11:15 AM
GD::Graph: "mixed" graph doesn't recognize "area" graph type Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM



Advertisments