(Geschwindigkeits-)Problem mit ADT Liste



  • Simonmicro schrieb:

    @theta

    Könntest du hierzu bitte noch etwas genauer werden??

    Danke.

    testlist wird nicht ordentlich gelöscht - allerdings wäre es besser, gleich eine automatische Variable dafür zu benutzen.


  • Mod

    Simonmicro schrieb:

    @theta

    Könntest du hierzu bitte noch etwas genauer werden??

    Danke.

    So ungefähr überall. Bitte Basics anlesen. "Regel der großen Drei" wurde schon genannt, besser auch gleich noch "RAII", um mal allgemein die Philosophie zu verstehen, wie man Ressourcen fehlerfrei und narrensicher verwaltet, noch dazu mit viel weniger Aufwand als du es gerade betreibst.



  • Hallo nochmal,

    ich werde mir diese Konzepte versuchen aneignen, schließlich bin ich kein C++-Profi, und eventuell dann nochmal eine Version hier hochstellen.

    Bis dann!

    Simonmicro



  • Mir war ein wenig langweilig und deshalb hab ich zu erst mal versucht, das ganze so hinzubiegen, dass es korrekt ist. aber da hatte ich nach wenigen minuten schon zu viele baustellen gefunden und dachte, es geht schneller, das ganze neu zu bauen und dir da zu zeigen, wie man es richtig macht. (dass das genau so lang gedauert hat, ist mir erst beim ersten mal auf-die-uhr-gucken aufgefallen :/)

    klammern hab ich mal anders gesetzt, weil ich deine variante nicht mag; was aber nicht heißt, dass sie falsch ist

    ich nehm einfach mal das ganze zeug, was design-technisch keine funktionen der liste sein darf (getcontent, positionen, ...)

    template <typename Datatype>
    struct ADT_List
    {
      bool isEmpty();
      void insert(Datatype x);
      void print();
    
      void delEntry();
    private:
      struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry()
        {
          next = nullptr;
        }
      };
    
      Entry start_entry;
    };
    

    jetzt machen wir uns erst mal über grundsätzliche dinge gedanken:
    wir haben immer ein item in der liste "start_entry". wie behandeln wir das? wir brauchen trotzdem ne leere liste, also ignorieren wir start_entry.content einfach immer und degradieren es zum dummy.
    damit wissen wir jetzt, wie isEmpty aussieht: return start_entry.next == nullptr;

    außerdem kennen wir jetzt schon das grundgerüst von print:
    die ausgabe an sich habe ich mal nur mit print_zeugs angedeutet:

    {
      Entry* pos = &start_entry;
    
      pos = pos->next;
      while(pos != nullptr)
      {
        print_zeugs( pos );
        pos = pos->next;
      };
    }
    

    das kann man etwas schöner schreiben:

    {
      for( Entry* pos = start_entry.next; pos != nullptr; pos = pos->next )
      {
        print_zeugs( pos );
      }
    }
    

    also sieht unsere liste nun erst mal so aus:

    template <typename Datatype>
    struct ADT_List
    {
      bool isEmpty()
      {
        return start_entry.next == nullptr;
      }
    
      void insert(Datatype x);
      void print()
      {
        for( Entry* pos = start_entry.next; pos != nullptr; pos = pos->next )
        {
          print_zeugs( pos );
        }
      }
    
      void delEntry();
    
    private:
      struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry()
        {
          next = nullptr;
        }
      };
    
      Entry start_entry;
    };
    

    hier fällt schon auf, dass start_entry / Anf / startentry kein schöner name ist, weil nicht ersichtlich ist, dass es nur ein dummy ist.
    da mir die ausführungen hier dann doch zu lang sind, wie man da schön abhilfe schaffen kann, leben wir aber damit.

    nun, da ich dein positions-merker in ner liste falsch finde (womit ich nicht allein stehen sollte), bau ich mal nur nen push_back(also item am ende einfügen) statt richtigem insert

    void push_back(Datatype to_add)
    {
      Entry* last = /*darum kümmern wir uns später*/;
    
      last->next = new Entry();
      last->next->content = to_add;
    }
    

    und ein pop_back(also letztes item löschen) statt delEntry:

    void pop_back()
    {
      Entry* one_before_last = /*dito*/;
    
      delete one_before_last->next;
      one_before_last->next = nullptr;
    }
    

    jetzt fällt im push_back schon mal auf, dass in den beiden wesentlichen zeilen folgendes passiert:

    last->next = new Entry();
      //last->next = 0x123;
      //last->next->content = Datatype();
      //last->next->next = nullptr;
    
      last->next->content = to_add;
      //last->next = 0x123;
      //last->next->content = to_add;
      //last->next->next = nullptr;
    

    sieht irgendwie so aus, als ob man die zweite zeile auch in der ersten machen könnte, indem wir Entry nen zusätzlichen (oder besser gleich anderen) Konstruktor verpassen:

    struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry(Datatype value)
        {
          next = nullptr;
          content = value;
        }
      };
    

    [Anmerkung: Hier geschieht (im Prinzip) leider noch immer genau das gleiche, wie oben: für content wirst erst der Standard-Konstruktur aufgerufen und danach wird der Zuweisungsoperator aufgerufen. Wenn du das besser machen möchtest, google nach "C++ Initialisierungsliste"]

    Damit sieht unser push_back jetzt so aus:

    {
      Entry* last = /*...*/;
      last->next = new Entry( to_add );
    }
    

    Einziges Problem:
    ADT_list besitzt einen Member vom Typ Entry . Es existiert aber kein parameterloser Konstruktor mehr für Entry.
    Also entweder brauchen wir einen eigenen Konstruktor für die Liste, der start_entry = Entry( irgendwas ) setzt (wieder: -> Initialisierungsliste; diesmal ist diese zwingend notwendig.) oder der einfache Weg: default-Argument für Entry::Entry

    struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry(Datatype value = Datatype())
        {
          next = nullptr;
          content = value;
        }
      };
    

    mittlerweile haben wir ne ziemlich lauffähige liste, die aber leider bisher ziemlich eingeschränkten zugriff von außen hat:

    template <typename Datatype>
    struct ADT_List
    {
      bool isEmpty()
      {
        return start_entry.next == nullptr;
      }
    
      void push_back(Datatype x)
      {
        Entry* last = /* TODO */;
        last->next = new Entry( to_add );
      }
    
      void pop_back()
      {
        Entry* one_before_last = /* TODO */;
    
        delete one_before_last->next;
        one_before_last->next = nullptr;
      }
    
      void print()
      {
        for( Entry* pos = start_entry.next; pos != nullptr; pos = pos->next )
        {
          //print_zeugs( pos );
        }
      }
    
    private:
      struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry(Datatype value = Datatype())
        {
          next = nullptr;
          content = value;
        }
      };
    
      Entry start_entry;
    };
    

    jetzt muss man sich langsam entscheiden, wie gründlich man das ganze machen möchte, um herauszufinden, wie wir weiter vorgehen wollen.
    wir entscheiden uns mal dafür, Entry doch (wieder) public zu machen, und auch außerhalb damit zu arbeiten (-> google "Iterator" ggf. mit "Konzept")

    Wenn wir außerhalb auch Zugriff auf einzelne Elemente haben möchten, brauchen wir also insbesondere einen Weg, einen Verweis auf das erste sowie letzte Item zurückzugeben.
    Da in der Praxis das letzte Element einer Spanne schwieriger zu behandeln ist als das erste nach der dieser Spanne, entscheiden wir uns gleich dazu, nicht das letzte sondern das erste nicht mehr gültige Item (bzw einen Verweis darauf) nach außen zu geben.

    also haben wir zwei weitere Funktionen, die wir begin und end nennen werden.
    damit sieht unsere Liste jetzt so aus:

    template <typename Datatype>
    struct ADT_List
    {
      bool isEmpty()
      {
    /*ist zwar weiterhin korrekt:
        return start_entry.next == nullptr;
      aber nicht so aussagekräftig, wie:
    */
        return begin() == end();
      }
    
      void push_back(Datatype x)
      {
    //  Entry* last = /* TODO */;
    //wird erst mal zu:
    //->
        Entry* last = &start_entry;
    
        while( last->next != nullptr )
          last = last->next;
    //<-
    
        last->next = new Entry( to_add );
      }
    
      void pop_back()
      {
    //  Entry* one_before_last = /* TODO */;
    //wird erst mal (!) zu:
    //->
        Entry* one_before_last = &start_entry;
        while( one_before_last->next->next != nullptr )
          one_before_last = one_before_last->next;
    //<-
    
        delete one_before_last->next;
        one_before_last->next = nullptr;
      }
    
      void print()
      {
    //  for( Entry* pos = start_entry.next; pos != nullptr; pos = pos->next )
    //können wir mit unserer range viel schöner schreiben:
        for( Entry* pos = begin(); pos != end(); pos = pos->next )
        {
          //print_zeugs( pos );
        }
      }
    
      struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry(Datatype value = Datatype())
        {
          next = nullptr;
          content = value;
        }
      };
    
      Entry* begin()
      {
        return start_entry.next;
      }
    
      Entry* end()
      {
    //logisch:
    //->
        Entry* last = begin();
    
        while(last->next != nullptr)
          last = last->next;
    
        return last->next;
    //<-
    //wird zu
        return nullptr;
      }
    
    private:
      Entry start_entry;
    };
    

    machen wir uns mal ein paar gedanken:
    isEmpty(): wenn das erste item der liste gleich das erste item nach der liste ist, ist die liste leer. gut, ist also richtig. [Anmerkung: Die Liste wird mit dieser Funktion nicht verändert. -> google "const correctness"]

    zu push_back(): kann man natürlich auch wieder schöner schreiben:

    Entry* last;
        for( last = &start_entry; last->next != end(); last = last->next )
          ;
    
    //...
    

    das &start_entry stört (mich) zwar ein wenig, aber begin() können wir hier nicht verwenden (!leere liste!).

    beim pop_back fällt sofort auf, dass dort X->next->next steht ohne das wir zuvor jemals X->next auf 0 getestet haben.
    ist ja auch klar: eine liste, aus der das letzte element entfernt werden soll, braucht mindestens ein (X->next) element.
    [für das abfragen solcher logikfehler wird normalerweise assert() genutzt -> "C++ assertion"]

    unser print gibt natürlich noch immer nichts aus, weil der körper der for-schleife leer ist.
    aber das bekommst du schon hin.
    [man könnte jetzt hinterfragen, ob die print-funktion wirklich member-funktion der Liste sein muss]

    begin() ist auch klar und end() wird durch die kommentare klar.

    also alles bestens abgesehen davon, dass unsere liste den speicher nicht allein wieder frei gibt (-> "memory leak").
    Wir brauchen also einen Destruktor. Der ist selbsterklärend und im nächsten Stück Code dabei.

    (merkt, dass er sich verzettelt hat, weil zu gründlich erklärt^^)

    ich hab mal noch weitestgehend kommentarlos deine main-funktion angepasst und eine erase-funktion (analog zu deiner delEntry) spendiert, damit dein bsp funktioniert:

    #include <cassert>
    
    template <typename Datatype>
    struct ADT_List
    {
    	struct Entry;
    
    	bool isEmpty()
    	{
    		return begin() == end();
    	}
    
    	void push_back(Datatype to_add)
    	{
    		Entry* last = &start_entry;
    		{
    			for (; last->next != end(); last = last->next)
    				;
    		}
    
    		last->next = new Entry(to_add);
    	}
    
    	void pop_back()
    	{
    		assert(!isEmpty());
    		Entry* one_before_last = &start_entry;
    		{
    			for (; one_before_last->next->next != nullptr; one_before_last = one_before_last->next)
    				;
    		}
    
    		delete one_before_last->next;
    		one_before_last->next = nullptr;
    	}
    
    	Entry* /*next*/ erase(Entry* del_me)
    	{
    		assert(del_me != nullptr);
    
    		Entry* before_del = &start_entry;
    		{
    			for (; before_del->next != del_me; before_del = before_del->next)
    				assert(before_del != nullptr);
    		}
    
    		before_del->next = del_me->next;
    		delete del_me;
    
    		return before_del->next;
    	}
    
    	struct Entry
    	{
    		Datatype content;
    		Entry *next;
    
    		Entry(Datatype value = Datatype())
    		{
    			next = nullptr;
    			content = value;
    		}
    	};
    
    	Entry* begin()
    	{
    		return start_entry.next;
    	}
    
    	Entry* end()
    	{
    		return nullptr;
    	}
    
    	void clear()
    	{
    		while (!isEmpty())
    			pop_back();
    	}
    
    	~ADT_List()
    	{
    		clear();
    	}
    
    private:
    	Entry start_entry;
    };
    
    #include <iostream>
    #include <ctime>
    
    template<class T>
    void print_list( /*const*/ ADT_List<T>& the_list )
    {
    #if 1
    	the_list;
    #else
    	for (auto i(the_list.begin()), e(the_list.end()); i != e; i = i->next)
    		std::cout << i << "[ " << i->content << ", -> " << i->next << " ]\n";
    	std::cout << '\n';
    #endif
    }
    
    int main()
    {
    	int lsize = 50*1000;
    	int step_size = 1000;
    
    	using namespace std;
    
    	ADT_List<int> testlist;
    
    	cout << "Create list..." << endl;
    	clock_t t1 = clock();
    	for (int r = 0; r < lsize; r++)
    		testlist.push_back(r);
    	clock_t t2 = clock();
    	print_list(testlist);
    	int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    	cout << time << " ms" << endl;
    
    	cout << "Edit list..." << endl;
    	t1 = clock();
    	int step = 0;
    	for (auto i(begin(testlist)), e(end(testlist)); i != e; )
    	{
    		if (++step % step_size == 0)
    			i = testlist.erase(i);
    		else
    			i = i->next;
    	}
    
    	t2 = clock();
    	print_list(testlist);
    	time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    	cout << time << " ms" << endl;
    
    	cout << "Clear list..." << endl;
    	t1 = clock();
    	testlist.clear();
    	t2 = clock();
    	print_list(testlist);
    	time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    	cout << time << " ms" << endl;
    
    	cout << "cu\n";
    	cin.get();
    }
    

    compiler nickt es auch ab und es tut das, was es soll.

    push_back in O(n) ist zwar kacke, aber ansonsten tut es auch das, was man von einer liste erwartet.

    bb

    EDIT: bugfix in main-fkt.


  • Mod

    Da sind aber auch massive Fehler drin, sowohl vom Design her als auch von der technischen Umsetzung. Mach mal ein einfaches:

    ADT_List<int> testlist2 = testlist;
    

    rein, mach irgendwas damit, und siehe, wie das Kartenhaus zusammen bricht.



  • SeppJ schrieb:

    Da sind aber auch massive Fehler drin, sowohl vom Design her als auch von der technischen Umsetzung. Mach mal ein einfaches:

    ADT_List<int> testlist2 = testlist;
    

    rein, mach irgendwas damit, und siehe, wie das Kartenhaus zusammen bricht.

    copyctor sowie op= gabs auch zuvor nicht.
    Soll ich nen
    Entry(const Entry&) = delete; und
    Entry& operator=(const Entry&) = delete;

    reineditieren? 😛

    edit: op= rieneditiert, damit du nicht wieder kritisierst, ich hätte nur die hälfte gemacht.



  • Schau dir einfach mal std::unique_ptr an, dann hast du schon mindestens die Hälfte aller Fehler beseitigt.


  • Mod

    unskilled schrieb:

    copyctor sowie op= gabs auch zuvor nicht.

    Und das war falsch, dass es die nicht gab! Dein Code soll doch zeigen, wie es richtig geht, oder?

    Das entschuldigt aber immer noch nicht das leere Dummy-Element; die vielen Methoden mit linearer Laufzeit wo konstant ginge; quadratische Laufzeiten, wo auch linear ginge; und bestimmt noch viel mehr, denn so genau mag ich gar nicht mehr gucken.



  • Das entschuldigt aber immer noch nicht das leere Dummy-Element; die vielen Methoden mit linearer Laufzeit wo konstant ginge; quadratische Laufzeiten, wo auch linear ginge; und bestimmt noch viel mehr, denn so genau mag ich gar nicht mehr gucken.

    hindert dich doch keiner dran, das selbst zu tun.

    sind alles nur noch kleine ergänzungen; ich hatte aber keine zeit mehr und nicht das gefühl, dass es mit dem kenntnissstand des TOs vereinbar ist.



  • Fängt doch alles schon mit der Designentscheidung an, bei einer einfach verketteten Liste push_back und pop_back anzubieten statt der Funktionen push_front und pop_front, die beide O(1) wären.

    Nächste merkwürdige Design-Entscheidung: die erase-Funktion. Sie nimmt als Parameter und gibt als Returntyp ein Entry*. Entry ist aber ein Implementierungsdetail, warum soll man das außen kennen?

    Und push_back macht eine Kopie durch call by value und dann eine weitere beim Speichern?

    Nenene, das ist auch keine empfehlenswerte Lösung.


  • Mod

    unskilled schrieb:

    Das entschuldigt aber immer noch nicht das leere Dummy-Element; die vielen Methoden mit linearer Laufzeit wo konstant ginge; quadratische Laufzeiten, wo auch linear ginge; und bestimmt noch viel mehr, denn so genau mag ich gar nicht mehr gucken.

    hindert dich doch keiner dran, das selbst zu tun.

    Ja, die Tage mal, wenn ich Zeit habe. Irgendwas Schickes mit unique Pointern, das sich ganz von alleine verwaltet und man programmiert nur die Struktur 😋


  • Mod

    Irgendwie sieht das Ganze immer gleich aus...

    #include <utility>
    
    template <typename T>
    class adt_list {
    	struct node {
    		node* next;
    	};
    	struct data_node {
    		template <typename... U>
    		data_node(node* next, U&&... args) noexcept(noexcept(T{std::forward<U>(args)...}))
    			: base{next}, data(std::forward<U>(args)...)
    		{}
    		node base;
    		T data;
    	};
    	static T& data(node* p) noexcept { return reinterpret_cast<data_node*>(p)->data; }
    
    public:
    	// types
    	class iterator;
    	class const_iterator;
    	friend class iterator;
    	friend class const_iterator;
    	class iterator {
    		friend class adt_list;
    		friend class const_iterator;
    		explicit iterator(node* elem) noexcept : elem(elem) {}
    	public:
    		T& operator*() const noexcept { return data(elem); }
    		T* operator->() const noexcept { return &data(elem); }
    		iterator& operator++() noexcept { elem = elem->next; return *this; }
    		iterator operator++(int) noexcept { auto i = *this; ++*this; return i; }
    		friend bool operator==(iterator lhs, iterator rhs) noexcept { return lhs.elem == rhs.elem; }
    		friend bool operator!=(iterator lhs, iterator rhs) noexcept { return lhs.elem != rhs.elem; }
    	private:
    		node* elem;
    	};
    
    	class const_iterator {
    		friend class adt_list;
    		explicit const_iterator(node* elem) noexcept : elem(elem) {}
    	public:
    		const_iterator(iterator other) noexcept : elem(other.elem) {}
    		const T& operator*() const noexcept { return data(elem); }
    		const T* operator->() const noexcept { return &data(elem); }
    		const_iterator& operator++() noexcept { elem = elem->next; return *this; }
    		const_iterator operator++(int) noexcept { auto i = *this; ++*this; return i; }
    		friend bool operator==(const_iterator lhs, const_iterator rhs) noexcept { return lhs.elem == rhs.elem; }
    		friend bool operator!=(const_iterator lhs, const_iterator rhs) noexcept { return lhs.elem != rhs.elem; }
    	private:
    		node* elem;
    	};
    
    	// construct/copy/destroy
    	adt_list() noexcept : elems{nullptr} {}
    	adt_list(const adt_list& other);
    	adt_list(adt_list&& other) noexcept : elems(other.elems) { other.elems = nullptr; }
    	adt_list& operator=(adt_list rhs) noexcept { swap( rhs ); }
    	~adt_list() noexcept { clear(); }
    
    	void clear() noexcept {
    		while ( !empty() )
    			pop_front();
    	}
    	void swap(adt_list& other) noexcept { std::swap( elems, other.elems ); }
    	friend void swap(adt_list& lhs, adt_list& rhs) noexcept { lhs.swap( rhs ); }
    
    	// iterators
    	iterator begin() noexcept { return iterator{ elems.next }; }
    	const_iterator begin() const noexcept { return const_iterator{ elems.next }; }
    	const_iterator cbegin() const noexcept { return const_iterator{ elems.next }; }
    	iterator before_begin() noexcept { return iterator{ &elems }; }
    	const_iterator before_begin() const noexcept { return const_iterator{ &elems }; }
    	const_iterator cbefore_begin() const noexcept { return const_iterator{ &elems }; }
    	iterator end() noexcept { return iterator{ nullptr }; }
    	const_iterator end() const noexcept { return const_iterator{ nullptr }; }
    	const_iterator cend() const noexcept { return const_iterator{ nullptr }; }
    
    	// capacity
    	bool empty() const noexcept { return elems != nullptr; }
    	std::size_t size() const noexcept {
    		std::size_t res = 0;
    		auto p = elems.next;
    		while ( p ) {
    			++res;
    			p = p->next;
    		}
    		return res;
    	}
    
    	// access
    	T& front() noexcept { return *begin(); }
    	const T& front() const noexcept { return *begin(); }
    
    	// modifiers
    	template <typename... U>
    	iterator insert_after(const_iterator pos, U&&... args) {
    		return iterator{ pos.elem->next = &( new data_node{ pos.elem->next, std::forward<U>( args )... } )->base };
    	}
    	iterator erase_after(const_iterator pos) noexcept {
    		data_node* p = reinterpret_cast<data_node*>(pos.elem->next);
    		pos.elem->next = pos.elem->next->next;
    		delete p;
    		return iterator{ pos.elem };
    	}
    	template <typename... U>
    	void push_front(U&&... args) {
    		insert_after( before_begin(), std::forward<U>( args )... );
    	}
    	void pop_front() noexcept {
    		erase_after( before_begin() );
    	}
    private:
    	node elems;
    };
    
    #include <iostream>
    #include <ctime>
    
    template<class T>
    void print_list( const adt_list<T>& l )
    {
    #if 0
    	for ( auto i = l.begin(), end = l.end(); i != end; ) {
    		auto next = i;
    		std::cout << &*i << "[ " << *i << ", -> " << (++next==end?nullptr:&*next) << " ]\n";
    		i = next;
    	}
        std::cout << '\n';
    #endif
    }
    
    int main()
    {
    	int lsize = 100000000;
    	int step_size = 4;
    
    	using namespace std;
    
    	adt_list<int> testlist;
    
    	{
    		cout << "Create list..." << endl;
    		clock_t t1 = clock();
    
    		auto pos = testlist.before_begin();
    		for (int r = 0; r < lsize; r++) {
    			pos = testlist.insert_after( pos, r );
    		}
    		clock_t t2 = clock();
    		//print_list( testlist );
    		std::cout << "size: " << testlist.size() << '\n';
    		int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    		cout << time << " ms" << endl;
    	}
    
    	{
    		cout << "Edit list..." << endl;
    		clock_t t1 = clock();
    		int step = 0;
    		auto i = testlist.before_begin(), n = begin( testlist ), e = end( testlist );
    		//std::cout << &*i << "[ " << *i << ", -> " << (++n==e?nullptr:&*n) << " ]\n";
    		for ( ; n != e;  )
    		{
    			if ( ++step % step_size == 0 )
    				n = testlist.erase_after( i );
    			i = n++;
    		}
    		clock_t t2 = clock();
    		print_list( testlist );
    		std::cout << "size: " << testlist.size() << '\n';
    		int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    		cout << time << " ms" << endl;
    	}
    
    	{
    		cout << "Clear list..." << endl;
    		clock_t t1 = clock();
    		testlist.clear();
    		clock_t t2 = clock();
    		print_list( testlist );
    		std::cout << "size: " << testlist.size() << '\n';
    		int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    		cout << time << " ms" << endl;
    	}
    
    	cout << "cu\n";
    	cin.get();
    }
    

    SeppJ schrieb:

    Irgendwas Schickes mit unique Pointern, das sich ganz von alleine verwaltet und man programmiert nur die Struktur 😋

    std::unique_ptr als Strukturelemente einer verketteten Liste sind wahrscheinlich keine so gute Idee. Es dürfte schwierig sein, Stacküberläufe beim Löschen großer Listen zu vermeiden.



  • camper schrieb:

    std::unique_ptr als Strukturelemente einer verketteten Liste sind wahrscheinlich keine so gute Idee. Es dürfte schwierig sein, Stacküberläufe beim Löschen großer Listen zu vermeiden.

    Warum?
    Ich habe unlängst einen rudimentären Binärbaum basierend auf Unique_ptr implementiert. Ok, der wird nie "groß" werden, aber wenn ich da ein Problem übersehen haben sollte, würde mich das interessieren.

    Was mich schon seit dem ersten Entwurf vom TE stört, ist dieses Dummy Element. Warum nicht ein (unique_ptr) auf das erste Element der Liste?



  • Schlangenmensch schrieb:

    camper schrieb:

    std::unique_ptr als Strukturelemente einer verketteten Liste sind wahrscheinlich keine so gute Idee. Es dürfte schwierig sein, Stacküberläufe beim Löschen großer Listen zu vermeiden.

    Warum?

    Stell dir vor, du hast eine einfach verkettete Liste mit 100k Elementen. Nun lasse diese Liste out of scope gehen. Der Destruktor wird aufgerufen. Der Unique-ptr-Destruktor muss nun den Destruktor des Elementes rufen, aus das er zeigt. Dies ist aber wieder eine Node, die zum Zerstören erst einmal die Nachfolger deleten muss. Und so weiter. D.h. du hast dann 100k Destruktor-Calls auf dem Stack und BOOOM.

    Wenn du einen Binärbaum hattest, wird der nicht besonders tief gewesen sein. Denn die Tiefe ist hier das Problem, nicht die Gesamtanzahl Elemente.



  • jo; klasse - der TO wird anhand einer fertigen liste bestimmt gut lernen, es selbst zu bauen.
    wenn das ein wettbewerb im weitpinkeln ist, hättet ihr davor bescheid sagen müssen, dann hätte ich auch nur ne fertige liste hier rein copy&pasted...

    merkt ihr nicht, dass es bei jedem anfänger-thread am ende nur noch darum geht, die c++igste lösung zu posten und der TO jedes mal nach 5-6 beiträgen aufhören kann(sollte!) zu lesen?



  • wob schrieb:

    Stell dir vor, du hast eine einfach verkettete Liste mit 100k Elementen. Nun lasse diese Liste out of scope gehen. Der Destruktor wird aufgerufen. Der Unique-ptr-Destruktor muss nun den Destruktor des Elementes rufen, aus das er zeigt. Dies ist aber wieder eine Node, die zum Zerstören erst einmal die Nachfolger deleten muss. Und so weiter. D.h. du hast dann 100k Destruktor-Calls auf dem Stack und BOOOM.

    Klingt logisch. Aber das sollte man doch umgehen können, wenn ein roher "nicht besitzender" Zeiger auf das nächste Element zeigt und die "besitzenden" Unique_Ptr in einem vector speichert.



  • Bei der Regel der großen 3/5 kann man sich etwas Arbeit sparen durch die Benutzung von unique_ptr. Im Destruktor kann man die Rekursion auflösen, indem man die unique_ptr manuell löscht.

    ~adt_list()
    {
       while( head_ )
       {
          auto& tmp = head_->next;
    // Fix dank theta
    //      head_.release();
          head_.reset( nullptr );
          head_ = tmp;
       }
    }
    

    Ansonsten @camper 👍 👍 👍



  • DocShoe schrieb:

    Beim ser Regel der großen 3/5 kann man sich etwas Arbeit sparen durch die Benutzung von unique_ptr. Im Destruktor kann man die Rekursion auflösen, indem man die unique_ptr manuell löscht.

    ~adt_list()
    {
       while( head_ )
       {
          auto& tmp = head_->next;
          head_.release();
          head_ = tmp;
       }
    }
    

    Ansonsten @camper 👍 👍 👍

    Hier wird aber nicht gelöscht. 🙄



  • Ouch, ja. Ich benutze std::unique_ptr nicht, sondern die boost smart_ptr. Hab mich dann bei der Auswahl der Methode vergriffen 😉


  • Mod

    Schlangenmensch schrieb:

    Klingt logisch. Aber das sollte man doch umgehen können, wenn ein roher "nicht besitzender" Zeiger auf das nächste Element zeigt und die "besitzenden" Unique_Ptr in einem vector speichert.

    Dann löst du das durch den unique_ptr verursachte Problem¹ aber durch mehr Code und mehr Verwaltung, anstatt die wesentlich einfachere Lösung zu nehmen, keinen uniqu_ptr zu benutzen.

    ¹: Danke camper, dass er daran gedacht hat!


Anmelden zum Antworten