CODEWITHSUNDEEP
c++stdmap
cpx
cpx

Reputation: 17557

Search in std::map for key that bounds the search value

Suppose if I have std::map<std::pair<int, int>, int> with key in map as a pair of two integer values.

Is it possible to find a key that bounds the value I am looking for?

For example: if map contains:

key = {4, 9}

Can I find this key based on that x is greater than 4 and x is smaller than 9? Where x is some integer value.

I hope it makes sense.

Upvotes: 2

Views: 366

Answers (3)

Deduplicator
Deduplicator

Reputation: 45654

If the intervals are non-overlapping, you can do it by using a slightly different map, utilising a transparent comparator:

std::map<std::pair<int, int>, int, std::less<>> themap;

The nice thing is now the comparison is transparent, so we can craft our own type which does the right thing for us:

struct target
{
    int value;
};
constexpr bool operator<(target a, std::pair<int, int> b) noexcept {
    return a.value <= b.first;
}
constexpr bool operator<(std::pair<int, int> a, target b) noexcept {
    return a.second <= b.value;
}

themap.find(target{value});

Upvotes: 2

Christophe
Christophe

Reputation: 73376

An std::map has a find() function that finds only exact matches, because the key is considered as a single value (even if composed of several elements as your map).

There are however two candidate solutions for your problem, depending on what exactly you try to achieve:

1) Use equal_range()

equal_range() will provide you a range defined by two iterators. The first points a an element that is not less than key and the second pointing to the first element greater than key.

So if you're looking for bounds related to an exact key, it could be what you were looking for:

auto r2 = m.equal_range ({1,2});
if (r2.first!=m.end()) {
    std::cout<<"Found range1 -> "<< r2.first->second << std::endl;
}
if (r2.second!=m.end()) {
    std::cout<<"Found range2 -> "<< r2.second->second << std::endl;
}
//attention the r2.first==r2.second if exact value not found.

If you were looking for bounds using only the first component of the pair, it won't provide you a partial search. But you could use it for searching the pair (x, 0); this will be more efficient than just iterating through the full map.

auto r3 = m.equal_range ({x,0});
for (auto r=r3.first; r!=m.end() && r->first.first==x; r++) {
    std::cout<<"In range -> "<< r->second << std::endl;
}
std::cout<<"That's all I found for <<x<<std::endl;

Here an online demo.

2) Use a map of maps

If your problem is related to partial keys, where you only know the first element, then it may be easier to use an std::map<int, std::map<int, int>>.

The search for partial keys will then be simplified:

auto r3 = m.find (x);   // look for first component
if (r3==m.end()) 
    std::cout<<"r3 not found"<<std::endl; 
else for (auto r : r3->second) {  // iterate on second component
    std::cout<<"In range -> "<< r.second << std::endl;
}

This simplicity comes however at the expense of a higher cost for the search of a full key, because you 'd need to first look for the first component, then for the second.

Demo code

Upvotes: 2

Jakub Piskorz
Jakub Piskorz

Reputation: 1073

You can use std::find_if algorithm. Check out this example on ideone

#include <algorithm>
#include <iostream>
#include <map>
#include <tuple>

int main() {
  std::map<std::pair<int, int>, int> m { { {1,3}, 4 }, { {6, 10}, 5 }, { {123, 126}, 111 } };
  int x = 8;

  auto result = std::find_if(std::begin(m), std::end(m), [x](const auto& v) {
      return v.first.first < x && x < v.first.second;
  });

  if(result != std::end(m)) {
      std::cout << "FOUND x " << result->second;
  }

  return 0;
}

Map can be considered as vector of pairs, and can be used in functions from the algorithm library. Find_if returns an iterator to the element if it matches the predicate (signature bool pred(const Type &a);). In your case Type is a std::pair<std::pair<int,int>, int>.

Upvotes: 0

Related Questions