Iterator vs. normale Schleifen

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.