What is the best way to use two keys with a std::map?

Question

I have a std::map that I'm using to store values for x and y coordinates. My data is very sparse, so I don't want to use arrays or vectors, which would result in a massive waste of memory. My data ranges from -250000 to 250000, but I'll only have a few thousand points at the most.

Currently I'm creating a std::string with the two coordinates (i.e. "12x45") and using it as a key. This doesn't seem like the best way to do it.

My other thoughts were to use an int64 and shove the two int32s into it and use it as a key.

Or to use a class with the two coordinates. What are the requirements on a class that is to be used as the key?

What is the best way to do this? I'd rather not use a map of maps.

Solution 1

Use std::pair<int32,int32> for the key:

std::map<std::pair<int,int>, int> myMap;

myMap[std::make_pair(10,20)] = 25;
std::cout << myMap[std::make_pair(10,20)] << std::endl;

Solution 2

I usually solve this kind of problem like this:

struct Point {
    int x;
    int y;
};

inline bool operator<(const Point& p1, const Point& p2) {
    if (p1.x != p2.x) {
        return p1.x < p2.x;
    } else {
        return p1.y < p2.y;
    }
}

Solution 3

Boost has a map container that uses one or more indices.

Multi Index Map

Solution 4

What are the requirements on a class that is to be used as the key?

The map needs to be able to tell whether one key's value is less than another key's value: by default this means that (key1 < key2) must be a valid boolean expression, i.e. that the key type should implement the 'less than' operator.

The map template also implements an overloaded constructor which lets you pass-in a reference to a function object of type key_compare, which can implement the comparison operator: so that alternatively the comparison can be implemented as a method of this external function object, instead of needing to be baked in to whatever type your key is of.

Solution 5

I think for your use case, std::pair, as suggested in David Norman's answer, is the best solution. However, since C++11 you can also use std::tuple. Tuples are useful if you have more than two keys, for example if you have 3D coordinates (i.e. x, y, and z). Then you don't have to nest pairs or define a comparator for a struct. But for your specific use case, the code could be written as follows:

int main() {
    using tup_t = std::tuple<int, int>;
    std::map<tup_t, int> m;

    m[std::make_tuple(78, 26)] = 476;
    tup_t t = { 12, 45 }; m[t] = 102;

    for (auto const &kv : m)
        std::cout << "{ " << std::get<0>(kv.first) << ", "
                          << std::get<1>(kv.first) << " } => " << kv.second << std::endl;
    return 0;
}

Output:

{ 12, 45 } => 102
{ 78, 26 } => 476

Note: Since C++17 working with tuples has become easier, espcially if you want to access multiple elements simultaneously. For example, if you use structured binding, you can print the tuple as follows:

for (auto const &[k, v] : m) {
    auto [x, y] = k;
    std::cout << "{ " << x << ", " << y << " } => " << v << std::endl;
}

Code on Coliru

View more solutions

Comments

[GManNickG]

This is explicit, which is good. Just note this is the same as typedef std::pair<int, int> Point;

[StackedCrooked]

Heh, until now I didn't know that std::pair has operator< defined. Love SO!

[Frizi]

It can be achieved by using boost's tuples as well.

[Emiliano]

Another requirement is that the key must be constant and cannot change

[bames53]

a pair works but is generic. Might be a good idea to define a custom type that expresses what the pair really means, cartesian coordinates or whatever.

[GManNickG]

This is pretty ugly. Why a macro for what should be a function? And this is way too many nested pairs. To answer your question on how to solve it: struct location { int x, y, z; }; bool operator<(const location& lhs, const location& rhs) { return std::tie(lhs.x, lhs.y, lhs.z) < std::tie(rhs.x, rhs.y, rhs.z); }

[user2548100]

@GManNickG, thanks for the reply. Will give this a try and report back. Yeah, this guy'll be smiling if this works!

[user2548100]

@GManNickG, This doesn't quite compile. I'll futz around with it here in VS 2012 C++. Probably get it working, but if you have a minute to spare, maybe post something that's compiling? TVMIA

[GManNickG]

Works for me: coliru.stacked-crooked.com/…, as well as in VS2012.

[Admin]

@GManNickG, color me impressed, and thanks for going the extra mile here. Up against a lean agile slice here, so appreciate the help.

[GManNickG]

@RocketRoy: Not a problem.

[rubenvb]

@GManNickG except the interface of x and y which is first and second for a std::pair.

[user2548100]

Eclipse has macro-expansion on hover, so macros work very nicely and keep your code from getting cluttered.

[Kyle Strand]

@bames53 The main problem with that is that you must then implement a comparison operator for the new type, which may not make sense if all you want to ensure is uniqueness.

[bluish]

This is very good because can be used also for keys containing more than 2 fields.

[zett42]

OP says he'd rather not use a map of maps, so this answer is not very likely to help. In addition, some explanations of the code could be helpful for others to understand your solution. Sorry if I'm complaining too much, but you have answered a very old question from 2009 that already has an answer with many upvotes. So it's very unlikely that your answer will provide something new or even better than the accepted answer.

[zett42]

Didn't even know until now that there are overloads of the comparison operators for std::pair.

[orzechow]

You can also add a comparator functor as a template argument of map: std::map<Point, std::string, PointComp> mapping;

[IceFire]

@KyleStrand how is this a problem? Uniqueness is not violated by a comparison operator. Besides, you might only define a comparison operator as third argument for map, not for the type itself. Speaking code and therefore code clarity definitely supports bames53's suggestion

[IceFire]

@GManNickG it is not. first and second is not as clear as x and y, the latter names carry other semantics

[Kyle Strand]

@IceFire I think what I was trying to say was that you wouldn't want to define an operator that implies a logical ordering on a type that isn't supposed to support the semantic concept of ordering, because it could be misused. But obviously using pair instead doesn't actually avoid that problem. I think your suggestion of providing the operator as a map argument is the correct solution.

[Sneftel]

The OP specifically mentioned they didn't want to use a map of maps.

[Crystal]

this would work with map but with unordered_map you also need to implement hash function for point.