Bekannte Fallen bei der Benutzung der STL

Lose Sammlung von Stolpersteine und derer Lösung bei der Benutzung der STL.

Löschen von Elementen aus einem Vector

Lösung des Problems: Das Erase Remove Idiom

Der STL-Container std::vector stellt eine Methode zum Löschen von Elementen aus dem Vector zu Verfügung. Diese Funktion erwartet einen oder zwei Iterator als Parameter. Es werden die Elemente gelöscht, auf die der Iterator zeigt bzw. die sich zwischen den Iteratoren befinden.

Soweit so einfach.

Aber sobald man in einer Schleife alle Elemente, die einem bestimmten Suchkriterium entsprechen, löschen möchte wird es kompliziert.

Der Aufruf von erase löscht das Element, auf das der Iterator z.Z. zeigt. Damit ist der Iterator nach dem Aufruf von erase nicht mehr gültig.

Die Funktion erase gibt jedoch einen gültigen Iterator zurück - das Element das nach dem Aktuellen Element kommt, oder end(), wenn der Iterator auf dem letzten Element stand.

Damit muss ein korrekter Aufruf von erase wie folgt geschrieben werden, wenn der Iterator weiter verwendet werden soll.

it = feld.erase(it);

Der Iterator wird durch den Aufruf von erase ungültig und wird in der gleichen Zeile wieder mit einem gültigen Wert besetzt.

Diese Zeile kann jedoch so nicht in einer for-Schleife verwendet werden.

Aufruf der Funktion erase in einer for-Schleife

Die Funktion erase liefert das nächste Element nach dem löschen. Dies bedeutet, dass die Funktion erase nicht sinnvoll in for-Schleifen verwendet werden kann.

Fehlerhaftes Beispiel:

for (vector<int>::iterator it=feld.begin(); it!=feld.end();++it) {
  if (*it == 7 || *it == 8)
  {
    it = feld.erase(it);
  }
}

Da die erase Funktion und der Inkrement-Teil der for-Schleifen den Iterator weitersetzen wird nach dem Löschen ein Element übersprungen. Dabei kann auch das Ende übersprungen werden, was in einem undefinierten Verhalten enden kann.

Nach dem Aufruf von erase steht it auf den Element hinter "7" (oder "8") und mit dem nächsten Schleifendurchlauf wird auf das übernächste Element geschaltet. Damit wird das Element direct hinter "7" nicht geprüft.

Wenn das letzte Element den Wert 7 enthält wird es zu einer Zugriffsverletzung kommen:

Nach dem Aufruf von erase hat der Iterator den Wert von feld.end(). Anschließend wird es zu einem Aufruf von ++it kommen. Die Aufruf kann gut gehen muss aber nicht. (Implementierungsabhängig!) Der nächste Schritt ist der Vergleich it!=feld.end(). Dieser Aufruf sollte zu einer Zugriffverletzung führen!

Eine mögliche Alternative wäre die Benutzung von erase in einer while Schleife:

while(it!=feld.end())
{
  if (*it == 7 || *it == 8)
  {
    it = feld.erase(it);
  }
  else
  {
    ++it;
  }
}

Alternativ könnte man eine for-Schleife verwenden, bei der das Weiterzählen des iterators außerhalb des Schleifenkopf geschieht. Dies ist jedoch unüblich bei einer for-Schleife. Die oben genannte while-Lösung sieht ebenfalls nicht besser aus.

Benutzung von remove_if

Mit erase kann keine einfache Lösung programmiert werden. Auch die Verwendung der Funktionen remove und remove_if aus der Header-Datei algorithm helfen nicht im ersten Ansatz.

Der Algorithmus remove_if löscht die gesuchten Element in einem Einzeiler, ohne die Länge des Containers anzupassen, so dass in einer weiteren Zeile das Ende angepasst werden muss:

vector<int>::iterator new_end=std::remove_if(feld.begin(), feld.end(), isSieben);
feld.erase(new_end, feld.end());

Der dritte Parameter von remove_if ist eine Funktion oder ein Functor. der außerhalb programmiert werden muss. Mit der boost::lambda Bibliothek kann der Aufruf vereinfacht werden:

using namespace boost::lambda;
...
vector<int>::iterator new_end=std::remove_if(feld.begin(), feld.end(), _1 == 7 || _1 == 8);
feld.erase(new_end, feld.end());

Mit _1 == 7 || _1 == 8 wird eine lokale Funktion generiert, die true zurückliefert, wenn ein Element gleich 7 oder 8 ist.

Mit der Kombination remove_if, erease und einem Lambda-Ausdruck kann das Löschen auf 2 Zeilen reduziert werden.

Wenn die Rückgabe von remove / remove_if als erster Parameter der erase-Funktion übergeben kann das Ganze als Einzeiler formuliert werden. Diese Schreibweise wird als Erase-remove Idiom bezeichnet.

Das Erase-remove Idiom

Erase-remove idiom

Die Funktionen remove und remove_if löschen Elemente aus einem STL-Container (hier der Container std::vector) ohne die Länge des Containers anzupassen.

Daher muss in einem 2. Schritt, mit Hilfe der Member-Methode erase, die Länge des Vectors angepasst werden. Dazu wird der Rückgabewert der remove bzw. remove_if-Funktion als erster Parameter der Methode erase übergeben. Als zweiter Parameter wird end() übergeben. Damit wird der Vector auf die neue Länge eingekürzt.

