STL Help for a newbie

Discussion in 'C++' started by Deepak, Oct 6, 2004.

  1. Deepak

    Deepak Guest

    Hello,
    I am working on a project where I am using the STL's "map"
    datastructure inside a class that just acts as a container for the map
    and manages it. The map a Key class to integers. The Key class just
    has two variables of user defined types. I had implemented the key
    comprarer structure that map requires like so:

    struct KeyComparer
    {
    bool operator() (const Key & k1, const Key & k2) const
    {
    return ((k1.getA() < k2.getA()) &&
    (k1.getB() < k2.getB()));
    }
    };


    What i am finding is that whenever i use the maps internal functions
    such as find(..) or insert(...) it doesnt work.
    I have overloaded the '<', '==', and '=' operators, have copy
    constructors/assignment operators defined.

    It seems like the find() is just comparing one of the two components
    of Key and therefore does not do the correct comparison even though i
    defined the comparer.
    The insert seems like it just doesnt insert beyond the first entry.
    I would really appreciate if someone could provide me with insight as
    to how to tackle this problem. Any help is appreciated.
    Sincerely,
    D
    Deepak, Oct 6, 2004
    #1
    1. Advertising

  2. "Deepak" <> wrote in message
    news:...
    > Hello,
    > I am working on a project where I am using the STL's "map"
    > datastructure inside a class that just acts as a container for the map
    > and manages it. The map a Key class to integers. The Key class just
    > has two variables of user defined types. I had implemented the key
    > comprarer structure that map requires like so:
    >
    > struct KeyComparer
    > {
    > bool operator() (const Key & k1, const Key & k2) const
    > {
    > return ((k1.getA() < k2.getA()) &&
    > (k1.getB() < k2.getB()));
    > }
    > };
    >
    >
    > What i am finding is that whenever i use the maps internal functions
    > such as find(..) or insert(...) it doesnt work.


    Your comparator is wrong. It doesn't do a less than comparison. What you
    probably want is this

    struct KeyComparer
    {
    bool operator() (const Key & k1, const Key & k2) const
    {
    return k1.getA() < k2.getA() || (!(k2.getA() < k1.getA()) && k1.getB() <
    k2.getB()));
    }
    };

    When you have a pair of keys then the combined key is less than if the first
    key is less than, OR if the first key is equal AND the second key is less
    than.

    Your comparotor simply doesn't do anything like a less than comparison so
    map gets confused.

    john
    John Harrison, Oct 6, 2004
    #2
    1. Advertising

  3. Deepak

    David Fisher Guest

    John Harrison wrote:
    > Deepak wrote:
    > > struct KeyComparer
    > > {
    > > bool operator() (const Key & k1, const Key & k2) const
    > > {
    > > return ((k1.getA() < k2.getA()) &&
    > > (k1.getB() < k2.getB()));
    > > }
    > > };
    > >
    > >
    > > What i am finding is that whenever i use the maps internal functions
    > > such as find(..) or insert(...) it doesnt work.

    >
    > Your comparator is wrong. It doesn't do a less than comparison.


    [snip]

    Simple example of why the comparison function is incorrect (assuming integer
    values and the existence of a Key(int a, int b) constructor):

    Key(1, 5) < Key(5, 1) returns false
    Key(5, 1) < Key(1, 5) returns false

    If A < B is false, and A > B is false, and A does not equal B, then there is
    a problem ...

    David Fisher
    Sydney, Australia
    David Fisher, Oct 6, 2004
    #3
  4. "David Fisher" <> wrote in message
    news:plN8d.4529$...
    > John Harrison wrote:
    > > Deepak wrote:
    > > > struct KeyComparer
    > > > {
    > > > bool operator() (const Key & k1, const Key & k2) const
    > > > {
    > > > return ((k1.getA() < k2.getA()) &&
    > > > (k1.getB() < k2.getB()));
    > > > }
    > > > };
    > > >
    > > >
    > > > What i am finding is that whenever i use the maps internal functions
    > > > such as find(..) or insert(...) it doesnt work.

    > >
    > > Your comparator is wrong. It doesn't do a less than comparison.

    >
    > [snip]
    >
    > Simple example of why the comparison function is incorrect (assuming

    integer
    > values and the existence of a Key(int a, int b) constructor):
    >
    > Key(1, 5) < Key(5, 1) returns false
    > Key(5, 1) < Key(1, 5) returns false
    >
    > If A < B is false, and A > B is false, and A does not equal B, then there

    is
    > a problem ...


    Whether Key(1, 5) equals Key(5, 1) is up to the OP (although I suspect its
    not what the OP intended). In itself this isn't an error. But consider this

    Key x(1, 3);
    Key y(3, 1);
    Key z(2, 4);

    Here we have x < y is false, and y < x is false, which implies x == y
    Also we have y < z is false, and z < y is false, which implies y == z
    But x < z, so we have x== y and y == z but x < z. That is an error because
    it breaks the rule that equality must be transitive.

    john
    John Harrison, Oct 6, 2004
    #4
  5. Deepak

    Deepak Guest

    Great Thanks guys. I understand the issue. Its rather clear now.
    I hope this change solves my problems.
    Thanks to google groups.
    Regards

    "John Harrison" <> wrote in message news:<>...
    > "David Fisher" <> wrote in message
    > news:plN8d.4529$...
    > > John Harrison wrote:
    > > > Deepak wrote:
    > > > > struct KeyComparer
    > > > > {
    > > > > bool operator() (const Key & k1, const Key & k2) const
    > > > > {
    > > > > return ((k1.getA() < k2.getA()) &&
    > > > > (k1.getB() < k2.getB()));
    > > > > }
    > > > > };
    > > > >
    > > > >
    > > > > What i am finding is that whenever i use the maps internal functions
    > > > > such as find(..) or insert(...) it doesnt work.
    > > >
    > > > Your comparator is wrong. It doesn't do a less than comparison.

    > >
    > > [snip]
    > >
    > > Simple example of why the comparison function is incorrect (assuming

    > integer
    > > values and the existence of a Key(int a, int b) constructor):
    > >
    > > Key(1, 5) < Key(5, 1) returns false
    > > Key(5, 1) < Key(1, 5) returns false
    > >
    > > If A < B is false, and A > B is false, and A does not equal B, then there

    > is
    > > a problem ...

    >
    > Whether Key(1, 5) equals Key(5, 1) is up to the OP (although I suspect its
    > not what the OP intended). In itself this isn't an error. But consider this
    >
    > Key x(1, 3);
    > Key y(3, 1);
    > Key z(2, 4);
    >
    > Here we have x < y is false, and y < x is false, which implies x == y
    > Also we have y < z is false, and z < y is false, which implies y == z
    > But x < z, so we have x== y and y == z but x < z. That is an error because
    > it breaks the rule that equality must be transitive.
    >
    > john
    Deepak, Oct 6, 2004
    #5
  6. Deepak

    Deepak Guest

    John
    From your explanation was this what you meant?
    struct KeyComparer
    {
    bool operator() (const Key & k1, const Key & k2) const
    {
    return k1.getA() < k2.getA() || ((k2.getA()== k1.getA()) && k1.getB() <
    k2.getB()));
    }
    };


    You suggested a slightly different comparison operator?
    Deepak
    "John Harrison" <> wrote in message news:<>...
    > "Deepak" <> wrote in message
    > news:...
    > > Hello,
    > > I am working on a project where I am using the STL's "map"
    > > datastructure inside a class that just acts as a container for the map
    > > and manages it. The map a Key class to integers. The Key class just
    > > has two variables of user defined types. I had implemented the key
    > > comprarer structure that map requires like so:
    > >
    > > struct KeyComparer
    > > {
    > > bool operator() (const Key & k1, const Key & k2) const
    > > {
    > > return ((k1.getA() < k2.getA()) &&
    > > (k1.getB() < k2.getB()));
    > > }
    > > };
    > >
    > >
    > > What i am finding is that whenever i use the maps internal functions
    > > such as find(..) or insert(...) it doesnt work.

    >
    > Your comparator is wrong. It doesn't do a less than comparison. What you
    > probably want is this
    >
    > struct KeyComparer
    > {
    > bool operator() (const Key & k1, const Key & k2) const
    > {
    > return k1.getA() < k2.getA() || (!(k2.getA() < k1.getA()) && k1.getB() <
    > k2.getB()));
    > }
    > };
    >
    > When you have a pair of keys then the combined key is less than if the first
    > key is less than, OR if the first key is equal AND the second key is less
    > than.
    >
    > Your comparotor simply doesn't do anything like a less than comparison so
    > map gets confused.
    >
    > john
    Deepak, Oct 6, 2004
    #6
  7. "Deepak" <> wrote in message
    news:...
    > John
    > From your explanation was this what you meant?
    > struct KeyComparer
    > {
    > bool operator() (const Key & k1, const Key & k2) const
    > {
    > return k1.getA() < k2.getA() || ((k2.getA()== k1.getA()) && k1.getB()
    > <
    > k2.getB()));
    > }
    > };
    >
    >
    > You suggested a slightly different comparison operator?
    > Deepak


    They should be the same, mine only uses operator< while yours assumes that
    Key has both operator< and operator==.

    john
    John Harrison, Oct 6, 2004
    #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. Allan Bruce

    To STL or not to STL

    Allan Bruce, Oct 16, 2003, in forum: C++
    Replies:
    41
    Views:
    1,010
    Christopher Benson-Manica
    Oct 17, 2003
  2. Replies:
    4
    Views:
    780
    Daniel T.
    Feb 16, 2006
  3. Replies:
    2
    Views:
    538
    klaus hoffmann
    Feb 22, 2006
  4. Replies:
    5
    Views:
    492
    Markus Schoder
    Apr 16, 2006
  5. Steve
    Replies:
    2
    Views:
    490
    Andre Kostur
    Nov 6, 2007
Loading...

Share This Page