How to find in c++ STL in a specific manner?

Question

map< pair<int,int> , int > m ;

Here pair.first and pair.second are positive and pair.second >= pair.first.

I would like to find all iterator/s in map m such that for a given key. Key is an integer which lies between pairs e.g. key is 2 and pair is [2,5] and [1,2] etc.
e.g. m[1,3] = 10 , m[3,5] = 6 , m[1,8] = 9 , m[7,8] = 15 then when I search for m.find(3) then it would return iterator for m[1,3] , m[1,8] , m[3,5] .If there is no key then it would return m.end().

Answer 1

I'm not sure why you want to do this, but these days Boost Interval Container library is pretty capable.

Assuming that you might have wanted to keep track of the total (sum) of mapped values for a specific point, you could simply apply a splitting Combining Style to your input data and profit:

Live On Coliru

#include <boost/icl/split_interval_map.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

namespace icl = boost::icl;

int main() {
    using Map  = icl::split_interval_map<int, int>;
    using Ival = Map::interval_type;
    Map m;
    m.add({Ival::closed(1,3), 10});
    m.add({Ival::closed(3,5), 6});
    m.add({Ival::closed(1,8), 9});
    m.add({Ival::closed(7,8), 15});

    for (auto e : m) std::cout << e.first << " -> " << e.second << "\n";

    std::cout << "------------------------------\n";

    for (auto e : boost::make_iterator_range(m.equal_range(Ival::closed(3,3))))
        std::cout << e.first << " -> " << e.second << "\n";
}

This will tell us:

[1,3) -> 19
[3,3] -> 25
(3,5] -> 15
(5,7) -> 9
[7,8] -> 24
------------------------------
[3,3] -> 25

Notice how

• the consolidation very accurately reflects that the point [3,3] is the only only point that coincided with both [1,3] and [3,5] from the input data simultaneously, and as a result, we get halfopen intervals in the combined set ([1,3), [3,3] and (3,5]).
• Note also how the query for this one point correctly returns the sum of 10+6+9 for all the three intervals you were interested in.

What Use Is This?

So, you see I shifted the focus of the question from the "How?" to the "What?". It usually helps to state the goal of code instead of the particular mechanics.

Of course, if instead of the sum you'd have been interested in the average, the minimum or the maximum, you'd likely find yourself writing some custom combining strategy.

Bonus In case you wanted, here's how you can at least write the solution to the problem posed in the OP using Boost Icl: Live On Coliru. Though it's not particularly efficient, it's straight forward and robust.

Answer 2

if you only need an iterator to the next value found in the map, you can use the std::find_if algorithm like this:

int key=2;
map<pair<int,int>, int>::iterator it =std::find_if(m.begin(),m.end(),
                         [key](pair<pair<int,int>,int> entry)
                         {
                           return (entry.first.first <= key) 
                                  && (entry.first.second >= key);
                         }
                         );

cout << "the next value is: [" << it->first.first << "/";
cout << it->first.second << "] " << it->second << endl;

Answer 3

There's no way to avoid a linear search from the start of the map, because if the first element is {0,INT_MAX} then it matches and the elements you want are not necessarily in a contiguous range, e.g. if you have {1,3},{2,2}{3,5} you only want the first and last elements when the key is 3.

You can stop searching when you reach an element with first greater than the key.

Something like this (untested):

typedef map< pair<int,int> , int > Map;

std::vector<Map::iterator>
find(int key, const Map& m)
{
  std::vector<Map::iterator> matches;
  for (Map::iterator it = m.begin(), end = m.end(); it != end && key <= it->first; ++it)
  {
    if (it.first >= key && key <= it.second)
      matches.push_back(it);
  }
  return matches;
}

You could turn it into a functor and use find_if but I'm not sure it's worth it.

If you just want one iterator returned per call:

typedef map< pair<int,int> , int > Map;

Map::iterator
find(int key, const Map& m, Map::iterator it)
{
  for (Map::iterator end = m.end(); it != end && key <= it->first; ++it)
  {
    if (it.first >= key && key <= it.second)
      return it;
  }
  return m.end();
}

Map::iterator
find(int key, const Map& m)
{ return find(key, m, m.begin()); }

Answer 4

I think that instead of iterators you could store (and use) corresponding keys of the map. If so then the code could look like

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <utility>

int main() 
{
    std::map<std::pair<int, int>, int> m;
    m[{ 1, 3}] = 10; 
    m[{ 3, 5}] = 6;
    m[{ 7, 8}] = 15;

    typedef std::map<std::pair<int, int>, int>::value_type value_type;
    typedef std::map<std::pair<int, int>, int>::key_type key_type;

    int search;

    auto in_range = [&search]( const value_type &value )
    {
        return value.first.first <= search && search <= value.first.second; 
    };

    search = 3;

    std::vector<key_type> v;
    v.reserve( std::count_if( m.begin(), m.end(), in_range ) );

    for ( const auto &p : m )
    {
        if ( in_range( p ) ) v.push_back( p.first );
    }

    for ( const auto &p : v ) 
    {
        std::cout << "[ " << p.first << ", " << p.second << " ]" << std::endl;
    }

    return 0;
}

The output is

[ 1, 3 ]
[ 3, 5 ]

Take into account that it is supposed that key.first is less than or equal to key.second where key is the key of the map.