c++ - 为什么我的自定义堆栈类使用这么多内存？

Question

我基于单链表创建了自己的堆栈，并且工作正常，但是当我看了一下内存使用情况...使用包含 100k 整数的堆栈的控制台应用程序占用 6.5 MB。这很糟糕，因为 4 字节 * 100k = 0.38 MB。我为每个“单元”结构分配内存，其中一个包含指向下一个的指针，但我认为它不会占用大量内存。问题的原因是什么？

template <typename T>
class Stack
{
        struct Unit
    {
        Unit *prev;
        T value;
        Unit(T value);
    };
public:
    Stack();
    void Push(T value);
    int Count();
    T Top();
    T Pop();
    ~Stack();
private:
    unsigned int count;
    Unit *top;

};

template<typename T>
Stack<T>::Unit::Unit(T value)
{
    this->value = value;
    prev = nullptr;
}

template<typename T>
Stack<T>::Stack()
{
    top = nullptr;
    count = 0;
}

template<typename T>
void Stack<T>::Push(T value)
{
    if (top == nullptr)
    {
        top = new Unit(value);
    }
    else
    {
        Unit *tmp = new Unit(value);
        tmp->prev = top;
        top = tmp;
    }
    count++;
}

template<typename T>
T Stack<T>::Pop()
{
    T value = top->value;
    Unit *tmp = top->prev;
    delete top;
    top = tmp;
    count--;
    return value;
}

template<typename T>
Stack<T>::~Stack()
{
    Unit *curr = top;
    if (!curr)
    {
        return;
    }
    while (curr)
    {
        Unit* tmp = curr->prev;
        delete curr;
        curr = tmp;
    }
}

Answer 1

在计算大小时，您没有考虑指针的大小和结构可能具有的任何填充。在您的平台上，指针可能是 4 或 8 个字节。此处讨论填充:Struct padding in C++

我在构造函数中为您的堆栈添加了一个 cout 以显示结构 Unit 的大小:

#include <iostream>
template<typename T>
Stack<T>::Stack()
{
    top = nullptr;
    count = 0;

    std::cout << "The size of each unit is "  << sizeof(Unit) << " bytes." << std::endl;
} 

// Rest of code is copied directly from the question.

int main() {

    Stack<int> myStack;

    return 0;
}

结果是:

The size of each unit is 16 bytes.

完整示例在这里:https://ideone.com/TWPvDv

编辑:

在看到提问者使用的是 Visual Studio 后，我进行了一些额外的调试以了解情况。在 Debug模式下，调试运行时会为每个分配添加额外的空间，以允许进行堆损坏检测和堆跟踪。我在 main 结束之前设置了一个断点，并查看了 TaskManager 中的内存使用情况(是的，这不是最准确的测量)。在 Debug模式下，整个应用程序使用超过 12MB，而在 Release模式下，总内存使用量为 2.6MB。

有关每个 block 的额外分配的信息在这里:

https://learn.microsoft.com/en-us/visualstudio/debugger/crt-debug-heap-details?view=vs-2019

The Debug versions of the heap functions call the standard or base versions used in Release builds. When you request a memory block, the debug heap manager allocates from the base heap a slightly larger block of memory than requested and returns a pointer to your portion of that block. For example, suppose your application contains the call: malloc( 10 ). In a Release build, malloc would call the base heap allocation routine requesting an allocation of 10 bytes. In a Debug build, however, malloc would call _malloc_dbg, which would then call the base heap allocation routine requesting an allocation of 10 bytes plus approximately 36 bytes of additional memory. All the resulting memory blocks in the debug heap are connected in a single linked list, ordered according to when they were allocated.