(Geschwindigkeits-)Problem mit ADT Liste

[SeppJ]

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.

[unskilled]

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.

[wob]

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.

[SeppJ]

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

[camper]

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.

[Schlangenmensch]

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?

[wob]

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.

[unskilled]

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?

[Schlangenmensch]

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.

[DocShoe]

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

[theta]

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.

[DocShoe]

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

[SeppJ]

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!