将两个键与 std::map 一起使用的最佳方法是什么？

Question

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

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

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

或者使用具有两个坐标的类。 用作密钥的类有哪些要求？

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

Answer 1

使用 std::pair 对于关键：

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;

Answer 2

我通常这样解决这类问题：

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

Answer 3

Boost 有一个使用一个或多个索引的映射容器。

多索引映射

Answer 4

用作密钥的类有什么要求？

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

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

Answer 5

这会将多个整数键填充到一个大整数中，在本例中为 _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;
}

提供了这个答案后，我怀疑这是否适合您，因为您需要两个单独且不同的键来在二维（X 和 Y）中导航。

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

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

如果使用它来创建一个稀疏的电子表格，我将使用两棵不同的树进行 RX，一棵树嵌套在另一棵树中。 让 Y 维度成为“老板”，并首先在 Y 空间中搜索分辨率，然后再进行 X 维度。 电子表格的高度大于宽度，并且您始终希望任何复合键中的第一个维度具有最大数量的唯一值。

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

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

Answer 6

我认为对于您的用例， std::pair ，正如David Norman的回答中所建议的，是最好的解决方案。 但是，从 C++11 开始，您也可以使用 std::tuple。 如果您有两个以上的键，例如，如果您有 3D 坐标（即 x、y 和 z），则元组非常有用。 那么你就不必嵌套对或为结构定义比较器。 但对于您的特定用例，代码可以编写如下：

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

输出：

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

注意：自C++17开始工作使用元组变得更加容易，特别是如果您想同时访问多个元素。
例如，如果您使用 结构化绑定，则可以按如下方式打印元组:

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

Coliru 上的代码

Answer 7

使用 std::pair。 如果您有许多此类映射，甚至最好使用 QHash,int> 。

Answer 8

希望您会发现它很有用：

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

Answer 9

顶部结果的替代方案，性能稍差，但可以更轻松地建立索引

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

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

Answer 10

首先也是最重要的，放弃字符串并使用 2 个整数，您现在可能已经完成了。 感谢您发现树是实现稀疏矩阵的最佳方法。 看起来通常会吸引不良实施。

仅供参考，三重复合键也可以使用，我假设也是一对。

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

注意：只要您的关键部分是基本数据类型，您就不需要再编写任何内容。 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;

如果有人想给我留下深刻的印象，请向我展示如何为 TresKeys 创建一个不依赖嵌套对的比较运算符，这样我就可以使用具有 3 个成员的单个 struct 并使用比较功能。

PS： TresKey12 给我带来了关于声明为pair,z 的地图的问题，因为它会生成x,pair，而这两个玩起来不太好。 对于 DosKeys 或 QuadKeys 来说这不是问题。 如果周五是炎热的夏季，您可能会发现输入 DosEquis 会产生意想不到的副作用
...呃..DosKeys很多次，是对墨西哥啤酒的渴望。 买者自负。 正如谢尔登·库珀所说：“没有奇思妙想的生活还算什么？”。