C++ set search for pair element?

Question

So I have a set of pairs<string ,string>

And I want to use find() to search for a single string which would be in the "first" of the pair, then if I find that string in first I want to return second from that function.

My current attempt is..

myList::iterator i;

i = theList.find(make_pair(realName, "*"));

return i->second;

Solution 1

Is C++11 acceptable?

auto it = find_if(theList.begin(), theList.end(),
    [&](const pair<string, string>& val) -> bool {
        return val.first == realName;
    });

return it->second;

Or in C++03, first define a functor:

struct MatchFirst
{
        MatchFirst(const string& realName) : realName(realName) {}

        bool operator()(const pair<string, string>& val) {
                return val.first == realName;
        }

        const string& realName;
};

then call it like so:

myList::iterator it = find_if(a.begin(), a.end(), MatchFirst(realName));
return it->second;

This will only return the first match, but from your question, it looks like that's all you're expecting.

Solution 2

You can use std::set<std::pair<std::string, std::string> > for this but you will need a custom comparison object for this because the pair's relational operator takes both elements for this. That said, it seems as if you actually should use a std::map<std::string, std::string> instead.

Solution 3

The definition of < for std::pair implements a lexicographical order and "" is the minimum element for strings. Combining this we get:

 typedef std::pair<std::string, std::string> StringPair;
 typedef std::set<StringPair> Set;

 std::string const* find_first(Set const& s, std::string const& key) {
   Set::const_iterator const it = s.lower_bound(std::make_pair(key, ""));

   // Check that it actually points to a valid element whose key is of interest.
   if (it == s.end() or it->first != key) { return 0; }

   // Yata!
   return &it->second;
 }

The trick is using lower_bound appropriately.

Returns an iterator pointing to the first element which does not compare less than value.

• If it returns end(), then it did not find anything interesting.
• Otherwise, it->first >= key so we get rid of the > case (of no interest to us)

I would point out though that this only returns the first element of the range. If you are interested in all elements, try:

typedef std::pair<Set::const_iterator, Set::const_iterator> SetItPair;

SetItPair equal_range_first(Set const& s, std::string const& key) {
  StringPair const p = std::make_pair(key, "");
  return std::make_pair(s.lower_bound(p), s.upper_bound(p));
}

This will return the full range of nodes in s whose first element is equal to key. You then just have to iterate over this range:

for (Set::const_iterator it = range.first; it != range.second; ++it) {
  // do something
}

And you don't even have to worry whether the return of lower_bound or upper_bound was end or not.

• if lower_bound returns end(), then so does upper_bound, and the loop is skipped
• if lower_bound points to a node for which it->first > key, then upper_bound will point to that same node, and the loop is skipped

That is the power of ranges: no need to make special checks, the ranges just end up empty when there is no match, and so the loop over them... is skipped in a single check.