CODEWITHSUNDEEP
c++stllower-bound
Alfred
Alfred

Reputation: 81

How to get lower_bound for map in a specific range?

I want to find the lower_bound for my target in a map(in a range).

I have known another solution:

int main() {
  map<int,int> m;
  auto it=m.lower_bound(10);
  cout<<it->first<<" "<<it->second<<endl;
  return 0;
}

BUT, I want to how to use std::lower_bound(m.begin(),m.end(),***).

int main() {
  map<int,int> m;
  auto it=std::lower_bound(m.begin(),m.end(),10);
  cout<<it->first<<" "<<it->second<<endl;
  return 0;
}

main.cpp:29:43: required from here /usr/local/Cellar/gcc/7.3.0_1/include/c++/7.3.0/bits/predefined_ops.h:65:22: error: no match for 'operator<' (operand types are 'std::pair' and 'const int') { return *__it < __val; }

Upvotes: 0

Views: 1101

Answers (2)

Toby Speight
Toby Speight

Reputation: 30860

The value_type of a map is std::pair<const Key,Value>, so you'll need to supply such a pair as argument.

Given that you are interested only in the key part, it's better to use the overload of std::lower_bound() that accepts a function object:

auto const it = std::lower_bound(m.begin(), m.end(), std::make_pair(10, 0),
                                 [](auto const& a, auto const& b){ return a.first < b.first; });

I believe, from reading the docs, but haven't confirmed, that we can use the map's comparer:

auto const it = std::lower_bound(m.begin(), m.end(), std::make_pair(10, 0),
                                 m.value_comp());

Upvotes: 2

Vlad from Moscow
Vlad from Moscow

Reputation: 311028

It seems you mean the following

#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>

int main() 
{
    std::map<int, int> m =
    {
        { 2, 1 }, { 4, 2 }, { 6, 3 }, { 8, 4 }, { 10, -1 }, { 10, 0 }, { 12, 2 } 
    };

    int key = 10;

    auto it = m.lower_bound( key );

    std::cout << "{ " << it->first << ", " << it->second << " }\n";

    it = std::lower_bound( std::begin( m ), std::end( m ), key,
                           [&]( const auto &p, const auto &value ) { return p.first < value; } );

    std::cout << "{ " << it->first << ", " << it->second << " }\n";

    return 0;
}

The program output is

{ 10, -1 }
{ 10, -1 }

That is in the standard algorithm std::lower_bound you can use a lambda expression.

Upvotes: 0

Related Questions