STL map find_if

[Mike Copeland]

I am trying to create a "find_if" that will allow me to find a
std::map object via a secondary field. That is, I need to search using
the "entName" field in the defined structure, even though the objects
are stored via the "bibNum" (integer) field. I have tried to find the
information in Google, but the conversion from what I find there to my
specific problem eludes me: I cannot compile the code below.

typedef struct ChipRecord // Chip Times record
{
int bibNum; // Bib #
short entAge; // Age
char entGender; // Gender (M/F)
char entRCode; // RCode
char entECode; // Entrant Type code
string entName; // Entrant Name
} tData; // entrant info records
tData tWork;
tData qWork;
typedef map<int, ChipRecord> BCI;
BCI bci;
map<int, ChipRecord>::iterator bIter;

class NameMatch
{
string m_name;
public:
NameMatch(string &name) : m_name(name) {}
bool operator()(const pair<unsigned int, BCI> &o)
{
return (m_name == o.second.);
}
};

Furthermore, I don't know how I'd actually implement a "find_if" with
the defined structures and object...so I'd like some help there, as
well. TIA

 

[Victor Bazarov]

I am trying to create a "find_if" that will allow me to find a
std::map object via a secondary field. That is, I need to search using
the "entName" field in the defined structure, even though the objects
are stored via the "bibNum" (integer) field. I have tried to find the
information in Google, but the conversion from what I find there to my
specific problem eludes me: I cannot compile the code below.

typedef struct ChipRecord // Chip Times record
{
int bibNum; // Bib #
short entAge; // Age
char entGender; // Gender (M/F)
char entRCode; // RCode
char entECode; // Entrant Type code
string entName; // Entrant Name
} tData; // entrant info records
tData tWork;
tData qWork;
typedef map<int, ChipRecord> BCI;
BCI bci;
map<int, ChipRecord>::iterator bIter;

class NameMatch
{
string m_name;
public:
NameMatch(string &name) : m_name(name) {}

NameMatch(string const& name) : m_name(name) {}

bool operator()(const pair<unsigned int, BCI> &o)
{
return (m_name == o.second.);
}

I would probably write this as

bool operator()(const map<int, ChipRecord>::value_type const& v) const
{
return v.second.entName == m_name;
}

};

Furthermore, I don't know how I'd actually implement a "find_if" with
the defined structures and object...so I'd like some help there, as
well. TIA

Off the top of my head:

typedef map<int, ChipRecord> my_map_t;

...
my_map_t my_map;
... // fill the map with values
my_map_t::iterator it = find_if(my_map.begin(), my_map.end(),
NameMatch("some_name"));
if (it != my_map.end()) // found!
...

V

 

[Jonathan Lee]

   I am trying to create a "find_if" that will allow me to find a

std::map object via a secondary field.

If this is a "one off" kind of search than you're probably best
iterating over the whole map and checking one at a time. For
example,

map<int, ChipRecord>::iterator it = bci.begin();
while (it != bci.end() && ((*it).second.entName != find_string))
++it;
if (it != bci.end()) {
// you found it
} else { /* you didn't */ }

Of course, that's assuming you know *nothing* about the order of
the ChipRecords wrt entName. Then again, even if you _knew_
something about the ordering you'd be doing a binary search of
the map based on the key. And every use of bci[key] implies a
lookup.

If you're doing this MANY times then I suggest:
1) index by entName instead. Unless you have a really good
reason to index by bibNum. Or make a temporary copy of
the map when you enter a section of code that will be
doing a bunch of entName lookups, and index the copy
by entName.
2) Replace the key of the map with a class that can
compare against an integer or a string. Like a pair
(bibNum, entName) such that (a, b) == (c, d) if
(a == c) or (b == d). That'll take a bit of work
and can potentially result in false positives.

Those are my thoughts.

--Jonathan

 

[meagar]

I am trying to create a "find_if" that will allow me to find a
std::map object via a secondary field. That is, I need to search using
the "entName" field in the defined structure, even though the objects
are stored via the "bibNum" (integer) field. I have tried to find the
information in Google, but the conversion from what I find there to my
specific problem eludes me: I cannot compile the code below.

typedef struct ChipRecord // Chip Times record
{
int bibNum; // Bib #
short entAge; // Age
char entGender; // Gender (M/F)
char entRCode; // RCode
char entECode; // Entrant Type code
string entName; // Entrant Name
} tData; // entrant info records

Adding a find_if that iterates over the map in linear time defeats the
purpose of storing things in a map.

Seems like what you might really want is a second map that uses entName as
its key. If it helps, think of it this way:

// bibNum -> ChipRecord, primary storage
map<int, ChipRecord*> chipRecords;

// Mapping of entName -> ChipRecord, for fast lookup
map<std::string, ChipRecord*> index;

Encapsulate your access to ChipRecords in a series of functions or a
dedicated class in order to prevent the maps from getting out of sync.

 

[Mike Copeland]

I am trying to create a "find_if" that will allow me to find a

Adding a find_if that iterates over the map in linear time defeats the
purpose of storing things in a map.

Seems like what you might really want is a second map that uses entName as
its key. If it helps, think of it this way:

// bibNum -> ChipRecord, primary storage
map<int, ChipRecord*> chipRecords;

// Mapping of entName -> ChipRecord, for fast lookup
map<std::string, ChipRecord*> index;

Encapsulate your access to ChipRecords in a series of functions or a
dedicated class in order to prevent the maps from getting out of sync.

Yes, I think I'll have to do that. Victor's information works
(thanks, Victor!), but the processing is _very_ slow. My application
must scan a map of ~15,000 objects about 12,000 times - I'm
reconstructing a database from information where the map key has been
lost...and I'm using information from an old database for the
scan/match.
I had no option for using a different map key (such as the entName)
because there are duplicate entName records throughout the database.
(Actually, I'm building a "new" database with base information and
changed data fields, but the source of the "changed data" doesn't have a
map key value - so I'm having to do this convoluted thing...).
Also, I have to do this for several existing databases. <sigh..>
Thanks to all!

 

[Mike Copeland]

I had no option for using a different map key (such as the entName)

Umm, duplicate keys are just fine with a multimap.

I didn't know that (as well as a lot of things!). Now, since bibNum
is unique (where entName isn't), I wonder if I can use multimap. I'll
have to look into that...
Thanks.