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

Discussion in 'C++' started by Digital Puer, Nov 8, 2009.

  1. Digital Puer

    Digital Puer Guest

    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?
     
    Digital Puer, Nov 8, 2009
    #1
    1. Advertising

  2. 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::pair<>. Also,
    sizeof(std::vector<int>) > sizeof(std::pair<int,int>). The access to the
    elements is harder, too.

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

    --
    VH
     
    Vaclav Haisman, Nov 8, 2009
    #2
    1. Advertising

  3. Digital Puer

    Digital Puer Guest

    On Nov 7, 11:51 pm, Vaclav Haisman <> 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::pair<>. Also,
    > sizeof(std::vector<int>) > sizeof(std::pair<int,int>). The access to the
    > elements is harder, too.
    >
    > Instead of std::vector<>, use either the std::pair<> or your own Edge class.
    >



    How does STL hash pair<int, int> for use as a map key?
     
    Digital Puer, Nov 8, 2009
    #3
  4. Digital Puer

    Guest

    On Nov 8, 12:55 pm, Digital Puer <> wrote:
    > On Nov 7, 11:51 pm, Vaclav Haisman <> 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::pair<>. Also,
    > > sizeof(std::vector<int>) > sizeof(std::pair<int,int>). The access to the
    > > elements is harder, too.

    >
    > > Instead of std::vector<>, use either the std::pair<> 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::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
     
    , Nov 8, 2009
    #4
  5. On Nov 8, 10:19 am, "" <>
    wrote:
    > On Nov 8, 12:55 pm, Digital Puer <> wrote:
    >
    >
    >
    > > On Nov 7, 11:51 pm, Vaclav Haisman <> 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::pair<>. Also,
    > > > sizeof(std::vector<int>) > sizeof(std::pair<int,int>). The access to the
    > > > elements is harder, too.

    >
    > > > Instead of std::vector<>, use either the std::pair<> 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::pair 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).
     
    Joshua Maurice, Nov 8, 2009
    #5
  6. Digital Puer

    Digital Puer Guest

    On Nov 8, 1:11 pm, Joshua Maurice <> wrote:
    > On Nov 8, 10:19 am, "" <>
    > wrote:
    >
    >
    >
    >
    >
    > > On Nov 8, 12:55 pm, Digital Puer <> wrote:

    >
    > > > On Nov 7, 11:51 pm, Vaclav Haisman <> 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::pair<>. Also,
    > > > > sizeof(std::vector<int>) > sizeof(std::pair<int,int>). The access to the
    > > > > elements is harder, too.

    >
    > > > > Instead of std::vector<>, use either the std::pair<> 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::pair 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?
     
    Digital Puer, Nov 8, 2009
    #6
  7. Digital Puer

    James Kanze Guest

    On Nov 8, 10:35 pm, Digital Puer <> wrote:
    > On Nov 8, 1:11 pm, Joshua Maurice <> wrote:
    > > On Nov 8, 10:19 am, "" <>
    > > wrote:
    > > > On Nov 8, 12:55 pm, Digital Puer <> wrote:
    > > > > On Nov 7, 11:51 pm, Vaclav Haisman <> 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::pair<>. Also,
    > > > > > sizeof(std::vector<int>) > sizeof(std::pair<int,int>).
    > > > > > The access to the elements is harder, too.


    > > > > > Instead of std::vector<>, use either the std::pair<>
    > > > > > 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::pair 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::pair 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
     
    James Kanze, Nov 9, 2009
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Barak
    Replies:
    0
    Views:
    814
    Barak
    Aug 7, 2003
  2. pmatos
    Replies:
    6
    Views:
    23,855
  3. Replies:
    8
    Views:
    1,939
    Csaba
    Feb 18, 2006
  4. jdm
    Replies:
    1
    Views:
    666
    Victor Bazarov
    May 18, 2010
  5. Emilio Mayorga
    Replies:
    6
    Views:
    344
    Martien Verbruggen
    Oct 8, 2003
Loading...

Share This Page