Roman Perepelitsa wrote:

2009/9/24 Ryan McConnehey <mccorywork@gmail.com <mailto:mccorywork@gmail.com>>

I have the following std::map signature.

typedef std::pair<std::string, int> cPair; typedef std::map<cPair, std::vector<classA> > cMap; cMap myMap;

When entering values into the map, the std::string is the only part of the key that needs to be unique. Upon retrieving map values both values of the key need to be compared. I've tried to define my insert comparison as follows, but am uncertain how to define the predicate with boost::lambda.

std::string givenName = "some_text_value"; int givenInt = 3; cMap::const_iterator itor = std::find_if( myMap.begin(), myMap.end(), boost::lambda::bind( ??? , _1) == givenName );

cMap::const_iterator itor = std::find_if(myMap.begin(), myMap.end(), boost::lambda::bind(&cMap::value_type::first, _1) == givenName);

Note that you can use std::map::find instead:

cMap::const_iterator itor = myMap.find(givenName);

I'd endorse Roman's suggestion, maybe something like: cMap::const_iterator itor = myMap.find(cMap::key_type(givenName, properInt)); You said "my insert comparison," as though perhaps if itor == myMap.end() you intend to follow up with an insertion. For such cases I typically just code the insert() call: std::pair<cMap::iterator, bool> inserted = myMap.insert(cMap::value_type(cMap::key_type(givenName, properInt), cmap::mapped_type())); if (! inserted.second) // oh, it already existed? { ... } The latter form traverses the map structure just once, whether or not there's an existing entry with this key value.

Ryan McConnehey wrote:

...

std::pair<cMap::iterator, bool> inserted = myMap.insert(cMap::value_type(cMap::key_type(givenName, properInt), cmap::mapped_type())); if (! inserted.second) // oh, it already existed? { ... }

Since I'm using both givenName and properInt as a key, the insert will never return false for just a duplicate of givenName.

Forgive me if this is a stupid question, but if you don't want to compare the int, why is it part of the key at all?

Also, if the insert did return false then it means a good value at that map key has been replaced. The reason I'm trying to catch this duplication is because "last value entered wins" doesn't meet the requirement I was given.

Not true. When insert() finds an existing key, it returns a std::pair with the iterator to that entry and 'false' meaning it wasn't newly inserted. Per Stroustrup: "The operation m.insert(val) attempts to add a (Key, T) pair val to m. Since maps rely on unique keys, insertion takes place only if there is not already an element in the m with that key. The return value of m.insert(val) is a pair<iterator, bool>. The bool is true if val was actually inserted. The iterator refers to the element of m holding the key k." ... "In fact, [] is little more than a convenient notation for insert(). The result of m[k] is equivalent to the result of (*(m.insert(make_pair(k,V())).first)).second, where V() is the default value for the mapped type."

Anthony Foglia wrote:

Nat Goodspeed wrote:

...

Forgive me if this is a stupid question, but if you don't want to compare the int, why is it part of the key at all?

He wants to compare the int upon retrieval, but it doesn't matter for insertion. But I think he'd be better off getting the map to only care about the string.

Or, even easier, make the key just the string and the value a pair of the int and the vector of classA:

typedef map<string, pair<int, vector<classA> > cMap;

Yes, that's what I was thinking: migrate the int from the key to the mapped_type.

Ryan wrote:

On Thu, Sep 24, 2009 at 11:38 AM, Anthony Foglia <AFoglia@princeton.com <mailto:AFoglia@princeton.com>> wrote:

Or, even easier, make the key just the string and the value a pair of the int and the vector of classA:

On Thu, Sep 24, 2009 at 12:01 PM, Nat Goodspeed <nat@lindenlab.com <mailto:nat@lindenlab.com>> wrote:

Yes, that's what I was thinking: migrate the int from the key to the mapped_type.

This would indeed make the insert easier at the cost of complicating the retrieval. By making the int part of the key the retrieval is trival

m_VariableDestinations.find(std::make_pair(name, intValue));

If I was to move the int out of the pair I found that it increased the difficulty quite a bit.

My other thought is: have you looked at all at Boost Multi-Index? http://www.boost.org/doc/libs/1_40_0/libs/multi_index/doc/index.html It may be that your dual key requirements would best be met by dual indexes.

Ryan wrote:

On Thu, Sep 24, 2009 at 12:01 PM, Nat Goodspeed <nat@lindenlab.com> wrote:

...

Yes, that's what I was thinking: migrate the int from the key to the mapped_type.

This would indeed make the insert easier at the cost of complicating the retrieval. By making the int part of the key the retrieval is trival

m_VariableDestinations.find(std::make_pair(name, intValue));

If I was to move the int out of the pair I found that it increased the difficulty quite a bit.

I don't think it's that bad. The retrieval will be only slightly worse with an extra ".second" you'd need to add to get the vector of classA.

On Thu, Sep 24, 2009 at 11:38 AM, Anthony Foglia <AFoglia@princeton.com>wrote:

...

He can pass a custom less functor class as the third template parameter to the map. Something like:

Is the advantave of using the custom functor over the lambda class the ability to use the insert function correctly? By using the functor the insert, that Nat recommended, would indeed only compare the name value and correctly return true or false regardless of the second parameter. Is this correct?

Yes, but it also will only compare the string value and not the int when using map::find as well. The only real difference comes down to how you get the vector<classA> value and the intValue from the iter. typedef map< pair<string,int>, vector<classA>, LessFirstOfPair > cMap1; typedef map< string, pair<int,vector<classA> > > cMap2; cMap1 map1; cMap2 map2; cMap1::iterator it1 = map1.find(make_pair(name,intValue)); cMap2::iterator it2 = map2.find(name); The int part of the "key" can be retrieved with it1->first.second it2->second.first And the vector<classA> can be retrieved with it1->second it2->second.second I guess one benefit is that by overriding the template parameter, using std::find_if becomes a little simpler, because both the string and int are in the same "area". I think you can get away with find_if(map1.begin(), map1.end(), bind(&cMap1::value_type::first, _1) ==make_pair(givenName, intValue)); but I haven't used bind and lambda often enough to be more than 60% certain I got that right. :-) Using map::find should be faster for big containers, but you'll need to manually check the int of the map key. it1 = map1.find(make_pair(name,intValue)); if ((it1 == map1.end()) || (it1->first.second != intValue)) { // not found } Using merely the string as the key sounds safer to me, both because it's easier to initially code, and it's easier to maintain. (Eventually you or the next coder will forget that in cMap1 the int part of the key is ignored.) I just kept the overloaded template parameter in my reply because that was my first thought. While writing it I realized the simpler, non-overengineered string-only key approach. -- Anthony Foglia Princeton Consultants (609) 987-8787 x233