Професионална програма
Loading...
+ Нов въпрос
Yoana_Borisova avatar Yoana_Borisova 4 Точки

07. List

Здравейте! Изпитвам затруднения със задача 07. List от упражнението за правилото на 3/5/0. И по-точно с имплементирането на функцята static List getReversed(List l) и деструктора. Когато рънна програмата ми изписва exit code -1073741819, което до колкото разбрах е от неправилно освобождаване на памет. Чудя се дали не трябва да напиша някаква функция за изтриването и на всеки нов Node, който създавам или той сам ще се изтрие, когато излезе от скоуп. Ето го кода ми ще съм благодарна на малко помощ:

#include "List.h"
#include <sstream>

List::List()=default;
List::List(const List& other){
 *this = other;
}
int List::first() const{
    return head->getValue();
}



void List::add(int value){
    Node* newV;
    newV->setValue(value);
    newV->setPrev(tail);
    newV->setNext(nullptr);

    Node* help=newV;
    newV=tail;
    tail=help;

    newV->setNext(tail);

}

void List::addAll(const List& other){
   tail->setNext(other.head);
   other.head->setPrev(tail);
}

void List::removeFirst(){
    Node* newFirst=head->getNext();
    Node* help = tail;
    tail=newFirst;
    newFirst=tail;

}

void List::removeAll(){
    head->setNext(nullptr);
    head->setValue(0);
    tail->setPrev(head);
    tail->setValue(0);
}

size_t List::getSize() const{
    if(isEmpty()){return 0;}
    size_t size=1;
    Node* curr=head;
    while(curr!=tail){
        curr=head->getNext();

      size++;
    }

    return size;
}

bool List::isEmpty() const{
    if(head->getNext()==nullptr){
        return true;
    }
    return false;
}

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

std::string List::toString() const{
    Node* curr=head;
    std::ostringstream out;
    while(curr!=tail||curr==tail){
        out<<curr->getValue()<<" ";
    }
    return out.str();
}

List& List::operator<<(const int& value){
    add(value);
    return *this;
}


List& List::operator<<(const List& other){
    addAll(other);
    return *this;
}

List& List::operator=(const List& other){
    head=other.head;
    tail=other.tail;
    size=other.size;
    return *this;
}

List::~List() {
    //??
    Node *curr = head;
    while (curr != tail) {
        curr = curr->getNext();
        delete curr->getPrev();
        curr->setPrev(nullptr);
    }
    delete curr;
    curr = nullptr;
}

//Node part

List::Node::Node(int value, Node * prev, Node * next){
    this->value=value;
    this->next=next;
    this->prev=prev;

}

int List::Node::getValue() const{
    return this->value;
}
void List::Node::setValue(int value){
    this->value=value;
}
List::Node* List::Node::getNext() const{
    return this->next;
}
void List::Node::setNext(Node * next){
    value=next->value;
    next=next->next;
    prev=next->prev;
}

List::Node * List::Node::getPrev() const{
    return this->prev;
}
void List::Node::setPrev(Node * prev){
    value=prev->value;
    next=prev->next;
    prev=prev->prev;
}


 

Тагове:
1
C++ OOP
ditchev avatar ditchev 36 Точки

Здравей, колежке :))

Най-напред да кажа, че в дадения main() не се проверява дали си имплементирала getReversed(List I) така, че тази функция я разписваш "по желание" :))) А деструктора ти, дори и да ти е странно, работи както трябва :)) Друг е въпроса, че е хубаво да се пипне (малко), ама това е пак "по желание" :)

Проблема е на друго място. Всъщност, на много други места ... И май се преплитат няколко проблема ...

Някак си обаче май не е много редно преди края на срока за предаване детайлно да те насочвам към конкретните ти грешки. Пък и съм сигурен, че сама ще ги откриеш.

Само за да започнем отнякъде: Защо всъщност в деструктора ползваш delete ???!!!

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

За да завърша: много е добре да си припомниш какво беше shallow copy !

2
15/08/2021 11:19:17
Smeshan avatar Smeshan 89 Точки

Здравейте,
аз също изпитвам затруднения.
Явно не ми е станало много ясно с тези временни копия, защото проследих, че в деструктура постъпва лист само с адрес и без нищо друго, и от там програмата гърми.

Иначе ако закоментирам деструктура получавам 40/100, като имам 1 Memory limit и 5 Runtime error. Които runtime errors не знам от къде идват също :?

List.cpp

Благодаря предварително за помощта!

Поздрави,
Илиян

2
15/08/2021 16:42:26
j.petrov_90 avatar j.petrov_90 372 Точки

Привет, Илиян,

На пръв прочит си се справил добре.
Не съм ти рънвал решението в Judge, но виждам следните проблеми:

