get range of map elements with equal values

Question

I've got a map declared as:

std::map< std::pair<int, int>, bool > allPositions; // essentially, keys are just 2D points

I need to get the range of its elements whose values are true

Using std::equal_range

auto range = std::equal_range(allPositions.begin(), allPositions.end(), true);

Gives these errors

Error C2672 'operator __surrogate_func': no matching overloaded function found xutility

Error C2893 Failed to specialize function template 'unknown-type std::less::operator ()(_Ty1 &&,_Ty2 &&) const' xutility

Error C2056 illegal expression xutility

Error C2672 'operator __surrogate_func': no matching overloaded function found algorithm

Error C2893 Failed to specialize function template 'unknown-type std::less::operator ()(_Ty1 &&,_Ty2 &&) const' algorithm

I think I don't need predicate function here because std::pair has got overloaded operator < otherwise map code wouldn't have been compiled

So how to use std::equal_range for map to get range of pairs with equal values ?

Answer 1

I need to get the range of its elements whose values are true

You will have to iterate the the map to get the iterators whose value pair is true... I have a working example Live On Coliru. Something like this does the lifting.

template<typename Map,
         typename Value    = typename Map::mapped_type,
         typename Compare  = std::equal_to<Value>,
         typename Iterator = typename Map::iterator>
std::vector<Iterator> equal_values(const Map& mp, const Value& val, Compare cmp = Compare()){
    std::vector<Iterator> rtn;
    for(auto iter = mp.begin(); iter != mp.end(); ++iter)
        if(cmp(iter->second, val))
            rtn.push_back(iter);
    return rtn;
}

Alternatively, you may want to use Boost.Bimap or Boost.MultiIndex

Answer 2

So how to use std::equal_range for map to get range of pairs with equal values ?

Let's say you have a map with following data:

{ {{0,0},false}, {{1,1},true}, {{2,2},false}, {{3,3},true} };

what you expect equal range to return for true? for false?

For that to work your container must be partitioned with respect to criteria you are using to get range. std::map is definitely not a such container for get range by value. So you would need to copy data or iterators into different container and sort it accordingly and use that container to get your ranges, or create such container on the fly by filtering. Or you can use container like boost::bimap or boost::multi_index which can provide multiple indexes.

Answer 3

So let's say you have a map as such:

using point = std::pair<int,int>;
std::map<point,bool> my_map;

And let's say you have some values in it as such:

my_map = { {{0,0},false}, {{0,1},true}, {{1,0},true}, {{1,1},false} };

Now let's see what the first iterator, when de-referenced, of this map will be:

{{0,0},false}

When you use std::equal_range(my_map.begin(), my_map.end(), true); you're asking that true be checked to the de-referenced iterators. But the de-referenced iterator is not a boolean. It's a pair of a point and a boolean.
So what you may want to try is the following:

using map_iter = std::map<point,bool>::iterator; //is {point,bool}
auto range = std::equal_range(my_map.begin(), my_map.end(), [](map_iter& iter){
  return iter.second == true;
};

Edit:
Just to clarify, this will address a compiler error but will not address the logical error of the values of the map not (necessarily) being sorted such that you can get a pair of iterators that define a range encompassing all of a matching value as a map is not sorted by value