用std :: map使用两个键的最好方法是什么?
我有一个std ::我用来存储x和y坐标的值。 我的数据非常稀less,所以我不想使用数组或向量,这会导致大量的内存浪费。 我的数据范围从-250000到250000,但我最多只有几千点。
目前我创build一个std ::string与两个坐标(即“12×45”),并将其用作关键。 这似乎不是最好的方式来做到这一点。
我的其他想法是使用一个int64,并将两个int32s移入它并将其用作一个键。
或者使用两个坐标的类。 什么是要被用作关键的类的要求?
做这个的最好方式是什么? 我宁愿不使用地图的地图。
使用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;
我通常这样解决这样的问题:
struct Point { Point() : x(), y() {} Point(int x, int y) : x(x), y(y) {} int x, y; }; bool operator<(const Point & lhs, const Point & rhs) // lhs = left-hand side // rhs = right-hand side { if (lhs.x != rhs.x) { return lhs.x < rhs.x; } else { return lhs.y < rhs.y; } } int main() { Point p1(0, 1); Point p2(0, 2); std::map<Point, std::string> mapping; mapping[p1] = "p1"; mapping.insert(std::make_pair(p2, "p2")); }
什么是要被用作关键的类的要求?
该映射需要能够判断一个键的值是否小于另一个键的值:默认情况下,这意味着(键1 <键2)必须是有效的布尔expression式,即键types应该实现'小于'运算符。
映射模板还实现了一个重载的构造函数,它允许您传入一个key_comparetypes的函数对象的引用,该函数可以实现比较运算符:或者,比较可以作为此外部函数对象的方法实现,而不是需要烘烤到任何types的密钥是。
Boost有一个使用一个或多个索引的地图容器。
多索引图
这将填充多个整数键到一个大整数,在这种情况下,一个_int64。 它比较长的是一个_int64,又长又长的(最丑的types声明,短的短的短的,只会稍微不那么优雅,十年前它被称为vlong,好多了,因为“进步”),所以没有比较function是需要的。
#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倍,而三重复合密钥是3倍。
如果使用这个创build一个稀疏的填充电子表格,我会RX使用2个不同的树,一个嵌套在另一个。 使Y维度为“boss”,在进入X维度之前先searchY空间进行parsing。 电子表格比它们宽,而且您总是希望任何复合键中的第一个维度具有最大数量的唯一值。
这种安排将为Y维度创build一个映射,X维度的映射就像数据一样。 当您到达Y维度的叶子时,您将开始在电子表格中为其列查找X维度。
如果您想要创build一个function强大的电子表格系统,请按照相同的方式添加Z维度,并以此作为示例,组织单位。 这是一个非常强大的预算/预测/会计系统的基础,它允许pipe理单位有很多血统细目账户来追踪pipe理费用等,而且这些账户不会占用自己种类的线路单位的空间跟踪的细节。
首先,将string交叉并使用2个整数,您现在可能已经完成了。 为了搞清楚树是实现稀疏matrix的最好方法, 通常看起来好坏的实施磁铁。
仅供参考,三重复合键也起作用,我也假设有一对。
尽pipe这样做会造成一些丑陋的子脚本,所以有一点macros观魔法会让你的生活更轻松。 我离开了这个通用的目的,但是如果为特定的地图创buildmacros,在macros中input参数是一个好主意。 TresKey12
经过testing,运行良好。 QuadKeys
也应该工作。
注意:只要你的关键部分是基本的数据types,你不需要再写更多的东西。 AKA,不用担心比较function。 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
创build一个不依赖嵌套对的TresKeys
,这样我就可以使用带有3个成员的单个struct
并使用比较函数。
PS: TresKey12给了我一个地图,声明为pair,z,因为它使x,对,这两个不好打。 DosKeys或QuadKeys不是问题。 如果周五炎热的夏天,你可能会发现一个意想不到的副作用,就是打字DosEquis … err.DosKeys一堆,是对墨西哥啤酒的渴求。 买者自负。 正如谢尔登·库珀(Sheldon Cooper)所说:“没有奇思妙想的生活是什么?
使用std :: pair。 如果你有很多这样的映射QHash<QPair<int,int>,int>
甚至可以使用QHash<QPair<int,int>,int>
。
希望你会发现它有用:
map<int, map<int, int>> troyka = { {4, {{5,6}} } }; troyka[4][5] = 7;