Das Problem mit den Listen

Halli Hallo Forum,

ich bin gerada dabei an einem list-Container zu verzweifeln.
Mir fehlt eine Funktion/ein Operator wie at oder [] beim vector-Container...

Muss ich wirklich in einer beliebig langen Liste ständig Iteratoren inkrementieren um nur einen Wert aus der Liste auszulesen?
Funktioniert hier denn gar nichts wie etwa sowas?:

list<int>::iterator it = int_list.begin() + 3;

Nexus

Nein, Random Access ist bei einer Liste nicht möglich. Wenn du ihn brauchst, nimmst du eben einen Container, der ihn unterstützt.

Was du aber machen kannst, ist std::advance() einzusetzen - nimm dann aber schlechte Performance in Kauf.

drakon

Die Frage deutet auf den falschen Einsatz des Containers. Listen sind dazu du, wenn man viel anfügt/löscht. Und z.B std::vector ist dazu da, wenn man genau diesen Zugriff braucht. Wenn du beides brauchst, kannst du dir mal die deque anschauen.
Schaue, welche Anforderung der Container erfüllen muss und dann wähle den richtigen davon aus.

Hier gibt es eine gute Entscheidungshilfe:
http://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container

Hi drakon,

die Grafik ist sehr hilfreich.
Ich komme dabei auf deque.
Allerdings vermisse ich da schon sehr das splice() von list
gibt es eine möglichkeit das bei deques nachzuahmen?

Nexus

Listenproblem schrieb:

Allerdings vermisse ich da schon sehr das splice() von list
gibt es eine möglichkeit das bei deques nachzuahmen?

Du kannst dir eine globale Funktion dafür schreiben. Zum Beispiel so:

template <typename Container>
void splice(Container& Source, typename Container::iterator SrcBegin, typename Container::iterator SrcEnd,
	Container& Dest, typename Container::iterator DstPosition)
{
	Dest.insert(DstPosition, SrcBegin, SrcEnd);
	Source.erase(SrcBegin, SrcEnd);
}

Hat jetzt zwar nicht genau die gleiche Schnittstelle wie std::list::splice() , aber das lässt sich leicht anpassen. Diese Version scheint mir sowieso intuitiver... Natürlich kann man noch viel mehr machen, zum Beispiel als Quelle und Ziel unterschiedliche Typen ermöglichen, mehr Überladungen bereitstellen, und so weiter. Aber das überlass ich dir.

Wichtig: Die Funktionalität ist natürlich nicht ganz gleich wie bei einer Liste. Hier kommt es zu Kopien und Zerstörungen, während bei der Liste nur Zeiger umgehängt werden. Zudem kann es in gewissen Containern wie std::vector recht ineffizient sein, in der Mitte einzufügen.

Danke dir Nexus

Darf ich trotzdem mal fragen wie ineffizient das ganze wirklich ist?
Zeigt sich das dann bei mehreren tausend Elementen oder bereits ab einigen zig Elementen?

Mein Container wird meiner meinung nach kaum über 100 Elemente hinauswachsen...

drakon

Das wird bei so wenigen Elementen kaum etwas ausmachen. Merken tut man die Differenzen der Container afaik erst ab ein paar Tausend Elementen. (Was aber kein Grund ist nicht die dafür gedachten Container zu nehmen).

Nexus

Wenn dir die Funktionalität wichtig ist, kannst du die Ineffektivität in Kauf nehmen. Bei 100 Elementen brauchst du dir nicht im Entferntesten Gedanken zu machen, das geht so extrem schnell. Bei 10 Millionen sähe es dann wieder anders aus...

Aber damit du trotzdem weisst, was ich gemeint habe und es auch in Fällen, in denen es wirklich wichtig ist, richtig anwendest, will ich es erklären. Ein std::vector ist intern wie ein Array aufgebaut, die Elemente liegen hintereinander im Speicher. Sagen wir, du hast 20000 Elemente in diesem Array und willst nun die Elemente 25-130 löschen bzw. dort einfügen. Nun müssen alle nachfolgenden Elemente umkopiert werden. Je mehr Elemente vorhanden sind, desto länger dauert das. Bei std::deque ist das Ganze weniger kritisch, da dieser Container aus mehreren Teilarrays aufgebaut ist und so normalerweise nicht die ganze Sequenz verschoben werden muss.