Liste in C++

Athar

Ich dachte, man könnte da etwas mit unions und placement new machen, aber Referenzen sind wirklich eisenhart - sie lassen sich gar nicht erst in eine union stecken.

SeppJ

Da ich das ganze ganz lustig fand ist hier zumindest mal ein Ansatz:

#include<iostream>

struct ref_list
{
  int data;
  ref_list & next;
  ref_list(unsigned int i): next((i>0) ? (*(new ref_list(i-1))):(*this)), data(i) {}

};

int main()
{
  ref_list foo(3);
  std::cout << foo.data << foo.next.data << foo.next.next.data << foo.next.next.next.data << foo.next.next.next.next.data << std::endl;
}

Es sollte leicht möglich sein, der Liste bei ihrer Erstellung auch vernünftige Daten mitzugeben anstatt dem langweiligen Durchzählen das ich hier benutzt habe. Ein Iterator sollte sich auch schreiben lassen. Und dann hat man eine Liste konstanter Länge, was natürlich eine sehr sinnvolle Anwendung für eine verkettete Liste ist . Aber nett zu sehen, dass so etwas überhaupt geht.

berniebutt

Alles was du in C gemacht hast, kannst du in C++ unverändert beibehalten und weiter so machen. Nur weil du jetzt C++ einsetzen willst, brauchst du nichts grundlegend anderes zu suchen. Effektiver wird es auch nicht. Manchmal sparst du gegenüber reinem C etwas Programmieraufwand oder gewinnst mehr Sicherheit, mehr nicht. Wo sich das lohnt, musst du selbst herausfinden. :p

ipsec

berniebutt schrieb:

Alles was du in C gemacht hast, kannst du in C++ unverändert beibehalten und weiter so machen. Nur weil du jetzt C++ einsetzen willst, brauchst du nichts grundlegend anderes zu suchen. Effektiver wird es auch nicht. Manchmal sparst du gegenüber reinem C etwas Programmieraufwand oder gewinnst mehr Sicherheit, mehr nicht. Wo sich das lohnt, musst du selbst herausfinden. :p

Das stimmt zwar prinzipiell, allerdings sollte man noch hinzufügen, dass man das nicht zum Anlass nehmen sollte, alle bekannten Programmiertechniken aus C in C++ weiterzuverwenden, ohne sich nach Alternativen umzuschauen.
C++ bietet für viele Konstrukte wesentlich abstraktere und effizientere (lies: wartbarerer, lesbarere, sicherere) Ausdrucksmöglichkeiten als C (schönes Beispiel ist RAII). Wenn man diese Möglichkeiten ignoriert und nur seine Algorithmus in Klassen packt, landet man bei "C mit Klassen", was hier im Forum oft (und zu Recht) als kein guter C++-Stil bezeichnet wird.

Um beim Beispiel zu bleiben: Die C++-Standardbibliothek bietet mit std::list eine performante, generische, sichere Implemetierung einer verketteten Liste, die effizient den Speicher selbst verwaltet und damit mögliche Fehlerquellen wie händische Allokationen vermeidet.
Außer zu Übungszwecken gibt es deswegen in einem Großteil der Fälle in C++ keinen Grund, eine Liste selbst zu implementieren. Neben möglichen Fehlerrisiken sowohl bei Implementierung als auch bei Nutzung wird man in eigentlich allen Fällen gegenüber std::list keinerlei Performanceverbesserungen haben.

ipsec

Ich habe mal SeppJs Idee verfeinert und eine Möglichkeit für eine Referenz-Liste gefunden, der man dynamisch zur Laufzeit Elemente hinzufügen kann.
Das Handling ist allerdings ein Krampf und möglich wird das überhaupt erst durch einen Hack über placement new, der wahrscheinlich nicht standardkonform ist. Kurzum: eine nette akademische Übung, aber in der Praxis eigentlich unbrauchbar.

Wie dem auch sei, der zu verfeinernde Ansatz:

#include<iostream>

class ref_list
{
	static ref_list* really_end;
	ref_list* end;

public:

	int data;
	ref_list& next;

