Manualna implementacja kolejki, kilka pytań odnośnie dynamicznej alokacji pamięci i wskaźników.

Question

Witam wszystkich,

jestem na etapie poznawania struktur danych używanych w programowaniu. Ostatnio zająłem się kolejką. Chciałbym prosić kogoś bardziej doświadczonego o sprawdzenie czy poprawnie ją zaimplementowałem oraz czy nie ma wycieków pamięci. Dodatkowo mam kilka pytań:

a) Czy opłaca się samemu implementować struktury danych czy raczej korzystać z gotowych bibliotek?

b) W metodzie Queue::remove() w linijce oznaczonej komentarzem "1", tworzę kopię wskazującą na "first", natomiast w linii "2" za pośrednictwem tej kopii niszczę element na który wskazuję "first". Rozumiem, że po tej operacji "first" wskazuję teraz na komórkę w pamięci, w której nic się nie znajduję, dopóki nie przekieruję go na następny element kolejki(linia nr 3)? Przepraszam, że tak niejasno ale nie mam pojęcia jak to inaczej ubrać w słowa. Liczę, że ktoś da radę zrozumieć moje wypociny. 

// ConsoleApplication4.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include "conio.h"

struct Node {

	int m_id;
	Node *next;

	Node(); // constructor



};

Node::Node() {

	next = nullptr;

}

struct Queue {

	Node *first;
	Node *last;

	Queue(); // constructor

	void add(int id); // dodaj do kolejki
	void remove(); // usuń z kolejki
	void print(); // wyświetl zawartość kolejki

	bool empty(); // czy pusta
	int size(); // zwraca wielkość kolejki

	void destroy(); // niszczy całą kolejkę



};

Queue::Queue() {

	first = last = nullptr;

}

void Queue::add(int id) {

	Node *node = new Node; // Tworzymy nowy węzeł

	node->m_id = id;

	if(!first) { 
		
		first = node;
		return;

	}


	// W przypadku braku informacji, szukamy ostatniego węzła

	if(!last) {
	
		Node *tmp = first;

		while(tmp->next)
			tmp = tmp->next;

		last = tmp;
	
	}

	
	node->next = nullptr;
	
	last->next = node;
	last = node;
		
}

void Queue::remove() {

	Node *tmp = first; // 1

	if(tmp) {
	
		first = nullptr;
		first = tmp->next; // 3
		delete tmp; // 2
	
	}

}

void Queue::print() {

	Node *tmp = first;

	std::cout << "FIRST --> ";

	while(tmp) {
	
		
		std::cout << tmp->m_id << " ";
		
		tmp = tmp->next;
	
	}

	std::cout << " <-- LAST";
}

bool Queue::empty() {

	return first == nullptr;

}

int Queue::size() {

	Node *tmp = first;

	int i = 0;

	while(tmp) {
	
		tmp = tmp->next;
		i++;
	
	}

	return i;

}

void Queue::destroy() {

	while(!this->empty())
		this->remove();

}

int main()
{

	Queue *queue = new Queue;

	queue->add(8);
	queue->add(66);
	queue->add(23);
	queue->print();

	std::cout << "\nSize: " << queue->size() << " Empty: " << queue->empty() << "\n\n";

	queue->remove();
	queue->print();

	std::cout << "\nSize: " << queue->size() << " Empty: " << queue->empty() << "\n\n";
	
	queue->destroy();
	queue->print();
	
	std::cout << "\nSize: " << queue->size() << " Empty: " << queue->empty() << "\n\n";

	delete queue;
	queue = nullptr;

	

	_getch();
	return 0;
}

 

Answer 1

Na szybko:

oraz czy nie ma wycieków pamięci

Proponuje bardzo prosty stress test for 1000000 razy stworz kolejke, cos dodaj, cos usun i patrz czy pamięć zjadana przez program rośnie, czy to w jakimś debugerze czy po prostu podglądając proces. To najprostsze rozwiązania przy takich prostych programach. Są też fajne programy do analizy wycieków np valgrind, którego użycie skraca się do valgrind moj_program i wypisuje Ci czy wszystko jest cacy z pamięcią.