Mit der Benutzung von Lambdas (boost::lambda oder C++0x lambda expressions) kann der benötigte Programmcode zum Löschen von bestimmten Elementen zusätzlich verkürzt werden.

#include <vector> // the general-purpose vector container
#include <algorithm> // remove and remove_if
#include <boost/lambda/lambda.hpp>
#include <iostream>

bool isSeven(const int i) // unary predicate returning true if and only if the argument is odd
{
  return i == 7;
}

int main()
{
  using namespace std;
  using namespace boost::lambda;

  int elements[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  // create a vector that holds the numbers from 0-9.
  vector<int> v(elements, elements + 10);

  // use the erase-remove idiom to remove all elements with the value 5
  v.erase( remove(v.begin(), v.end(), 5), v.end());

  // use the erase-remove idiom to remove all elements with the value 7 (with the help of the isSeven-function / functor)
  v.erase( remove_if(v.begin(), v.end(), isSeven), v.end() );

  // use the erase-remove idiom to remove all elements with the value 8 (boost lambda)
  v.erase( remove_if(v.begin(), v.end(), _1 == 8), v.end() );

  // use the erase-remove idiom to remove all elements with the value 2 (C++0x lambda expressions)
  v.erase( remove_if(v.begin(), v.end(),
    [](const int i) {return i == 2;}
    ), v.end() );

  for_each(v.begin(), v.end(),std::cout << boost::lambda::_1 << &quot;\n&quot;);
}

Gehe n-Schritte weiter

Die passende Funktion heißt std::advance. Die Übersetzung liefert für advance sowohl "der Annäherungsversuch", "der Fortschritt" aber auch "die Erhöhung".

Ich finde den Namen der Funktion nicht sehr intuitiv, daher taucht diese Funktion in dieser Liste auf. Ansonsten macht die Funktion was erwartet wird, bis auf die Anmerkung, dass innerhalb von advance keinerlei Range check vorgenommen wird. Wird mittels advance hinter die Grenzen eines Feldes zugegriffen, wird es unweigerlich zu einer Access violation kommen.

Für unidirektionale Iteratoren kann ein negativer Offset verwendet werden. Für Eingabe- oder Forwärts-Iterators muss der Offset nicht negativ (non-negativ) sein. Diese Einschränkung wird nicht getestet. Dies bedeutet, dass ein gutmütig programmierter Iterator sich einfach nicht bewegen wird, während ein aggressiv programmierter Iterator abstürzen wird.

Eine Zahl in einen Text verwandeln und umgekehrt.

Um eine Zahl in den Text zu verwandeln würde man in C die Funktion sprintf o.ä. verwenden. In der MFC gib es eine sehr verwandte Funktion als Member-Funktion der Klasse CString: Format.

Diese Funktionen sind NICHT typsicher!

Wenn der Format-String nicht zum Eingabetyp passt, kann das Programm abstürzen. Ein Wechsel des Datentyps einer Variablen, die nur ganz selten in einer der Wandlungsroutine verwendet wird, kann zu einem echten Problem werden.

Dies trifft genauso auf den Aufruf der Funktion aus der C-Bibliothek, wie auf die Member Funktion der Klasse CString zu. Dass es sich um eine C++ Klasse handelt schützt auch hier nicht vor Fehlern.

Die Funktion sprintf neigt zudem zum Pufferüberlauf (Buffer Overflows.). Hier sollte die Funtkion sprintf_n verwendet werden, die zusätzlich eine Puffergröße übergeben bekommt.

Es wäre besser wenn man Funktionen verwenden würde, die Typecht arbeiten.

Für den umgekehrten Fall (String nach Zahl) bieten sich die Funktionen atoi, atof, ... an. Diese Funktionen melden keinen Fehler, so dass eine fehlerhafte Konvertierung nicht erkannt werden kann.

In der Boost gibt es fertige Cast-Operatoren, die das Wandeln automatisch, typecht und mit einem Fehlerhandling durchführen: Die boost::lexical_cast-Familie.

#include <boost/lexical_cast.hpp>

....

using namespace std;

std::string text1 = "3.14"; double d1, d2;

try { // Text in ein (double-)Wert wandeln. d1 = boost::lexical_cast(text1); cout << "aus: " << text1 << " wurde: " << d1 << endl;

// Ein (double-)Wert in einen Text ausgeben.
d2 = 2.71;
text1= boost::lexical_cast<std::string>(d2);
cout << "aus: " << d2 << " wurde: " << text1 << endl;

} catch (boost::bad_lexical_cast& e) { cout << "Fehler: " << e.what() << endl; }

Zusätzlich enthält die boost-Bibliothek eine Klasse zum Formatieren eines String, die ähnlich arbeit wie die sprintf Funktion, sich aber typecht verhält: boost::format. boost::format hat außerdem weitere Erweiterungen, welche flexiblere Formatierungen von Strings erlauben. Hier kann z.B. der Übersetzer auch die Reihenfolge von Argumenten vertauschen.

#include <boost/format.hpp>

....

  using namespace std;
  using namespace boost;

  std::string text1 = "ABC";
  double d1 = 3.14;
  int i1 = 42;

  // Reihenfolge im Format verändert gegenüber der Reihenfolge der Parameter
  cout << format("->%2%<->%1%<->%3%<-\n") % i1 % d1 % text1;

Missing:

C++11 Beispiel mit toString()