Iterator vs. normale Schleifen

groovemaster

Phoemuex schrieb:

@ Falsche Antwort: Das spricht dann doch aber für meine Mehtode

Nein, eben nicht. Erstmal ist hier int für Index fehlplatziert. Und eine Liste mit einem Iterator durchzugehen ist im Normalfall performanter als mit einem Index. Ua gibt es ja genau dafür Iteratoren, um das ganze unabhängig von der Implementierung zu abstrahieren.

Ponto

Phoemuex schrieb:

Mir ist gerade noch etwas eingefallen. Gibt es auch bei list eine Funktion list::size() oder nicht? Sonst wäre das bei listen ja echt sinvoller.

list hat auch einen size() member. Dieser ist aber oft in O(n) implementiert. Er zählt einfach bei jedem Aufruf alle Elemente in der Liste.

DEvent

deswegen ist doch da der nachteil bei der normalen schleife. da muss jedesmal size() aufgerufen werden.

finix

Phoemuex schrieb:

@ Falsche Antwort: Das spricht dann doch aber für meine Mehtode, bei der anderen muss man dann ja die iterator-Deklaration anpassen.

Wenn du wirklich nicht weißt ob vector/list/was_auch_immer:

typedef vector<int> bazcontainer;

// ...

bazcontainer foo;

// ...

for(bazcontainer::iterator iter = foo.begin(); iter!= foo.end(); ++iter) {
  cout << *iter << endl;
}

// wird zu (fuer bazcontainer == list<int> || provides_iterators(bazcontainer))

for(bazcontainer::iterator iter = foo.begin(); iter!= foo.end(); ++iter) {
  cout << *iter << endl;
}

Walli

DEvent schrieb:

deswegen ist doch da der nachteil bei der normalen schleife. da muss jedesmal size() aufgerufen werden.

Genau, es wäre viel zu schwierig den Wert vorher einmal zu berechnen...

for(site_t i = 0, end = v.size(); i != end; ++i)
  foo(v[i]);

evilissimo

Phoemuex schrieb:

Mir ist gerade noch etwas eingefallen. Gibt es auch bei list eine Funktion list::size() oder nicht? Sonst wäre das bei listen ja echt sinvoller.

@eViLiSSiMo: Man kann ja einfach eine Variable nehmen, in die man foo.size() schreibt. Geht allerdings nicht, wenn man die Größe des Vektors in der Schleife verändert.

Danke schonmal

Felix

Es gibt imo nur 1 Variante wo dies vorkommt. und das ist das löschen von bestimmten elementen.
Und dies ist auch noch nur mit iteratoren möglich.
Wenn du nun einen ganzen Bereich löschen willst dann wärst du schön dumm das selbst in ner schleife zu machen da es ne schöne vector methode dafür gibt, nennt sich erase(iterator start , iterator end)
und für alle elemente noch besser : clear()

MfG

Jetzt möchte ich gerne mal sehen, wie du

std::list<int> foo;

for(int i = 0; i < foo.size(); ++i)
  do_something_with(foo[i]);

kompilieren willst. std::list hat keinen operator[], Iteratoren dagegen haben alle STL-container. std::vector ist an der Stelle ein Sonderfall, weils als drop-in-replacement für arrays gedacht ist.

Besonders deutlich wird das bei templates, zum Beispiel:

template<typename container_t>
void print_container(container_t const &cont) {
  for(container_t::const_iterator i = cont.begin(); i != cont.end(); ++cont)
    std::cout << *i << std::endl;
}

// ...

std::list<int> foo;
std::vector<int> bar;

// ...

print_container(foo);
print_container(bar);

DEvent

Walli schrieb:

DEvent schrieb:

deswegen ist doch da der nachteil bei der normalen schleife. da muss jedesmal size() aufgerufen werden.

Genau, es wäre viel zu schwierig den Wert vorher einmal zu berechnen...
for(site_t i = 0, end = v.size(); i != end; ++i)
  foo(v[i]);

klar kann man dass, es ging aber um die schleife, die am anfang geposted wurde.

phlox81

eViLiSSiMo schrieb:

z.b. der ständige aufruf von .size()
//Edit
und in der ersten variante wird performance durch den ständigen aufruf von
.end() verschwendet.

Sollte ein guter Compiler das heute nicht wegoptimieren können ?
Oder muss man jetzt vorher immer eine end variable erstellen ??

Devil

evilissimo

@devil81

Nicht alles ist so vorhersehbar und deswegen weg optimierbar.
Aber wenn es auf Geschwindigkeit ankommt, würde ich von std::vector<> ab raten.
Da kann ne eigene Problemoptimierte Variante evtl. viel besser sein.

MfG

Wenns um Geschwindigkeit geht, ist gerade bei vector in den meisten Implementierungen die Iterator-Variante sinnvoller. Meistens ist da std::vector<t>::iterator sowieso nur ein t*.

Was size() angeht, vector und alle anderen STL-Container sind templates, das heißt, der Inhalt von size() ist vorher bekannt und in aller Regel dermaßen trivial, dass ein vernünftiger Compiler den Kram inlinen kann. Das selbe gilt auch für begin() und end().

finix

0xdeadbeef schrieb:

Was size() angeht, vector und alle anderen STL-Container sind templates, das heißt, der Inhalt von size() ist vorher bekannt [...]

Nope. Für vector schon, aber list.size() ist häufig O(n). Wie soll den auch die Größe einer Liste zur Compilezeit bekannt sein?

Walli

DEvent schrieb:

Walli schrieb:
DEvent schrieb:

deswegen ist doch da der nachteil bei der normalen schleife. da muss jedesmal size() aufgerufen werden.

Genau, es wäre viel zu schwierig den Wert vorher einmal zu berechnen...
for(site_t i = 0, end = v.size(); i != end; ++i)
  foo(v[i]);
klar kann man dass, es ging aber um die schleife, die am anfang geposted wurde.

Wo geht das dort nicht? cout wird wohl kaum die Größe des vectors verändern.

Phoemuex

Wieso hat list den keinen Index-Operator? Haben das nicht (fast) alle Container-Klassen? Wenn nur vector einen Index-Operator hat, kann ich das Argument verstehen.

Danke

Felix

groovemaster

finix schrieb:

Für vector schon, aber list.size() ist häufig O(n). Wie soll den auch die Größe einer Liste zur Compilezeit bekannt sein?

Zur Compilzeit bekannt ist Quatsch, aber eine size() Laufzeit von O(n) ist auch nicht der Normalfall. Genauso kann man bei jedem Einfügen und Löschen die Grösse aktualisieren, dann ist size() auch nicht mehr als die simple Rückgabe eines Wertes.

Shade Of Mine

groovemaster schrieb:

Genauso kann man bei jedem Einfügen und Löschen die Grösse aktualisieren, dann ist size() auch nicht mehr als die simple Rückgabe eines Wertes.

Die Frage ist nur, ob man das will
Manchmal kann es sinnvoll sein die Laenge nicht mitzuspeichern.

@Phoemuex:
ein op[] fuer list haette O(N), es sei denn man erzeugt mehr overhead in der list... was auch wieder bloed ist.

Walli

Phoemuex schrieb:

Wieso hat list den keinen Index-Operator?

Weil eine List eine unangemessene Datenstruktur ist, wenn man einen Indexzugriff haben will. Ein Zugriff per Indexoperator würde wie gesagt (von irgendwelchen Tricks mal abgesehen) O(n) kosten. Wenn du nun per Indexoperator auf das Element am Ende der Liste zugreifen willst muss die Liste einmal komplett durchlaufen werden.