C++ 在 std::map 中使用两个键的最佳方法是什么？

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

提问by Roland Rabien

I have a std::map that I'm using to store values for x & 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.

我有一个 std::map 用于存储 x & y 坐标的值。我的数据非常稀疏，所以我不想使用数组或向量，这会导致大量内存浪费。我的数据范围从 -250000 到 250000，但我最多只有几千点。

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

目前我正在创建一个带有两个坐标（即“12x45”）的 std::string 并将其用作键。这似乎不是最好的方法。

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

我的其他想法是使用 int64 并将两个 int32 推入其中并将其用作密钥。

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.

做这个的最好方式是什么？我宁愿不使用地图地图。

回答by David Norman

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

使用 std::pair<int32,int32> 作为键：

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;

回答by StackedCrooked

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

回答by DeadHead

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

Boost 有一个使用一个或多个索引的地图容器。

Multi Index Map

多索引映射

回答by ChrisW

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.

映射需要能够判断一个键的值是否小于另一个键的值：默认情况下，这意味着 (key1 < key2) 必须是一个有效的布尔表达式，即键类型应该实现“小于”运算符。

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.

map 模板还实现了一个重载构造函数，它允许您传入对 key_compare 类型的函数对象的引用，该函数对象可以实现比较运算符：以便比较可以作为此外部函数对象的方法来实现，而不是需要烘焙到您的密钥的任何类型。

回答by ChrisW

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.

这会将多个整数键填充为一个大整数，在本例中为 _int64。它比较为 _int64，AKA long long（有史以来最丑陋的类型声明。short short short short，只会稍微不那么优雅。10 年前它被称为 vlong。好多了。对于“进步”来说就这么多），所以没有比较功能是需要的。

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

提供了这个答案后，我怀疑这对您有用，因为您需要两个单独且不同的键来在 2 个维度 X 和 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.

另一方面，如果您已经有了 XY 坐标，并且只想将一个值与该键相关联，那么这会非常有效，因为 _int64 比较与 Intel X86 芯片上的任何其他整数比较花费的时间相同 - 1 个时钟。

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

在这种情况下，此合成密钥的比较速度是三重复合密钥的 3 倍。

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.

如果使用它来创建一个人口稀少的电子表格，我会使用 2 个不同的树进行 RX，一个嵌套在另一个中。使 Y 维度成为“boss”，在进行 X 维度之前，首先搜索 Y 空间以进行解析。电子表格的高度大于宽度，并且您总是希望任何复合键中的第一个维度具有最大数量的唯一值。

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.

这种安排将为 Y 维度创建一个映射，该映射将具有 X 维度的映射作为数据。当您到达 Y 维度中的叶子时，您开始在电子表格中的列中搜索它的 X 维度。

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.

如果您想创建一个非常强大的电子表格系统，请以相同的方式添加 Z 维度，并将其用于例如组织单位。这是一个非常强大的预算/预测/会计系统的基础，它允许管理单位拥有大量详细的账户来跟踪管理费用等，而不会让这些账户占用有自己类型的线单位的空间要跟踪的详细信息。

回答by MadH

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

使用 std::pair。QHash<QPair<int,int>,int>如果您有许多这样的映射，甚至可以更好地使用。

回答by user2548100

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.

首先，放弃字符串并使用 2 个整数，您现在可能已经完成了。感谢您发现树是实现稀疏矩阵的最佳方式。通常，它似乎是一个吸引不良实现的磁铁。

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 TresKey12is tested and running fine. QuadKeysshould also work.

虽然它会产生一些丑陋的子脚本，所以一点宏魔法会让你的生活更轻松。我留下了这个通用目的，但是如果您为特定地图创建宏，则在宏中对参数进行类型转换是一个好主意。经TresKey12测试，运行良好。QuadKeys也应该工作。

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.

注意：只要您的关键部分是基本数据类型，您就不需要再写任何东西了。AKA，无需担心比较函数。STL 为您提供了保障。只需将其编码并让它撕裂。

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 TresKeysthat doesn't rely on nesting pairs so I can use a single structwith 3 members and use a comparison function.

如果有人想给我留下深刻印象，请告诉我如何制作一个TresKeys不依赖嵌套对的比较运算符，这样我就可以使用struct具有 3 个成员的单个并使用比较函数。

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

PS：TresKey12 给了我声明为pair,z 的地图的问题，因为它使x,pair，而这两个不能很好地发挥作用。DosKeys 或 QuadKeys 不是问题。不过，如果这是一个炎热的夏季星期五，您可能会发现在 DosEquis 中打字会产生意想不到的副作用......错误.. 多次使用 DosKeys，是对墨西哥啤酒的渴求。买者自负。正如谢尔顿·库珀所说，“没有奇思妙想的生活是什么？”。

回答by Hennadii Niemtsov

Hope you will find it useful:

希望你会发现它有用：

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