Loading...
Jovanna avatar Jovanna 186 Точки

C++ Advanced, Task07_05_Linked_List - защо ни е Node * prev? И къде бъркам в деструктора?

Здравейте,

не мога да разбера защо имаме тук и пойнтери назад, това възможност за обрато обхождане ли е? Повечето реализации, които намерих са с пойнтери с връзка само за напред, защо ни трябват и за назад?

Kak да разпиша деструктора, kъде бъркам тук или е правилно разписан?

List::~List() {   
    if (!this->size != 0) {
        Node * tempH = this->head;                
        this->tail = NULL;                       // Toва зануляване тук вярно ли е? , мисля че е nullptr  this->tail за първия елемент ??
        Node * tempT = this->tail;
        while (tempH->getNext() != NULL) {
            tempT = tempH;
            tempH = tempH->getNext();
            delete tempT;
        }
        delete tempH;
    }

//имаме:

class Node {
    private:
        int value;
        Node * prev;
        Node * next;

и полета на клас List:

    Node * head;
    Node * tail;
    size_t size;

Поздрави!

 

Тагове:
0
C++ Programming 23/10/2018 17:24:50
MartinBG avatar MartinBG 4803 Точки

Node* prev ни дава възможност за обхождане на списъка в обратен ред. Конкретно в тази задача може и да не ти се наложи да го ползваш, но с него е най-лесно да имплементираш getReversed метода.

 

В C++ е прието да се използва nullptr вместо NULL (или 0) за пойнтъри, които не са инициализирани, но и двата варианта ще работят.

Деструктурът ти е поне една идея по-сложно разписан от необходимото и в този си вид остaвя списъка в невалиден стейт*. Това, което трябва да направиш, е да обходиш и изтриеш всички елементи от началото до края, т.е. докато getNext() != nullptr и после да сетнеш размера на 0, а head и tail на nullptr.

Разбира се, може да обходиш елементите и в обратен ред при триенето (getTail() -> while getPrev() != nullptr)

* В предпоследната лекция беше обяснено защо е добре да сетваме всички указатели на nullptr, след като освободим паметта към която сочат, в деструктора.

1
23/10/2018 18:32:09
kolioi avatar kolioi 641 Точки

Най-лесния начин е само да извикаш removeAll() в деструктора. А пък removeAll() просто обхожда целия списък и освобождава паметта на всеки node. Може да тръгнеш от началото към края (от head към tail) или обратно, няма никакво значение. Аз съм го направил така

void List::removeAll()
{
	while (this->size)	// или while (!isEmpty())
		this->removeFirst();
}

Не е необходимо да нулираш head и tail в деструктора, но е абсолютно задължително да го направиш в конструкторите smiley

2
Jovanna avatar Jovanna 186 Точки

Здравейте,

много благодаря за помощта, започва да ми става по-ясно.

дали успях да коригирам, сега деструкторът ще оставя ли списъка в невалиден стейт :

List::~List() {   
    Node * temp = this->head;
    Node  * prevPtr = nullptr;
    while (temp->getNext() != nullptr) {
        prevPtr = temp;
        temp = this->head->getNext();
        delete prevPtr;
        prevPtr = nullptr;        
    }
    delete temp;
    temp = nullptr;
    this->head = nullptr;
    this->tail = nullptr;
    this->size = 0;
    //ИЛИ Ver.2:
    //this->removeAll();
}

А с вариант 2/ (RamoveAll() + RemoveFirst()),   RemoveFirst правилно ли се разписва по този начин?

void List::removeFirst() {    
    if (this->size > 0) {
        Node *temp = this->head;
        this->tail = this->head;
        this->head = temp->getNext();
        delete temp;
        temp = nullptr;
        this->size--;
    }
}

...за първи път пиша подобен код и ми е сложно.

0
23/10/2018 21:58:37
MartinBG avatar MartinBG 4803 Точки

Най-добре използвай removeAll() в деструктура (и навсякъде, където трябва да се занули листа).

Използването на removeFirst() в removeAll() също е добър пример за преизползване на кода, но трябва да се има предвид, че е по-бавно заради допълнителната логика в removeFirst(), която няма смисъл в контекста на removeAll().

 

Деструктурът изглежда коректен.

В removeFirst() не ми харесва този ред:

this->tail = this->head;

Защо сетваш tail да сочи към Node, който ще бъде изтрит?

tail трябва да сочи към последният валиден елемент в списъка, или към nullptr ако списъкът е празен.

Съответно head трябва винаги да сочи към първият елемент в списъка или към nullptr.

 

1
23/10/2018 22:23:29
Jovanna avatar Jovanna 186 Точки

kolioi: за 4-та, запази в статична променлива map<string, int> всяка дума и после в метода get за int-a трий, за да нулираш мап-а  за следващия тест

1
kolioi avatar kolioi 641 Точки

Ето ти още един лесен начин за деструктора

List::~List()
{
	for (Node* node = this->head; node;)
	{
		Node* temp = node;
		node = node->getNext();
		delete temp;
	}
//	this->removeAll();
}

Не е необходимоп да нулираш head, tail и size, защото обекта вече не съществува след като се извика деструктора.

И с риск да ми се карат, един хак: някои методи, например getReversed() не се използват в кода, така че може да не се имплементират въобще. Например този код е достатъчен да се компилира програмата, но не прави нищо

List List::getReversed(List l)
{
	return l;
}

Изпробвано, работи и джадж дава 100/100 smiley

1
24/10/2018 00:05:02
MartinBG avatar MartinBG 4803 Точки

Коментарите на kolioi относно липсата на нужда от нулирането на поинтъри в деструктора, ме провокираха да се зачета по-подробно по темата, за което му благодаря! :)

По време на лекцията зададох уточняващ въпрос за ситуации, при които може да достъпим полета/методи на унищожен обект и как сетването на поинтърите на nullptr би ни помогнало, и отговорът който получих ми се стори смислен към момента, но след прочетеното съм убеден, че kolioi е прав, че това излишно.

Както се оказва, това не само е излишно, но е опасно и е лоша идея/практика:

- Допълнителни операции, които бавят

- Повече код -> по-трудно четене, нужда от поддържане, възможност за грешки

- Компилаторът в Release най-вероятно ще ги оптимизира, т.е. премахне, защото са ненужни

- В Debug компилаторът често презаписва освободените указателите с някаква известна нему стойност, която да улесни дебъгването

- След деструктора обектът вече не съществува. Всеки опит да се достъпи той или паметта, която е ползвал е недефинирано поведение, като е много вероятно тази памет вече да се ползва от друг обект, т.е. и нашия nullptr да е презаписан, което допълнително обезсмисля сетването му

- Ако по някаква причина паметта все още не е променена при опита ни да я достъпим след деструктура и сме сетнали пойнтъра на nullptr, всъщност може да прикрием бъг, който иначе ще хванем (например двойно освобождаване на памет, което може да се случи при повторно извикване на деструктора, но не само)

 

Накратко - няма ситуация, при която сетването на nullptr на указатели към освободена в деструктора памет да носи някаква полза. Най-вероятно идеята е дошла за подсигуряване срещу достъп до (вече) чужда памет, но както по-горе споменах, тази сигурност е измамна и само прикрива тези проблеми. Ситуация, при която външен код държи указател към вътрешни ресурси на обект, върху чиито живот няма контрол, е грешка в дизайна и nullptr не е решение.

Горното разбира се с пълна сила важи и за ресетването на други полета в деструктора (напр. size = 0) - това също е излишно, защото всеки достъп до обекта след деструктора е недефинирано поведение.

 

Още веднъж благодаря на kolioi за коментара, който ме провокира да се зачета по темата!

 

Няколко теми по въпроса: 

do-i-have-to-set-pointer-to-nullptr-in-destructor

is-it-worth-setting-pointers-to-null-in-a-destructor

is-the-c-compiler-optimizer-allowed-to-break-my-destructor-ability-to-be-calle

 

3
24/10/2018 16:15:05
kolioi avatar kolioi 641 Точки

Благодаря за коментара. Линковете са интересни. Аз просто се ръководя от правилото, че един пойнтер го нулираме само ако след това ще го използваме отново. Обаче след като се извика деструктора, обекта не съществува повече и няма как да използваме пойнтера (нямаме достъп до него чрез обекта). С две думи: няма обект - няма проблем, както казваше един мустакат чичко wink

1
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.