std::list

Hallo,

ich würde gerne eine doppelt verkettete LIste benutzen. Wie wird denn verfahren wenn ein element umgehängt werden muss z.B. von position 4 auf position 0?
Wird dann teuer umhergespeichert oder geht das schnell weil nur pointer umgehängt werden?

Kann man auch auf willkürliche Positionen einfügen udn nicht nur am anfang oder ende?

BorisDieKlinge

das ist der vorteil von eine Liste bzw. std::list! Egal wo eingefügt wird vorne, hinten, mitte ist gleich viel aufwand. beim vertauschen von eleemten wird das element nicht umkopiert, sodner nur die position also die pointer kontexte vertauscht.

ok danke -

ich habe im Moment ein iterator problem:

warum kann ich folgende schleife nicht kompilieren:

for(std::list< std::pair< ND, MY_DATA<T> > >::iterator pos = my_lst.begin(); pos != my_lst.end(); pos++)

ND ist einfach nur ein umbenannter Typ, und MY_DATA ein templatebasiertes struct...

Mein Compiler schreit mit
error: expected `;' before 'pos'

Nexus

Hast du die For-Schleife in einem Funktionstemplate, in dem der Templatetyp T angegeben wurde? Weil T von MY_DATA ist sonst unbekannt...

Das Thema hatten wir schon mal und steht auch z.B. in Effektiv C++ drin: du mußt ein typename vorsetzen:

for(typename std::list< std::pair< ND, MY_DATA<T> > >::iterator pos = my_lst.begin(); pos != my_lst.end(); pos++)

Hoffe das funzt... sonst wirds peinlich für mich.

ja mit typename gehts - ihr habt natürlich recht danke euch

und noch ne frage:

wenn ich ein element irgendwo in der mitte ganz an den anfang stellen will und die restlichen einfach nur um eins weiterschieben will - muss ich dazu wirklich erst die daten des elements extrahieren, dann das element löschen und dann vorne einfügen?

oder gibt es was eleganteres wie eine art make_first ?

Nexus

Du könntest standardmässig zuerst erase() und dann insert() oder push_front() zu verwenden. Alternativ nützt dir auch splice() , schau doch mal hier nach.

Aber das sollte von der Performance her nicht schlimm sein...

Jo ok danke.
Nächste frage

template <class T>  bool 
AAA<T>::In_AAA(const Key key)
{      
    struct DATA<T> data;
    typename std::list< std::pair< Key, DATA<T> > >::iterator pos;

    for(pos = m_c.begin(); pos != m_c.end(); ++pos) 
    {
        data = *pos;
        if (key == data.first)
        {
            m_found = *pos;
            return true;    
        }
    }

    return false;
}

warum kann ich denn nicht den gefundenen iterator zuweisen? Geht das nicht dass ich praktisch das element zuweise wo mir *pos hinzeigt?
oder müsste ich eine vollständige Kopie anlegen?

Braunstein

Was geht denn bei dir nicht und was willst du erreichen? Warum kopierst du dein Datenelement vor dem Vergleich? Was ist m_found?
So viele Fragen.