Inna twórczość > C, C++
Delete this a struktury drzewiaste
Wonski:
Cześć,
Ostatnio zaimplementowałem banalnie prostą strukturę drzewiastą. jednak podczas implementowania operacji czyszczenia drzewa, byłem zmuszony użyć dosyć niebezpiecznego i triku, a mianowicie wywołałem operator delete na wskaźniku this.
Jest to oczywiście jak najbardziej dozwolona operacja, jednak jest w niej bardzo dużo "ale".
Jedni mówią, ze konstrukcja jest jak najbardziej ok, a inni , ze użycie delete this, wprowadza sporo obostrzeń, struktura jest niebezpieczna w użyciu i ogólnie to dobry wyznacznik tego, że kod zmierza w złą stronę:
https://stackoverflow.com/questions/7039597/what-will-happen-if-you-do-delete-this-in-a-member-function
Oczywiście podczas implementacji starałem się by to było absolutnie bezpieczne i raczej działanie tego kodu nie jest niezdefiniowane:
Struktura drzewa: (interesująca metoda to clearTree)
--- Kod: ---class Node{
public:
Node(int dataParam) : _mParent{ nullptr }, _mLeftChild{ nullptr }, _mRightChild{ nullptr }, _mData{ dataParam } {
}
Node* searchNode(int dataParam) {
if (this == nullptr) {
return this;
} if (_mData == dataParam) {
return this;
} if (_mData < dataParam) {
return _mLeftChild->searchNode(dataParam);
}
return _mRightChild->searchNode(dataParam);
}
Node* insertNode(int dataParam) {
static Node* lParrent;
if (this == nullptr) {
auto* retNode = new Node(dataParam); // każdy obiekt jest tworzony przy użyciu zwykłego new
retNode->_mParent = lParrent;
return retNode;
} if (dataParam <= _mData) {
lParrent = this;
_mLeftChild = _mLeftChild->insertNode(dataParam);
} else {
lParrent = this;
_mRightChild = _mRightChild->insertNode(dataParam);
}
return this;
}
int treeSize() const {
if (this == nullptr) {
return 0;
}
return _mLeftChild->treeSize() + 1 + _mRightChild->treeSize();
}
void printTree() const {
if (this == nullptr) {
return;
}
_mLeftChild->printTree();
std::cout << _mData << ' ';
_mRightChild->printTree();
}
void clearTree() { // zastępuje niejako destruktor
if(this != nullptr) {
_mLeftChild->clearTree();
_mRightChild->clearTree();
// niebezpieczne w chuj, ale w tej sytuacji raczej poprawne
delete this;
// dalej już nikt nie ma dostępu do składowych
}
}
private:
Node* _mParent;
Node* _mLeftChild;
Node* _mRightChild;
int _mData;
};
--- Koniec kodu ---
Kod kliencki:
--- Kod: ---int main( int argc, char* argv[] ) {
Node* rootNode = new Node(29); // spełniony wymóg co do delete this;
rootNode->insertNode(34);
rootNode->insertNode(32);
rootNode->insertNode(87);
rootNode->insertNode(21);
rootNode->insertNode(34);
rootNode->insertNode(2);
rootNode->insertNode(1);
rootNode->printTree();
std::cout << '\n' << rootNode->treeSize() << '\n';
rootNode->clearTree(); //niebezpieczne
rootNode = nullptr; // po wywołaniu metody, clear, już nikt nie ma dostępu do obiektu
system("PAUSE");
return 0;
}
--- Koniec kodu ---
Oczywiście jedną z możliwych opcji jest jeszcze jawne wywołanie destruktora, co również jest uważane za błąd projektowy.
Jest też opcja by zaimplementować wskaźniki liści jako wskaźniki słabe, tj std::weak_ptr, ale to i tak pozostaje problem z kontrolą czasu życia tych obiektów.
Ogólnie jest to strasznie niewygodne, bo wprowadza na klienta sporo ograniczeń. Nie ma opcji zarządzania tym przez smart pointery, więc klient musi pamiętać o ręcznym zarządzaniu pamięci. Musi również zapewnić by nikt po wywołaniu metody clear nie miał dostępu do obiektu.
Nie mam pojęcia jak inaczej można rozwiązać sytuację w której życie obiektu jest uzależnione od nie tyle od scope w którym się znajduje co od klienta, który decyduje w którym momencie obiekt ma przestać istnieć.
Adanos:
A po co chcesz w ogóle używać delete this by wyczyścić drzewo? Zazwyczaj robi się rekurencyjną metodę, która przyjmuje jako parametr root i usuwasz poddrzewa. Z drugiej strony, dlaczego nie użyjesz po prostu sprytnych wskaźników, tylko używasz zwykłych wskaźników? Usuwanie obiektu powinno się odbywać w destruktorze.
Wonski:
Niekoniecznie akurat całe drzewo
Zauważ, że mam metodę, searchNode, która zwraca wskaźnik do odpowiedniego węzła. Na tym węźle również mogę wywołać metodę clearTree.
Ogólnie zamysł jest taki, że jeżeli usunę dany węzeł to usuwam również wszystkie odgałęzienia i liście jakie z niego wychodzą.
Jeżeli wywołam to na korzeniu to tak jakbym usunął całe drzewo.
Jeżeli wywołam ma węźle z trzeciego poziomu to te poniżej nie zostaną usunięte.
A dlaczego chcę to zrobić? Ponieważ czas życia obiektu zależy od klienta.
Gdybym zamiast delete this przypisał do tego nullptr to byłby to memory leak... ponieważ tracę uchwyt do zasobu. (Ale pewnie da się to załatwić poprzez shared i weak ptr )
Obiekt powinien kończyć życie przez wywołanie destruktora, jeżeli kontrola programu wychodzi poza scope.
Jednak jeżeli czas życia obiektu jest zależny od klienta to nie widzę innego sposobu.
Gdyby po wywołaniu metody clear, wywołał się jeszcze destruktor to byłoby to niezdefiniowane zachowanie (dwukrotne zniszczenie obiektu).
Pewnie jak zwykle zjebałem design, ale chciałbym chociaż wiedzieć jak zarządzać pamięcią w strukturach rekurencyjnych. Pierwszy raz mam do czynienia z czymś takim :D
Co do smart pointerów to prototypuję strukturę podobną do drzewa, tylko ogólniejszą (tzn. graf) i tym razem na smartach:
--- Kod: ---class Graph
{
public:
explicit Graph(NodeProperties&& propertiesParam) : _mProperties{ std::move( propertiesParam ) } {
}
Graph& connectTo(std::shared_ptr<Graph>&& targetNode, EdgeProperties&& edgePropertiesParam) {
_mOutputNodes.push_back(std::make_pair(std::move(targetNode), std::move( edgePropertiesParam )));
return *_mOutputNodes.back().first;
}
void printGraph() const {
if (_mProperties._mIsMarked == true)
return;
_mProperties._mIsMarked = true;
std::cout << _mProperties._mValue << '\n';
for(const auto& node : _mOutputNodes)
node.first->printGraph();
}
int GraphSize() const {
}
~Graph() {
std::cout << "node is removed\n";
}
private:
std::list< std::pair< std::shared_ptr< Graph >, EdgeProperties > > _mOutputNodes;
NodeProperties _mProperties;
void clearNodeMarkFlags() {
for (const auto& node : _mOutputNodes) node.first->_mProperties._mIsMarked = false;
}
};
--- Koniec kodu ---
Jest oczywiscie kilka poprawek, jak chociażby metoda connectTo, ale to kilka minut pracy.
inż. Avallach:
--- Cytat: Sztywny w 2017-07-16, 12:30 ---Nie mam pojęcia jak inaczej można rozwiązać sytuację w której życie obiektu jest uzależnione od nie tyle od scope w którym się znajduje co od klienta, który decyduje w którym momencie obiekt ma przestać istnieć.
--- Koniec cytatu ---
Jeśli klient zna podstawy C++, to te dwie rzeczy oznaczają dokładnie to samo. Klient steruje czasem życia obiektu poprzez jego scope w kodzie. Może w tym celu stworzyć { blok w kodzie otaczający deklarację i użycie } albo wyczyścić zawartość zmiennej (jeśli deklarujemy to jako wartość lub inteligentny wskaźnik).
Metoda Clear powinna stać się destruktorem, ale klient nie powinien wołać go bezpośrednio - to byłby już jego błąd, nie twój. W C++ do sterowania czasem życia obiektu służą inne proste konstrukcje.
Wonski:
Ok, dobra rozumiem. Zgadzam się z tym.
A co w momencie gdy chcę się pozbyć węzła z drzewa? Przecież drzewo to nie struktura stała, mogę dodawać i usuwać elementy. A usunięcie węzła z drzewa automatycznie kończy jego żywot, bo nie ma już wskaźnika, który by na niego wskazywał. Usunięcie węzła to operacja, którą wykonuje klient.
Nie obejdzie się bez inteligentnych wskaźników.
Tzn wskaźnik na parent jako weak_ptr, a liście jako shared_ptr
Nawigacja
[#] Następna strona
Idź do wersji pełnej