Map losing elements!?

Discussion in 'C++' started by Johannes Bauer, Oct 2, 2008.

  1. Hello group,

    I've been trying around with a simple std::map<mytype, unsigned> for an
    hour now and can't find the bug. It is my belief that I am missing
    something incredibly obvious... please help me see it.

    Scenario: I created the map and inserted some elements. Afterwards I try
    to iterate over them:

    std::map<mytype, unsigned int> values;
    /* insert some values, say 5 */

    /* this will then report 5 */
    std::cerr << "cnt = " << values.size() << std::endl;

    for (std::map<mytype, unsigned int>::iterator j = values.begin(); j !=
    values.end(); j++) {
    std::cerr << j->second << " -> ";
    j->first.Dump();
    std::cerr << std::endl;
    }

    However in the "for" loop, always only 2 items show up. I figured
    something was wrong with my operator< - essentialy "mytype" is just a
    container around a LENGTH byte unsigned char[] array:

    bool operator<(const mytype &Other) const {
    for (unsigned int i = 0; i < LENGTH; i++) {
    if (Other.Data < Data) return true;
    }
    return false;
    }

    Can anyone explain this behaviour?

    Thanks in advance,
    Johannes

    --
    "Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
    verlästerung von Gott, Bibel und mir und bewusster Blasphemie."
    -- Prophet und Visionär Hans Joss aka HJP in de.sci.physik
    <48d8bf1d$0$7510$>
     
    Johannes Bauer, Oct 2, 2008
    #1
    1. Advertising

  2. Johannes Bauer

    LR Guest

    Johannes Bauer wrote:

    > bool operator<(const mytype &Other) const {
    > for (unsigned int i = 0; i < LENGTH; i++) {
    > if (Other.Data < Data) return true;
    > }
    > return false;
    > }



    Are you sure you didn't mean
    if(Data < Other.Data) return true;


    Either way, this doesn't work.

    I'm not sure what your mytype looks like, so please consider this
    incorrect-won't-work snippet:

    class M {
    enum { LENGTH = 3 };
    int a[LENGTH];
    public:
    M(const int q, const int r, const int s) {
    a[0] = q;
    a[1] = r;
    a[2] = s;
    }

    // this comparison is insufficient and won't work
    // for the intended purpose.
    bool operator<(const M &m) const {
    for(size_t i=0; i<LENGTH; i++) {
    if(a < m.a)
    return true;
    }
    return false;
    }
    };

    int main() {
    const M a(1,2,3);
    const M b(2,1,3);
    std::cout << (a < b) << std::endl;
    std::cout << (b < a) << std::endl;
    }

    The output from this indicates that (a<b) and (b<a) are both true. That
    will cause problems with std::map. Your comparison function is incorrect.

    When trying a < b
    when i==0, 1 < 2 returns true.

    When trying b < a
    when i==0, 2 < 1 has no effect and the loop continues.
    when i==1, 1 < 2 returns true.

    LR
     
    LR, Oct 2, 2008
    #2
    1. Advertising

  3. Johannes Bauer

    James Kanze Guest

    On Oct 2, 2:44 am, Johannes Bauer <> wrote:

    > I've been trying around with a simple std::map<mytype,
    > unsigned> for an hour now and can't find the bug. It is my
    > belief that I am missing something incredibly obvious...
    > please help me see it.


    > Scenario: I created the map and inserted some elements.
    > Afterwards I try to iterate over them:


    > std::map<mytype, unsigned int> values;
    > /* insert some values, say 5 */


    > /* this will then report 5 */
    > std::cerr << "cnt = " << values.size() << std::endl;


    > for (std::map<mytype, unsigned int>::iterator j = values.begin(); j !=
    > values.end(); j++) {
    > std::cerr << j->second << " -> ";
    > j->first.Dump();
    > std::cerr << std::endl;
    > }


    > However in the "for" loop, always only 2 items show up. I
    > figured something was wrong with my operator< - essentialy
    > "mytype" is just a container around a LENGTH byte unsigned
    > char[] array:


    > bool operator<(const mytype &Other) const {
    > for (unsigned int i = 0; i < LENGTH; i++) {
    > if (Other.Data < Data) return true;
    > }
    > return false;
    > }


    > Can anyone explain this behaviour?


    Your comparison operator is obviously wrong. If we suppose Data
    is an int[3], then what happens if you compare { 1, 2, 3 } and
    { 2, 1, 3 }. Regardless of the order, you're function returns
    true, i.e. given
    Data a = { 1, 2, 3 } ;
    Data b = { 2, 1, 3 } ;
    your function returns true for both a<b and b<a. One of the
    requirements is that if a<b, then !(b<a). What you probably
    want is something more like:

    for ( int i = 0 ;
    i != LENGTH && data[ i ] == other.data[ i ] ;
    ++ i ) {
    }
    return i != LENGTH
    && data[ i ] < other.data[ i ] ;

    (In this case, your result depends entirely on the first
    non-equal element, and if false if all elements are equal.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Oct 2, 2008
    #3
  4. Johannes Bauer

    James Kanze Guest

    On Oct 2, 3:22 am, Sam <> wrote:
    > Johannes Bauer writes:
    > > I've been trying around with a simple std::map<mytype,
    > > unsigned> for an hour now and can't find the bug. It is my
    > > belief that I am missing something incredibly obvious...
    > > please help me see it.


    > > Scenario: I created the map and inserted some elements.
    > > Afterwards I try to iterate over them:


    > > std::map<mytype, unsigned int> values;
    > > /* insert some values, say 5 */


    > > /* this will then report 5 */
    > > std::cerr << "cnt = " << values.size() << std::endl;


    > > for (std::map<mytype, unsigned int>::iterator j = values.begin(); j !=
    > > values.end(); j++) {
    > > std::cerr << j->second << " -> ";
    > > j->first.Dump();
    > > std::cerr << std::endl;
    > > }


    > > However in the "for" loop, always only 2 items show up. I
    > > figured something was wrong with my operator< - essentialy
    > > "mytype" is just a container around a LENGTH byte unsigned
    > > char[] array:


    > > bool operator<(const mytype &Other) const {
    > > for (unsigned int i = 0; i < LENGTH; i++) {
    > > if (Other.Data < Data) return true;
    > > }
    > > return false;
    > > }


    > > Can anyone explain this behaviour?


    > Although your operator< does look wrong, this wouldn't really
    > explain your claimed problem. If there are 5 elements in the
    > map, then there are 5 elements in the plan.


    It's undefined behavior. Consider an implementation which
    maintains a dummy node for end, and a separate count for all
    insertions. An error in the comparison operator could easily
    cause the implementation to insert the node behind end, or
    somewhere else it is no longer accessible. More generally, once
    he has inserted an element using this comparison function,
    anything goes.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Oct 2, 2008
    #4
  5. Johannes Bauer

    Guest

    On 2 Oct, 01:44, Johannes Bauer <> wrote:
    > bool operator<(const mytype &Other) const {
    >         for (unsigned int i = 0; i < LENGTH; i++) {
    >                 if (Other.Data < Data) return true;
    >         }
    >         return false;
    >
    > }


    You could use std::lexicographical_compare:

    bool operator<(const mytype &Other) const {
     
    , Oct 2, 2008
    #5
  6. Johannes Bauer

    Guest

    On 2 Oct, 10:01, wrote:
    > On 2 Oct, 01:44, Johannes Bauer <> wrote:
    >
    > > bool operator<(const mytype &Other) const {
    > >         for (unsigned int i = 0; i < LENGTH; i++) {
    > >                 if (Other.Data < Data) return true;
    > >         }
    > >         return false;

    >
    > > }

    >
    > You could use std::lexicographical_compare:
    >
    > bool operator<(const mytype &Other) const {


    oops...

    bool operator<(const mytype &Other) const {
    return std::lexicographical_compare( Other.Data, Other.Data +
    LENGTH, Data, Data + LENGTH );
    }

    should do the trick.

    Guy
     
    , Oct 2, 2008
    #6
  7. Hello everyone again,

    Johannes Bauer schrieb:

    > Can anyone explain this behaviour?


    Of course you could :-\

    Thank you very much for your kind suggestions, each and every one of you
    has pointed out the correct solution (my broken operator<)... I really
    looked over it over and over again, but really didn't see the mistake
    (that the for loop should only continue when a == b).

    Guess I should stop writing code after 3 am...

    Thanks again!

    Kind regards,
    Johannes

    --
    "Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
    verlästerung von Gott, Bibel und mir und bewusster Blasphemie."
    -- Prophet und Visionär Hans Joss aka HJP in de.sci.physik
    <48d8bf1d$0$7510$>
     
    Johannes Bauer, Oct 2, 2008
    #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. alex
    Replies:
    1
    Views:
    690
    Lau Lei Cheong
    Feb 4, 2005
  2. Matthias Hildebrand
    Replies:
    5
    Views:
    8,192
    krogers
    Mar 20, 2012
  3. Vlad
    Replies:
    0
    Views:
    388
  4. Patrick Guio
    Replies:
    6
    Views:
    3,264
    chris
    Oct 20, 2004
  5. Jason C
    Replies:
    4
    Views:
    706
    Morty Abzug
    Jun 26, 2012
Loading...

Share This Page