Find the first value greater than user specified value from a map container

Question

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!

Is std::find_if absolutely needed? If not, Mark B's answer is faster. — Mooing Duck, Sep 07 '11 at 17:27

score 4 · Answer 1 · answered Sep 07 '11 at 14:51

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.

Kerrek SB · Accepted Answer · 2018-09-10T08:45:55.090

3

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));

edited Sep 10 '18 at 08:45

answered Sep 07 '11 at 14:30

Kerrek SB

464,522
92
875
1,084

Thank you for your answer. But my compiler doesn't support lamda function. – GoldenLee Sep 07 '11 at 14:33
1

How old is your compiler? Use the predicate then. It does exactly the same thing. – Kerrek SB Sep 07 '11 at 14:34
Your solution will work if you change bool operator< to bool operator(). Thank you! – GoldenLee Sep 07 '11 at 14:48
I have added code to print the find output. Need to assign output of find_if to an interator. – xxx374562 Sep 10 '18 at 05:24

Alexander Poluektov · Answer 3 · 2011-09-07T14:48:35.273

2

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));
}

edited Sep 07 '11 at 14:48

answered Sep 07 '11 at 14:31

Alexander Poluektov

7,844
1
28
32

score 0 · Answer 4 · edited Sep 07 '11 at 15:03

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"

Find the first value greater than user specified value from a map container

4 Answers4

Linked