uproszczenie kodu Mariusz: template <class T> void LinkedList<T>::insert(T k,int (*Compare)(T,T)) { Link<T> *x,*y,*z; x = new Link<T>(k); y = getFirst(); z = nullptr; while(y != nullptr && Compare(x−>getData(),y−>getData()) > 0) { z = y; y = y−>getNext(); } x−>setNext(y); x−>setPrevious(z); if(z == nullptr) { if(getFirst() != nullptr) getFirst()−>setPrevious(x); setFirst(x); } else { if(y != nullptr) y−>setPrevious(x); z−>setNext(x); } if(x−>getNext() == nullptr) setLast(x); } Jak wyrugować jedną ze zmiennych lokalnych i w miarę możliwości uprościć kod

Pytający: Po paru zmianach można tak uprościć (wymaga bezpośredniego dostępu do first, last i składowych węzła oraz potrzebny jest konstruktor węzła inicjalizujący wszystkie pola): template <class T> void LinkedList<T>::insert(T value, int(*compare)(const T&, const T&)) { Link<T> **addrNextPtr = &first; while (*addrNextPtr && compare(value, (*addrNextPtr)−>data) > 0) addrNextPtr = &(*addrNextPtr)−>next; Link<T> **addrPrevPtr = *addrNextPtr ? &(*addrNextPtr)−>previous : &last; *addrNextPtr = *addrPrevPtr = new Link<T>(value, *addrNextPtr, *addrPrevPtr); } Tu masz dopisaną tę funkcję z komentarzami: https://ideone.com/PbuWop (to zmodyfikowana wersja któregoś Twojego kodu, acz nie jestem pewny, czy ostatniego) Jak zwykle co nieco pozmieniałem, najistotniejsze linie: • 17 // deklaracja listy • 31, 150 // dodatkowy konstruktor • 40 // nowy przyjaciel (tego powyżej też nieco zmieniłem) • 131, 210 // insert • 508 // zmieniłem na wstawianie sortujące, w ramach testu Reszta to niezbyt istotne zmiany typu zmiana NULL na nullptr, czy konstruktory z listami inicjalizacyjnymi. Zmieniłem też przekazywanie argumentów do komparatora na przekazywanie przez stałą referencję zamiast przez wartość.

Pytający: Poprawka (dość duża rozbieżność w linach jakoś rzuciła się w oczy): • 31, 49 // dodatkowy konstruktor

Mariusz: [Warning] friend declaration 'std:: ostream& operator<<(std:: ostream&, Link<T>&)' declares a non−template function [−Wnon−template−friend] Wyskoczyło to ostrzeżenie Gdybym chciał zmieniać pozostałe funkcje to powywalać gettery i settery z tych funkcji i odwoływać się do adresów pól składowych klasy Wynika z tego że przydatność getterów i setterów jest dość ograniczona Gdyby chciał bawić się klasą zagnieżdzoną to przydałoby się wprowadzić iteratory, przeciążyć operator przypisania , napisać konstruktor kopiujący tylko czy nie będzie problemów z szablonami ? Za czasów Symfonii i Pasji Grębosza nie można było ich zagnieżdżać Z funkcji to może dopiszę insertBefore , przydałyby się takie jak SplitAfter , SplitBefore , Concat gdyby ktoś chciał się bawić np rekurencyjnym sortowaniem Usuwanie powtórzeń z posortowanej listy (tak właściwie wystarczyłoby wstawianie powtórzeń na koniec listy i zwracanie wskaźnika na ogon podlisty bez powtórzeń) mogłoby się przydać do algorytmu Grahama Jak przekształcić tę listę w listę cykliczną ? Niby następnik ogona to głowa a poprzednik głowy to ogon ale czy nie trzeba by było zmodyfikować funkcje tej listy

Dziadek Mróz: Lista cykliczna na chłopski rozum: first −> el −> el −> ... −> el −> last −> first

Dziadek Mróz: To dla jednokierunkowej, dla dwukierunkowej dla first idzie prev do last last <− first <− el <− ... <− el <− last first −> el −> ... −> el −> last −> first

Pytający: Ano moja zmiana tamtego "przyjaciela" faktycznie nie do końca była sensowna. Była to zmiana typu "na szybko, działa, więc jest ok" (co mnie teraz właśnie najbardziej dziwi, to brak jakiegokolwiek ostrzeżenia u mnie, pewnie kwestia kompilatora). Tu masz ładnie opisane różne możliwe podejścia: https://stackoverflow.com/a/4661372 Znaczy miałeś w swoim kodzie to podejście "ekstrawertyczne". U mnie miało być to drugie podejście "introwertyczne" (to bez inliningu), jednak nie dopisałem potrzebnych deklaracji poprzedzających (u mnie przecież działało...), tu poprawione (linie 15, 16): https://ideone.com/dfYBgw Jeśli chcesz pozmieniać funkcje na wersje z podwójnym wskaźnikami, to wtedy należy odwoływać się do adresów pól składowych. Jeśli operujesz zwykłymi wskaźnikami to nie jest to niezbędne, wystarczą kopie, ale wtedy nie obejdzie się bez rozważania przypadków typu: if (warunek) head = ... else tmp_wezel−>next= ... Co do przydatności tych getterów i setterów: nie zawierają w sobie żadnej logiki (w sensie np. nie sprawdzają czy zapisywana wartość jest dozwolona, spełnia jakieś warunki (przykładowo jeśli miałbyś pole z jakimś tam indeksem, to taki setter mógłby się upewniać, że wartość należy do jakiegoś tam przedziału/zakresu)). Poza tym czy użytkownik powinien mieć dostęp do pól takich jak next, prev itp. i móc zmieniać ich wartości? Raczej nie, to są szczegóły implementacyjne, o których użytkownik nie musi nic wiedzieć i lepiej, żeby nic nie mógł tam namieszać. Znowuż odwołam się do listy z biblioteki standardowej: https://en.cppreference.com/w/cpp/container/list przykładowo metody front(), back() zwracają referencje do wartości (T& lub const T&), nie do żadnych węzłów. Poza tym masz masę innych metod (w tym operatorów) i one właśnie stanowią interfejs użytkownika. Do tego iteratory, a wtedy możesz używać np. różnych standardowych algorytmów (sortowania, porównywania leksykograficznego z własnym komparatorem, znajdowania wartości, zliczania wystąpień i wiele innych): https://en.cppreference.com/w/cpp/header/algorithm . Co do zagnieżdżania, węzły wcale nie muszą być szablonami, a i tak będą rozróżnialne. Przecież przykładowo LinkedList<int>::Link i LinkedList<double>::Link to różne typy. Zatem powinno chyba wystarczyć: template<class T> LinkedList { class Link {...} ... } A jakbyś jednak chciał, żeby na zewnątrz tej klasy można było węzły traktować jako typu Link<T>, to można użyć "alias template": https://ideone.com/LiCs2k https://en.cppreference.com/w/cpp/language/type_alias A przy zamianie na listę cykliczną niektóre funkcje na pewno musiałbyś nieco zmodyfikować, przykładowo bez zmian takie wyszukiwanie (find()) by Ci się zapętliło dla niepustej listy bez wyszukiwanej wartości (bo szuka dopóki węzeł jest różny od nullptr i wartość w nim jest różna od poszukiwanej).

Mariusz: Używam gcc 6.3.0 , mam też ten pobrany z Code::Blocks IDE Bawiłem się jeszcze rekurencyjnym sortowaniem przez scalanie i oto co otrzymałem https://ideone.com/M2PEgW Ciekawe czy kod wymaga jakichś poprawek i czy można go jakoś uprościć