I need to create a map with a custom key type, but then I want to search the key by a value of a different type. I can define operator< and operator== between the value and key types, but I cannot cast a value to a key.

Say, if a key was a values range: a value can be less or inside (equal) or more, but I cannot make a range from the value. It is logically obvious how to define if a value matches a key or not. But it is not possible to use a value as an argument for find().

Is it possible to find the necessary map node without iterating over the whole map? Maybe other container would help? I just wish to reduce the search time, for the map can be relatively large.

#include <string>
#include <map>

// define key structure
struct key{
    int min;
    int max;
    key(int _min, int _max): min(_min), max(_max){}
    inline bool operator < (const key& m) const {return min < m.min;}
};

typedef int value;

// define comparators between key and value
bool operator <  (const value& k, const key& m){
    return k < m.min;
}
bool operator <  (const key& m, const value& k){
    return m.max < k;
}
bool operator == (const value& k, const key& m){
    return (k >= m.min) && (k <= m.max);
}
bool operator == (const key& m, const value& k){
    return k == m;
}

int main(){
    std::map<key, std::string> map;
    map.emplace(key(1,5), "1-5");
    map.emplace(key(6,10), "6-10");
    map.emplace(key(11,20), "11-20");
    // try to search
    map.find(value(15)); // Error: no matching function to call to 'find'
    return 0;
}

Well, look, this code does what I need:

std::string Find(const std::map<key, std::string>& map, const value& v){
    for (auto it: map) {
        if (v == it.first) return it.second;
    }
    return ""; // for not found
}

Yet the complexity of this approach is linear, while std::map::find is faster. key(15,15) does not exist, there is key (11,20) that should be found. I agree that std::map it not a right container, but what else can be used?

I need to create a map with a custom key type, but then I want to search the key by a value of a different type. I can define operator< and operator== between the value and key types, but I cannot cast a value to a key.

Say, if a key was a values range: a value can be less or inside (equal) or more, but I cannot make a range from the value. It is logically obvious how to define if a value matches a key or not. But it is not possible to use a value as an argument for find().

Is it possible to find the necessary map node without iterating over the whole map? Maybe other container would help? I just wish to reduce the search time, for the map can be relatively large.

#include <string>
#include <map>

// define key structure
struct key{
    int min;
    int max;
    key(int _min, int _max): min(_min), max(_max){}
    inline bool operator < (const key& m) const {return min < m.min;}
};

typedef int value;

// define comparators between key and value
bool operator <  (const value& k, const key& m){
    return k < m.min;
}
bool operator <  (const key& m, const value& k){
    return m.max < k;
}
bool operator == (const value& k, const key& m){
    return (k >= m.min) && (k <= m.max);
}
bool operator == (const key& m, const value& k){
    return k == m;
}

int main(){
    std::map<key, std::string> map;
    map.emplace(key(1,5), "1-5");
    map.emplace(key(6,10), "6-10");
    map.emplace(key(11,20), "11-20");
    // try to search
    map.find(value(15)); // Error: no matching function to call to 'find'
    return 0;
}

Well, look, this code does what I need:

std::string Find(const std::map<key, std::string>& map, const value& v){
    for (auto it: map) {
        if (v == it.first) return it.second;
    }
    return ""; // for not found
}

Yet the complexity of this approach is linear, while std::map::find is faster. key(15,15) does not exist, there is key (11,20) that should be found. I agree that std::map it not a right container, but what else can be used?

• c++

• 2 A map is NOT the datastructure to do this with. You need some kind of ordered list of ranges (that you can binary search) that all map to the same value. Time to start writing your own datastructure I think. – Pepijn Kramer Commented Mar 11 at 13:40
• 2 A bit off topic: based on how your key looks like I think you need to use Boost ICL. See some demo – Marek R Commented Mar 11 at 13:57
• 6 @Jarod42 The moment any of the ranges overlap there is an issue (which is not detected currently at compile time) this is not a strict weak ordering and will result in UB at runtime. So as it stands it is not the kind of key or general solution I'd consider "production ready" – Pepijn Kramer Commented Mar 11 at 14:00
• 1 If your key contains two values, but you only use one of them for ordering, that would be a questionable design. In any case, you can just search for key(15,15) instead of value(15) whatever that means. Also, check out the lower_bound() method et al. (en.cppreference/w/cpp/container/map/lower_bound), which may be quite what you're looking for. In any case, concerning your question, it would help if you described what you want to achieve, not how to achieve that with a flawed approach! My guess is that you have e.g. a value and then search for ranges it falls into. – Ulrich Eckhardt Commented Mar 11 at 14:58
• 2 Usually in a std::map, the key is what you use to find the value. The value is associated with a key. The std::map is optimized for searching by key. You probably want a different container. – Thomas Matthews Commented Mar 11 at 17:20

2 Answers 2

I believe that you are looking for something like std::lower_bound or std::upper_bound. Although for ranges the most efficient solution would probably be creating your own container that will handle more than just searching, like collisions, overlapping and more. I have something like that (the element type inside the container I was referring to), which I'm not sure is optimal, but it might help you in the way for what you need: range.hpp.

Hope you find it helpful.

I needed a key-value storage. Search is performed by unique key and either value should be returned or key is not found.
The solution seems to be obvious: std::map.

But there is one more condition. I need to search in key field but using variable of different type. There is no way to cast 'search' type to 'key' type. Yet I could define if search is less than key.

So:

class Key {...}; // some stucture 
class Value {...}; // the information to be stored under key
class Search {...}; // some class NOT equal to key, but comparable
bool operator< (const Seach& s, const Key& k) {...} // somehow I know if search is less then key
bool operator==(const Seach& s, const Key& k) {...} // does s match k

void main(){
    std::map<Key, Value> M; // create map
    M.emplace (Key(XXX), Valye(YYY)); // fill the map
    Search S (CCC); // create a search value

    auto x = M.find(S); // Error, find only can accept Key type
}

Thus the original question was "Is it possible to use std::map::find with different type". The answer is NO. Solution: define order for Key type, use numerable container and perform binary search:

bool operator< (const Key& k1, const Key& k2) {...}
std::vector< std::pair<Key, Value> >::iterator Find(std::vector< std::pair<Key, Value> > V, const Search& what, int start=0, int finish=0){
    if (0==finish) finish = V.size(); // called without range, assume whole vector
    if ((finish - start) < 5) { // if the rest is small, just find necessary key
        for (int i=start; i<finish; ++i){
            if (what == V[i].first) return V[i];
        }
        return V.end();
    }
    int middle = (start + finish)/2; get Key from the middle and search in left or right part
    if (ip < V[middle].first) {
        return get(V, what, start, middle);
    }
    return get(V, what, middle, finish);
}
void main(){
    std::vector< std::pair<Key, Value> > M; // create container
    M.emplace_back (Key(XXX), Valye(YYY)); // fill it
    std::sort(V.begin(), V.end()); // now vector is ordered
    Search S (CCC); // create a search value

    auto x =Find(M, S);
}