好,所以任务就是这样,我将获得点(x,y)的坐标,且两个(x,y)的范围都在-10 ^ 6到10 ^ 6之间.我必须检查是否有特定点(x,y)是否给了元组.简而言之,我如何回答查询是否设置了特定的point(2D).到目前为止,我能想到的最好的方法就是保持std :: map< std :: pair< int,int&gt ;, bool>每当给出一个点时,我都将其标记为1.尽管它必须在对数时间内运行,并且是一种相当优化的回答查询的方式,但我想知道是否有更好的方法可以做到这一点.

如果有人使用上述数据结构作为哈希表,那么如果有人能说出实际的复杂度,我也会很高兴.我的意思是说std​​ :: map的复杂度在大小上将是O(log N)与键的结构无关的元素的存在？

解决方法:

为了使用哈希映射,您需要使用std :: unordered_map而不是std :: map.使用此方法的约束是您的值类型需要为其定义一个哈希函数,如in this answer所述.要么为此,要么仅使用boost::hash：

std :: unordered_map< std :: pair< int,int&gt ;, boost :: hash< std :: pair< int,int> &GT map_of_pairs;

我想到的另一种方法是将32位int值存储在64位整数中,如下所示：

uint64_t i64;
uint32_t a32, b32;
i64 = ((uint64_t)a32 << 32) | b32;

如this answer中所述.x和y分量可以存储在整数的高字节和低字节中,然后可以使用std :: unordered_map< uint64_t,bool>.尽管我很想知道这是否比以前的方法更有效,或者它是否产生了不同的代码.