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 freuen

    mfg 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 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?



  • 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 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".


Log in to reply