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

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.

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;

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;
	}
}

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

Multi Index Map

> 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.

This will stuff multiple integer keys into a large integer, in this case, an _int64. It compares as an _int64, AKA long long (The ugliest type declaration ever. short short short short, would only be slightly less elegant. 10 years ago it was called vlong. Much better. So much for "progress"), so no comparison function is needed.

#define ULNG  unsigned long
#define BYTE  unsigned char
#define LLNG  long long 
#define ULLNG unsigned long long

// --------------------------------------------------------------------------
ULLNG PackGUID(ULNG SN,  ULNG PID, BYTE NodeId) {
	ULLNG CompKey=0;
	
	PID = (PID << 8) + NodeId;
	CompKey = ((ULLNG)CallSN << 32) + PID;
 
	return CompKey;
}

Having provided this answer, I doubt this is going to work for you, as you need two separate and distinct keys to navigate with in 2 dimensions, X and Y.

On the other hand, if you already have the XY coordinate, and just want to associate a value with that key, then this works spectacularly, because an _int64 compare takes the same time as any other integer compare on Intel X86 chips - 1 clock.

In this case, the compare is 3X as fast on this synthetic key, vs a triple compound key.

If using this to create a sparsely populated spreadsheet, I would RX using 2 distinct trees, one nested inside the other. Make the Y dimension "the boss", and search Y space first to resolution before proceeding to the X dimension. Spreadsheets are taller than they are wide, and you always want the 1st dimension in any compound key to have the largest number of unique values.

This arrangement would create a map for the Y dimension that would have a map for the X dimension as it's data. When you get to a leaf in the Y dimension, you start searching it's X dimension for the column in the spreadsheet.

If you want to create a very powerful spreadsheet system, add a Z dimension in the same way, and use that for, as an example, organizational units. This is the basis for a very powerful budgeting/forecasting/accounting system, one which allows admin units to have lots of gory detail accounts to track admin expenses and such, and not have those accounts take up space for line units which have their own kinds of detail to track.

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

Use std::pair. Better even use QHash<QPair<int,int>,int> if you have many of such mappings.

Hope you will find it useful:

map<int, map<int, int>> troyka = { {4, {{5,6}} } };
troyka[4][5] = 7;

An alternative for the top result that is slightly less performant but allows for easier indexing

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

myMap[10][20] = 25;
std::cout << myMap[10][20] << std::endl;

First and foremost, ditch the string and use 2 ints, which you may well have done by now. Kudos for figuring out that a tree is the best way to implement a sparse matrix. Usually a magnet for bad implementations it seems.

FYI, a triple compound key works too, and I assume a pair of pairs as well.

It makes for some ugly sub-scripting though, so a little macro magic will make your life easier. I left this one general purpose, but type-casting the arguments in the macro is a good idea if you create macros for specific maps. The TresKey12 is tested and running fine. QuadKeys should also work.

NOTE: As long as your key parts are basic data types you DON'T need to write anything more. AKA, no need to fret about comparison functions. The STL has you covered. Just code it up and let it rip.

using namespace std;	// save some typing
#define DosKeys(x,y)      std::make_pair(std::make_pair(x,y))
#define TresKeys12(x,y,z) std::make_pair(x,std::make_pair(y,z))
#define TresKeys21(x,y,z) std::make_pair(std::make_pair(x,y),z))

#define QuadKeys(w,x,y,z) std::make_pair(std::make_pair(w,x),std::make_pair(y,z))


map<pair<INT, pair<ULLNG, ULLNG>>, pIC_MESSAGE> MapMe;
MapMe[TresKey12(Part1, Part2, Part3)] = new fooObject;

If someone wants to impress me, show me how to make a compare operator for TresKeys that doesn't rely on nesting pairs so I can use a single struct with 3 members and use a comparison function.

PS: TresKey12 gave me problems with a map declared as pair,z as it makes x,pair, and those two don't play nice. Not a problem for DosKeys, or QuadKeys. If it's a hot summer Friday though, you may find an unexpected side-effect of typing in DosEquis ... err.. DosKeys a bunch of times, is a thirst for Mexican beer. Caveat Emptor. As Sheldon Cooper says, "What's life without whimsy?".