How does the == operator for multimaps behave ?

Discussion in 'C++' started by Nikhil.S.Ketkar@gmail.com, Aug 30, 2008.

  1. Guest

    Hi,

    How does the == operator for multimap in STL behave ? I was under the
    impression that this is supposed to properly compare multimaps for
    equality. It seems that what it actually does is just check if each
    member in location L in one multimap is equal to the the member in
    location L in the other multimap. The documentation on
    http://www.sgi.com/tech/stl/Multimap.html says "Tests two multimaps
    for equality. This is a global function, not a member function." and
    nothing more.

    Am I missing something ?
    I have added an illustrative program with output.

    Thanks,
    Nikhil

    #include <iostream>
    #include <map>

    int main(int argc, char *argv)
    {
    int numbers[] = {1,2,3,4,5};

    std::multimap<int, int> a;
    a.insert(std::pair<int, int>(numbers[0], numbers[2]));
    a.insert(std::pair<int, int>(numbers[0], numbers[4]));
    a.insert(std::pair<int, int>(numbers[1], numbers[3]));
    a.insert(std::pair<int, int>(numbers[2], numbers[2]));
    a.insert(std::pair<int, int>(numbers[2], numbers[4]));


    std::multimap<int, int> b;
    b.insert(std::pair<int, int>(numbers[0], numbers[2]));
    b.insert(std::pair<int, int>(numbers[0], numbers[4]));
    b.insert(std::pair<int, int>(numbers[1], numbers[3]));
    b.insert(std::pair<int, int>(numbers[2], numbers[2]));
    b.insert(std::pair<int, int>(numbers[2], numbers[4]));


    std::cout << "Multimap a and b were found to be ";
    if (a == b)
    std::cout << "equal.\n";
    else
    std::cout << "unequal.\n";

    std::multimap<int, int> c;
    c.insert(std::pair<int, int>(numbers[0], numbers[4]));
    c.insert(std::pair<int, int>(numbers[0], numbers[2]));
    c.insert(std::pair<int, int>(numbers[1], numbers[3]));
    c.insert(std::pair<int, int>(numbers[2], numbers[2]));
    c.insert(std::pair<int, int>(numbers[2], numbers[4]));

    std::cout << "Multimap a and c were found to be ";
    if (a == c)
    std::cout << "equal.\n";
    else
    std::cout << "unequal.\n";

    return 0;
    }

    // Output
    //------------------------------------------------------------------------------
    // Multimap a and b were found to be equal.
    // Multimap a and c were found to be unequal.
    //------------------------------------------------------------------------------
     
    , Aug 30, 2008
    #1
    1. Advertising

  2. On 2008-08-30 06:46, wrote:
    > Hi,
    >
    > How does the == operator for multimap in STL behave ? I was under the
    > impression that this is supposed to properly compare multimaps for
    > equality. It seems that what it actually does is just check if each
    > member in location L in one multimap is equal to the the member in
    > location L in the other multimap.


    Yes, it checks if the two multimaps are equal, and two multimaps are
    equal if all the contained elements are equal. Perhaps you wanted to
    check for identity, if two references/pointers to multimaps referes to
    the same multimap? In that case compare the addresses of the objects
    referred to.

    --
    Erik Wikström
     
    Erik Wikström, Aug 30, 2008
    #2
    1. Advertising

  3. Kai-Uwe Bux Guest

    wrote:

    > Hi,
    >
    > How does the == operator for multimap in STL behave ? I was under the
    > impression that this is supposed to properly compare multimaps for
    > equality.


    Yes.

    > It seems that what it actually does is just check if each
    > member in location L in one multimap is equal to the the member in
    > location L in the other multimap.


    Well, that is how "equality" is defined for containers. If you think there
    is a difference, maybe you want to explain what you mean by "properly
    equal" (as opposed to just "equal").

    Anyway, table 65 (Container requirements) defines the semantics of "==" for
    all containers as

    a == b
    if and only if
    a.size() == b.size() and equal( a.begin(), a.end(), b.begin(), b.end() )



    > The documentation on
    > http://www.sgi.com/tech/stl/Multimap.html says "Tests two multimaps
    > for equality. This is a global function, not a member function." and
    > nothing more.
    >
    > Am I missing something ?
    > I have added an illustrative program with output.
    >
    > Thanks,
    > Nikhil
    >
    > #include <iostream>
    > #include <map>
    >
    > int main(int argc, char *argv)
    > {
    > int numbers[] = {1,2,3,4,5};
    >
    > std::multimap<int, int> a;
    > a.insert(std::pair<int, int>(numbers[0], numbers[2]));
    > a.insert(std::pair<int, int>(numbers[0], numbers[4]));
    > a.insert(std::pair<int, int>(numbers[1], numbers[3]));
    > a.insert(std::pair<int, int>(numbers[2], numbers[2]));
    > a.insert(std::pair<int, int>(numbers[2], numbers[4]));
    >
    >
    > std::multimap<int, int> b;
    > b.insert(std::pair<int, int>(numbers[0], numbers[2]));
    > b.insert(std::pair<int, int>(numbers[0], numbers[4]));
    > b.insert(std::pair<int, int>(numbers[1], numbers[3]));
    > b.insert(std::pair<int, int>(numbers[2], numbers[2]));
    > b.insert(std::pair<int, int>(numbers[2], numbers[4]));
    >
    >
    > std::cout << "Multimap a and b were found to be ";
    > if (a == b)
    > std::cout << "equal.\n";
    > else
    > std::cout << "unequal.\n";
    >
    > std::multimap<int, int> c;
    > c.insert(std::pair<int, int>(numbers[0], numbers[4]));
    > c.insert(std::pair<int, int>(numbers[0], numbers[2]));
    > c.insert(std::pair<int, int>(numbers[1], numbers[3]));
    > c.insert(std::pair<int, int>(numbers[2], numbers[2]));
    > c.insert(std::pair<int, int>(numbers[2], numbers[4]));
    >
    > std::cout << "Multimap a and c were found to be ";
    > if (a == c)
    > std::cout << "equal.\n";
    > else
    > std::cout << "unequal.\n";
    >
    > return 0;
    > }
    >
    > // Output
    > //------------------------------------------------------------------------------
    > // Multimap a and b were found to be equal.
    > // Multimap a and c were found to be unequal.
    > //------------------------------------------------------------------------------


    This output is correct.

    BTW: what is the motivation to use such an indirect way of specifying the
    elements of the maps (by using the array "numbers")?



    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Aug 30, 2008
    #3
  4. Guest

    Thanks. That makes it quite clear.


    The way I thought about it is that a multimap is a many-to-many
    function and that equality of multimap implies that the functions are
    identical. That is if I have two sets X = {1,2,3} and Y = {2,3,4} and
    two functions from X to Y, say A = {1->2, 2->3, 3->4} and B = {1->2, 3-
    >4, 2->3}, A is equal to B as the order does not matter, only the

    mapping.

    The example is just something I made up to make my question clear, I
    was actually comparing two multimaps representing many-to-many
    functions on two sets. I guess I will have to write that on my own.


    Thanks again,
    Nikhil
     
    , Aug 30, 2008
    #4
  5. Kai-Uwe Bux Guest

    wrote:

    > Thanks. That makes it quite clear.
    >
    >
    > The way I thought about it is that a multimap is a many-to-many
    > function and that equality of multimap implies that the functions are
    > identical.


    That is correct from a practical point of view. How did you run into
    violations of that notion?

    > That is if I have two sets X = {1,2,3} and Y = {2,3,4} and
    > two functions from X to Y, say A = {1->2, 2->3, 3->4} and B = {1->2, 3-
    >>4, 2->3}, A is equal to B as the order does not matter, only the

    > mapping.


    Well, as long as you don't provide your own comparison predicate, the
    multimap will be sorted in ascending order. So, in your example, B will
    simply not happen since the multimap _will_ store the argument-value pairs
    in the order

    1->2 2->3 3->4

    It will _not_ store the pairs in order of insertion.

    Therefore, only the mapping matters as long as the order defaults to the one
    given by std::less. Only if you provide your own comparison predicates, you
    can tweak the ordering of std::multimap.



    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Aug 30, 2008
    #5
  6. Kai-Uwe Bux Guest

    Kai-Uwe Bux wrote:

    > wrote:
    >
    >> Thanks. That makes it quite clear.
    >>
    >>
    >> The way I thought about it is that a multimap is a many-to-many
    >> function and that equality of multimap implies that the functions are
    >> identical.

    >
    > That is correct from a practical point of view. How did you run into
    > violations of that notion?
    >
    >> That is if I have two sets X = {1,2,3} and Y = {2,3,4} and
    >> two functions from X to Y, say A = {1->2, 2->3, 3->4} and B = {1->2, 3-
    >>>4, 2->3}, A is equal to B as the order does not matter, only the

    >> mapping.

    >
    > Well, as long as you don't provide your own comparison predicate, the
    > multimap will be sorted in ascending order. So, in your example, B will
    > simply not happen since the multimap _will_ store the argument-value pairs
    > in the order
    >
    > 1->2 2->3 3->4
    >
    > It will _not_ store the pairs in order of insertion.
    >
    > Therefore, only the mapping matters as long as the order defaults to the
    > one given by std::less. Only if you provide your own comparison
    > predicates, you can tweak the ordering of std::multimap.


    Oops: correction.

    The multimap is only sorted by keys. If you use the same key twice, then the
    order of insertion does matter. Sorry for the confusion. The example drove
    me in that direction.


    Anyway, as a fix, you could use:

    std::map< key_type, std::set< mapped_type > >

    which models multivalued functions as set-valued functions.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Aug 30, 2008
    #6
    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. Michael
    Replies:
    4
    Views:
    14,481
    Michael
    Aug 4, 2005
  2. Replies:
    12
    Views:
    2,236
    Howard
    Jun 16, 2005
  3. Raymond Hettinger
    Replies:
    3
    Views:
    280
    Claudio Grondi
    Aug 26, 2005
  4. devel
    Replies:
    3
    Views:
    1,001
    Daniel T.
    Apr 10, 2006
  5. brad

    maps turn into multimaps

    brad, Aug 26, 2008, in forum: C++
    Replies:
    14
    Views:
    539
    juanvicfer
    Aug 27, 2008
Loading...

Share This Page