Утечка памяти в тривиальной реализации стека

Question

У меня неплохой опыт работы с Python и Java, но недавно я решил изучать C ++. Я решил сделать быструю реализацию целочисленного стека, но у нее огромная утечка памяти, которую я не могу понять. Когда я выталкиваю узел, кажется, что он не освобождает память, даже если я явно удаляю старый узел после его удаления. Когда я запускаю его, он использует 150 Мб памяти, но не освобождает его после очистки стека. Буду признателен за любую помощь, так как это мой первый набег на язык без сборки мусора. Это было скомпилировано с gcc 4.3 на 64-битной Kubuntu.

 //a trivial linked list based stack of integers

#include <iostream>
using namespace std;

class Node
{
    private:
        int num;
        Node * next;
    public:
        Node(int data, Node * next);
        int getData();
        Node * getNext();
};
Node::Node(int data, Node * next_node)
{
    num = data;
    next = next_node;
}
inline int Node::getData()
{
    return num;
}
inline Node* Node::getNext()
{
    return next;
}


class Stack
{
    private:
        unsigned long int n;
        Node * top;
    public:
        Stack(int first);
        Stack();
        void push(int data);
        int pop();
        int peek();
        unsigned long int getSize();
        void print();
        void empty();
};
Stack::Stack(int first)
{
    Node first_top (first, NULL);
    top = &first_top;
    n = 1;
}
Stack::Stack()
{
    top = NULL;
    n = 0;
}
void Stack::push(int data)
{
    Node* old_top = top;
    Node* new_top = new Node(data,old_top);
    top = new_top;
    n++;
}
int Stack::pop()
{
    Node* old_top = top;
    int ret_num = old_top->getData();
    top = old_top->getNext();
    delete old_top;
    n--;
    return ret_num;
}
inline int Stack::peek()
{
    return top->getData();
}
inline unsigned long int Stack::getSize()
{
    return n;
}
void Stack::print()
{
    Node* current = top;
    cout << "Stack: [";
    for(unsigned long int i = 0; i<n-1; i++)
    {
        cout << current->getData() << ", ";
        current = current->getNext();
    }
    cout << current->getData() << "]" << endl;
}
void Stack::empty()
{
    unsigned long int upper = n;
    for(unsigned long int i = 0; i<upper; i++)
    {
        this->pop();
    }
}

Stack createStackRange(int start, int end, int step = 1)
{
    Stack stack = Stack();
    for(int i = start; i <= end; i+=step)
    {
        stack.push(i);
    }
    return stack;
}

int main()
{
    Stack s = createStackRange(0,5e6);
    cout << s.peek() << endl;
    sleep(1);
    cout << "emptying" <<endl;
    s.empty();
    cout << "emptied" <<endl;
    cout << "The size of the stack is " << s.getSize()<<endl;
    cout << "waiting..." << endl;
    sleep(10);
    return 0;
}

Answer 1

Как вы ЗНАЕТЕ, что память не освобождается? Библиотека времени выполнения будет управлять распределением и не сможет освободить память обратно в ОС, пока программа не завершится. В этом случае память будет доступна для других выделений в вашей программе во время ее выполнения.

Однако .... у вас, похоже, другие проблемы. Мой C ++ действительно ржавый, так как я занимаюсь Java уже 15 лет, но в конструкторе Stack :: Stack вы выделяете экземпляр Node в системном стеке, а затем сохраняете ссылку на него в своем «стеке». Этот экземпляр Node выходит из области видимости после завершения конструктора, оставляя висячий указатель.

Answer 2

Stack::Stack(int first)
{
    Node first_top (first, NULL);
    top = &first_top;
    n = 1;
}

Это неправильно, вы не можете назначить адрес локального объекта члену класса (вверху), так как локальные объекты уничтожаются при возврате функции.

Создайте узел в куче, а не в стеке, сделайте что-то вроде этого:

 Stack::Stack(int first)
    {
        top = new Node(first, NULL);
        n = 1;
    }

И проясните концепцию списка ссылок и используйте ручку и бумагу, если вы можете это сделать.

Ваша операция Stack :: Push (int) кажется некорректной, проверьте, что вы забыли сделать.

Мое предложение - попытаться реализовать универсальный стек с помощью шаблона , чтобы он работал для всех типов данных.

Answer 3

Когда возвращается createStackRange(), он возвращает копию стека, используя сгенерированный компилятором конструктор копирования, который просто создает побитовую копию (т. Е. Он будет копировать указатель на первый узел и размер.) *

Если серьезно, вам не хватает деструктора для класса Stack. В идеале вам нужно пройтись по списку и вызвать delete на каждом Node. Объект Stack, созданный в стеке процессоров, будет автоматически очищаться при выходе из main (), но без деструктора узлы будут по-прежнему выделяться после завершения программы. Вы, вероятно, хотите что-то подобное для этого:

Stack::~Stack()
{
    while ( top )
    {
        Next *next = top->getNext();
        delete top;
        top = next;
    }
}

Если подумать, то компилятор C ++ автоматически сгенерирует для вас конструкторы и деструкторы копирования, но обычно они мелкие. Если вам нужно глубокое поведение, вы должны сделать это самостоятельно, где-нибудь реализовать.

Answer 4

Проанализировав код, я не смог найти утечку, поэтому скомпилировал ее и сам запустил в отладчике. Я согласен с Джимом Гаррисоном - я думаю, что вы видите артефакт времени выполнения, а не фактическую утечку, потому что я не вижу его на моей стороне. Проблемы, на которые указывают NickLarsen и smith , являются фактическими проблемами, которые вы хотите исправить, но если вы проследите код, ни одна из них не должна вызывать описанную вами проблему. Код, который выделяет Смит, никогда не вызывается в вашем примере, и код, который выделяет Ник, вызовет другие проблемы, но не тот, который вы видите.

Answer 5

Обратите внимание, что вы должны бросать свой собственный стек только в образовательных целях. Для любого реального кода вы должны использовать реализацию стека, которая поставляется со стандартной библиотекой C ++ ...

Answer 6

Создайте заглушку для тестирования вашего кода и инструмент анализа памяти пользователя, такой как "Valgrind". Это обнаружит утечки памяти и повреждения для вас.

проверьте man-страницы для получения дополнительной информации.