Re: hashtable or map? (map inserts not behaving as I expect - and I cant find a decent simple exampl

Discussion in 'C++' started by Kai-Uwe Bux, Dec 21, 2008.

  1. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    Obnoxious User wrote:

    > On Sun, 21 Dec 2008 16:44:33 +0000, (2b|!2b)==? wrote:
    >
    >> I have a list of items that I want to ignore during processing. I read a
    >> list of items from file and populate a map variable. However, only a
    >> subset of the items are being inserted in the map.
    >>
    >> The struct for IgnoreItem looks like this:
    >>
    >> struct IgnoreItem
    >> {
    >> //ctors and op== omitted for the sake of brevity
    >>
    >> bool operator<(const IgnoreItem& key) const {
    >> if ( _stricmp(syb.c_str(), key.syb.c_str()) < 0)
    >> return true;
    >> else if (_stricmp(key.syb.c_str(), syb.c_str()) < 0)
    >> return false;
    >> else if ( xid < key.xid )
    >> return true ;
    >> else if ( key.xid < xid )
    >> return false;
    >> else if ( icid < key.icid)
    >> return true ;
    >> else
    >> return key.icid < icid ;
    >> }


    I think, you messed up on the third criterion: if the syb and xid compare
    equal, you return true whenever icid of *this and key differ.

    >>
    >> std::string syb;
    >> unsigned char xid ;
    >> long icid ;
    >> };
    >>

    >
    > That's just messed up.
    >
    > Pseudo code:
    >
    > if(syb < key.syb) return true;
    > if(syb == key.syb) {
    > if(xid < key.xid) return true;
    > if(xid == key.xid) {
    > if(icid < key.icid) return true;
    > }
    > }
    > return false;
    >
    > Do you see the pattern?


    Well, there is another pattern, which is closer to the code posted:

    if ( lhs.syb < rhs.syb ) return true;
    if ( rhs.syb < lhs.syb ) return false;
    if ( lhs.xid < rhs.xid ) return true;
    if ( rhs.xid < lhs.xid ) return false;
    if ( lhs.icid < rhs.icid ) return true;
    if ( rhs.icid < lhs.icid ) return false;
    return false;


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Dec 21, 2008
    #1
    1. Advertising

  2. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    (2b|!2b)==? wrote:

    > Kai-Uwe Bux wrote:
    >> Obnoxious User wrote:
    >>
    >>> On Sun, 21 Dec 2008 16:44:33 +0000, (2b|!2b)==? wrote:
    >>>
    >>>> I have a list of items that I want to ignore during processing. I read
    >>>> a list of items from file and populate a map variable. However, only a
    >>>> subset of the items are being inserted in the map.
    >>>>
    >>>> The struct for IgnoreItem looks like this:
    >>>>
    >>>> struct IgnoreItem
    >>>> {
    >>>> //ctors and op== omitted for the sake of brevity
    >>>>
    >>>> bool operator<(const IgnoreItem& key) const {
    >>>> if ( _stricmp(syb.c_str(), key.syb.c_str()) < 0)
    >>>> return true;
    >>>> else if (_stricmp(key.syb.c_str(), syb.c_str()) < 0)
    >>>> return false;
    >>>> else if ( xid < key.xid )
    >>>> return true ;
    >>>> else if ( key.xid < xid )
    >>>> return false;
    >>>> else if ( icid < key.icid)
    >>>> return true ;
    >>>> else
    >>>> return key.icid < icid ;
    >>>> }

    >>
    >> I think, you messed up on the third criterion: if the syb and xid compare
    >> equal, you return true whenever icid of *this and key differ.
    >>
    >>>> std::string syb;
    >>>> unsigned char xid ;
    >>>> long icid ;
    >>>> };
    >>>>
    >>> That's just messed up.
    >>>
    >>> Pseudo code:
    >>>
    >>> if(syb < key.syb) return true;
    >>> if(syb == key.syb) {
    >>> if(xid < key.xid) return true;
    >>> if(xid == key.xid) {
    >>> if(icid < key.icid) return true;
    >>> }
    >>> }
    >>> return false;
    >>>
    >>> Do you see the pattern?

    >>
    >> Well, there is another pattern, which is closer to the code posted:
    >>
    >> if ( lhs.syb < rhs.syb ) return true;
    >> if ( rhs.syb < lhs.syb ) return false;
    >> if ( lhs.xid < rhs.xid ) return true;
    >> if ( rhs.xid < lhs.xid ) return false;
    >> if ( lhs.icid < rhs.icid ) return true;
    >> if ( rhs.icid < lhs.icid ) return false;
    >> return false;
    >>
    >>
    >> Best
    >>
    >> Kai-Uwe Bux

    >
    > Hi Kai,


    It's Kai-Uwe. I do not have a middle name.

    > thanks for pointing out my pretzel logic. I updated my code to
    > reflect the changes you mentioned - however the effect is still the same
    > - I only have 21 items in the map instead of the original list of 84,
    > and the syb fields of the keys are unique.


    Then the bug might not be hinding in the comparison function. Please post
    the smallest complete program that exhibits the problem.

    > This is a problem because the
    > rows (i.e. composite fields) in my list that are unique ... I am tempted
    > to write a hashing dunction that takes a string, char, long and returns
    > a long, so that I use that as the key instead ... but that is simply
    > avoiding the issue of storing my IgnoreItem keys which are unique, in a
    > std::map ...


    True.


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Dec 21, 2008
    #2
    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. puzzlecracker
    Replies:
    3
    Views:
    1,108
    HalcyonWild
    Jun 2, 2005
  2. Nagaraj
    Replies:
    1
    Views:
    838
    Lionel B
    Mar 1, 2007
  3. Simon Strandgaard

    how to expect eof with expect+pty

    Simon Strandgaard, Dec 20, 2006, in forum: Ruby
    Replies:
    4
    Views:
    336
    Simon Strandgaard
    Dec 20, 2006
  4. Daniel Pitts
    Replies:
    20
    Views:
    1,652
    albertom
    Feb 19, 2013
  5. Phil
    Replies:
    0
    Views:
    155
Loading...

Share This Page