- не update-ваш подобаващо брояча "size" на твоя клас. Провери всички места, където това трябва да се случи.
- не си успял да имплементираш правилото на 3 (The Rule of Three) за твоя клас.
Точно това кара и програмата ти да гърми с имплементацията на конструктора, която в последствие си закоментирал.
Обърни внимание на copy constructor-а ти и copy assignment оператора. Ти ефективно си направил member wise копие на класа ти, т.е. все едно си ползвал default-ните copy constructor и copy assigment оператор.
Това се нарича shallow copy както е отбелязал колегата. Ти имаш нужда от deep copy (ново заделяне на данни и чак тогава копиране)

Какво учихме в лекцията?
Когато класа ти управлява динамични ресурси (в случая Node-ове) - значи ще имаш нужда от custom имплементация.
Имаш нужда от custom имплементация на едно -> значи имаш нужда от custom имплементация на всичките.

Поздрави,
Живко
 

0
ditchev avatar ditchev 36 Точки

Здравей, Илиян,

напреднал си, но както се казва: Още може :))

С две думи: съобразил си първия ми въпрос/забележка към Йоана, обаче втория ... :((

Конкретно: обърни особено внимание на функциите от ред 28 и 114 !!!

А-а-а да, във функцията ти addAll(const List& other) има една умопомрачителна грешка, ама тя е лесна за откриване.

Тук там има още дреболии, които следва да се оправят, примерно, не зачиташ май изобщо променливата size :)), ама и това е към 'белите кахъри' :))

Не се тревожи за деструктора, в ред ти е (не че не може да се усъвършенства, напр. има една функция, която по името и разбираш, че мре да влезе в деструктора, но на този етап е опасно да не забиеш в premature optimizations :))

Като цяло std::list е много интересен и полезен STL-контейнер, Много различен от std::vector например. Заслужава внимание начина по който std::list (! не-) инвалидира итераторите си. Зачитам от последния working draft ISO/IEC 14882:2020: 

точка 22.3.10.4 Modifiers [list.modifiers]  /става дума за insert, emplace_front, emplace_back, push_front, push_back etc/: /стр.830 ff/

Remarks: Does not affect the validity of iterators and references. If an exception is thrown there are no effects.

ps. Подчертаването е мое.

Да го сравним с std::vector:

точка 22.3.11.5 Modifiers[vector.modifiers] /insert, emplace_back, emplace, push_back/ стр. 838:

Remarks: Causes reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past the-end iterator. If no reallocation happens, then references, pointers, and iterators before the insertion point remain valid but those at or after the insertion point, including the past-the-end iterator, are invalidated.

ps. Подчертаването е мое.

Преведено на български: ако имаш например range-based for loop, който инсъртва в клас std::list нямаш проблем, end() си е валиден. Ако обаче инсъртваш в клас std::vector - end() се инвалидира, и то винаги, независимо дали имаш не запълнено capacity във вектора / щото си се изхитрил и си ползвал reserve()./

Това е малко лирично отклонение към последната задача от предната седмица: Sequence.

/Другите контейнери, които биха могли да се използват при нея са std::multiset и std::multimap, но темата става обширна :))/

Поздрави!

0
j.petrov_90 avatar j.petrov_90 372 Точки

Привет, Йоанче,

Задачата хич не е лесна.
Имай предвид, че тази задача е една от "класиките" - да си имплементираш std::list без да ползваш на готово функционалности от STL-а.
Във всеки един университет е гаранция, че ще минеш от там.
До колко помня (дано не греша) на теб ти е рано за университет, така че давай смело - ще помагаме! :)

Колегата @ditchev ти е дал добри насоки.
И аз не искам да ти "изплювам" готовото решение, а искам ти сама да си намериш грешките и да ги коригираш.

Да запомнем от там, че сме хора, а не сме машини.
Като виждаш, че имаш грешка - не се чуди какво се случва - а пуски дебъгера.
Започни да минаваш пред кода ред по ред, функция по функция и разжлеждай стойностите на променливите.
Ще се очудиш колко лесно се хващат грешки :)

Няколко жокера:
- в деструктора ползваш delete, но никъде не си заделила памет динамично. Може би там където създаваш нещо - там трябва да има заделяне на памет
- в решението ти няма абсолютно нито една проверка
Представи си, че имаш само 1 елемент в списъка. Неговият next трябва да е nullptr. Ти обаче никъде не проверяваш за nullptr. Т.е. никъде не гледаш дали имаш curr element, да не говорим за next
- default-ния ти конструктор много прецеква работата. По този начин всичките ти променливи са неинициализирани
- относно функцията getReversedList - ами как трябва да изглежда? Листа си има глава (head) има си и опашка (tail). Тогава създаваш един нов списък и започваш да прибавяш елементи от към главата му, докато в оригиналния списък ги взимаш в обратен ред (от опашката към главата).

