类构造中的 C++ 内存泄漏

Question

我正在编写一些 C++，尝试使用数组实现哈希表。

哈希函数取自 this堆栈溢出帖子。

由于哈希表在运行时动态调整大小，因此实现了以下简单策略:

通过 % table's total size 插入元素.

当# of elements inserted (= current size) >= table's total size ,

创建 new table大小加倍，然后重新插入所有元素。

表的桶每个都包含一个值和一个 bool 值，指示所述元素是否应该在表内。

请注意，该表仅针对非负整数值。

我无法通过表格结构:
内存使用量逐渐增加，CPU 也是如此。

这应该意味着存在与检查何时增加表大小的条件相关的问题。

表的构造函数和析构函数:

// I'm defining these here because they depend on the integer's bit size.
#define INVERSE 0x119de1f3
#define HASHER  0x45d9f3b


HashTable::HashTable(size_t initial_size, uint32_t *initial_data)
{
    total_size = 4U * initial_size;
    current_size = initial_size;

    data = new table[total_size];

    build(initial_data);
}

HashTable::~HashTable()
{
    delete[] data;

    total_size = 0U;
    current_size = 0U;
}

为了构建，我们散列并将每个初始元素放入(插入)到表中:

void HashTable::build(uint32_t *initial_data)
{
    for (size_t i = 0U; i < current_size; i += 1U)
    {
        insert(initial_data[i]);
    }
}

要插入，我们还使用哈希函数:

void HashTable::insert(uint32_t num)
{
    uint32_t index = hash(num);

    try
    {
        data[index].num = num;
        data[index].exists = true;

        current_size += 1U;
    }
    catch (out_of_range& error)
    {
        ;   // TODO stuff after writing main.
    }
}

uint32_t HashTable::hash(uint32_t num)
{
    if (current_size >= total_size / 2U) {
        doubleTable();

        for (size_t i = 0U; i < current_size; i += 1U)
        {
            insert(data[i].num);
        }
    }

    num = ((num >> 16) ^ num) * HASHER;
    num = ((num >> 16) ^ num) * HASHER;
    num =  (num >> 16) ^ num;

    return (num % total_size);
}

最后，这是一个虚拟的 main 函数:

int main(void)
{
    uint32_t initial_data[3] = {1, 3, 5};

    HashTable h(3U, initial_data);
    return 0;
}

这是表格的结构:

struct table
{
    uint32_t num;
    bool exists = false;
};

以及相关定义:

class HashTable
{
    private:
        table *data;

        size_t total_size;
        size_t current_size;

        uint32_t hash(uint32_t num);
        uint32_t unhash(uint32_t num);

        void build(uint32_t *initial_data);

        void doubleTable(void);

    public:
        HashTable(size_t initial_size, uint32_t *initial_data);
        ~HashTable();

        void insert(uint32_t num);

使用 -ggdb3 编译后并运行 valgrind，我得到一个纠缠 uninitialized value of size 8错误。

以下是一些 valgrind 日志:

--1632-- Valgrind options:
--1632--    --leak-check=full
--1632--    --show-leak-kinds=all
--1632--    --track-origins=yes
--1632--    --verbose
--1632--    --log-file=valgrind-out.txt

==1632== Use of uninitialised value of size 8
==1632==    at 0x1093E8: HashTable::insert(unsigned int) (in /home/xlxs4/Git/CCDT/src/structures/hashtable/a.out)
==1632==    by 0x1095DC: HashTable::hash(unsigned int) (in /home/xlxs4/Git/CCDT/src/structures/hashtable/a.out)
==1632==    by 0x1093BD: HashTable::insert(unsigned int) (in /home/xlxs4/Git/CCDT/src/structures/hashtable/a.out)
==1632==    by 0x1096B0: HashTable::build(unsigned int*) (in /home/xlxs4/Git/CCDT/src/structures/hashtable/a.out)
==1632==    by 0x10933C: HashTable::HashTable(unsigned long, unsigned int*) (in /home/xlxs4/Git/CCDT/src/structures/hashtable/a.out)
==1632==    by 0x10920A: main (main.cpp:15)
==1632==  Uninitialised value was created by a heap allocation
==1632==    at 0x483950F: operator new[](unsigned long) (vg_replace_malloc.c:423)
==1632==    by 0x1092F7: HashTable::HashTable(unsigned long, unsigned int*) (in /home/xlxs4/Git/CCDT/src/structures/hashtable/a.out)
==1632==    by 0x10920A: main (main.cpp:15)

我已经在 eliminating undefined values 上浏览过这篇文章和这篇关于 uninitialized value of size 8 的帖子.

我错过了什么？

如果您需要任何进一步的分类，或者希望我进一步解释我的思维过程，请告诉我。

提前致谢 :)

Answer 1

xxs4:

This shouldn't be duplicated as @Frank said above. Nonetheless, I figured it out. I re-wrote the code according to the rule of three principles and I utilized initialization lists. What caused the problem I described in the post, is that i < current_size in build will never terminate, as current_size gets incremented each time insert is being called. I don't have sufficient reputation to answer my own question, as it seems. Thanks to all who helped!