Frage zu std::list



  • Ich hab mir hier -> http://www.cplusplus.com/reference/stl/list/ gerade mal den Artikel zu std::list durchgelesen aber ein paar Sachen nicht richtig verstanden.

    List containers are implemented as doubly-linked lists;

    - Was ist eine doppelt verlinkte Liste?

    Doubly linked lists can store each of the elements they contain in different and unrelated storage locations.

    - Was sind beziehungslose storage locations?

    std::list sieht im moment für mich so aus wie std::vector
    Naja, außer das ich bei std::list folgendes nicht machen kann:

    cout<<mylist[0];
    

    das mag der Compiler nicht.

    #include <iostream>
    #include <list>
    using namespace std;
    
    int main()
    {
    list<int> mylist;
    list<int>::iterator it;
    
    mylist.push_back(1);
    mylist.push_back(2);
    mylist.push_back(3);
    
    it = mylist.begin();
    cout<<  *it << endl;
    
    cout<<mylist[0]<<endl; // 'operator+' ist im Typ 'list<int,allocator<int> >' für Argumente des Typs 'int' nicht implementiert
    return 0;
    }
    




  • Jeder Knoten entählt einen Zeiger auf seinen Vorgänger und Nachfolger. Bei einer einfach verketteten Liste wäre es nur der Vorgänger.

    Was sind beziehungslose storage locations?

    Bei einem Array lägen alle Elemente normalerweise hintereinander im Speicher, bei einer Liste (nicht nur bei doppelten, auch bei Bäumen u.ä.) liegen die Elemente irgendwo im Speicher und die Liste wird dadurch verkettet, dass jedes Element wie schon gesagt Zeiger auf Vorgänger bzw. Nachfolger enthält.
    Grob gesagt hat die Liste dort, wo das Array die einzelnen Elemente hat ihre Knoten.

    das mag der Compiler nicht.

    Nein, Listen/Bäume implementieren keinen sog. random-Access-Zugriff. Eine Liste hat auch von der implementierung wenig mit einem Array zu tun. Aber das zu erklären dauert hier zu lange, guck dir den Wikipedia Artikel an.
    Bei Fragen kannste ja immernoch fragen.



  • Edit: bei einer einfachen wäre es nur der Nachfolger.



  • Ungefaehr so saehe eine minimale Implementierung einer verketteten Liste aus:

    struct Liste {
        Liste* Naechste;
    };
    

    Eine doppelt-verkettete Liste:

    struct Liste {
        Liste* Naechste;
        Liste* Letzte;
    };
    

    Einzelne Elemente mit dem Indexoperator [] aufzurufen ist schiwerig, da man alle Elemente durchlaufen muss, bis man das gesuchte Element findet. Daher mag das dein Compiler auch nicht. 🙂
    Moechte man z.B. das dritte Elemente einer Liste aufrufen, muesste man sowas machen:

    Liste* Dritte = Erste->Naechste->Naechste;
    

    Ein Vector hingegen ist nur eine Abstraktion von einem einfachen Array mit dem Vorteil, dass sich der Benutzer nicht mehr um den Speichermanagment kuemmern muss.


Log in to reply