Find the first value greater than user specified v

问题:

I have a map container. How to return the first value greater than the user-specified search value by using find_if as follows:

std::map<string, int>::iterator it = find_if(Mymap.begin(), Mymap.end(), ......

Thank you very much!

回答1:

With a lambda:

int n = MYVALUE;
auto it = std:: find_if(Mymap.begin(), Mymap.end(),
                        [n](const std::pair<std::string, int> & x) -> bool
                        { return x.second > n; }
                       );

(If the value is fixed you can put it directly inside the lambda body. For C++14 and later, the lambda capture can be [n = MYVALUE] and you don't need a separate outer variable n.)

With a predicate:

struct Finder
{
  Finder(int n_) : n(n_) { }
  int n;
  bool operator()(const std::pair<std::string, int> & x) const
  {
    return x.second > n;
  }
};

auto it = std::find_if(Mymap.begin(), Mymap.end(), Finder(MYVALUE));

回答2:

Are you sure you want to be doing a linear search for any item with a value greater than your criteria through the container?

It would probably be better to also keep a separate index of sorted values that you could call upper_bound on, performing in logarithmic time rather than linear in the number of elements. Alternately look into boost::multi_index instead.

回答3:

For C++03 you need to provide comparator object, or deal with some tricky bindings:

typedef map<string, int>::value_type Value;

struct Comp
{
    Comp(int v) : m_v(v) { }

    bool operator()(const Value& v) const
    {
        return v.second > m_v;
    }

    int m_v;
};

void f()
{
    map<string, int> Mymap;
    map<string, int>::iterator it = find_if(Mymap.begin(), Mymap.end(), Comp(42));
}

回答4:

You may find the book of B.Stroustrup very useful when it comes to STL features. And he proposes this code:

bool gt_42 (const pair <const string ,int>& r )
{
    return  r.second >42 ;
}
void f (map <string,int >& m )
{
    typedef map <string ,int >:: const_iterator MI ;
    MI i = find_if (m.begin (), m.end (), gt_42 );
    // ...
}

From chapter "A Tour of the Standard Library" (available in .pdf file) of "The C++ Programming Language, Special Edition"