Array mit doppelt verketteter Liste

Werner Salomon

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 auf std::advance(list.begin(), index) zurückgreifen.

Wenn ich mir dein Problem so durchlese, sieht ein std::vector bzw. hier der std::vector<std::vector> für deine Aufgabe besser geeignet zu sein. Zugriffe sind dann ganz intuitiv mit data[x][y] möglich.

@Werner: Warum musst du unbedingt ein Zeiger auf std::list<T> zurückgeben und keine Referenz?

Werner Salomon

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.

hustbaer

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?

Vicious Falcon

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 ).

Nexus

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.

Werner Salomon

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

hustbaer

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 [][].

Nexus

Zumindest von meiner Seite sollte das kein Vorwurf sein, mehr ein Hinweis.

Und gegen rohe Arrays trete ich andauernd ein!
Ich weise oft auf std::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".