我有一个std::map用于存储 x 和 y 坐标的值。我的数据非常稀疏，所以我不想使用数组或向量，这会导致大量内存浪费。我的数据范围从-250000到250000，但我最多只有几千个点。
目前我正在std::string使用两个坐标（即"12x45"）创建一个并将其用作键。这似乎不是最好的方法。
我的其他想法是使用 int64 并将两个 int32 推入其中并将其用作键。
或者使用具有两个坐标的类。对用作键的类有什么要求？
做这个的最好方式是什么？我宁愿不使用地图的地图。
问问题
70403 次
10 回答
139
使用 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;
于 2009-07-11T00:15:58.730 回答
33
我通常这样解决这类问题：
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;
}
}
于 2009-07-11T00:25:47.407 回答
7
Boost 有一个使用一个或多个索引的地图容器。
于 2009-07-11T00:18:39.463 回答
5
对用作键的类有什么要求？
映射需要能够判断一个键的值是否小于另一个键的值：默认情况下，这意味着 (key1 < key2) 必须是一个有效的布尔表达式，即键类型应该实现“小于”运算符。
map 模板还实现了一个重载的构造函数，它允许您传入对 key_compare 类型的函数对象的引用，它可以实现比较运算符：因此，或者可以将比较实现为这个外部函数对象的方法，而不是需要烘焙到您的密钥的任何类型。
于 2009-07-11T00:31:25.910 回答
1
这会将多个整数键填充到一个大整数中，在本例中为 _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;
}
提供了这个答案后，我怀疑这是否适合您，因为您需要两个单独且不同的键来在 2 维 X 和 Y 中导航。
另一方面，如果您已经有了 XY 坐标，并且只想将值与该键相关联，那么这非常有效，因为 _int64 比较与 Intel X86 芯片上的任何其他整数比较所用的时间相同 - 1 个时钟。
在这种情况下，此合成密钥的比较速度是三重复合密钥的 3 倍。
如果使用它来创建一个人口稀少的电子表格，我将使用 2 棵不同的树进行 RX，其中一棵嵌套在另一棵内。将 Y 维设为“boss”，首先搜索 Y 空间以进行解析，然后再进行 X 维。电子表格的高度大于宽度，并且您总是希望任何复合键中的第一个维度具有最大数量的唯一值。
这种安排将为 Y 维度创建一个映射，该映射将具有 X 维度的映射作为它的数据。当您到达 Y 维度中的叶子时，您开始在其 X 维度中搜索电子表格中的列。
如果您想创建一个功能非常强大的电子表格系统，请以相同的方式添加 Z 维度，并将其用于组织单位的示例。这是一个非常强大的预算/预测/会计系统的基础，它允许管理单位有很多血淋淋的详细帐户来跟踪管理费用等，并且这些帐户不会占用有自己类型的行单位的空间要跟踪的详细信息。
于 2013-09-09T06:13:55.067 回答
1
我认为对于您的用例，std::pair正如大卫诺曼的回答所建议的那样，是最好的解决方案。但是，从C++11开始，您也可以使用std::tuple. 如果您有两个以上的键，则元组很有用，例如，如果您有 3D 坐标（即x、y和z）。然后，您不必嵌套对或为 a 定义比较器struct。但是对于您的特定用例，代码可以编写如下：
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;
}
于 2020-08-05T11:45:47.750 回答
0
使用 std::pair。QHash<QPair<int,int>,int>如果您有许多这样的映射，甚至更好地使用。
于 2009-07-11T13:48:15.367 回答
-1
希望你会发现它有用：
map<int, map<int, int>> troyka = { {4, {{5,6}} } };
troyka[4][5] = 7;
于 2017-03-06T01:41:58.303 回答
-1
最佳结果的替代方案，性能稍差，但允许更轻松地进行索引
std::map<int, std::map<int,int>> myMap;
myMap[10][20] = 25;
std::cout << myMap[10][20] << std::endl;
于 2021-03-15T09:50:58.607 回答
-2
首先，放弃字符串并使用 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不依赖嵌套对的比较运算符，这样我就可以使用struct具有 3 个成员的单个并使用比较函数。
PS： TresKey12 给我一个声明为 pair,z 的地图的问题，因为它使 x,pair，这两个玩得不好。DosKeys 或 QuadKeys 不是问题。如果这是一个炎热的夏天星期五，你可能会发现输入 DosEquis 的意外副作用...... err.. DosKeys 很多次，是对墨西哥啤酒的渴望。买者自负。正如 Sheldon Cooper 所说，“没有奇思妙想的生活是什么？”。
于 2013-07-10T16:23:56.103 回答