hashtable or map? (map inserts not behaving as I expect - and I cant find a decent simple example for hashtable)
(2b|!2b)==?
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 ;
}
std::string syb;
unsigned char xid ;
long icid ;
};
It seems that the map is inserting items with unique syb fields only.
For example, in my ignore-list file, I have 84 entries - however, when I
load into the map there are only 24 entries, each with a unique syb.
I would prefer to use a hashtable since it gives me constant time
access, and I will be doing my lookups in a loop - however, for the life
of me, I cant find any simple hash_map example that get straight to the
point and show how to do this. In the absence of any useful hash
examples, I would have been content with having to use std::map for now
- but it seems to be determing uniqueness based on the syb field alone -
Q1). Can anyone explain why only a subset of my ignore list is being
inserted? (whats wrong with the op< that I have implemented above)?
Q2). Can anyone provide a snippet that will show how can use hash_map
(or some other hashing container) to store the IgnoreItem items ?
Obnoxious User
> 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 ;
> }
>
> 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?
--
OU
Kai-Uwe Bux
> 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
(2b|!2b)==?
Hi Kai, 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. 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 ...
Kai-Uwe Bux
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
(2b|!2b)==?
Hi Kai-Uwe, (apologies for truncating your name earlier). I found the
problem - it was in another part of the program (population of the keys)
- its all working fine now. many tx for your help for the op< logic.