Очаквам те да се върнеш с по-добро решение :)
Ти си на ход.

Поздрави,
Живко

1
15/08/2021 21:55:38
Smeshan avatar Smeshan 89 Точки

Здравейте колеги,
наслагах пропуснатите size увеличения и намаления, където ги бях изпуснал (надявам се това сте имали предвид).

Иначе копи конструктура тотално го бях изпуснал. Eто как ги направих да изглеждат:
Copy constructor:

List::List(const List& other)
	: head(size ? new Node(other.head->getValue(), other.head->getPrev(), other.head->getNext()) : nullptr)
	, tail(size ? new Node(other.tail->getValue(), other.tail->getPrev(), other.tail->getNext()) : nullptr)
	, size(other.size) {
}

Copy assignment:

List& List::operator=(const List& other) {
	if (this != &other) {
		this->size = other.size;
		Node* newHead = new Node(other.head->getValue(), other.head->getPrev(), other.head->getNext()); // allocate
		if (this->head != nullptr) {
			delete this->head;  // deallocate
		}
		this->head = newHead;

		Node* newTail = new Node(other.tail->getValue(), other.tail->getPrev(), other.tail->getNext()); // allocate
		if (this->tail != nullptr) {
			delete this->tail;  // deallocate
		}
		this->tail = newTail;
	}
	return *this;
}

Доколкото разбирам всъщност "данните" на един лист са в head и tail, и съответно тях трябва да алокиръм и делокиръм. Нали? Защото пробвах нещо от сорта на List* newList = new List(other); , но после не ми дава this = newList;. Или всъщност точно това е задачата да има new List, в който вече правя това с new Node за head и tail?

И уж напълно ми е ясно вече какво трябва да направя и какво трябва да стане, но сега гръмна още повече.. След известно време прекарано с дебъгера, в Copy assignment отнякъде се появява лист с value -587983213 .. незнайно от къде и програмата гърми.
Ето целия код:
List.cpp

Не знам колко е трудна тази задача, защото в главата ми е ясна логиката и как работи един лист, но не мога да го изпиша вярно с код :(

Поздрави,
Илиян

1
16/08/2021 12:55:38
j.petrov_90 avatar j.petrov_90 372 Точки

Привет, Илиян,

Доближаваш се до целта, но има още път, който трябва да изминеш.
Дали листа държи данните си в "head" и "tail"? - Не, не ги държи там.

Разгледай собствена си функция

void List::add(int value) {

и би трябвало да си отговориш на въпроса.

Данните в един лист могат да са безкрайно много. Нищо не пречи да имаш 1 милион Node-a.
Head и Tail са ти само пойнтъри към първия е респективно последния Node от тези 1 милион.

Т.е. не е достатъчно да заделиш нови данни само за Node-а под head-a и tail-а.
защото това ще значи, че останалите (1 милион - 2) елемента имаш shallow copy.
Или казано по друг начиш - в 2 или повече листа ще имаш референции към една и съща динамична памет.
От там нататък задачата ти е бомба със закъснител.

Какво трябваше да направиш?
Да направиш deep copy на абсолютно всички node-ове, които искаш да копираш.

Поздрави

0
Smeshan avatar Smeshan 89 Точки

Борбата и бомбите продължават..
И ето заделям нова памет newHead с датата на other.head. След това казвам head = newHead. След това слагам итератор към следващия елемент (този след other.head) и трия датата на other.head. И би трябвало съм готов с head-a?
След това слагам пойнтър към следващия елемент от this (този след this->head) и започвам да итерирам елемент по елемент, като създавам нова задалена памет за всеки Node с данните на от other, премествам итераторите, трия другите данни и сменям итератора от този node да сочи към новите данни. След това същото и за опашката. 

List::List(const List& other) {
	Node* newHead = new Node(other.head->getValue(), other.head->getPrev(), other.head->getNext());
	head = newHead;
	
	Node* otherIt = other.head->getNext();
	delete other.head;

	Node* thisIt = this->head->getNext();

	while (otherIt != other.tail) {
		Node* newNode = new Node(otherIt->getValue(), otherIt->getPrev(), otherIt->getNext());
		
		otherIt = other.head->getNext();
		delete otherIt;

		thisIt = newNode;
		thisIt = thisIt->getNext();
	}
	Node* newTail = new Node(other.tail->getValue(), other.tail->getPrev(), other.tail->getNext());
	tail = newTail;
	delete other.tail;

	this->size = other.size;

}

Не е ли това логиката :?

Поздрави.

0
kolioi avatar kolioi 621 Точки

Преди време бях писал един коментар за getReversed() и как ефективно да обърнем списък без да заделяме памет.

Link

2