std::list ich brauche nur Durchlaufen in eine Richtung

Für meine std::list brauche ich nur Durchlaufen in eine Richtung. Welchen Container könnte ich da verwenden, der den zusätzlichen Platz für die doppelte Verkettung nicht braucht?

Nexus

std::forward_list aus C++0x

knivil

Um wieviel Speicher handelt es sich denn und fuer welches System? Microcontroller?

Nexus schrieb:

std::forward_list aus C++0x

Danbekschön.

Wo liegt der Fehler in folgendem Code?

#include <forward_list>
#include <iostream>
using namespace std;

int main()
{
	forward_list<int> l;
	for (size_t i = 0; i < 10; ++i)
		l.push_front(i);

	for (auto i = l.begin(); i != l.end(); ++i)
		cout << *i;

	for (auto i = l.begin(); i != l.end(); ++i)
	{
		if (*i < 5)
			i = l.erase_after(i);
	}

	for (auto i = l.begin(); i != l.end(); ++i)
		cout << *i;
}

mit remove_if funzt es.

aber ich würde es gerne mit erase_after machen. Wie geht das?

camper

Ich spekuliere mal, dass das ungefähr

if (*i < 5 && next(i) != l.end())

heißen müsste.

Nein, das funzt nicht.

krümelkacker

Beschreib doch mal in Worten, was Du machen willst und/oder was da rauskommen soll. Und welches remove_if meinst Du? Meinst du forward_list<>::remove_if oder std::remove_if?

Das remove_if von der Liste wird wahrscheinlich in etwa so aussehen:

template<class T, class Alloc, class Predicate>
void forward_list_remove_if(forward_list<T,Alloc> & list, Predicate pred)
{
  auto iter = list.before_begin();
  auto const endi = list.end();
  for (;;) {
    auto nx = next(iter);
    if (nx==endi) break;
    if (pred(*nx)) {
      l.erase_after(iter);
    } else {
      iter = nx;
    }
  }
}

(ungetestet)

erase_after löscht nämlich nicht das Element, auf das der Iterator zeigt, sondern das folgende Element. Ich musste mich eben auch fragen, warum die Schnittstelle bei forward_list so "komisch" ist. Aber das hat wirklich damit zu tun, dass in allen Knoten nur ein next-Zeiger gespeichert ist. Wenn das aktuelle Element gelöscht werden soll, muss der next-Zeiger im vorherigen Knoten geändert werden. Wenn Du aber nur einen Zeiger auf den aktuellen Knoten hast, kannst Du den Vorgäner nicht mehr bekommen, da es ja keine doppeltverkettete Liste ist. Statt sich im Iterator zwei Zeiger zu merken (aktueller Knoten und Vorgänger) haben sie sich dazu entschlossen, die ganzen _after-Operationen einzuführen. Damit man dann noch am Listanfang etwas anstellen kann, benötigt man aber einen begin-Vorgänger, also before_begin.