	ref_list(int d, ref_list& n) : data(d), end(really_end), next(n) {}
	ref_list(int d) : data(d), end(new ref_list(0, *really_end)), next(*end) {}

	void push_back(int data)
	{
		if(&next != end)
			next.push_back(data);
		else
		{
			end = new ref_list(0, *ref_list::really_end);
			new (&next) ref_list(data);
		}
	}
};

ref_list* ref_list::really_end = new ref_list(0, *ref_list::really_end);  // Keine Ahnung, ob sowas möglich ist, aber es scheint zu funktionieren (VS 2008)

int main()
{
	ref_list foo(0);
	foo.push_back(1);
	foo.push_back(2);
	foo.push_back(3);
	std::cout << foo.data << foo.next.data << foo.next.next.data << foo.next.next.next.data <<
		foo.next.next.next.next.data << foo.next.next.next.next.next.data << std::endl;
}

// Ausgabe: 012300

berniebutt

ipsec schrieb:

Das stimmt zwar prinzipiell, allerdings sollte man noch hinzufügen, dass man das nicht zum Anlass nehmen sollte, alle bekannten Programmiertechniken aus C in C++ weiterzuverwenden, ohne sich nach Alternativen umzuschauen ....

Das stimmt vollkommen! Ist aber für Umsteiger von C nach C++ ein Lernprozess. Man muss eben verstehen und ausprobieren, was die erweiterten Techniken von C++ an vereinfachter Programmierung und mehr Sicherheit bieten. Und dann sollte man es auch nutzen! 'C mit Klassen' ist für Umsteiger aber schon mal ein guter Einstieg. Um beim Beispiel mit Listen zu bleiben, handelt es sich um vorbereitete Klassen, die man einfach verwenden kann und die mehr bieten als man in C selbst oder nur mit grossem Aufwand hätte realisieren können. :p

Jeder Compiler ist eine Sammlung von Werkzeugen zur Programmierung. Ich sträube mich dagegen, jedes bessere Werkzeug auch einsetzen zu müssen. Wenn dies die Entwickler bei der Einführung von C++ mit einem Bruch zum alten C gemacht hätten, wären nur wenige seinerzeit auf C++ umgestiegen.

Ich möchte jetzt keine neue Diskussion C versus C++. Die hatten wir hier schon zur Genüge!

Tachyon

Studentxyz schrieb:

Hi

in C implementiert man Listen mit Pointern. Macht man das in C++ auch oder benutzt man hier Referenzen?

Man implementiert i.d.R. in C++ gar nichts selbst, sondern benutzt std::list .

volkard

Tachyon schrieb:

Studentxyz schrieb:

Hi

in C implementiert man Listen mit Pointern. Macht man das in C++ auch oder benutzt man hier Referenzen?

Man implementiert i.d.R. in C++ gar nichts selbst, sondern benutzt std::list .

Naja, hängt davon ab, was man macht. Man benutzt i.d.R nicht std::list, sondern std::vector oder std::queue. Oder gleich Datenbenaken. Oder eigene Listen. Also std::list eigentlich nicht.
Mal eine Liste zu schreiben, ist sicherlich eine gute Übung zum Umgang mit Zeigern/Referenzen/Handles/Verweisen.

knivil

Liste fuer Referenzen: Wird ein Wert veraendert, so wird nicht der Dateninhalt kopiert oder mit placement new ersetzt, sonder man konstruiert ein neues Listenelement (Referenz ueber Initialisierungsliste setzen) und fuegt es an der entsprechenden Stellen ein. So aehnlich wird es in funktionalen Sprachen gemacht.

Man implementiert i.d.R. in C++ gar nichts selbst, sondern benutzt std::list .. Man benutzt i.d.R nicht std::list, sondern std::vector oder std::queue

Was ihr so fuer Regeln habt, viel zu viele fuer meinen Geschmack.

berniebutt

knivil schrieb:

Was ihr so fuer Regeln habt, viel zu viele fuer meinen Geschmack.

Ich kenne eigentlich nur eine Regel: 'Schnell, sicher, effizient, und leicht wartbar eine konkrete Zielsetzung realisieren!' Aber genau da unterscheiden sich manchmal die Denkweisen und damit die Programmierstile. :p