a - zawsze gdy się da korzystaj z gotowych implementacji. Wynajdywanie koła od nowa jest złe z dwóch powodów:

• zajmuje czas
• osoby, które czytają Twój kod muszą dodkowo ogarnąć Twoją implementacje ogólnie znanych i już rozwiązanych problemów

Jedyny plus wynajdywania koła od nowa jest głębsze zrozumienie tego koła. Dlatego warto sobie dla treningu raz zaimplementować a potem korzystać z gotowych rozwiązań.

b - musisz pamiętać, że robiąc delete wskaźnik zwalniasz pamięć na którą ten wskaźnik wskazuje, nic wiecej, sam wskaźnik dalej pokazuje dokładnie w to samo miejsce. Zwolnienie pamięci oznacza, że zrzekasz się tej pamięci i nie należy już ona do programu, czyli jest wolna i może zostać ponownie wykorzystana na np inną zmienną.

        first = nullptr;
        first = tmp->next; // 3

ustawienie firsta na nullptr jest bez sensu skoro zostanie linijke nizej nadpisany. Posiadanie wskaźnika do pamięci która nie należy do Ciebie nie jest przestępstwem :D. Czasem można nawet odczytać jej wartość albo nawet coś tam zapisać. Spowoduje to niezdefiniowane zachowanie i okazjonalnie memory access violation, segmentation fault i takie tam, więc nie polecam.

Co do implementacji to nie jest zła. Nie podoba mi się jedynie brak destruktora i brak składowej size :D. Po przechodzić za każdym razem po wszystkich elementach?

Definiowanie konstruktora tylko po to żeby ustawić nullptr też nie jest za fajne, skoro od C++11 można zrobić po prostu tak:

struct Node {
 
    int m_id;
    Node *next = nullptr;
};

Ostatnia sprawa to ciekawostka - listy to przestarzałość ze względu na to, że nie są cache-friendly i są sensowne tylko w teori. Sytuacje, w których warto wybrać liste ponad tablice dynamiczną czy częściową tablice dynamiczną (std::dequeue) już prawie nie występują. Sam twórca C++ tutaj o tym mówił.

Comments

Na taką odpowiedź liczyłem. Bardzo mi pomogła, zajmę się poprawkami w kodzie jak tylko wrócę do domu. Serdecznie dziękuję!

Answer 2

IMO lepiej korzystać z gotowych bibliotek w programach (szczególnie tych większych), zwiększa to czytelność kodu, ale warto rozumieć działanie danej struktury a zaimplementowanie jej pomaga ;)

Answer 3

Jeśli chcesz sprawdzać wycieki pamięci - zainteresuj się valgrindem.

Najczęściej standardowe kontenery są odpowiednie, więc nie ma sensu implementować ich samemu. Z drugiej strony warto jest umieć je zaimplementować. Choćby dlatego, że prędzej czy później zdarzy się przypadek, że gotowe struktury będą zwyczajnie gorsze dla jakiegoś szczególnego przypadku użycia.

Jeśli chodzi o sam styl pisania, to klasa węzeł mogłaby być w klasie Kolejka, ponadto zadbaj o odpowiednią hermetyzację - wskaźniki na węzły nie powinny być publiczne!

W ramach poćwiczenia możesz też zaimplementować kolejkę na tablicy (coś jak bufor cykliczny, wykorzystując działanie modulo). Oczywiście w przypadku zapełnienia, alokowałbyś nową, większą tablicę.

Comments

Co do valgrinda - czytałem o nim, ale został wydany tylko i wyłącznie w wersji na linuxa. Może czas zmienić system :)

Co do uwag stylu pisania. Jestem w trakcie nauki C++  i jeszcze nie poznałem takich właściwości jak publiczne i prywatne zmienne. Mimo wszystko wezmę sobie to do serca i z pewnością będę zwracał na to uwagę w przyszłości.

---

W takim razie powodzenia!

Pamiętaj, że nie musisz instalować systemu na fizycznej maszynie, zawsze możesz sobie odpalić system na maszynie wirtualnej (Virtual Box czy coś podobnego).