Array mit doppelt verketteter Liste
-
Hallo,
ich bin leider ein ziemlich anfänger in C++ habe jedoch ein ziemlich großes Problem für mich.
Ich bräuchte ein Array mit N x M Feldern in dem jeweils eine eigene doppelt verkettete Liste ist.
Kann mir dabei vlt jemand helfen ich würde mich tierisch freuenmfg Koni
-
std::liststd::list
-
Wenn du ein bischen mehr dazu schreiben könntest wäre mir echt geholfen.
Vlt noch ein bischen mehr zu meinem Problem Ich berechne die Größe des Arrays erst und möchte dann die spezifische Liste direkt durch die angabe der Zeile und Spalte im Array ansprechen können.
danke Konstantin
-
an Deiner Stelle würde ich das ganze in eine Klasse fassen .. etwa so
#include <list> #include <vector> template< typename T > class ArrayNM { public: ArrayNM( std::size_t n, std::size_t m ) : m_m( m ) , m_data( n * m ) {} std::list< T >* operator[]( std::size_t i ) { return &m_data[ i * m_m ]; } private: std::size_t m_m; std::vector< std::list< T > > m_data; };
Du hast den Typ in der Liste nicht genannt, daher das Template.
Die Anwendung, etwa von einer Liste von double, sähe dann so aus
ArrayNM< double > list_arr( 3, 4 ); list_arr[2][1].push_back( 3.14 );
Gruß
Werner
-
Weisst du überhaupt was eine doppelt verkettete Liste ist? Du kannst in konstanter Zeit Elemente hinzufügen und verschieben, aber das Ansprechen eines Elements an einem bestimmten Index ist extrem langsam - in linearer Zeit - weshalb die
std::list
keine solchen Zugriffe per[]
-Operator zulässt.
Wenn du so etwas dennoch machen willst, und das ist bei einer doppelt verketteten Liste nicht zu empfehlen, dann musst du aufstd::advance(list.begin(), index)
zurückgreifen.Wenn ich mir dein Problem so durchlese, sieht ein
std::vector
bzw. hier derstd::vector<std::vector>
für deine Aufgabe besser geeignet zu sein. Zugriffe sind dann ganz intuitiv mitdata[x][y]
möglich.@Werner: Warum musst du unbedingt ein Zeiger auf
std::list<T>
zurückgeben und keine Referenz?
-
stl schrieb:
@Werner: Warum musst du unbedingt ein Zeiger auf
std::list<T>
zurückgeben und keine Referenz?weil ansonsten Zeile 2 im zweiten Listing meines Postings nicht funktionieren würde.
Werner Salomon schrieb:
ArrayNM< double > list_arr( 3, 4 ); list_arr[2][1].push_back( 3.14 ); // <=== deswegen muss ArrayNM::operator[] einen Zeiger liefern
-
Achso, erst jetzt habe ich die Frage richtig verstanden.
-
Werner Salomon schrieb:
stl schrieb:
@Werner: Warum musst du unbedingt ein Zeiger auf
std::list<T>
zurückgeben und keine Referenz?weil ansonsten Zeile 2 im zweiten Listing meines Postings nicht funktionieren würde.
Werner Salomon schrieb:
ArrayNM< double > list_arr( 3, 4 ); list_arr[2][1].push_back( 3.14 ); // <=== deswegen muss ArrayNM::operator[] einen Zeiger liefern
Tu dir selbst, der Welt, und uns einen Gefallen, und gib statt dessen einen Proxy zurück.
Der Zeiger-Trick ist zum weinen.
-
wenn da ein pointer zurückkommt müsste es dann nicht
list_arr[2][1]->push_back( 3.14 );
sein?@hustbaer: magst du das mit dem proxy ausführen?
-
Wäre es nicht noch besser, in der Klasse einen
std::vector<T> Arr;
zu deklarieren? Dann könnte sich der Anwender selber einen Container auswählen
ArrayNM<std::vector<int> >myarr(xdim,ydim);
Und auf Elemente könnte dann direkt (bei obiger Deklaration) mit
myarr[x][y][z]
zugegriffen werden.
Schnell getestet mit Codepad (auch mit Zeigerrückgabe :p ).
-
hustbaer schrieb:
Tu dir selbst, der Welt, und uns einen Gefallen, und gib statt dessen einen Proxy zurück.
Der Zeiger-Trick ist zum weinen.Da muss ich zustimmen, alleine schon weil man Index-Fehler mit
assert
abfangen könnte.dead=cat+curiosity schrieb:
wenn da ein pointer zurückkommt müsste es dann nicht
list_arr[2][1]->push_back( 3.14 );
sein?Nein, da
operator[]
bereits dereferenziert.dead=cat+curiosity schrieb:
@hustbaer: magst du das mit dem proxy ausführen?
Als Proxy meint er eine kleine Klasse, die nur dazu da ist, den zweiten Index-Operator zu ermöglichen. Ein Objekt dieser Klasse muss vom ersten
operator[]
zurückgegeben werden.
-
Nexus schrieb:
hustbaer schrieb:
Tu dir selbst, der Welt, und uns einen Gefallen, und gib statt dessen einen Proxy zurück.
Der Zeiger-Trick ist zum weinen.Da muss ich zustimmen, alleine schon weil man Index-Fehler mit
assert
abfangen könnte.Ich glaub' hier wird mit zweierlei Mass gemessen oder hätte einer von Euch beiden es bemängelt, wenn ich ein schlichtes
std::list<double> arr[N][M];
vorgeschlagen hätte.
Klar ist ein Proxy eine gute Idee; aber die Entrüstung finde ich unangemessen . Das ist schon lustig; in der Vergangenheit bin ich für sowas wie einen Proxy schon gescholten worden; das sei für Anfänger zu kompliziert.
Gruß
Werner
-
Ja ist/war vermutlich übertrieben.
Aber ich finde den Zeiger-Trick echt ...Sagen wir mal ich würde sowas einem Anfänger nicht hinwerfen, am Ende verwendet er es dann noch.
Dann lieber gleich ohne fancy-shmancy [][].
-
Zumindest von meiner Seite sollte das kein Vorwurf sein, mehr ein Hinweis.
Und gegen rohe Arrays trete ich andauernd ein!
Ich weise oft aufstd::tr1::array
hin. Bei gewissen Anfängern ist es vielleicht auch nicht angebracht. Oder umso mehr, je nach Philosophie.Hier ist der Zeiger eben so ein Zwischending. Halt nach dem Motto "entweder nur ein einfaches Array oder gleich richtig".