我正在 InterviewBit 上解决问题并遇到一个问题, 这是链接 https://www.interviewbit.com/problems/diffk-ii/ . 当我使用 C++ STL map 解决这个问题时,它显示了消息
超出内存限制。您的提交未在分配的内存限制内完成。 这是我的代码
int Solution::diffPossible(const vector<int> &A, int B) {
int n = A.size();
map< int , int > mp;
for(int i =0;i<n; i++)
mp[A[i]] = i;
int k = B;
for(int i =0; i<n; i++){
if(mp.find(A[i]+k) != mp.end() && mp[A[i]+k] != i){
return 1;
}
if(mp.find(A[i]-k) != mp.end() && mp[A[i]-k] != i){
return 1;
}
}
return 0;
}
当我用 unorderd_map 解决方案替换 map 时。 这是代码
int Solution::diffPossible(const vector<int> &A, int B) {
int n = A.size();
unordered_map< int , int > mp;
for(int i =0;i<n; i++)
mp[A[i]] = i;
int k = B;
for(int i =0; i<n; i++){
if(mp.find(A[i]+k) != mp.end() && mp[A[i]+k] != i){
return 1;
}
if(mp.find(A[i]-k) != mp.end() && mp[A[i]-k] != i){
return 1;
}
}
return 0;
}
这意味着 map 占用的内存比 unordered_map 多。 谁能解释这是怎么回事?为什么 map 占用更多内存 空间比 unordered_map?
最佳答案
map 被实现为二叉搜索树并且每个节点(除了有用数据之外)通常存储3 个指针(指向左 child ,右 child 和 parent )。
无序映射作为哈希表实现,其中每个节点都在链表中。在单链表(属于相关桶)的情况下,每个节点只有 1 个指针。 更新:但是,每个桶还有一个额外的指针。在没有冲突的理想情况下,内存中存储的每个元素将有 2 个指针。
请注意,2 个 int
通常会占用 8 个字节,与单个指针相同。
例如,查看 GNU libstdc++ 实现。 RB树的节点定义如下:
struct _Rb_tree_node_base
{
typedef _Rb_tree_node_base* _Base_ptr;
typedef const _Rb_tree_node_base* _Const_Base_ptr;
_Rb_tree_color _M_color;
_Base_ptr _M_parent;
_Base_ptr _M_left;
_Base_ptr _M_right;
...
在那里,您可以观察到这 3 个指针。
一般来说,很难说哪个容器会消耗更少的整体内存。然而,我创建了一个基准测试,将 1M 随机数插入两个容器并测量最大驻留大小 (MaxRSS) 以反射(reflect)所有消耗的内存空间,包括,例如,堆管理数据。结果如下:
- 48,344 kB for
std::map
, - 50 888 kB for
std::unordered_map
, - 40,932 kB for
std::unordered_map
withreserve
。
请注意,由于存储桶列表的重新分配,无序映射(广告 2.)的内存消耗较高。这就是 reserve
成员函数的用途。如果一个人关心内存消耗并且事先知道元素的数量,他/她应该总是预分配(这与 vector 的情况相同)。
关于c++ - 在内存使用方面,c++ 中的 map 和 unordered_map 有什么区别吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56438738/