Löschen eines Elements in std::list konstant?

Ja, eigentlich ist es klar. Ich frage nur, weil ich jetzt schon mehrmals in Foren gelesen habe, dass insert und delete bei einer Liste immer konstant ist. hm

Jester

insert und delete ist konstant... Du mußt das entsprechende Listenelement (also einen Iterator darauf) aber schon in der Hand halten. Die Zeit die Du brauchst um den zu finden, kannst Du nicht insert/delete aufbrummen.

pumuckl

Das n-te Element zu löschen besteht eben aus zwei Schritten:

Das n-te Element finden (O(n))
Das gefundene Element löschen (O(1), wie überall gesagt wird)

Jester

Das find ich etwas unpräzise. Das n-te Element zu finden kann viel schneller gehen... je nach Kontex und welche weiteren Datenstrukturen noch so vorhanden sind. Da einfach mal so O(n) zu veranschlagen überschätzt die Komplexität häufig bei weitem.

pumuckl

Jester schrieb:

Das find ich etwas unpräzise. Das n-te Element zu finden kann viel schneller gehen... je nach Kontex und welche weiteren Datenstrukturen noch so vorhanden sind. Da einfach mal so O(n) zu veranschlagen überschätzt die Komplexität häufig bei weitem.

Im Durchschnitt, ohne irgendwelche Vorgaben, Sortierungen usw. ist ein std::list<>::find() doch O(n) oder irre ich mich da? Natürlich kann man in speziellen Fällen immer noch was rauskitzeln, nur wurde hier eine allgemeine Frage gestellt - und afaik ist O(n) da die ebenso allgemeine antwort.

volkard

Jester schrieb:

Das find ich etwas unpräzise. Das n-te Element zu finden kann viel schneller gehen... je nach Kontex und welche weiteren Datenstrukturen noch so vorhanden sind. Da einfach mal so O(n) zu veranschlagen überschätzt die Komplexität häufig bei weitem.

bei einer std::list ?

Nexus

pumuckl schrieb:

Im Durchschnitt, ohne irgendwelche Vorgaben, Sortierungen usw. ist ein std::list<>::find() doch O(n) oder irre ich mich da?

Seit wann hat std::list ein find() ?

Aber ich würde auch meinen, O(n) sei fürs Suchen in einer verketteten Liste gerechtfertigt. Wenn man stets alle Spezialfälle berücksichtigt, kann eben keine allgemeingültigen Komplexitätsangaben mehr machen.

Jester

Ich wollte lediglich anmerken, dass O(n) zwar richtig ist, aber eben keinesfalls scharf. Beispielsweise würde mit der Analyse bei so ziemlich allen Algorithmen bei denen ich je Listen benutzt habe so ein zusätzlicher Faktor n in die Laufzeit mit reinkommen. Mein Punkt ist lediglich, dass es häufig eben besser geht, indem man ein geschicktes Mapping von Elementen auf ListNodes ermöglicht (da ist std::list natürlich nicht gerade super für, aber es geht teilweise).

Konkret würde ich folgende Ansicht vertreten: entweder man schafft es effizient die richtige Stelle zum einfügen/löschen zu finden (sagen wir in konstanter oder logarithmischer Zeit) oder man sollte die liste wegwerfen und einen vector oder sowas nehmen.

pumuckl

Nexus schrieb:

pumuckl schrieb:

Im Durchschnitt, ohne irgendwelche Vorgaben, Sortierungen usw. ist ein std::list<>::find() doch O(n) oder irre ich mich da?

Seit wann hat std::list ein find() ?

Sry mein Fehler *Kopf->Tisch*
std::find<std::list<>::iterator,> wäre richtig bzw- nach den vom OT gegebenen Vorgaben (Liste, n-tes Element) std::advance<std::list<>::iterator,> was O(n) ist.

klugscheisser inc!