Implementacja stosu przy użyciu unique_ptr

0

Cześć
Napisałem bardzo prostą wersje stosu przy użyciu unique_ptr. Wydawało mi się, że stos działa poprawnie dopóki nie umieściłem w nim większej liczby elementów - ponad kilka tysięcy węzłów. Próba wykonania programu TestStack.cpp kończy się błędem przepełnienia stosu. Błąd wyskakuje przy niszczeniu stosu (wyjściu z zakresu lokalnego). Ma ktoś pomysł co może być tego przyczyną?

// Stack.h
#pragma once

#include <iostream>
#include <memory>

template <class T>
class Stack
{
private:
	struct Node
	{
		std::unique_ptr<Node> next;
		T value;
	};
	std::unique_ptr<Node> top = nullptr;
public:
	Stack() = default;
	Stack(const Stack & s) = delete;
	Stack & operator=(const Stack & s) = delete;

	void push(const T & elem);
	void pop();
	const T & front() const { return top->value; }
	void showStack() const;
};

template<class T>
void Stack<T>::push(const T & elem)
{
	auto newNode = std::make_unique<Node>();
	newNode->value = elem;

	if (top)
		newNode->next = move(top);

	top = move(newNode);
}

template<class T>
void Stack<T>::pop()
{	
	if (top)
		top = std::move(top->next);
}

template<class T>
void Stack<T>::showStack() const
{
	Node* tmp = top.get();

	while (tmp)
	{
		std::cout << tmp->value << std::endl;
		tmp = tmp->next.get();
	}
}
// TestStack.cpp
#include "Stack.h"

const int STACK_SIZE = 10000;

int main()
{
	using namespace std;

	{
		Stack<int> s;
		for (int i = 0; i < STACK_SIZE; i++)
			s.push(0);

		cout << "Stos gotowy";
		cin.get();
	}
	cout << "Stos usuniety";

	cin.get();
	return 0;
}
3

Problemem jest zastosowanie unique_ptr. Z destruktora wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor ;)

Call stack rośnie pi razy oko tak:

~Stack
  ~Node1
    ~Node2
      ~Node3
        ~Node4
         ~Node5
           ...
                                                           ~NodeStackTop

EDIT: jak elementów jest mało to wszystko jest ok. Jak zaczyna ich być więcej to gdzieś po drodze się to wysypuje.

5

Niestety, jest to znany problem związany z użyciem unique_ptr. Rozwiązaniem jest własna implementacja destruktora, która go niweluje.

0
alagner napisał(a):

Problemem jest zastosowanie unique_ptr. Z destruktora wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor, z którego wołasz destruktor ;)

Call stack rośnie pi razy oko tak:

~Stack
  ~Node1
    ~Node2
      ~Node3
        ~Node4
         ~Node5
           ...
                                                           ~NodeStackTop

Hmm....coś w tym jest. Nie ma zatem możliwości zaimplementowania stosu przy użyciu (dowolnych) inteligentnych wskaźników?? jesteśmy skazani na zwykłe wskaźniki rodem z C czy może jest jakieś sprytne obejście?

2

Jak najbardziej powinieneś używać unique_ptr. Tutaj po prostu nie możesz zdać się na domyślnie wygenerowany destruktor.

0

Jak chcesz swobody (w sensie szybkości) dodawania/zrzucania to użyj std::list, zapakuj w odpowiedni interfejs i z bani (w tym konkretnym przypadku).

0

Wielkie dzięki!

2

Taki destruktor może wyglądać tak:

~Stack()
    {
    	for (std::unique_ptr<Node> current = std::move(top);
             current;
             current = std::move(current->next));
    }

1 użytkowników online, w tym zalogowanych: 0, gości: 1