如何在 C++ 中编写正确的哈希表析构函数
我正在写一个 c++ 哈希表
I am writing a c++ Hashtable
这是我的析构函数:
HashMap::~HashMap()
{
for (int i=0; i<cap; i++)
{
Node* ptr = Hashtable[i];
while (ptr!=NULL)
{
Node* delptr;
delptr=ptr;
ptr=ptr->next;
delete delptr;
}
}
delete [] Hashtable;
}
我的添加功能:
void HashMap::add(const std::string& key, const std::string& value)
{
int index = hashfunction(key)%cap;;
Node* ptr=Hashtable[index];
Node* newnode=new Node;
if (contains(key)==false)
{
if (ptr == nullptr)
{
newnode->key=key;
newnode->value=value;
newnode->next=NULL;
Hashtable[index]=newnode;
}
else
{
newnode->key=key;
newnode->value=value;
newnode->next=NULL;
while(ptr->next != NULL)
{
ptr = ptr->next;
}
ptr->next=newnode;
}}}
但我不断收到内存泄漏错误
But I keeps getting memory leak error
==13676==
==13676== HEAP SUMMARY:
==13676== in use at exit: 12 bytes in 1 blocks
==13676== total heap usage: 42 allocs, 41 frees, 669 bytes allocated
==13676==
==13676== 12 bytes in 1 blocks are definitely lost in loss record 1 of 1
==13676== at 0x402BE94: operator new(unsigned int) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==13676== by 0x804BF8D: HashMap::add(std::string const&, std::string const&) (HashMap.cpp:112)
==13676== by 0x804AFD2: main (main.cpp:18)
==13676==
==13676== LEAK SUMMARY:
==13676== definitely lost: 12 bytes in 1 blocks
==13676== indirectly lost: 0 bytes in 0 blocks
==13676== possibly lost: 0 bytes in 0 blocks
==13676== still reachable: 0 bytes in 0 blocks
==13676== suppressed: 0 bytes in 0 blocks
==13676==
==13676== For counts of detected and suppressed errors, rerun with: -v
==13676== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
其指示的行是 Node* newnode=new Node;因为我这里使用了new"，所以需要释放这个newnode，但是析构函数只释放Hashtable中的内容.如果我不使用newnode"，我会出现空指针访问错误，因为nullptr 无法访问Node(Node 是一个具有键和值的结构)，我只能让指针指向一个newnode".但是，添加额外的删除新节点"会使我收到超过 20 个错误.我真的需要你的帮助！
The line its indicates is Node* newnode=new Node; because I use "new" here, this newnode needed to be deallocated, but the destructor only deallocate content in Hashtable. If I don't use "newnode", I will have null-pointer access error because nullptr does not have access to Node (Node is a struct has key and value), I can only let the pointer points to a "newnode."However, adding extra "delete newnode" makes me getting more than 20 errors. I really need you help!
如果我写这个，我仍然得到一个错误
If I write this, I still get an error
if (contains(key)==false)
{
if (ptr == nullptr)
{
Node* newnode=new Node;
newnode->key=key;
newnode->value=value;
newnode->next=NULL;
Hashtable[index]=newnode;
}
else
{
Node* newnode=new Node;
newnode->key=key;
newnode->value=value;
newnode->next=NULL;
while(ptr->next != NULL)
{
ptr = ptr->next;
}
ptr->next=newnode;
}}
推荐答案
问题在于你这样做:
Node* newnode=new Node;
if (contains(key)==false)
// ... store it
/*
else
leak it
*/
你需要做的是在新的之前做条件.
What you need to do is do the conditional BEFORE the new.
if(contains(key) == true) {
// use the existing entry.
...
return;
}
else {
Node* newnode=new Node;
// ... rest of your code for inserting a new entry here.
}
---- 编辑----
---- Edit ----
ValGrind 告诉您的是，您的代码在 HashMap.cpp 第 112 行分配了一个指针，但它从未存储地址――当有人使用包含(key)" 不返回 false.您不存储指针，因此您分配的节点被分配，但您的代码没有跟踪它 -> 这是一个泄漏.
What ValGrind is telling you is that your code allocated a pointer at HashMap.cpp line 112, but it never stored the address -- this is what happens in your code when someone calls the add function with a key for which "contains(key)" does not return false. You don't store the pointer, and so the Node you allocated is left allocated but your code is not tracking it -> it's a leak.
相关文章