[X] Aufbau der STL - Teil 3: Hilfsklassen und Erweiterungen

[CStoll]

Können bitte alle nochmal hier drübersehen? Von meiner Seite ist der Artikel fertig - und wenn's keine gravierenden Meldungen gibt, soll der weiter in die Rechtschreibkontrolle.
(besser zu früh als zu spät)

Artchi schrieb:

Es ergibt keine neue Version, weil es ja eine Erweiterung ist. Eine neue Version ist es nur, wenn sich was am Standard selbst was ändern würde. Man muß sich das so vorstellen, das es DEN C++ Standard gibt, der ja irgendwo festgelegt ist. Jetzt kommen _nur_ Libraries als _Erweiterung_ dazu, die in einem _separaten_ Dokument (dem Technical Report, steht für TR) festgelegt sind. Es ist eine Erweiterung, und keine Änderung/Neuerung des Standards.

Der TR soll in Zukunft die Arbeit des Kommittees erleichtern auf Anforderungen aus der Community zu reagieren. Da TRs einfach unbürokratischer verabschiedet werden können. Und TRs sind auch keine C++-Besonderheit, sondern sind eine ISO-Eigenheit.

OK, das habe ich soweit verstanden.
(und trotzdem sehe ich einen Unterschied zwischen "ANSI C++" und "ANSI C++ mit TR1")

[michba]

Wie wärs mit einem kleinen Beispiel im Kapitel "Funktoren", z.B. bind1st oder bind2nd?

[estartu]

In 3.1 ist ein Tag zerschossen.
3.2 scheint zu fehlen.

Sieht sonst gut aus.

[CStoll]

Danke für die Info, ist schon korrigiert.
(da sollte irgendjemand mal die Wirkungsweise der cpp-Tags überprüfen - ein [i] in meinem Beispielcode hat den gesamten nachfolgenden Abschnitt anscheinend zerpflückt)

[michba]

Es hat anscheinend niemand mehr etwas hinzuzufügen.
Ich denke, du kannst den Artikel jetzt auf [R] setzen, damit das mit der Rechtschreibkorrektur nicht so stressig wird.

[CStoll]

Lässt sich machen (noch ein paar eigene Ergänzungen einfügt und einen Schritt weiterspringt).

[michba]

Neben den Hauptbestandteilen der STL - Container, Iteratoren und Algorithmen - exisitieren in der Standardbibliothek von C++ noch etliche weitere Klassen, die von versierten Programmierern genutzt werden können - einige davon arbeiten auch unmittelbar mit der STL zusammen. Im letzten Teil meiner Serie will ich einen kurzen Überblick über diese Klassen geben. Außerdem gehe ich darauf ein, wie die Funktionalitäten der STL vom Programmierer erweitert werden können.

Inhalt

1. weitere Klassen
2. Fehlerbehandlung
3. Erweiterungsmöglichkeiten
4. weitere Informationen

1 weitere Klassen

Als Ergänzung zu den obigen Klassen gibt es noch einige kleinere Hilfsklassen in der C++-Bibliothek. Diese werden teilweise von den STL-Elementen genutzt, können aber auch alleinstehend eingesetzt werden.

1.1 pair

voller Name:

template<typename FT,typename ST>
struct std::pair;

template<typename FT,typename ST>
pair<FT,ST> make_pair(const FT&,const ST&);

Header:

include <utility>

Ein Pair (Paar) ist eine einfache Struktur, die zwei Elemente von verschiedenen Typen miteinander kombinieren kann. Diese Klasse wird unter anderem von Maps und Multimaps genutzt, um die Schlüssel-Wert-Paare zusammenzufassen. Außerdem ermöglichen sie es einer Funktion, zwei Werte gemeinsam zurückzugeben. Die letzte Möglichkeit wird auch von einigen Funktionen der STL genutzt, die mehrere Werte zusammen zurückgeben wollen, unter anderem equal_range() (gibt den Zielbereich des gesuchten Wertes als Paar zurück) und der insert()-Methode von Set und Map (diese gibt ein Paar aus einem Iterator und einem bool zurück, der angibt ob insert() das Element einfügen konnte).

Die beiden Teile des Paares können direkt über "p.first" bzw. "p.second" angesprochen und modifiziert werden. Außerdem können Paare verschiedener Typen einander zugewiesen werden, solange ihre Elementtypen ineinander umgewandelt werden können.

Die Hilfsfunktion make_pair() ist die schnellste Möglichkeit, zwei Werte zu einem pair zusammenzufassen - sie ist zum Beispiel hilfreich, um Werte in eine (multi)Map einzufügen.

1.2 Funktoren

Header:

#include <functional>

Funktoren sind Objekte, die den Operator () überladen haben. Dadurch können sie wie normale Funktionen genutzt werden. Gegenüber einer normalen Funktion haben sie jedoch einige deutliche Vorteile:

• sie können einen internen Status haben - und zwar in verschiedenen Exemplaren unabhängig voneinander.
• sie haben einen eigenen Typ und können deshalb auch als Template-Parameter an STL-Container weitergegeben werden.

Die C++-Bibliothek bietet unter anderem Binder, mit deren Hilfe ein Parameter einer binären Funktion festgelegt werden kann, Wrapperklassen für normale Funktionen und Klassenmethoden und vordefinierte Funktoren für viele C++-Operatoren (zu diesen gehört auch die Klasse less<>, die als Standard-Ordnungskriterium von Sets und Maps verwendet wird).

In der STL werden Funktoren als Vergleichskriterium für assoziative Container und Priority-Queues und als optionale Arbeitsfunktionen für die meisten Algorithmen verwendet.

Zum Beispiel lassen sich die vordefinierten Funktor-Adapter verwenden, um alle Elemente eines Containers mit einem festen Wert zu potenzieren:

vector<double> data;
...
transform(data.begin(),data.end(),bind2nd(ptr_fun(pow),3));
/* Kombination zweier Funktor-Adapter:
  bind2nd - legt den zweiten Parameter eines binären Funktors fest
  ptr_fun - wrappt eine "normale" Funktion in einen Funktor
*/

1.3 Streams

Die Stream-Klassen wurden als Ersatz für die printf()- und scanf()-Familie der C-Standardbibliothek eingeführt. Sie bieten eine typsichere und erweiterbare Möglichkeit, Daten formatiert ein- und auszulesen. Dazu überladen sie die Operatoren << und >>, mit deren Hilfe alle eingebauten Datentypen von C++ aus- bzw. eingegeben werden können.

Entwickler können ihre eigenen Klassen mit dem selben Mechanismus verarbeiten, indem sie die geeigneten Operatoren überladen.

Die Ein- und Ausgabe über Streams werde ich in einem späteren Artikel behandeln.
~wird ersetzt durch:~
Die Ein- und Ausgabe über Streams behandelt der Artikel "Ein- und Ausgabe in C++".

1.4 Locales und Facetten

Locales und Facetten dienen zur Internationalisierung der Ein- und Ausgabe-Operationen und werden sehr intensiv von den IO-Streams verwendet. Eine Facette modelliert einen bestimmten Aspekt der Ein/Ausgabe, wie zum Beispiel die Darstellung von Zahlen oder die Sortierung von landesspezifischen Sonderzeichen (z.B. Umlaute), ein Locale fasst Facetten für alle Einsatzbereiche zu einer Einheit zusammen.

Im Gegensatz zu C, wo nur ein Locale für alle Ein/Ausgabe-Operationen festgelegt werden konnte, kann in C++ jeder Stream sein eigenes Locale übergeben bekommen und verwalten.

1.5 komplexe Zahlen

voller Name:

template<typename T>
class std::complex;

Header:

#include <complex>

Die Klasse complex dient zur Verwendung und Berechnung von komplexen Zahlen. Komplexe Zahlen können aus einer reellen Zahl (als Realteil) oder aus zwei reellen Werten (Realteil und Imaginärteil) konstruiert werden, außerdem sind viele mathematische Operationen und Funktionen (z.B. Potenzen, Logarithmus, Winkelfunktionen,...) für komplexe Zahlen definiert.

Die Standardbibliothek definiert außer der allgemeinen Klasse complex<> auch Spezialisierungen für alle Gleitkommatypen (float, double und long double).

1.6 Valarrays

voller Name:

template<typename T>
class std::valarray;

class slice;  //eindimensionaler "Streifen" aus dem Valarray
class gslice; //mehrdimensionaler "Streifen"

Header:

#include <valarray>

Valarrays sind eine spezielle Form von Containern, die für parallele mathematische Operationen entwickelt wurden. Sie implementieren viele mathematische Operationen und Funktionen so, dass sie parallel auf alle Elemente angewendet werden.

//operator[] (slice)
template<typename T>class std::slice_array;
//operator[] (glice)
template<typename T>class std::gslice_array;
//operator[] (valarray<bool>)
template<typename T>class std::mask_array;
//operator[] (valarray<size_t>)
template<typename T>class std::indirect_array;

Diese Hilfsklassen können nicht direkt erzeugt werden. Sie entstehen bei speziellen Index-Operationen aus einem Valarray und bieten Zugriff auf bestimmte Teile des Arrays. Jede der vier Klassen entspricht einer bestimmten Methode zur Definition des Teilbereiches. Ein Teilarray kann genutzt werden, um eine mathematische Operation nur auf einem Teil der Elemente auszuführen, z.B. nur auf allen geraden Zahlen oderauf jedem vierten Element.

1.7 Bitsets

voller Name:

template<size_t N>
class std::bitset;

Header:

#include <bitset>

Bitsets werden zur Verwaltung von Einzelbits verwendet. Im Gegensatz zu einem vector<bool> steht die Größe des Bitsets bereits zur Compilezeit fest.

Ein Bitset kann zum Beispiel verwendet werden, um eine fixe Gruppe von Flags platzsparend unterzubringen. Außerdem können sie auch zur Umwandlung von Zahlen in bzw. aus einer Binärdarstellung genutzt werden. Dafür exisitieren Konstruktoren und Umwandlungsoperatoren sowohl für ganze Zahlen (unsigned long) als auch für Strings (Binärdarstellung).

#include <bitset>
#include <iostream>
#include <limits> //numeric_limits

int main()
{
  //Dezimal nach Binär:
  cout<<"4711 = "<< bitset<numeric_limits<int>::digits>(4711)<<endl;

  //Binär nach Dezimal
  cout<<"1011010110 = "<<bitset<10>(string("1011010110")).to_ulong()<<endl;
  //Achtung: Eine direkte Umwandlung von char* nach bitset ist afaik nicht erlaubt
}

1.8 Auto-Pointer

voller Name:

template<typename T>
class auto_ptr;

Header:

#include <memory>

Die Klasse auto_ptr ist (leider) die einzige Smart-Pointer-Klasse, die im aktuellen C++-Standard vorgesehen ist. Auto-Pointer sorgen dafür, dass ein von ihnen verwaltetes Heap-Objekt automatisch gelöscht wird, wenn sie ihren Scope verlassen. Dazu stellen sie sicher, dass immer genau ein Auto-Pointer auf dieses Objekt verweist - eine Zuweisung zwischen Auto-Pointern entzieht dem Ursprungspointer den Besitz und setzt ihn auf NULL zurück.

Achtung: Auto-Pointer sind nicht dazu geeignet, Heap-Objekte an mehreren Stellen im Programm gemeinsam zu nutzen. Für diesen Zweck sind Smart-Pointer mit Referenzzählung (z.B. Boost::shared_ptr - siehe "Schlaue Pointer" im Magazin) besser geeignet.
Mit dem Technical Report TR1 wurden diese Smart-Pointer übrigens in den Standard aufgenommen.

Achtung: Da die Containerklassen der STL ihre Elemente bei Bedarf kopieren dürfen, sind Auto-Pointer NICHT zum Einsatz in STL-Containern geeignet.

1.9 Exception-Klassen

Header:

#include <stdexcept>
#include <exception> //ecxeption (Basisklasse) und bad_exception
#include <new>       //bad_alloc
#include <typeinfo>  //bad_cast und bad_typeid
#include <ios>       //ios_base::failure

Die Exception-Klassen wurden zur Unterstützung der Exception-Verarbeitung in C++ (try/catch) entworfen. Sie bieten eine eigene Hierarchie von verschiedenen Klassen, die je nach auftretender Fehlersituation verwendet werden können - sowie eine einheitliche Schnittstelle. Auf diese Weise lassen sich auch komplette Kategorien von Fehlern (z.B. alle logischen Fehler) oder sogar alle "Beschwerden" der Standardbibliothek mit einer einzigen catch-Klausel abfangen und auswerten:

try
{
  //etliche Operationen, die Probleme bereiten könnten
}
catch(std::exception& e)
{
  //hier landen alle Standard-Exceptions:
  cerr<<"Wir haben einen Fehler: "<<e.what()<<endl;
}

Die Basisklasse 'exception' definiert zur Fehlerauswertung eine virtuelle Methode what(), mit der die Fehlerursache erfragt werden kann - diese liefert für alle abgeleiteten Klassen einen implementationsspezifischen C-String (const char*). Weitere Zugriffsmöglichkeiten sind jedoch nicht vorgesehen.

In der Standard-Bibliothek sind folgende Exception-Klassen definiert:

Klasse             Basis          Verwendung

exception          -              Basis für alle Exception-Klassen
bad_alloc          exception      Fehler in new
bad_cast           exception      Fehler in dynamic_cast (Referenzen)
bad_typeid         exception      Fehler bei typeid Operator
ios_base::failure  exception      Fehler bei IO-Streams
bad_exception      exception      throw() Spezifikation umgangen

logic_error        exception      Logische Fehler (könnten vom Programm umgangen werden)
domain_error       logic_error    Domain-Fehler
invalid_argument   logic_error    ungültiges Argument (z.B. "0012" an bitset-Ctor)
length_error       logic_error    Maximallänge überschritten
out_of_range       logic_error    Bereichsüberschreitungen (z.B. bei vector::at())

runtime_error      exception      Laufzeitfehler (i.d.R. nicht abfangbar)
range_error        runtime_error  interner Bereichsfehler
overflow_error     runtime_error  arithmetischer Überlauf
underflow_error    runtime_error  arithmetischer Unterlauf

2 Fehlerbehandlung

Die meisten Methoden und Funktionen der STL sind so entworfen, dass sie möglichst beste Performance bieten. Deshalb wird größtenteils darauf verzichtet, Falscheingaben abzufangen. Wer ungültige Parameter, wie zum Beispiel einen ungültigen Iterator-Bereich, an einen STL-Algorithmus übergibt, erhält im Allgemeinen undefiniertes Verhalten.

Die einzige Funktion der STL, die wirklich ihre Eingabewerte auf Gültigkeit prüft, ist die Methode at() von vector<> und deque<> - diese wirft eine out_of_range Exeption, wenn sie mit einem ungültigen Index aufgerufen wird. In anderen Komponenten der C++-Standard-Bibliothek (z.B. in der string-Klasse oder bei den IO-Streams) erfolgt dagegen eine gründlichere Fehlerkontrolle.

Im Fall einer extern auftretenden Exception (z.B. in den Prädikaten, die an einen Algorithmus übergeben wurden) bieten alle Bestandteile der STL die Garantie, keine Speicherlecks zu produzieren und in einen "sicheren" Zustand zu wechseln. Einige der Container-Operationen bieten darüber hinaus eine "Commit-or-Rollback"-Garantie - entweder die Operation wird erfolgreich durchgeführt oder der Container bleibt unverändert. Andere Operationen gelingen garantiert (solange die Destruktoren der beteiligten Objekte keine Exceptions werfen können).

3 Erweiterungsmöglichkeiten

Die gesamte STL ist nach dem open-closed-Prinzip aufgebaut - offen für Erweiterungen, geschlossen für Modifikationen. Die existierenden Bestandteile der STL sollten als gegeben vorausgesetzt werden, können jedoch problemlos mit eigenen Klassen und Funktionen kombiniert werden.
(theoretisch ist es auch möglich, in den STL-Headern rumzupfuschen, aber ich rate dringend davon ab)

3.1. eigene Container

Um eine eigene Containerklasse für die Zusammenarbeit mit der STL vorzubereiten, gibt es drei mögliche Ansätze:

direkt

Der einfachste Weg, einen Container STL-tauglich zu machen, ist es, einen passenden Iterator für den Container zu finden oder zu definieren und diese Iteratoren den STL-Algorithmen zur Verfügung zu stellen. So dienen zum Beispiel blanke Pointer als "Iterator" für C-Arrays:

int values[100];
generate(values,values+100,rand);// füllen mit Zufallszahlen
sort(values,values+100);         // gesamtes Array sortieren
reverse(values,values+10);       // erste 10 Elemente umdrehen
...

Für andere Datenstrukturen ist es in der Regel notwendig, eine eigene Iteratorklasse zu bauen. Dazu finden sich im Kapitel 3.2 weitere Informationen.

per Wrapper

Etwas stärker ist die Kopplung, wenn um eine bestehende Containerstruktur eine Wrapper-Klasse aufgebaut wird, die die wichtigsten Methoden für STL-Container (z.B. begin(), end(), size(), etc.) implementiert und in Aufrufe der Container-eigenen Methoden übersetzt. Auf diese Weise ließe sich ein STL-Interface um ein Array oder ein Datenbank-System herum aufbauen.

//Beispiel: Array-Wrapper
template<typename T,size_t N>
class CArray
{
  T vals[N];
public:
  typedef T        value_type;
  typedef T*       iterator;
  typedef const T* const_iterator;
  ...//eventuell einige weitere typedef's

  //Iterator-Erzeugung:
  iterator begin()                  {return vals;}
  const_iterator begin() const      {return vals;}
  iterator end()                    {return vals+N;}
  const_iterator end() const        {return vals+N;}

  //Größe:
  size_t size() const               {return N;}

  //Elementzugriff:
  T& operator[] (int j)             {return vals[j];}
  const T& operator[] (int j) const {return vals[j];}

  //Umwandlung in Array:
  T* as_array()                     {return vals;}
}

invasiv

Die aufwendigste Methode besteht darin, die eigene Containerklasse von Anfang an so zu konzipieren, dass sie ein mehr oder weniger vollständiges STL-Interface bereitstellt. Dieser Ansatz wurde z.B. verwendet, als die string-Klasse entworfen wurde.

3.2 eigene Iteratoren

Da die gesamte STL auf Templates aufbaut, ist der Entwurf eines neuen Iterators eigentlich recht einfach - alles, was sich wie ein Iterator verhält, ist ein Iterator (und alles, was die Operationen bereitstellt, die von einem Algorithmus verwendet werden, kann diesem Algorithmus übergeben werden).

Als Unterstützung für den Entwickler gibt es trotzdem eine Protokollklasse iterator, die als Basis für eigene Iteratoren verwendet werden kann:

template<typename Cat,typename T,typename Diff=ptrdiff_t,typename Ptr=T*,typename Ref=T&>
struct std::iterator;

struct output_iterator_tag {};
struct input_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

Diese Klasse definiert lediglich die Datentypen, die für die Arbeit mit den iterator_traits benötigt werden.

Die leeren Hilfsklassen (..._tag) können als Parameter 'Cat' verwendet werden und kennzeichnen die Einordnung des eigenen Iteratortyps in eine der Kategorien (siehe Teil 2 der Artikelserie). Die für diese Kategorie nötigen Operationen müssen allerdings selbst bereitgestellt werden. Diese Klassen sind voneinander abgeleitet, um die Austauschbarkeit der einzelnen Kategorien darzustellen - zum Beispiel kann jeder Random-Access-Iterator auch als Input-Iterator genutzt werden.

Achtung: Die Klasse forward_iterator_tag ist nicht von output_iterator_tag abgeleitet, weil Forward-Iteratoren nicht vollständig äquivalent zu Output-Iteratoren sind (siehe Kapitel 2.3 im zweiten Teil der Serie).

Ein Beispiel für eigene Iteratoren wäre ein Spezial-Inserter für assoziative Container. Im Gegensatz zum Inserter der STL benötigt diese Variante keine Einfügeposition und kann dadurch eventuell schneller arbeiten (insert() mit der falschen Zielposition ist üblicherweise langsamer als ein insert() ohne vorgegebene Position):

template<typename Cont>
class ainsert_iterator : public iterator<output_iterator_tag,void,void,void,void>
{
protected:
  Cont& container;
public:
  explicit ainsert_iterator(Cont& c) : container(c) {}

  // Wertzuweisung *it=x
  ainsert_iterator& operator=(const typename Cont::value_type& val)
  {
    container.insert(val);
    return *this;
  }

  //Dereferenzierung
  ainsert_iterator& operator*() {return *this;}

  //Inkrement
  ainsert_iterator& operator++() {return *this;}
  ainsert_iterator& operator++(int) {return *this;}
};

template<typename Cont>
inline ainsert_iterator<Cont> asso_inserter(Cont& c)
{ return ainsert_iterator<Cont>(c); }

operator* und operator= stellen den üblichen Weg dar, mit dem bei einem Output-Iterator die Wertzuweisung realisiert wird. "Höherwertige" Iteratorklassen liefern dagegen meistens eine Referenz auf ihren Elementtyp oder eine Pseudo-Referenz zurück, wenn sie dereferenziert werden.

Folgende Operatoren werden benötigt, um eine vollwertige Iteratorklasse zu erzeugen:

Operator                                   Bedeutung               Kategorien

Iter::Iter(const Iter&)                    Kopier-Konstruktor      OIFBR
Iter& Iter::operator=(const Iter&)         Zuweisung                 FBR

Ref Iter::operator*()                      Dereferenzierung        OIFBR
Ptr Iter::operator->()                     Memberzugriff            IFBR
Ref Iter::operator[](Diff)                 Indexzugriff                R

Iter& Iter::operator++()                   Inkrement (Präfix)      OIFBR
Iter Iter::operator++(int)                 Inkrement (Postfix)     OIFBR
Iter& Iter::operator--()                   Dekrement (Präfix)         BR
Iter Iter::operator--(int)                 Dekrement (Postfix)        BR
Iter& Iter::operator+=(Diff)               Inkrement (n Schritte)      R
Iter& Iter::operator-=(Diff)               Dekrement (n Schritte)      R
Iter operator+(Diff,const Iter&)           n't nächste Position        R
Iter operator+(const Iter&,Diff)           n't nächste Position        R
Iter operator-(const Iter&,Diff)           n't vorige Position         R
Diff operator-(const Iter&, const Iter&)   Abstand                     R

bool operator==(const Iter&,const Iter&)   Vergleich (gleich)       IFBR
bool operator!=(const Iter&,const Iter&)   Vergleich (ungleich)     IFBR
bool operator [i]x[/i](const Iter&,const Iter&)   Vergleich (<,<=,>=,>)       R

Dabei ist "Ref" eine Referenz auf den Elementtyp oder eine Klasse, die entsprechende Funktionalität zur Verfügung stellt (für Output-Iteratoren wird ein operator=(T) benötigt, für alle anderen Kategorien auch Elementzugriff und eine Umwandlung nach T), "Ptr" ein Pointer oder Smart-Pointer auf den Elementtyp (benötigt auf jeden Fall einen operator->()) und "Diff" der Differenztyp des Iterators (normalerweise ein vorzeichenbehafteter Ganzzahltyp).

3.3 eigene Algorithmen

In der Regel ist der schwierigste Teil der Algorithmen-Entwicklung die Frage, was der Algorithmus eigentlich machen soll. Wenn die Arbeitsweise feststeht, kann der Algorithmus vorübergehend auf einem int-Array implementiert werden.

Wenn feststeht, dass der Algorithmus korrekt funktioniert, kann er in eine Template-Funktion umgewandelt werden, indem alle Vorkommen von 'int*' durch den Template-Parameter 'It' und alle Vorkommen von 'int' (außer Zählvariablen) durch 'typename iterator_traits<It>::value_type' oder einen eigenen Template-Parameter ersetzt werden.

//Ausgangspunkt:
int* worker(int* data, size_t len,...)
{
  ...
}

//Zwischenschritt: Start+Länge -> Start+Ende
int* worker(int* beg, int* end,...)
{
  //ersetze len durch end-beg
  ...
}

//Ergebnis: Template-Funktion
template<typename It,...>
It worker(It beg, It end,...)
{
  typedef typename iterator_traits<It>::value_type val;
  //ersetze int* durch It und int durch val
}

Anmerkung: Wenn möglich, sollten für die Arbeit die Hilfsfunktionen advance() statt Iterator-Addition, difference() statt Iterator-Subtraktion und swap() oder iter_swap() statt Elementaustausch verwendet werden.

Ein Beispiel für einen eigenen Algorithmus wäre eine Funktion, die alle Duplikate aus einer unsortierten Datensammlung entfernt:

//als Quellbereich wird ein Forward-Iterator benötigt, weil Input-Iteratoren nicht sicher kopiert werden können
template<typename FwdIt,typename OutIt>
OutIt unsorted_unique_copy(FwdIt sbeg,FwdIt send,OutIt dbeg)
{
  for(FwdIt pos=sbeg;pos!=send;++pos)
    if(find(sbeg,pos,*pos)==pos) *dbeg++ = *pos;
  return dbeg;
}

template<typename FwdIt>
FwdIt unsorted_unique(FwdIt beg,FwdIt end)
{
  return unsorted_unique_copy(beg,end,beg);
}

Um den Algorithmen die Arbeit zu erleichtern, existiert eine Hilfsklasse "iterator_traits", die einige Typdefinitionen für einen Iterator enthält:

template<typename It>
struct iterator_traits
{
  typedef typename It::value_type        value_type;        // Werttyp
  typedef typename It::iterator_category iterator_category; // Kategorie: Output, Input,...
  typedef typename It::difference_type   difference_type;   // Differenz zwischen Iteratoren
  typedef typename It::pointer           pointer;           // Zeiger auf T
  typedef typename It::reference         reference          // Referenz auf T
};

Die Typdefinitionen dieser Klasse können verwendet werden, um z.B. den Typ einer temporären Variablen passend zum Iterator festzulegen.

template<typename Iter>
void foo_alg(Iter beg,Iter end)
{
  if(beg==end) return;
  typename iterator_traits<Iter>::value_type temp=*beg;
  ...
}

template<typename Iter>
void bar_alg(Iter beg,Iter end)
{
  typename iterator_traits<Iter>::difference_type dist=distance(beg,end);
  ...
}

Die Kategorie des Iterators kann genutzt werden, um einen Algorithmus so zu optimieren, dass er die "besten" Operationen des Iterator-Typs verwendet:

//"öffentliche Version":
//wird vom Nutzer aufgerufen und delegiert die Arbeit weiter
template<typename Iter>
Iter algo(Iter beg,Iter end)
{ return algo(beg,end,iterator_traits<Iter>::iterator_category()); }

//Version für Random Access Iteratoren:
//nutzt die komplette Vielfalt der Iterator-Arithmetik
template<typename RanIt>
RanIt algo(RanIt beg,RanIt end,random_access_iterator_tag)
{
  ...
}

//Version für andere Typen:
//nutzt nur Inkrement-Operator
template<typename InIt>
InIt algo(InIt beg,InIt end,input_iterator_tag)
{
  ...
}

Dank der Vererbungsbeziehung zwischen den Tag-Klassen wird die zweite Version des Algorithmus' auch von Forward- und Bidirektionalen Iteratoren verwendet.

Außer der allgemeinen Version der iterator_traits - die alle benötigten Typdefinitionen in der instanziierten Klasse voraussetzt - gibt es noch Spezialisierungen für Pointer und const-Pointer. Iterator-Klassen, die die benötigten Typen nicht selber bereitstellen können oder wollen - z.B. weil sie aus einer fremden Bibliothek integriert wurden - , dürfen ebenfalls eine Spezialisierung der iterator_traits anlegen.

Anmerkung: Wenn ein eigener Iterator von der Hilfsklasse iterator<> abgeleitet wird (siehe Kapitel 3.2), stellt er automatisch alle nötigen Typdefinitionen für die Iterator-Traits bereit.

3.4 eigene Funktoren

Als Funktor kann theoretisch jede Klasse verwendet werden, die den operator() überladen hat. Für die Zusammenarbeit mit den STL-Funktor-Adaptern ist es jedoch notwendig, die Argument- und Rückgabetypen des eigenen operator() anzugeben. Diese Arbeit können die Protokollklassen unary_function und binary_function für den Entwickler übernehmen:

//Functor: Res f(Arg x);
template<typename Arg,typename Res>
struct unary_function;

//Functor: Res f(Arg1 x,Arg2 y);
template<typename Arg1,typename Arg2,typename Res>
struct binary_function;

Ein Beispiel für einen selbstdefinierten Funktor ist die mean-Klasse, die ich im Teil 2 vorgestellt habe, ein anderes Beispiel wäre ein Composer, der mehrere Funktionen zusammenfassen kann (entsprechende Klassen gibt es z.B. in der Boost-Bibliothek):

//c(x,y) = f(g(x),h(y))
template<typename Op1,typename Op2,typename Op3>
class compose_f_gx_hy_t : public binary_function<typename Op2::argument_type,
                                                 typename Op3::argument_type,
                                                 typename Op1::result_type>
{
  Op1 op1;
  Op2 op2;
  Op3 op3;
public:
  compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
  : op1(f), op2(g), op3(h)
  {}

  typename Op1::result_type
  operator() (const typename Op2::argument_type& x,const typename Op3::argument_type& y)
  { return op1(op2(x),op3(y)); }
};

//Hilfsfunktion zur Erzeugung eines Composer's
template<typename Op1,typename Op2,typename Op3>
inline compose_f_gx_hy_t<Op1,Op2,Op3>
compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
{ return compose_f_gx_hy_t<Op1,Op2,Op3>(f,g,h); }

Anmerkung: Analog dazu lassen sich alle Kombinationen aus unären und binären Funktionen mit geeigneten Composern darstellen.

4. weitere Informationen

C++ Referenz

The C++ Standard Library | ISBN: 0201379260 - Nicolai M. Josuttis - The C++ Standard Library
Die C++-Standardbibliothek | ISBN: 3540256938 - Stefan Kuhlins, Martin Schrader - Die C++ Standardbibliothek

[michba]

Sorry, dass ich erst jetzt dazu komme, aber es ist ja noch ein wenig Zeit...
Ich hoffe, dass ich nicht all zu viele Fehler übersehen habe; ich habe nämlich nur sehr wenig gefunden

[Mr. B]

Neben den Hauptbestandteilen der STL - Container, Iteratoren und Algorithmen - existieren in der Standardbibliothek von C++ noch etliche weitere Klassen, die von versierten Programmierern genutzt werden können. Einige davon arbeiten auch unmittelbar mit der STL zusammen. Im letzten Teil meiner Serie will ich einen kurzen Überblick über diese Klassen geben. Außerdem gehe ich darauf ein, wie die Funktionalitäten der STL vom Programmierer erweitert werden können.

Inhalt

1. weitere Klassen
2. Fehlerbehandlung
3. Erweiterungsmöglichkeiten
4. weitere Informationen

1 weitere Klassen

Als Ergänzung zu den obigen Klassen gibt es noch einige kleinere Hilfsklassen in der C++-Bibliothek. Diese werden teilweise von den STL-Elementen genutzt, können aber auch allein stehend eingesetzt werden.

1.1 pair

voller Name:

template<typename FT,typename ST>
struct std::pair;

template<typename FT,typename ST>
pair<FT,ST> make_pair(const FT&,const ST&);

Header:

include <utility>

Ein Pair (Paar) ist eine einfache Struktur, die zwei Elemente von verschiedenen Typen miteinander kombinieren kann. Diese Klasse wird unter anderem von Maps und Multimaps genutzt, um die Schlüssel-Wert-Paare zusammenzufassen. Außerdem ermöglichen sie es einer Funktion, zwei Werte gemeinsam zurückzugeben. Die letzte Möglichkeit wird auch von einigen Funktionen der STL genutzt, die mehrere Werte zusammen zurückgeben wollen, unter anderem equal_range() (gibt den Zielbereich des gesuchten Wertes als Paar zurück) und der insert()-Methode von Set und Map (diese gibt ein Paar aus einem Iterator und einem bool zurück, der angibt, ob insert() das Element einfügen konnte).

Die beiden Teile des Paares können direkt über "p.first" bzw. "p.second" angesprochen und modifiziert werden. Außerdem können Paare verschiedener Typen einander zugewiesen werden, solange ihre Elementtypen ineinander umgewandelt werden können.

Die Hilfsfunktion make_pair() ist die schnellste Möglichkeit, zwei Werte zu einem pair zusammenzufassen - sie ist zum Beispiel hilfreich, um Werte in eine (Multi-)Map einzufügen.

1.2 Funktoren

Header:

#include <functional>

Funktoren sind Objekte, die den Operator () überladen haben. Dadurch können sie wie normale Funktionen genutzt werden. Gegenüber einer normalen Funktion haben sie jedoch einige deutliche Vorteile:

• sie können einen internen Status haben - und zwar in verschiedenen Exemplaren unabhängig voneinander.
• sie haben einen eigenen Typ und können deshalb auch als Template-Parameter an STL-Container weitergegeben werden.

Die C++-Bibliothek bietet unter anderem Binder, mit deren Hilfe ein Parameter einer binären Funktion festgelegt werden kann, Wrapperklassen für normale Funktionen und Klassenmethoden und vordefinierte Funktoren für viele C++-Operatoren (zu diesen gehört auch die Klasse less<>, die als Standard-Ordnungskriterium von Sets und Maps verwendet wird).

In der STL werden Funktoren als Vergleichskriterium für assoziative Container und Priority-Queues und als optionale Arbeitsfunktionen für die meisten Algorithmen verwendet.

Zum Beispiel lassen sich die vordefinierten Funktor-Adapter verwenden, um alle Elemente eines Containers mit einem festen Wert zu potenzieren:

vector<double> data;
...
transform(data.begin(),data.end(),bind2nd(ptr_fun(pow),3));
/* Kombination zweier Funktor-Adapter:
  bind2nd - legt den zweiten Parameter eines binären Funktors fest
  ptr_fun - wrappt eine "normale" Funktion in einen Funktor
*/

1.3 Streams

Die Stream-Klassen wurden als Ersatz für die printf()- und scanf()-Familie der C-Standardbibliothek eingeführt. Sie bieten eine typsichere und erweiterbare Möglichkeit, Daten formatiert ein- und auszulesen. Dazu überladen sie die Operatoren << und >>, mit deren Hilfe alle eingebauten Datentypen von C++ aus- bzw. eingegeben werden können.

Entwickler können ihre eigenen Klassen mit demselben Mechanismus verarbeiten, indem sie die geeigneten Operatoren überladen.

Die Ein- und Ausgabe über Streams werde ich in einem späteren Artikel behandeln.
~wird ersetzt durch:~
Die Ein- und Ausgabe über Streams behandelt der Artikel "Ein- und Ausgabe in C++".

1.4 Locales und Facetten

Locales und Facetten dienen zur Internationalisierung der Ein- und Ausgabe-Operationen und werden sehr intensiv von den IO-Streams verwendet. Eine Facette modelliert einen bestimmten Aspekt der Ein/Ausgabe, wie zum Beispiel die Darstellung von Zahlen oder die Sortierung von landesspezifischen Sonderzeichen (z.B. Umlaute), ein Locale fasst Facetten für alle Einsatzbereiche zu einer Einheit zusammen.

Im Gegensatz zu C, wo nur ein Locale für alle Ein/Ausgabe-Operationen festgelegt werden konnte, kann in C++ jeder Stream sein eigenes Locale übergeben bekommen und verwalten.

1.5 komplexe Zahlen

voller Name:

template<typename T>
class std::complex;

Header:

#include <complex>

Die Klasse complex dient zur Verwendung und Berechnung komplexer Zahlen. Komplexe Zahlen können aus einer reellen Zahl (als Realteil) oder aus zwei reellen Werten (Realteil und Imaginärteil) konstruiert werden. Außerdem sind viele mathematische Operationen und Funktionen (z.B. Potenzen, Logarithmus, Winkelfunktionen,...) für komplexe Zahlen definiert.

Die Standardbibliothek definiert außer der allgemeinen Klasse complex<> auch Spezialisierungen für alle Gleitkommatypen (float, double und long double).

1.6 Valarrays

voller Name:

template<typename T>
class std::valarray;

class slice;  //eindimensionaler "Streifen" aus dem Valarray
class gslice; //mehrdimensionaler "Streifen"

Header:

#include <valarray>

Valarrays sind eine spezielle Form von Containern, die für parallele mathematische Operationen entwickelt wurden. Sie implementieren viele mathematische Operationen und Funktionen so, dass sie parallel auf alle Elemente angewendet werden.

//operator[] (slice)
template<typename T>class std::slice_array;
//operator[] (glice)
template<typename T>class std::gslice_array;
//operator[] (valarray<bool>)
template<typename T>class std::mask_array;
//operator[] (valarray<size_t>)
template<typename T>class std::indirect_array;

Diese Hilfsklassen können nicht direkt erzeugt werden. Sie entstehen bei speziellen Indexoperationen aus einem Valarray und bieten Zugriff auf bestimmte Teile des Arrays. Jede der vier Klassen entspricht einer bestimmten Methode zur Definition des Teilbereiches. Ein Teilarray kann genutzt werden, um eine mathematische Operation nur auf einem Teil der Elemente auszuführen, z.B. nur auf allen geraden Zahlen oder auf jedem vierten Element.

1.7 Bitsets

voller Name:

template<size_t N>
class std::bitset;

Header:

#include <bitset>

Bitsets werden zur Verwaltung von Einzelbits verwendet. Im Gegensatz zu einem vector<bool> steht die Größe des Bitsets bereits zur Compilezeit fest.

Ein Bitset kann zum Beispiel verwendet werden, um eine fixe Gruppe von Flags Platz sparend unterzubringen. Außerdem können sie auch zur Umwandlung von Zahlen in bzw. aus einer Binärdarstellung genutzt werden. Dafür existieren Konstruktoren und Umwandlungsoperatoren sowohl für ganze Zahlen (unsigned long) als auch für Strings (Binärdarstellung).

#include <bitset>
#include <iostream>
#include <limits> //numeric_limits

int main()
{
  //Dezimal nach Binär:
  cout<<"4711 = "<< bitset<numeric_limits<int>::digits>(4711)<<endl;

  //Binär nach Dezimal
  cout<<"1011010110 = "<<bitset<10>(string("1011010110")).to_ulong()<<endl;
  //Achtung: Eine direkte Umwandlung von char* nach bitset ist afaik nicht erlaubt
}

1.8 Auto-Pointer

voller Name:

template<typename T>
class auto_ptr;

Header:

#include <memory>

Die Klasse auto_ptr ist (leider) die einzige Smart-Pointer-Klasse, die im aktuellen C++-Standard vorgesehen ist. Auto-Pointer sorgen dafür, dass ein von ihnen verwaltetes Heap-Objekt automatisch gelöscht wird, wenn sie ihren Scope verlassen. Dazu stellen sie sicher, dass immer genau ein Auto-Pointer auf dieses Objekt verweist - eine Zuweisung zwischen Auto-Pointern entzieht dem Ursprungspointer den Besitz und setzt ihn auf NULL zurück.

Achtung: Auto-Pointer sind nicht dazu geeignet, Heap-Objekte an mehreren Stellen im Programm gemeinsam zu nutzen. Für diesen Zweck sind Smart-Pointer mit Referenzzählung (z.B. Boost::shared_ptr - siehe "Schlaue Pointer" im Magazin) besser geeignet.
Mit dem Technical Report TR1 wurden diese Smart-Pointer übrigens in den Standard aufgenommen.

Achtung: Da die Containerklassen der STL ihre Elemente bei Bedarf kopieren dürfen, sind Auto-Pointer NICHT zum Einsatz in STL-Containern geeignet.

1.9 Exception-Klassen

Header:

#include <stdexcept>
#include <exception> //ecxeption (Basisklasse) und bad_exception
#include <new>       //bad_alloc
#include <typeinfo>  //bad_cast und bad_typeid
#include <ios>       //ios_base::failure

Die Exception-Klassen wurden zur Unterstützung der Exception-Verarbeitung in C++ (try/catch) entworfen. Sie bieten eine eigene Hierarchie von verschiedenen Klassen, die je nach auftretender Fehlersituation verwendet werden können, sowie eine einheitliche Schnittstelle. Auf diese Weise lassen sich auch komplette Kategorien von Fehlern (z.B. alle logischen Fehler) oder sogar alle "Beschwerden" der Standardbibliothek mit einer einzigen catch-Klausel abfangen und auswerten:

try
{
  //etliche Operationen, die Probleme bereiten könnten
}
catch(std::exception& e)
{
  //hier landen alle Standard-Exceptions:
  cerr<<"Wir haben einen Fehler: "<<e.what()<<endl;
}

Die Basisklasse 'exception' definiert zur Fehlerauswertung eine virtuelle Methode what(), mit der die Fehlerursache erfragt werden kann - diese liefert für alle abgeleiteten Klassen einen implementationsspezifischen C-String (const char*). Weitere Zugriffsmöglichkeiten sind jedoch nicht vorgesehen.

In der Standardbibliothek sind folgende Exception-Klassen definiert:

Klasse             Basis          Verwendung

exception          -              Basis für alle Exception-Klassen
bad_alloc          exception      Fehler in new
bad_cast           exception      Fehler in dynamic_cast (Referenzen)
bad_typeid         exception      Fehler bei typeid Operator
ios_base::failure  exception      Fehler bei IO-Streams
bad_exception      exception      throw() Spezifikation umgangen

logic_error        exception      Logische Fehler (könnten vom Programm umgangen werden)
domain_error       logic_error    Domain-Fehler
invalid_argument   logic_error    ungültiges Argument (z.B. "0012" an bitset-Ctor)
length_error       logic_error    Maximallänge überschritten
out_of_range       logic_error    Bereichsüberschreitungen (z.B. bei vector::at())

runtime_error      exception      Laufzeitfehler (i.d.R. nicht abfangbar)
range_error        runtime_error  interner Bereichsfehler
overflow_error     runtime_error  arithmetischer Überlauf
underflow_error    runtime_error  arithmetischer Unterlauf

2 Fehlerbehandlung

Die meisten Methoden und Funktionen der STL sind so entworfen, dass sie möglichst beste Performance bieten. Deshalb wird größtenteils darauf verzichtet, Falscheingaben abzufangen. Wer ungültige Parameter, wie zum Beispiel einen ungültigen Iterator-Bereich, an einen STL-Algorithmus übergibt, erhält im Allgemeinen undefiniertes Verhalten.

Die einzige Funktion der STL, die wirklich ihre Eingabewerte auf Gültigkeit prüft, ist die Methode at() von vector<> und deque<> - diese wirft eine out_of_range Exeption, wenn sie mit einem ungültigen Index aufgerufen wird. In anderen Komponenten der C++-Standard-Bibliothek (z.B. in der string-Klasse oder bei den IO-Streams) erfolgt dagegen eine gründlichere Fehlerkontrolle.

Im Falle einer extern auftretenden Exception (z.B. in den Prädikaten, die an einen Algorithmus übergeben wurden) bieten alle Bestandteile der STL die Garantie, keine Speicherlecks zu produzieren und in einen "sicheren" Zustand zu wechseln. Einige der Container-Operationen bieten darüber hinaus eine "Commit-or-Rollback"-Garantie - entweder die Operation wird erfolgreich durchgeführt oder der Container bleibt unverändert. Andere Operationen gelingen garantiert (solange die Destruktoren der beteiligten Objekte keine Exceptions werfen können).

3 Erweiterungsmöglichkeiten

Die gesamte STL ist nach dem open-closed-Prinzip aufgebaut - offen für Erweiterungen, geschlossen für Modifikationen. Die existierenden Bestandteile der STL sollten als gegeben vorausgesetzt werden, können jedoch problemlos mit eigenen Klassen und Funktionen kombiniert werden
(theoretisch ist es auch möglich, in den STL-Headern rumzupfuschen, aber ich rate dringend davon ab).

3.1. Eigene Container

Um eine eigene Containerklasse für die Zusammenarbeit mit der STL vorzubereiten, gibt es drei mögliche Ansätze:

direkt

Der einfachste Weg, einen Container STL-tauglich zu machen, ist es, einen passenden Iterator für den Container zu finden oder zu definieren und diese Iteratoren den STL-Algorithmen zur Verfügung zu stellen. So dienen zum Beispiel blanke Pointer als "Iterator" für C-Arrays:

int values[100];
generate(values,values+100,rand);// füllen mit Zufallszahlen
sort(values,values+100);         // gesamtes Array sortieren
reverse(values,values+10);       // erste 10 Elemente umdrehen
...

Für andere Datenstrukturen ist es in der Regel notwendig, eine eigene Iteratorklasse zu bauen. Dazu finden sich im Kapitel 3.2 weitere Informationen.

per Wrapper

Etwas stärker ist die Kopplung, wenn um eine bestehende Containerstruktur eine Wrapper-Klasse aufgebaut wird, die die wichtigsten Methoden für STL-Container (z.B. begin(), end(), size(), etc.) implementiert und in Aufrufe der Container-eigenen Methoden übersetzt. Auf diese Weise ließe sich ein STL-Interface um ein Array oder ein Datenbanksystem herum aufbauen.

//Beispiel: Array-Wrapper
template<typename T,size_t N>
class CArray
{
  T vals[N];
public:
  typedef T        value_type;
  typedef T*       iterator;
  typedef const T* const_iterator;
  ...//eventuell einige weitere typedef's

  //Iterator-Erzeugung:
  iterator begin()                  {return vals;}
  const_iterator begin() const      {return vals;}
  iterator end()                    {return vals+N;}
  const_iterator end() const        {return vals+N;}

  //Größe:
  size_t size() const               {return N;}

  //Elementzugriff:
  T& operator[] (int j)             {return vals[j];}
  const T& operator[] (int j) const {return vals[j];}

  //Umwandlung in Array:
  T* as_array()                     {return vals;}
}

invasiv

Die aufwendigste Methode besteht darin, die eigene Containerklasse von Anfang an so zu konzipieren, dass sie ein mehr oder weniger vollständiges STL-Interface bereitstellt. Dieser Ansatz wurde z.B. verwendet, als die string-Klasse entworfen wurde.

3.2 Eigene Iteratoren

Da die gesamte STL auf Templates aufbaut, ist der Entwurf eines neuen Iterators eigentlich recht einfach - alles, was sich wie ein Iterator verhält, ist ein Iterator (und alles, was die Operationen bereitstellt, die von einem Algorithmus verwendet werden, kann diesem Algorithmus übergeben werden).

Als Unterstützung für den Entwickler gibt es trotzdem eine Protokollklasse iterator, die als Basis für eigene Iteratoren verwendet werden kann:

template<typename Cat,typename T,typename Diff=ptrdiff_t,typename Ptr=T*,typename Ref=T&>
struct std::iterator;

struct output_iterator_tag {};
struct input_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

Diese Klasse definiert lediglich die Datentypen, die für die Arbeit mit den iterator_traits benötigt werden.

Die leeren Hilfsklassen (..._tag) können als Parameter 'Cat' verwendet werden und kennzeichnen die Einordnung des eigenen Iteratortyps in eine der Kategorien (siehe Teil 2 der Artikelserie). Die für diese Kategorie nötigen Operationen müssen allerdings selbst bereitgestellt werden. Diese Klassen sind voneinander abgeleitet, um die Austauschbarkeit der einzelnen Kategorien darzustellen - zum Beispiel kann jeder Random-Access-Iterator auch als Input-Iterator genutzt werden.

Achtung: Die Klasse forward_iterator_tag ist nicht von output_iterator_tag abgeleitet, weil Forward-Iteratoren nicht vollständig äquivalent zu Output-Iteratoren sind (siehe Kapitel 2.3 im zweiten Teil der Serie).

Ein Beispiel für eigene Iteratoren wäre ein Spezial-Inserter für assoziative Container. Im Gegensatz zum Inserter der STL benötigt diese Variante keine Einfügeposition und kann dadurch eventuell schneller arbeiten (insert() mit der falschen Zielposition ist üblicherweise langsamer als ein insert() ohne vorgegebene Position):

template<typename Cont>
class ainsert_iterator : public iterator<output_iterator_tag,void,void,void,void>
{
protected:
  Cont& container;
public:
  explicit ainsert_iterator(Cont& c) : container(c) {}

  // Wertzuweisung *it=x
  ainsert_iterator& operator=(const typename Cont::value_type& val)
  {
    container.insert(val);
    return *this;
  }

  //Dereferenzierung
  ainsert_iterator& operator*() {return *this;}

  //Inkrement
  ainsert_iterator& operator++() {return *this;}
  ainsert_iterator& operator++(int) {return *this;}
};

template<typename Cont>
inline ainsert_iterator<Cont> asso_inserter(Cont& c)
{ return ainsert_iterator<Cont>(c); }

operator* und operator= stellen den üblichen Weg dar, mit dem bei einem Output-Iterator die Wertzuweisung realisiert wird. "Höherwertige" Iteratorklassen liefern dagegen meistens eine Referenz auf ihren Elementtyp oder eine Pseudo-Referenz zurück, wenn sie dereferenziert werden.

Folgende Operatoren werden benötigt, um eine vollwertige Iteratorklasse zu erzeugen:

Operator                                   Bedeutung               Kategorien

Iter::Iter(const Iter&)                    Kopierkonstruktor       OIFBR
Iter& Iter::operator=(const Iter&)         Zuweisung                 FBR

Ref Iter::operator*()                      Dereferenzierung        OIFBR
Ptr Iter::operator->()                     Memberzugriff            IFBR
Ref Iter::operator[](Diff)                 Indexzugriff                R

Iter& Iter::operator++()                   Inkrement (Präfix)      OIFBR
Iter Iter::operator++(int)                 Inkrement (Postfix)     OIFBR
Iter& Iter::operator--()                   Dekrement (Präfix)         BR
Iter Iter::operator--(int)                 Dekrement (Postfix)        BR
Iter& Iter::operator+=(Diff)               Inkrement (n Schritte)      R
Iter& Iter::operator-=(Diff)               Dekrement (n Schritte)      R
Iter operator+(Diff,const Iter&)           n't nächste Position        R
Iter operator+(const Iter&,Diff)           n't nächste Position        R
Iter operator-(const Iter&,Diff)           n't vorige Position         R
Diff operator-(const Iter&, const Iter&)   Abstand                     R

bool operator==(const Iter&,const Iter&)   Vergleich (gleich)       IFBR
bool operator!=(const Iter&,const Iter&)   Vergleich (ungleich)     IFBR
bool operator [i]x[/i](const Iter&,const Iter&)   Vergleich (<,<=,>=,>)       R

Dabei ist "Ref" eine Referenz auf den Elementtyp oder eine Klasse, die entsprechende Funktionalität zur Verfügung stellt (für Output-Iteratoren wird ein operator=(T) benötigt, für alle anderen Kategorien auch Elementzugriff und eine Umwandlung nach T), "Ptr" ein Pointer oder Smart-Pointer auf den Elementtyp (benötigt auf jeden Fall einen operator->()) und "Diff" der Differenztyp des Iterators (normalerweise ein vorzeichenbehafteter Ganzzahltyp).

3.3 Eigene Algorithmen

In der Regel ist der schwierigste Teil der Algorithmenentwicklung die Frage, was der Algorithmus eigentlich machen soll. Wenn die Arbeitsweise feststeht, kann der Algorithmus vorübergehend auf einem int-Array implementiert werden.

Wenn feststeht, dass der Algorithmus korrekt funktioniert, kann er in eine Template-Funktion umgewandelt werden, indem alle Vorkommen von 'int*' durch den Template-Parameter 'It' und alle Vorkommen von 'int' (außer Zählvariablen) durch 'typename iterator_traits<It>::value_type' oder einen eigenen Template-Parameter ersetzt werden.

//Ausgangspunkt:
int* worker(int* data, size_t len,...)
{
  ...
}

//Zwischenschritt: Start+Länge -> Start+Ende
int* worker(int* beg, int* end,...)
{
  //ersetze len durch end-beg
  ...
}

//Ergebnis: Template-Funktion
template<typename It,...>
It worker(It beg, It end,...)
{
  typedef typename iterator_traits<It>::value_type val;
  //ersetze int* durch It und int durch val
}

Anmerkung: Wenn möglich, sollten für die Arbeit die Hilfsfunktionen advance() statt Iterator-Addition, difference() statt Iterator-Subtraktion und swap() oder iter_swap() statt Elementaustausch verwendet werden.

Ein Beispiel für einen eigenen Algorithmus wäre eine Funktion, die alle Duplikate aus einer unsortierten Datensammlung entfernt:

//als Quellbereich wird ein Forward-Iterator benötigt, weil Input-Iteratoren nicht sicher kopiert werden können
template<typename FwdIt,typename OutIt>
OutIt unsorted_unique_copy(FwdIt sbeg,FwdIt send,OutIt dbeg)
{
  for(FwdIt pos=sbeg;pos!=send;++pos)
    if(find(sbeg,pos,*pos)==pos) *dbeg++ = *pos;
  return dbeg;
}

template<typename FwdIt>
FwdIt unsorted_unique(FwdIt beg,FwdIt end)
{
  return unsorted_unique_copy(beg,end,beg);
}

Um den Algorithmen die Arbeit zu erleichtern, existiert eine Hilfsklasse "iterator_traits", die einige Typdefinitionen für einen Iterator enthält:

template<typename It>
struct iterator_traits
{
  typedef typename It::value_type        value_type;        // Werttyp
  typedef typename It::iterator_category iterator_category; // Kategorie: Output, Input,...
  typedef typename It::difference_type   difference_type;   // Differenz zwischen Iteratoren
  typedef typename It::pointer           pointer;           // Zeiger auf T
  typedef typename It::reference         reference          // Referenz auf T
};

Die Typdefinitionen dieser Klasse können verwendet werden, um z.B. den Typ einer temporären Variablen passend zum Iterator festzulegen.

template<typename Iter>
void foo_alg(Iter beg,Iter end)
{
  if(beg==end) return;
  typename iterator_traits<Iter>::value_type temp=*beg;
  ...
}

template<typename Iter>
void bar_alg(Iter beg,Iter end)
{
  typename iterator_traits<Iter>::difference_type dist=distance(beg,end);
  ...
}

Die Kategorie des Iterators kann genutzt werden, um einen Algorithmus so zu optimieren, dass er die "besten" Operationen des Iterator-Typs verwendet:

//"öffentliche Version":
//wird vom Nutzer aufgerufen und delegiert die Arbeit weiter
template<typename Iter>
Iter algo(Iter beg,Iter end)
{ return algo(beg,end,iterator_traits<Iter>::iterator_category()); }

//Version für Random Access Iteratoren:
//nutzt die komplette Vielfalt der Iterator-Arithmetik
template<typename RanIt>
RanIt algo(RanIt beg,RanIt end,random_access_iterator_tag)
{
  ...
}

//Version für andere Typen:
//nutzt nur Inkrement-Operator
template<typename InIt>
InIt algo(InIt beg,InIt end,input_iterator_tag)
{
  ...
}

Dank der Vererbungsbeziehung zwischen den Tag-Klassen wird die zweite Version des Algorithmus' auch von Forward- und Bidirektionalen Iteratoren verwendet.

Außer der allgemeinen Version der iterator_traits - die alle benötigten Typdefinitionen in der instanziierten Klasse voraussetzt - gibt es noch Spezialisierungen für Pointer und const-Pointer. Iterator-Klassen, die die benötigten Typen nicht selber bereitstellen können oder wollen - z.B. weil sie aus einer fremden Bibliothek integriert wurden - , dürfen ebenfalls eine Spezialisierung der iterator_traits anlegen.

Anmerkung: Wenn ein eigener Iterator von der Hilfsklasse iterator<> abgeleitet wird (siehe Kapitel 3.2), stellt er automatisch alle nötigen Typdefinitionen für die Iterator-Traits bereit.

3.4 eigene Funktoren

Als Funktor kann theoretisch jede Klasse verwendet werden, die den operator() überladen hat. Für die Zusammenarbeit mit den STL-Funktor-Adaptern ist es jedoch notwendig, die Argument- und Rückgabetypen des eigenen operator() anzugeben. Diese Arbeit können die Protokollklassen unary_function und binary_function für den Entwickler übernehmen:

//Functor: Res f(Arg x);
template<typename Arg,typename Res>
struct unary_function;

//Functor: Res f(Arg1 x,Arg2 y);
template<typename Arg1,typename Arg2,typename Res>
struct binary_function;

Ein Beispiel für einen selbst definierten Funktor ist die mean-Klasse, die ich in Teil 2 vorgestellt habe. Ein anderes Beispiel wäre ein Composer, der mehrere Funktionen zusammenfassen kann (entsprechende Klassen gibt es z.B. in der Boost-Bibliothek):

//c(x,y) = f(g(x),h(y))
template<typename Op1,typename Op2,typename Op3>
class compose_f_gx_hy_t : public binary_function<typename Op2::argument_type,
                                                 typename Op3::argument_type,
                                                 typename Op1::result_type>
{
  Op1 op1;
  Op2 op2;
  Op3 op3;
public:
  compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
  : op1(f), op2(g), op3(h)
  {}

  typename Op1::result_type
  operator() (const typename Op2::argument_type& x,const typename Op3::argument_type& y)
  { return op1(op2(x),op3(y)); }
};

//Hilfsfunktion zur Erzeugung eines Composers
template<typename Op1,typename Op2,typename Op3>
inline compose_f_gx_hy_t<Op1,Op2,Op3>
compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
{ return compose_f_gx_hy_t<Op1,Op2,Op3>(f,g,h); }

Anmerkung: Analog dazu lassen sich alle Kombinationen aus unären und binären Funktionen mit geeigneten Composern darstellen.

4. weitere Informationen

C++ Referenz

The C++ Standard Library | ISBN: 0201379260 - Nicolai M. Josuttis - The C++ Standard Library
Die C++-Standardbibliothek | ISBN: 3540256938 - Stefan Kuhlins, Martin Schrader - Die C++ Standardbibliothek[/quote]

[Mr. B]

Unter Punkt 3.3 gibbet ein Wort namens "instanziieren".
Ich glaube aber, du meintest eher "instanzieren", oder?

Ich war mir aber nicht sicher, deshalb hab ichs mal so gelassen. Also schau, was du damit machst

Mr. B

[CStoll]

Neben den Hauptbestandteilen der STL - Container, Iteratoren und Algorithmen - existieren in der Standardbibliothek von C++ noch etliche weitere Klassen, die von versierten Programmierern genutzt werden können. Einige davon arbeiten auch unmittelbar mit der STL zusammen. Im letzten Teil meiner Serie will ich einen kurzen Überblick über diese Klassen geben. Außerdem gehe ich darauf ein, wie die Funktionalitäten der STL vom Programmierer erweitert werden können.

Inhalt

1. weitere Klassen
2. Fehlerbehandlung
3. Erweiterungsmöglichkeiten
4. weitere Informationen

1 weitere Klassen

Als Ergänzung zu den obigen Klassen gibt es noch einige kleinere Hilfsklassen in der C++-Bibliothek. Diese werden teilweise von den STL-Elementen genutzt, können aber auch allein stehend eingesetzt werden.

1.1 pair

voller Name:

template<typename FT,typename ST>
struct std::pair;

template<typename FT,typename ST>
pair<FT,ST> make_pair(const FT&,const ST&);

Header:

include <utility>

Ein Pair (Paar) ist eine einfache Struktur, die zwei Elemente von verschiedenen Typen miteinander kombinieren kann. Diese Klasse wird unter anderem von Maps und Multimaps genutzt, um die Schlüssel-Wert-Paare zusammenzufassen. Außerdem ermöglichen sie es einer Funktion, zwei Werte gemeinsam zurückzugeben. Die letzte Möglichkeit wird auch von einigen Funktionen der STL genutzt, die mehrere Werte zusammen zurückgeben wollen, unter anderem equal_range() (gibt den Zielbereich des gesuchten Wertes als Paar zurück) und der insert()-Methode von Set und Map (diese gibt ein Paar aus einem Iterator und einem bool zurück, der angibt, ob insert() das Element einfügen konnte).

Die beiden Teile des Paares können direkt über "p.first" bzw. "p.second" angesprochen und modifiziert werden. Außerdem können Paare verschiedener Typen einander zugewiesen werden, solange ihre Elementtypen ineinander umgewandelt werden können.

Die Hilfsfunktion make_pair() ist die schnellste Möglichkeit, zwei Werte zu einem pair zusammenzufassen - sie ist zum Beispiel hilfreich, um Werte in eine (Multi-)Map einzufügen.

1.2 Funktoren

Header:

#include <functional>

Funktoren sind Objekte, die den Operator () überladen haben. Dadurch können sie wie normale Funktionen genutzt werden. Gegenüber einer normalen Funktion haben sie jedoch einige deutliche Vorteile:

• sie können einen internen Status haben - und zwar in verschiedenen Exemplaren unabhängig voneinander.
• sie haben einen eigenen Typ und können deshalb auch als Template-Parameter an STL-Container weitergegeben werden.

Die C++-Bibliothek bietet unter anderem Binder, mit deren Hilfe ein Parameter einer binären Funktion festgelegt werden kann, Wrapperklassen für normale Funktionen und Klassenmethoden und vordefinierte Funktoren für viele C++-Operatoren (zu diesen gehört auch die Klasse less<>, die als Standard-Ordnungskriterium von Sets und Maps verwendet wird).

In der STL werden Funktoren als Vergleichskriterium für assoziative Container und Priority-Queues und als optionale Arbeitsfunktionen für die meisten Algorithmen verwendet.

Zum Beispiel lassen sich die vordefinierten Funktor-Adapter verwenden, um alle Elemente eines Containers mit einem festen Wert zu potenzieren:

vector<double> data;
...
transform(data.begin(),data.end(),bind2nd(ptr_fun(pow),3));
/* Kombination zweier Funktor-Adapter:
  bind2nd - legt den zweiten Parameter eines binären Funktors fest
  ptr_fun - wrappt eine "normale" Funktion in einen Funktor
*/

1.3 Streams

Die Stream-Klassen wurden als Ersatz für die printf()- und scanf()-Familie der C-Standardbibliothek eingeführt. Sie bieten eine typsichere und erweiterbare Möglichkeit, Daten formatiert ein- und auszulesen. Dazu überladen sie die Operatoren << und >>, mit deren Hilfe alle eingebauten Datentypen von C++ aus- bzw. eingegeben werden können.

Entwickler können ihre eigenen Klassen mit demselben Mechanismus verarbeiten, indem sie die geeigneten Operatoren überladen.

Die Ein- und Ausgabe über Streams werde ich in einem späteren Artikel behandeln.
~wird ersetzt durch:~
Die Ein- und Ausgabe über Streams behandelt der Artikel "Ein- und Ausgabe in C++".

1.4 Locales und Facetten

Locales und Facetten dienen zur Internationalisierung der Ein- und Ausgabe-Operationen und werden sehr intensiv von den IO-Streams verwendet. Eine Facette modelliert einen bestimmten Aspekt der Ein/Ausgabe, wie zum Beispiel die Darstellung von Zahlen oder die Sortierung von landesspezifischen Sonderzeichen (z.B. Umlaute), ein Locale fasst Facetten für alle Einsatzbereiche zu einer Einheit zusammen.

Im Gegensatz zu C, wo nur ein Locale für alle Ein/Ausgabe-Operationen festgelegt werden konnte, kann in C++ jeder Stream sein eigenes Locale übergeben bekommen und verwalten.

1.5 komplexe Zahlen

voller Name:

template<typename T>
class std::complex;

Header:

#include <complex>

Die Klasse complex dient zur Verwendung und Berechnung komplexer Zahlen. Komplexe Zahlen können aus einer reellen Zahl (als Realteil) oder aus zwei reellen Werten (Realteil und Imaginärteil) konstruiert werden. Außerdem sind viele mathematische Operationen und Funktionen (z.B. Potenzen, Logarithmus, Winkelfunktionen,...) für komplexe Zahlen definiert.

Die Standardbibliothek definiert außer der allgemeinen Klasse complex<> auch Spezialisierungen für alle Gleitkommatypen (float, double und long double).

1.6 Valarrays

voller Name:

template<typename T>
class std::valarray;

class slice;  //eindimensionaler "Streifen" aus dem Valarray
class gslice; //mehrdimensionaler "Streifen"

Header:

#include <valarray>

Valarrays sind eine spezielle Form von Containern, die für parallele mathematische Operationen entwickelt wurden. Sie implementieren viele mathematische Operationen und Funktionen so, dass sie parallel auf alle Elemente angewendet werden.

//operator[] (slice)
template<typename T>class std::slice_array;
//operator[] (glice)
template<typename T>class std::gslice_array;
//operator[] (valarray<bool>)
template<typename T>class std::mask_array;
//operator[] (valarray<size_t>)
template<typename T>class std::indirect_array;

Diese Hilfsklassen können nicht direkt erzeugt werden. Sie entstehen bei speziellen Indexoperationen aus einem Valarray und bieten Zugriff auf bestimmte Teile des Arrays. Jede der vier Klassen entspricht einer bestimmten Methode zur Definition des Teilbereiches. Ein Teilarray kann genutzt werden, um eine mathematische Operation nur auf einem Teil der Elemente auszuführen, z.B. nur auf allen geraden Zahlen oder auf jedem vierten Element.

1.7 Bitsets

voller Name:

template<size_t N>
class std::bitset;

Header:

#include <bitset>

Bitsets werden zur Verwaltung von Einzelbits verwendet. Im Gegensatz zu einem vector<bool> steht die Größe des Bitsets bereits zur Compilezeit fest.

Ein Bitset kann zum Beispiel verwendet werden, um eine fixe Gruppe von Flags Platz sparend unterzubringen. Außerdem können sie auch zur Umwandlung von Zahlen in bzw. aus einer Binärdarstellung genutzt werden. Dafür existieren Konstruktoren und Umwandlungsoperatoren sowohl für ganze Zahlen (unsigned long) als auch für Strings (Binärdarstellung).

#include <bitset>
#include <iostream>
#include <limits> //numeric_limits

int main()
{
  //Dezimal nach Binär:
  cout<<"4711 = "<< bitset<numeric_limits<int>::digits>(4711)<<endl;

  //Binär nach Dezimal
  cout<<"1011010110 = "<<bitset<10>(string("1011010110")).to_ulong()<<endl;
  //Achtung: Eine direkte Umwandlung von char* nach bitset ist afaik nicht erlaubt
}

1.8 Auto-Pointer

voller Name:

template<typename T>
class auto_ptr;

Header:

#include <memory>

Die Klasse auto_ptr ist (leider) die einzige Smart-Pointer-Klasse, die im aktuellen C++-Standard vorgesehen ist. Auto-Pointer sorgen dafür, dass ein von ihnen verwaltetes Heap-Objekt automatisch gelöscht wird, wenn sie ihren Scope verlassen. Dazu stellen sie sicher, dass immer genau ein Auto-Pointer auf dieses Objekt verweist - eine Zuweisung zwischen Auto-Pointern entzieht dem Ursprungspointer den Besitz und setzt ihn auf NULL zurück.

Achtung: Auto-Pointer sind nicht dazu geeignet, Heap-Objekte an mehreren Stellen im Programm gemeinsam zu nutzen. Für diesen Zweck sind Smart-Pointer mit Referenzzählung (z.B. Boost::shared_ptr - siehe "Schlaue Pointer" im Magazin) besser geeignet.
Mit dem Technical Report TR1 wurden diese Smart-Pointer übrigens in den Standard aufgenommen.

Achtung: Da die Containerklassen der STL ihre Elemente bei Bedarf kopieren dürfen, sind Auto-Pointer NICHT zum Einsatz in STL-Containern geeignet.

1.9 Exception-Klassen

Header:

#include <stdexcept>
#include <exception> //ecxeption (Basisklasse) und bad_exception
#include <new>       //bad_alloc
#include <typeinfo>  //bad_cast und bad_typeid
#include <ios>       //ios_base::failure

Die Exception-Klassen wurden zur Unterstützung der Exception-Verarbeitung in C++ (try/catch) entworfen. Sie bieten eine eigene Hierarchie von verschiedenen Klassen, die je nach auftretender Fehlersituation verwendet werden können, sowie eine einheitliche Schnittstelle. Auf diese Weise lassen sich auch komplette Kategorien von Fehlern (z.B. alle logischen Fehler) oder sogar alle "Beschwerden" der Standardbibliothek mit einer einzigen catch-Klausel abfangen und auswerten:

try
{
  //etliche Operationen, die Probleme bereiten könnten
}
catch(std::exception& e)
{
  //hier landen alle Standard-Exceptions:
  cerr<<"Wir haben einen Fehler: "<<e.what()<<endl;
}

Die Basisklasse 'exception' definiert zur Fehlerauswertung eine virtuelle Methode what(), mit der die Fehlerursache erfragt werden kann - diese liefert für alle abgeleiteten Klassen einen implementationsspezifischen C-String (const char*). Weitere Zugriffsmöglichkeiten sind jedoch nicht vorgesehen.

In der Standardbibliothek sind folgende Exception-Klassen definiert:

Klasse             Basis          Verwendung

exception          -              Basis für alle Exception-Klassen
bad_alloc          exception      Fehler in new
bad_cast           exception      Fehler in dynamic_cast (Referenzen)
bad_typeid         exception      Fehler bei typeid Operator
ios_base::failure  exception      Fehler bei IO-Streams
bad_exception      exception      throw() Spezifikation umgangen

logic_error        exception      Logische Fehler (könnten vom Programm umgangen werden)
domain_error       logic_error    Domain-Fehler
invalid_argument   logic_error    ungültiges Argument (z.B. "0012" an bitset-Ctor)
length_error       logic_error    Maximallänge überschritten
out_of_range       logic_error    Bereichsüberschreitungen (z.B. bei vector::at())

runtime_error      exception      Laufzeitfehler (i.d.R. nicht abfangbar)
range_error        runtime_error  interner Bereichsfehler
overflow_error     runtime_error  arithmetischer Überlauf
underflow_error    runtime_error  arithmetischer Unterlauf

2 Fehlerbehandlung

Die meisten Methoden und Funktionen der STL sind so entworfen, dass sie möglichst beste Performance bieten. Deshalb wird größtenteils darauf verzichtet, Falscheingaben abzufangen. Wer ungültige Parameter, wie zum Beispiel einen ungültigen Iterator-Bereich, an einen STL-Algorithmus übergibt, erhält im Allgemeinen undefiniertes Verhalten.

Die einzige Funktion der STL, die wirklich ihre Eingabewerte auf Gültigkeit prüft, ist die Methode at() von vector<> und deque<> - diese wirft eine out_of_range Exeption, wenn sie mit einem ungültigen Index aufgerufen wird. In anderen Komponenten der C++-Standard-Bibliothek (z.B. in der string-Klasse oder bei den IO-Streams) erfolgt dagegen eine gründlichere Fehlerkontrolle.

Im Falle einer extern auftretenden Exception (z.B. in den Prädikaten, die an einen Algorithmus übergeben wurden) bieten alle Bestandteile der STL die Garantie, keine Speicherlecks zu produzieren und in einen "sicheren" Zustand zu wechseln. Einige der Container-Operationen bieten darüber hinaus eine "Commit-or-Rollback"-Garantie - entweder die Operation wird erfolgreich durchgeführt oder der Container bleibt unverändert. Andere Operationen gelingen garantiert (solange die Destruktoren der beteiligten Objekte keine Exceptions werfen können).

3 Erweiterungsmöglichkeiten

Die gesamte STL ist nach dem open-closed-Prinzip aufgebaut - offen für Erweiterungen, geschlossen für Modifikationen. Die existierenden Bestandteile der STL sollten als gegeben vorausgesetzt werden, können jedoch problemlos mit eigenen Klassen und Funktionen kombiniert werden
(theoretisch ist es auch möglich, in den STL-Headern rumzupfuschen, aber ich rate dringend davon ab).

3.1. Eigene Container

Um eine eigene Containerklasse für die Zusammenarbeit mit der STL vorzubereiten, gibt es drei mögliche Ansätze:

direkt

Der einfachste Weg, einen Container STL-tauglich zu machen, ist es, einen passenden Iterator für den Container zu finden oder zu definieren und diese Iteratoren den STL-Algorithmen zur Verfügung zu stellen. So dienen zum Beispiel blanke Pointer als "Iterator" für C-Arrays:

int values[100];
generate(values,values+100,rand);// füllen mit Zufallszahlen
sort(values,values+100);         // gesamtes Array sortieren
reverse(values,values+10);       // erste 10 Elemente umdrehen
...

Für andere Datenstrukturen ist es in der Regel notwendig, eine eigene Iteratorklasse zu bauen. Dazu finden sich im Kapitel 3.2 weitere Informationen.

per Wrapper

Etwas stärker ist die Kopplung, wenn um eine bestehende Containerstruktur eine Wrapper-Klasse aufgebaut wird, die die wichtigsten Methoden für STL-Container (z.B. begin(), end(), size(), etc.) implementiert und in Aufrufe der Container-eigenen Methoden übersetzt. Auf diese Weise ließe sich ein STL-Interface um ein Array oder ein Datenbanksystem herum aufbauen.

//Beispiel: Array-Wrapper
template<typename T,size_t N>
class CArray
{
  T vals[N];
public:
  typedef T        value_type;
  typedef T*       iterator;
  typedef const T* const_iterator;
  ...//eventuell einige weitere typedef's

  //Iterator-Erzeugung:
  iterator begin()                  {return vals;}
  const_iterator begin() const      {return vals;}
  iterator end()                    {return vals+N;}
  const_iterator end() const        {return vals+N;}

  //Größe:
  size_t size() const               {return N;}

  //Elementzugriff:
  T& operator[] (int j)             {return vals[j];}
  const T& operator[] (int j) const {return vals[j];}

  //Umwandlung in Array:
  T* as_array()                     {return vals;}
}

invasiv

Die aufwendigste Methode besteht darin, die eigene Containerklasse von Anfang an so zu konzipieren, dass sie ein mehr oder weniger vollständiges STL-Interface bereitstellt. Dieser Ansatz wurde z.B. verwendet, als die string-Klasse entworfen wurde.

3.2 Eigene Iteratoren

Da die gesamte STL auf Templates aufbaut, ist der Entwurf eines neuen Iterators eigentlich recht einfach - alles, was sich wie ein Iterator verhält, ist ein Iterator (und alles, was die Operationen bereitstellt, die von einem Algorithmus verwendet werden, kann diesem Algorithmus übergeben werden).

Als Unterstützung für den Entwickler gibt es trotzdem eine Protokollklasse iterator, die als Basis für eigene Iteratoren verwendet werden kann:

template<typename Cat,typename T,typename Diff=ptrdiff_t,typename Ptr=T*,typename Ref=T&>
struct std::iterator;

struct output_iterator_tag {};
struct input_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

Diese Klasse definiert lediglich die Datentypen, die für die Arbeit mit den iterator_traits benötigt werden.

Die leeren Hilfsklassen (..._tag) können als Parameter 'Cat' verwendet werden und kennzeichnen die Einordnung des eigenen Iteratortyps in eine der Kategorien (siehe Teil 2 der Artikelserie). Die für diese Kategorie nötigen Operationen müssen allerdings selbst bereitgestellt werden. Diese Klassen sind voneinander abgeleitet, um die Austauschbarkeit der einzelnen Kategorien darzustellen - zum Beispiel kann jeder Random-Access-Iterator auch als Input-Iterator genutzt werden.

Achtung: Die Klasse forward_iterator_tag ist nicht von output_iterator_tag abgeleitet, weil Forward-Iteratoren nicht vollständig äquivalent zu Output-Iteratoren sind (siehe Kapitel 2.3 im zweiten Teil der Serie).

Ein Beispiel für eigene Iteratoren wäre ein Spezial-Inserter für assoziative Container. Im Gegensatz zum Inserter der STL benötigt diese Variante keine Einfügeposition und kann dadurch eventuell schneller arbeiten (insert() mit der falschen Zielposition ist üblicherweise langsamer als ein insert() ohne vorgegebene Position):

template<typename Cont>
class ainsert_iterator : public iterator<output_iterator_tag,void,void,void,void>
{
protected:
  Cont& container;
public:
  explicit ainsert_iterator(Cont& c) : container(c) {}

  // Wertzuweisung *it=x
  ainsert_iterator& operator=(const typename Cont::value_type& val)
  {
    container.insert(val);
    return *this;
  }

  //Dereferenzierung
  ainsert_iterator& operator*() {return *this;}

  //Inkrement
  ainsert_iterator& operator++() {return *this;}
  ainsert_iterator& operator++(int) {return *this;}
};

template<typename Cont>
inline ainsert_iterator<Cont> asso_inserter(Cont& c)
{ return ainsert_iterator<Cont>(c); }

operator* und operator= stellen den üblichen Weg dar, mit dem bei einem Output-Iterator die Wertzuweisung realisiert wird. "Höherwertige" Iteratorklassen liefern dagegen meistens eine Referenz auf ihren Elementtyp oder eine Pseudo-Referenz zurück, wenn sie dereferenziert werden.

Folgende Operatoren werden benötigt, um eine vollwertige Iteratorklasse zu erzeugen:

Operator                                   Bedeutung               Kategorien

Iter::Iter(const Iter&)                    Kopierkonstruktor       OIFBR
Iter& Iter::operator=(const Iter&)         Zuweisung                 FBR

Ref Iter::operator*()                      Dereferenzierung        OIFBR
Ptr Iter::operator->()                     Memberzugriff            IFBR
Ref Iter::operator[](Diff)                 Indexzugriff                R

Iter& Iter::operator++()                   Inkrement (Präfix)      OIFBR
Iter Iter::operator++(int)                 Inkrement (Postfix)     OIFBR
Iter& Iter::operator--()                   Dekrement (Präfix)         BR
Iter Iter::operator--(int)                 Dekrement (Postfix)        BR
Iter& Iter::operator+=(Diff)               Inkrement (n Schritte)      R
Iter& Iter::operator-=(Diff)               Dekrement (n Schritte)      R
Iter operator+(Diff,const Iter&)           n't nächste Position        R
Iter operator+(const Iter&,Diff)           n't nächste Position        R
Iter operator-(const Iter&,Diff)           n't vorige Position         R
Diff operator-(const Iter&, const Iter&)   Abstand                     R

bool operator==(const Iter&,const Iter&)   Vergleich (gleich)       IFBR
bool operator!=(const Iter&,const Iter&)   Vergleich (ungleich)     IFBR
bool operator [i]x[/i](const Iter&,const Iter&)   Vergleich (<,<=,>=,>)       R

Dabei ist "Ref" eine Referenz auf den Elementtyp oder eine Klasse, die entsprechende Funktionalität zur Verfügung stellt (für Output-Iteratoren wird ein operator=(T) benötigt, für alle anderen Kategorien auch Elementzugriff und eine Umwandlung nach T), "Ptr" ein Pointer oder Smart-Pointer auf den Elementtyp (benötigt auf jeden Fall einen operator->()) und "Diff" der Differenztyp des Iterators (normalerweise ein vorzeichenbehafteter Ganzzahltyp).

3.3 Eigene Algorithmen

In der Regel ist der schwierigste Teil der Algorithmenentwicklung die Frage, was der Algorithmus eigentlich machen soll. Wenn die Arbeitsweise feststeht, kann der Algorithmus vorübergehend auf einem int-Array implementiert werden.

Wenn feststeht, dass der Algorithmus korrekt funktioniert, kann er in eine Template-Funktion umgewandelt werden, indem alle Vorkommen von 'int*' durch den Template-Parameter 'It' und alle Vorkommen von 'int' (außer Zählvariablen) durch 'typename iterator_traits<It>::value_type' oder einen eigenen Template-Parameter ersetzt werden.

//Ausgangspunkt:
int* worker(int* data, size_t len,...)
{
  ...
}

//Zwischenschritt: Start+Länge -> Start+Ende
int* worker(int* beg, int* end,...)
{
  //ersetze len durch end-beg
  ...
}

//Ergebnis: Template-Funktion
template<typename It,...>
It worker(It beg, It end,...)
{
  typedef typename iterator_traits<It>::value_type val;
  //ersetze int* durch It und int durch val
}

Anmerkung: Wenn möglich, sollten für die Arbeit die Hilfsfunktionen advance() statt Iterator-Addition, difference() statt Iterator-Subtraktion und swap() oder iter_swap() statt Elementaustausch verwendet werden.

Ein Beispiel für einen eigenen Algorithmus wäre eine Funktion, die alle Duplikate aus einer unsortierten Datensammlung entfernt:

//als Quellbereich wird ein Forward-Iterator benötigt, weil Input-Iteratoren nicht sicher kopiert werden können
template<typename FwdIt,typename OutIt>
OutIt unsorted_unique_copy(FwdIt sbeg,FwdIt send,OutIt dbeg)
{
  for(FwdIt pos=sbeg;pos!=send;++pos)
    if(find(sbeg,pos,*pos)==pos) *dbeg++ = *pos;
  return dbeg;
}

template<typename FwdIt>
FwdIt unsorted_unique(FwdIt beg,FwdIt end)
{
  return unsorted_unique_copy(beg,end,beg);
}

Um den Algorithmen die Arbeit zu erleichtern, existiert eine Hilfsklasse "iterator_traits", die einige Typdefinitionen für einen Iterator enthält:

template<typename It>
struct iterator_traits
{
  typedef typename It::value_type        value_type;        // Werttyp
  typedef typename It::iterator_category iterator_category; // Kategorie: Output, Input,...
  typedef typename It::difference_type   difference_type;   // Differenz zwischen Iteratoren
  typedef typename It::pointer           pointer;           // Zeiger auf T
  typedef typename It::reference         reference          // Referenz auf T
};

Die Typdefinitionen dieser Klasse können verwendet werden, um z.B. den Typ einer temporären Variablen passend zum Iterator festzulegen.

template<typename Iter>
void foo_alg(Iter beg,Iter end)
{
  if(beg==end) return;
  typename iterator_traits<Iter>::value_type temp=*beg;
  ...
}

template<typename Iter>
void bar_alg(Iter beg,Iter end)
{
  typename iterator_traits<Iter>::difference_type dist=distance(beg,end);
  ...
}

Die Kategorie des Iterators kann genutzt werden, um einen Algorithmus so zu optimieren, dass er die "besten" Operationen des Iterator-Typs verwendet:

//"öffentliche Version":
//wird vom Nutzer aufgerufen und delegiert die Arbeit weiter
template<typename Iter>
Iter algo(Iter beg,Iter end)
{ return algo(beg,end,iterator_traits<Iter>::iterator_category()); }

//Version für Random Access Iteratoren:
//nutzt die komplette Vielfalt der Iterator-Arithmetik
template<typename RanIt>
RanIt algo(RanIt beg,RanIt end,random_access_iterator_tag)
{
  ...
}

//Version für andere Typen:
//nutzt nur Inkrement-Operator
template<typename InIt>
InIt algo(InIt beg,InIt end,input_iterator_tag)
{
  ...
}

Dank der Vererbungsbeziehung zwischen den Tag-Klassen wird die zweite Version des Algorithmus' auch von Forward- und Bidirektionalen Iteratoren verwendet.

Außer der allgemeinen Version der iterator_traits - die alle benötigten Typdefinitionen in der instanzierten Klasse voraussetzt - gibt es noch Spezialisierungen für Pointer und const-Pointer. Iterator-Klassen, die die benötigten Typen nicht selber bereitstellen können oder wollen - z.B. weil sie aus einer fremden Bibliothek integriert wurden - , dürfen ebenfalls eine Spezialisierung der iterator_traits anlegen.

Anmerkung: Wenn ein eigener Iterator von der Hilfsklasse iterator<> abgeleitet wird (siehe Kapitel 3.2), stellt er automatisch alle nötigen Typdefinitionen für die Iterator-Traits bereit.

3.4 eigene Funktoren

Als Funktor kann theoretisch jede Klasse verwendet werden, die den operator() überladen hat. Für die Zusammenarbeit mit den STL-Funktor-Adaptern ist es jedoch notwendig, die Argument- und Rückgabetypen des eigenen operator() anzugeben. Diese Arbeit können die Protokollklassen unary_function und binary_function für den Entwickler übernehmen:

//Functor: Res f(Arg x);
template<typename Arg,typename Res>
struct unary_function;

//Functor: Res f(Arg1 x,Arg2 y);
template<typename Arg1,typename Arg2,typename Res>
struct binary_function;

Ein Beispiel für einen selbst definierten Funktor ist die mean-Klasse, die ich in Teil 2 vorgestellt habe. Ein anderes Beispiel wäre ein Composer, der mehrere Funktionen zusammenfassen kann (entsprechende Klassen gibt es z.B. in der Boost-Bibliothek):

//c(x,y) = f(g(x),h(y))
template<typename Op1,typename Op2,typename Op3>
class compose_f_gx_hy_t : public binary_function<typename Op2::argument_type,
                                                 typename Op3::argument_type,
                                                 typename Op1::result_type>
{
  Op1 op1;
  Op2 op2;
  Op3 op3;
public:
  compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
  : op1(f), op2(g), op3(h)
  {}

  typename Op1::result_type
  operator() (const typename Op2::argument_type& x,const typename Op3::argument_type& y)
  { return op1(op2(x),op3(y)); }
};

//Hilfsfunktion zur Erzeugung eines Composers
template<typename Op1,typename Op2,typename Op3>
inline compose_f_gx_hy_t<Op1,Op2,Op3>
compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
{ return compose_f_gx_hy_t<Op1,Op2,Op3>(f,g,h); }

Anmerkung: Analog dazu lassen sich alle Kombinationen aus unären und binären Funktionen mit geeigneten Composern darstellen.

4. weitere Informationen

C++ Referenz

The C++ Standard Library | ISBN: 0201379260 - Nicolai M. Josuttis - The C++ Standard Library
Die C++-Standardbibliothek | ISBN: 3540256938 - Stefan Kuhlins, Martin Schrader - Die C++ Standardbibliothek

---

OK, alles bis hierhin ist eingearbeitet.

[evilissimo]

Achja, nach dem du ja auch auf boost verweist, solltest du eventuell auch einen Link auf boost setzen
Nur der Formhalber *fg*

[CStoll]

Neben den Hauptbestandteilen der STL - Container, Iteratoren und Algorithmen - existieren in der Standardbibliothek von C++ noch etliche weitere Klassen, die von versierten Programmierern genutzt werden können. Einige davon arbeiten auch unmittelbar mit der STL zusammen. Im letzten Teil meiner Serie will ich einen kurzen Überblick über diese Klassen geben. Außerdem gehe ich darauf ein, wie die Funktionalitäten der STL vom Programmierer erweitert werden können.

Inhalt

1. weitere Klassen
2. Fehlerbehandlung
3. Erweiterungsmöglichkeiten
4. weitere Informationen

1 weitere Klassen

Als Ergänzung zu den obigen Klassen gibt es noch einige kleinere Hilfsklassen in der C++-Bibliothek. Diese werden teilweise von den STL-Elementen genutzt, können aber auch allein stehend eingesetzt werden.

1.1 pair

voller Name:

template<typename FT,typename ST>
struct std::pair;

template<typename FT,typename ST>
pair<FT,ST> make_pair(const FT&,const ST&);

Header:

include <utility>

Ein Pair (Paar) ist eine einfache Struktur, die zwei Elemente von verschiedenen Typen miteinander kombinieren kann. Diese Klasse wird unter anderem von Maps und Multimaps genutzt, um die Schlüssel-Wert-Paare zusammenzufassen. Außerdem ermöglichen sie es einer Funktion, zwei Werte gemeinsam zurückzugeben. Die letzte Möglichkeit wird auch von einigen Funktionen der STL genutzt, die mehrere Werte zusammen zurückgeben wollen, unter anderem equal_range() (gibt den Zielbereich des gesuchten Wertes als Paar zurück) und der insert()-Methode von Set und Map (diese gibt ein Paar aus einem Iterator und einem bool zurück, der angibt, ob insert() das Element einfügen konnte).

Die beiden Teile des Paares können direkt über "p.first" bzw. "p.second" angesprochen und modifiziert werden. Außerdem können Paare verschiedener Typen einander zugewiesen werden, solange ihre Elementtypen ineinander umgewandelt werden können.

Die Hilfsfunktion make_pair() ist die schnellste Möglichkeit, zwei Werte zu einem pair zusammenzufassen - sie ist zum Beispiel hilfreich, um Werte in eine (Multi-)Map einzufügen.

1.2 Funktoren

Header:

#include <functional>

Funktoren sind Objekte, die den Operator () überladen haben. Dadurch können sie wie normale Funktionen genutzt werden. Gegenüber einer normalen Funktion haben sie jedoch einige deutliche Vorteile:

• sie können einen internen Status haben - und zwar in verschiedenen Exemplaren unabhängig voneinander.
• sie haben einen eigenen Typ und können deshalb auch als Template-Parameter an STL-Container weitergegeben werden.

Die C++-Bibliothek bietet unter anderem Binder, mit deren Hilfe ein Parameter einer binären Funktion festgelegt werden kann, Wrapperklassen für normale Funktionen und Klassenmethoden und vordefinierte Funktoren für viele C++-Operatoren (zu diesen gehört auch die Klasse less<>, die als Standard-Ordnungskriterium von Sets und Maps verwendet wird).

In der STL werden Funktoren als Vergleichskriterium für assoziative Container und Priority-Queues und als optionale Arbeitsfunktionen für die meisten Algorithmen verwendet.

Zum Beispiel lassen sich die vordefinierten Funktor-Adapter verwenden, um alle Elemente eines Containers mit einem festen Wert zu potenzieren:

vector<double> data;
...
transform(data.begin(),data.end(),bind2nd(ptr_fun(pow),3));
/* Kombination zweier Funktor-Adapter:
  bind2nd - legt den zweiten Parameter eines binären Funktors fest
  ptr_fun - wrappt eine "normale" Funktion in einen Funktor
*/

1.3 Streams

Die Stream-Klassen wurden als Ersatz für die printf()- und scanf()-Familie der C-Standardbibliothek eingeführt. Sie bieten eine typsichere und erweiterbare Möglichkeit, Daten formatiert ein- und auszulesen. Dazu überladen sie die Operatoren << und >>, mit deren Hilfe alle eingebauten Datentypen von C++ aus- bzw. eingegeben werden können.

Entwickler können ihre eigenen Klassen mit demselben Mechanismus verarbeiten, indem sie die geeigneten Operatoren überladen.

Die Ein- und Ausgabe über Streams werde ich in einem späteren Artikel behandeln.
~wird ersetzt durch:~
Die Ein- und Ausgabe über Streams behandelt der Artikel "Ein- und Ausgabe in C++".

1.4 Locales und Facetten

Locales und Facetten dienen zur Internationalisierung der Ein- und Ausgabe-Operationen und werden sehr intensiv von den IO-Streams verwendet. Eine Facette modelliert einen bestimmten Aspekt der Ein/Ausgabe, wie zum Beispiel die Darstellung von Zahlen oder die Sortierung von landesspezifischen Sonderzeichen (z.B. Umlaute), ein Locale fasst Facetten für alle Einsatzbereiche zu einer Einheit zusammen.

Im Gegensatz zu C, wo nur ein Locale für alle Ein/Ausgabe-Operationen festgelegt werden konnte, kann in C++ jeder Stream sein eigenes Locale übergeben bekommen und verwalten.

1.5 komplexe Zahlen

voller Name:

template<typename T>
class std::complex;

Header:

#include <complex>

Die Klasse complex dient zur Verwendung und Berechnung komplexer Zahlen. Komplexe Zahlen können aus einer reellen Zahl (als Realteil) oder aus zwei reellen Werten (Realteil und Imaginärteil) konstruiert werden. Außerdem sind viele mathematische Operationen und Funktionen (z.B. Potenzen, Logarithmus, Winkelfunktionen,...) für komplexe Zahlen definiert.

Die Standardbibliothek definiert außer der allgemeinen Klasse complex<> auch Spezialisierungen für alle Gleitkommatypen (float, double und long double).

1.6 Valarrays

voller Name:

template<typename T>
class std::valarray;

class slice;  //eindimensionaler "Streifen" aus dem Valarray
class gslice; //mehrdimensionaler "Streifen"

Header:

#include <valarray>

Valarrays sind eine spezielle Form von Containern, die für parallele mathematische Operationen entwickelt wurden. Sie implementieren viele mathematische Operationen und Funktionen so, dass sie parallel auf alle Elemente angewendet werden.

//operator[] (slice)
template<typename T>class std::slice_array;
//operator[] (glice)
template<typename T>class std::gslice_array;
//operator[] (valarray<bool>)
template<typename T>class std::mask_array;
//operator[] (valarray<size_t>)
template<typename T>class std::indirect_array;

Diese Hilfsklassen können nicht direkt erzeugt werden. Sie entstehen bei speziellen Indexoperationen aus einem Valarray und bieten Zugriff auf bestimmte Teile des Arrays. Jede der vier Klassen entspricht einer bestimmten Methode zur Definition des Teilbereiches. Ein Teilarray kann genutzt werden, um eine mathematische Operation nur auf einem Teil der Elemente auszuführen, z.B. nur auf allen geraden Zahlen oder auf jedem vierten Element.

1.7 Bitsets

voller Name:

template<size_t N>
class std::bitset;

Header:

#include <bitset>

Bitsets werden zur Verwaltung von Einzelbits verwendet. Im Gegensatz zu einem vector<bool> steht die Größe des Bitsets bereits zur Compilezeit fest.

Ein Bitset kann zum Beispiel verwendet werden, um eine fixe Gruppe von Flags Platz sparend unterzubringen. Außerdem können sie auch zur Umwandlung von Zahlen in bzw. aus einer Binärdarstellung genutzt werden. Dafür existieren Konstruktoren und Umwandlungsoperatoren sowohl für ganze Zahlen (unsigned long) als auch für Strings (Binärdarstellung).

#include <bitset>
#include <iostream>
#include <limits> //numeric_limits

int main()
{
  //Dezimal nach Binär:
  cout<<"4711 = "<< bitset<numeric_limits<int>::digits>(4711)<<endl;

  //Binär nach Dezimal
  cout<<"1011010110 = "<<bitset<10>(string("1011010110")).to_ulong()<<endl;
  //Achtung: Eine direkte Umwandlung von char* nach bitset ist afaik nicht erlaubt
}

1.8 Auto-Pointer

voller Name:

template<typename T>
class auto_ptr;

Header:

#include <memory>

Die Klasse auto_ptr ist (leider) die einzige Smart-Pointer-Klasse, die im aktuellen C++-Standard vorgesehen ist. Auto-Pointer sorgen dafür, dass ein von ihnen verwaltetes Heap-Objekt automatisch gelöscht wird, wenn sie ihren Scope verlassen. Dazu stellen sie sicher, dass immer genau ein Auto-Pointer auf dieses Objekt verweist - eine Zuweisung zwischen Auto-Pointern entzieht dem Ursprungspointer den Besitz und setzt ihn auf NULL zurück.

Achtung: Auto-Pointer sind nicht dazu geeignet, Heap-Objekte an mehreren Stellen im Programm gemeinsam zu nutzen. Für diesen Zweck sind Smart-Pointer mit Referenzzählung (z.B. Boost::shared_ptr - siehe "Schlaue Pointer" im Magazin) besser geeignet.
Mit dem Technical Report TR1 wurden diese Smart-Pointer übrigens in den Standard aufgenommen.

Achtung: Da die Containerklassen der STL ihre Elemente bei Bedarf kopieren dürfen, sind Auto-Pointer NICHT zum Einsatz in STL-Containern geeignet.

1.9 Exception-Klassen

Header:

#include <stdexcept>
#include <exception> //ecxeption (Basisklasse) und bad_exception
#include <new>       //bad_alloc
#include <typeinfo>  //bad_cast und bad_typeid
#include <ios>       //ios_base::failure

Die Exception-Klassen wurden zur Unterstützung der Exception-Verarbeitung in C++ (try/catch) entworfen. Sie bieten eine eigene Hierarchie von verschiedenen Klassen, die je nach auftretender Fehlersituation verwendet werden können, sowie eine einheitliche Schnittstelle. Auf diese Weise lassen sich auch komplette Kategorien von Fehlern (z.B. alle logischen Fehler) oder sogar alle "Beschwerden" der Standardbibliothek mit einer einzigen catch-Klausel abfangen und auswerten:

try
{
  //etliche Operationen, die Probleme bereiten könnten
}
catch(std::exception& e)
{
  //hier landen alle Standard-Exceptions:
  cerr<<"Wir haben einen Fehler: "<<e.what()<<endl;
}

Die Basisklasse 'exception' definiert zur Fehlerauswertung eine virtuelle Methode what(), mit der die Fehlerursache erfragt werden kann - diese liefert für alle abgeleiteten Klassen einen implementationsspezifischen C-String (const char*). Weitere Zugriffsmöglichkeiten sind jedoch nicht vorgesehen.

In der Standardbibliothek sind folgende Exception-Klassen definiert:

Klasse             Basis          Verwendung

exception          -              Basis für alle Exception-Klassen
bad_alloc          exception      Fehler in new
bad_cast           exception      Fehler in dynamic_cast (Referenzen)
bad_typeid         exception      Fehler bei typeid Operator
ios_base::failure  exception      Fehler bei IO-Streams
bad_exception      exception      throw() Spezifikation umgangen

logic_error        exception      Logische Fehler (könnten vom Programm umgangen werden)
domain_error       logic_error    Domain-Fehler
invalid_argument   logic_error    ungültiges Argument (z.B. "0012" an bitset-Ctor)
length_error       logic_error    Maximallänge überschritten
out_of_range       logic_error    Bereichsüberschreitungen (z.B. bei vector::at())

runtime_error      exception      Laufzeitfehler (i.d.R. nicht abfangbar)
range_error        runtime_error  interner Bereichsfehler
overflow_error     runtime_error  arithmetischer Überlauf
underflow_error    runtime_error  arithmetischer Unterlauf

2 Fehlerbehandlung

Die meisten Methoden und Funktionen der STL sind so entworfen, dass sie möglichst beste Performance bieten. Deshalb wird größtenteils darauf verzichtet, Falscheingaben abzufangen. Wer ungültige Parameter, wie zum Beispiel einen ungültigen Iterator-Bereich, an einen STL-Algorithmus übergibt, erhält im Allgemeinen undefiniertes Verhalten.

Die einzige Funktion der STL, die wirklich ihre Eingabewerte auf Gültigkeit prüft, ist die Methode at() von vector<> und deque<> - diese wirft eine out_of_range Exeption, wenn sie mit einem ungültigen Index aufgerufen wird. In anderen Komponenten der C++-Standard-Bibliothek (z.B. in der string-Klasse oder bei den IO-Streams) erfolgt dagegen eine gründlichere Fehlerkontrolle.

Im Falle einer extern auftretenden Exception (z.B. in den Prädikaten, die an einen Algorithmus übergeben wurden) bieten alle Bestandteile der STL die Garantie, keine Speicherlecks zu produzieren und in einen "sicheren" Zustand zu wechseln. Einige der Container-Operationen bieten darüber hinaus eine "Commit-or-Rollback"-Garantie - entweder die Operation wird erfolgreich durchgeführt oder der Container bleibt unverändert. Andere Operationen gelingen garantiert (solange die Destruktoren der beteiligten Objekte keine Exceptions werfen können).

3 Erweiterungsmöglichkeiten

Die gesamte STL ist nach dem open-closed-Prinzip aufgebaut - offen für Erweiterungen, geschlossen für Modifikationen. Die existierenden Bestandteile der STL sollten als gegeben vorausgesetzt werden, können jedoch problemlos mit eigenen Klassen und Funktionen kombiniert werden
(theoretisch ist es auch möglich, in den STL-Headern rumzupfuschen, aber ich rate dringend davon ab).

3.1. Eigene Container

Um eine eigene Containerklasse für die Zusammenarbeit mit der STL vorzubereiten, gibt es drei mögliche Ansätze:

direkt

Der einfachste Weg, einen Container STL-tauglich zu machen, ist es, einen passenden Iterator für den Container zu finden oder zu definieren und diese Iteratoren den STL-Algorithmen zur Verfügung zu stellen. So dienen zum Beispiel blanke Pointer als "Iterator" für C-Arrays:

int values[100];
generate(values,values+100,rand);// füllen mit Zufallszahlen
sort(values,values+100);         // gesamtes Array sortieren
reverse(values,values+10);       // erste 10 Elemente umdrehen
...

Für andere Datenstrukturen ist es in der Regel notwendig, eine eigene Iteratorklasse zu bauen. Dazu finden sich im Kapitel 3.2 weitere Informationen.

per Wrapper

Etwas stärker ist die Kopplung, wenn um eine bestehende Containerstruktur eine Wrapper-Klasse aufgebaut wird, die die wichtigsten Methoden für STL-Container (z.B. begin(), end(), size(), etc.) implementiert und in Aufrufe der Container-eigenen Methoden übersetzt. Auf diese Weise ließe sich ein STL-Interface um ein Array oder ein Datenbanksystem herum aufbauen.

//Beispiel: Array-Wrapper
template<typename T,size_t N>
class CArray
{
  T vals[N];
public:
  typedef T        value_type;
  typedef T*       iterator;
  typedef const T* const_iterator;
  ...//eventuell einige weitere typedef's

  //Iterator-Erzeugung:
  iterator begin()                  {return vals;}
  const_iterator begin() const      {return vals;}
  iterator end()                    {return vals+N;}
  const_iterator end() const        {return vals+N;}

  //Größe:
  size_t size() const               {return N;}

  //Elementzugriff:
  T& operator[] (int j)             {return vals[j];}
  const T& operator[] (int j) const {return vals[j];}

  //Umwandlung in Array:
  T* as_array()                     {return vals;}
}

invasiv

Die aufwendigste Methode besteht darin, die eigene Containerklasse von Anfang an so zu konzipieren, dass sie ein mehr oder weniger vollständiges STL-Interface bereitstellt. Dieser Ansatz wurde z.B. verwendet, als die string-Klasse entworfen wurde.

3.2 Eigene Iteratoren

Da die gesamte STL auf Templates aufbaut, ist der Entwurf eines neuen Iterators eigentlich recht einfach - alles, was sich wie ein Iterator verhält, ist ein Iterator (und alles, was die Operationen bereitstellt, die von einem Algorithmus verwendet werden, kann diesem Algorithmus übergeben werden).

Als Unterstützung für den Entwickler gibt es trotzdem eine Protokollklasse iterator, die als Basis für eigene Iteratoren verwendet werden kann:

template<typename Cat,typename T,typename Diff=ptrdiff_t,typename Ptr=T*,typename Ref=T&>
struct std::iterator;

struct output_iterator_tag {};
struct input_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

Diese Klasse definiert lediglich die Datentypen, die für die Arbeit mit den iterator_traits benötigt werden.

Die leeren Hilfsklassen (..._tag) können als Parameter 'Cat' verwendet werden und kennzeichnen die Einordnung des eigenen Iteratortyps in eine der Kategorien (siehe Teil 2 der Artikelserie). Die für diese Kategorie nötigen Operationen müssen allerdings selbst bereitgestellt werden. Diese Klassen sind voneinander abgeleitet, um die Austauschbarkeit der einzelnen Kategorien darzustellen - zum Beispiel kann jeder Random-Access-Iterator auch als Input-Iterator genutzt werden.

Achtung: Die Klasse forward_iterator_tag ist nicht von output_iterator_tag abgeleitet, weil Forward-Iteratoren nicht vollständig äquivalent zu Output-Iteratoren sind (siehe Kapitel 2.3 im zweiten Teil der Serie).

Ein Beispiel für eigene Iteratoren wäre ein Spezial-Inserter für assoziative Container. Im Gegensatz zum Inserter der STL benötigt diese Variante keine Einfügeposition und kann dadurch eventuell schneller arbeiten (insert() mit der falschen Zielposition ist üblicherweise langsamer als ein insert() ohne vorgegebene Position):

template<typename Cont>
class ainsert_iterator : public iterator<output_iterator_tag,void,void,void,void>
{
protected:
  Cont& container;
public:
  explicit ainsert_iterator(Cont& c) : container(c) {}

  // Wertzuweisung *it=x
  ainsert_iterator& operator=(const typename Cont::value_type& val)
  {
    container.insert(val);
    return *this;
  }

  //Dereferenzierung
  ainsert_iterator& operator*() {return *this;}

  //Inkrement
  ainsert_iterator& operator++() {return *this;}
  ainsert_iterator& operator++(int) {return *this;}
};

template<typename Cont>
inline ainsert_iterator<Cont> asso_inserter(Cont& c)
{ return ainsert_iterator<Cont>(c); }

operator* und operator= stellen den üblichen Weg dar, mit dem bei einem Output-Iterator die Wertzuweisung realisiert wird. "Höherwertige" Iteratorklassen liefern dagegen meistens eine Referenz auf ihren Elementtyp oder eine Pseudo-Referenz zurück, wenn sie dereferenziert werden.

Folgende Operatoren werden benötigt, um eine vollwertige Iteratorklasse zu erzeugen:

Operator                                   Bedeutung               Kategorien

Iter::Iter(const Iter&)                    Kopierkonstruktor       OIFBR
Iter& Iter::operator=(const Iter&)         Zuweisung                 FBR

Ref Iter::operator*()                      Dereferenzierung        OIFBR
Ptr Iter::operator->()                     Memberzugriff            IFBR
Ref Iter::operator[](Diff)                 Indexzugriff                R

Iter& Iter::operator++()                   Inkrement (Präfix)      OIFBR
Iter Iter::operator++(int)                 Inkrement (Postfix)     OIFBR
Iter& Iter::operator--()                   Dekrement (Präfix)         BR
Iter Iter::operator--(int)                 Dekrement (Postfix)        BR
Iter& Iter::operator+=(Diff)               Inkrement (n Schritte)      R
Iter& Iter::operator-=(Diff)               Dekrement (n Schritte)      R
Iter operator+(Diff,const Iter&)           n't nächste Position        R
Iter operator+(const Iter&,Diff)           n't nächste Position        R
Iter operator-(const Iter&,Diff)           n't vorige Position         R
Diff operator-(const Iter&, const Iter&)   Abstand                     R

bool operator==(const Iter&,const Iter&)   Vergleich (gleich)       IFBR
bool operator!=(const Iter&,const Iter&)   Vergleich (ungleich)     IFBR
bool operator [i]x[/i](const Iter&,const Iter&)   Vergleich (<,<=,>=,>)       R

Dabei ist "Ref" eine Referenz auf den Elementtyp oder eine Klasse, die entsprechende Funktionalität zur Verfügung stellt (für Output-Iteratoren wird ein operator=(T) benötigt, für alle anderen Kategorien auch Elementzugriff und eine Umwandlung nach T), "Ptr" ein Pointer oder Smart-Pointer auf den Elementtyp (benötigt auf jeden Fall einen operator->()) und "Diff" der Differenztyp des Iterators (normalerweise ein vorzeichenbehafteter Ganzzahltyp).

3.3 Eigene Algorithmen

In der Regel ist der schwierigste Teil der Algorithmenentwicklung die Frage, was der Algorithmus eigentlich machen soll. Wenn die Arbeitsweise feststeht, kann der Algorithmus vorübergehend auf einem int-Array implementiert werden.

Wenn feststeht, dass der Algorithmus korrekt funktioniert, kann er in eine Template-Funktion umgewandelt werden, indem alle Vorkommen von 'int*' durch den Template-Parameter 'It' und alle Vorkommen von 'int' (außer Zählvariablen) durch 'typename iterator_traits<It>::value_type' oder einen eigenen Template-Parameter ersetzt werden.

//Ausgangspunkt:
int* worker(int* data, size_t len,...)
{
  ...
}

//Zwischenschritt: Start+Länge -> Start+Ende
int* worker(int* beg, int* end,...)
{
  //ersetze len durch end-beg
  ...
}

//Ergebnis: Template-Funktion
template<typename It,...>
It worker(It beg, It end,...)
{
  typedef typename iterator_traits<It>::value_type val;
  //ersetze int* durch It und int durch val
}

Anmerkung: Wenn möglich, sollten für die Arbeit die Hilfsfunktionen advance() statt Iterator-Addition, difference() statt Iterator-Subtraktion und swap() oder iter_swap() statt Elementaustausch verwendet werden.

Ein Beispiel für einen eigenen Algorithmus wäre eine Funktion, die alle Duplikate aus einer unsortierten Datensammlung entfernt:

//als Quellbereich wird ein Forward-Iterator benötigt, weil Input-Iteratoren nicht sicher kopiert werden können
template<typename FwdIt,typename OutIt>
OutIt unsorted_unique_copy(FwdIt sbeg,FwdIt send,OutIt dbeg)
{
  for(FwdIt pos=sbeg;pos!=send;++pos)
    if(find(sbeg,pos,*pos)==pos) *dbeg++ = *pos;
  return dbeg;
}

template<typename FwdIt>
FwdIt unsorted_unique(FwdIt beg,FwdIt end)
{
  return unsorted_unique_copy(beg,end,beg);
}

Um den Algorithmen die Arbeit zu erleichtern, existiert eine Hilfsklasse "iterator_traits", die einige Typdefinitionen für einen Iterator enthält:

template<typename It>
struct iterator_traits
{
  typedef typename It::value_type        value_type;        // Werttyp
  typedef typename It::iterator_category iterator_category; // Kategorie: Output, Input,...
  typedef typename It::difference_type   difference_type;   // Differenz zwischen Iteratoren
  typedef typename It::pointer           pointer;           // Zeiger auf T
  typedef typename It::reference         reference          // Referenz auf T
};

Die Typdefinitionen dieser Klasse können verwendet werden, um z.B. den Typ einer temporären Variablen passend zum Iterator festzulegen.

template<typename Iter>
void foo_alg(Iter beg,Iter end)
{
  if(beg==end) return;
  typename iterator_traits<Iter>::value_type temp=*beg;
  ...
}

template<typename Iter>
void bar_alg(Iter beg,Iter end)
{
  typename iterator_traits<Iter>::difference_type dist=distance(beg,end);
  ...
}

Die Kategorie des Iterators kann genutzt werden, um einen Algorithmus so zu optimieren, dass er die "besten" Operationen des Iterator-Typs verwendet:

//"öffentliche Version":
//wird vom Nutzer aufgerufen und delegiert die Arbeit weiter
template<typename Iter>
Iter algo(Iter beg,Iter end)
{ return algo(beg,end,iterator_traits<Iter>::iterator_category()); }

//Version für Random Access Iteratoren:
//nutzt die komplette Vielfalt der Iterator-Arithmetik
template<typename RanIt>
RanIt algo(RanIt beg,RanIt end,random_access_iterator_tag)
{
  ...
}

//Version für andere Typen:
//nutzt nur Inkrement-Operator
template<typename InIt>
InIt algo(InIt beg,InIt end,input_iterator_tag)
{
  ...
}

Dank der Vererbungsbeziehung zwischen den Tag-Klassen wird die zweite Version des Algorithmus' auch von Forward- und Bidirektionalen Iteratoren verwendet.

Außer der allgemeinen Version der iterator_traits - die alle benötigten Typdefinitionen in der instanzierten Klasse voraussetzt - gibt es noch Spezialisierungen für Pointer und const-Pointer. Iterator-Klassen, die die benötigten Typen nicht selber bereitstellen können oder wollen - z.B. weil sie aus einer fremden Bibliothek integriert wurden - , dürfen ebenfalls eine Spezialisierung der iterator_traits anlegen.

Anmerkung: Wenn ein eigener Iterator von der Hilfsklasse iterator<> abgeleitet wird (siehe Kapitel 3.2), stellt er automatisch alle nötigen Typdefinitionen für die Iterator-Traits bereit.

3.4 eigene Funktoren

Als Funktor kann theoretisch jede Klasse verwendet werden, die den operator() überladen hat. Für die Zusammenarbeit mit den STL-Funktor-Adaptern ist es jedoch notwendig, die Argument- und Rückgabetypen des eigenen operator() anzugeben. Diese Arbeit können die Protokollklassen unary_function und binary_function für den Entwickler übernehmen:

//Functor: Res f(Arg x);
template<typename Arg,typename Res>
struct unary_function;

//Functor: Res f(Arg1 x,Arg2 y);
template<typename Arg1,typename Arg2,typename Res>
struct binary_function;

Ein Beispiel für einen selbst definierten Funktor ist die mean-Klasse, die ich in Teil 2 vorgestellt habe. Ein anderes Beispiel wäre ein Composer, der mehrere Funktionen zusammenfassen kann (entsprechende Klassen gibt es z.B. in der Boost-Bibliothek):

//c(x,y) = f(g(x),h(y))
template<typename Op1,typename Op2,typename Op3>
class compose_f_gx_hy_t : public binary_function<typename Op2::argument_type,
                                                 typename Op3::argument_type,
                                                 typename Op1::result_type>
{
  Op1 op1;
  Op2 op2;
  Op3 op3;
public:
  compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
  : op1(f), op2(g), op3(h)
  {}

  typename Op1::result_type
  operator() (const typename Op2::argument_type& x,const typename Op3::argument_type& y)
  { return op1(op2(x),op3(y)); }
};

//Hilfsfunktion zur Erzeugung eines Composers
template<typename Op1,typename Op2,typename Op3>
inline compose_f_gx_hy_t<Op1,Op2,Op3>
compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
{ return compose_f_gx_hy_t<Op1,Op2,Op3>(f,g,h); }

Anmerkung: Analog dazu lassen sich alle Kombinationen aus unären und binären Funktionen mit geeigneten Composern darstellen.

4. weitere Informationen

C++ Referenz

Boost C++ Bibliothek

The C++ Standard Library | ISBN: 0201379260 - Nicolai M. Josuttis - The C++ Standard Library
Die C++-Standardbibliothek | ISBN: 3540256938 - Stefan Kuhlins, Martin Schrader - Die C++ Standardbibliothek

[GPC]

Hi,

machst du bitte auch noch ne [E] Version von deinem Artikel, damit wir den mit rausgeben können? Merci.

MfG

GPC

[CStoll]

Neben den Hauptbestandteilen der STL - Container, Iteratoren und Algorithmen - existieren in der Standardbibliothek von C++ noch etliche weitere Klassen, die von versierten Programmierern genutzt werden können. Einige davon arbeiten auch unmittelbar mit der STL zusammen. Im letzten Teil meiner Serie will ich einen kurzen Überblick über diese Klassen geben. Außerdem gehe ich darauf ein, wie die Funktionalitäten der STL vom Programmierer erweitert werden können.

Inhalt

1. weitere Klassen
2. Fehlerbehandlung
3. Erweiterungsmöglichkeiten
4. weitere Informationen

1 weitere Klassen

Als Ergänzung zu den obigen Klassen gibt es noch einige kleinere Hilfsklassen in der C++-Bibliothek. Diese werden teilweise von den STL-Elementen genutzt, können aber auch allein stehend eingesetzt werden.

1.1 pair

voller Name:

template<typename FT,typename ST>
struct std::pair;

template<typename FT,typename ST>
pair<FT,ST> make_pair(const FT&,const ST&);

Header:

include <utility>

Ein Pair (Paar) ist eine einfache Struktur, die zwei Elemente von verschiedenen Typen miteinander kombinieren kann. Diese Klasse wird unter anderem von Maps und Multimaps genutzt, um die Schlüssel-Wert-Paare zusammenzufassen. Außerdem ermöglichen sie es einer Funktion, zwei Werte gemeinsam zurückzugeben. Die letzte Möglichkeit wird auch von einigen Funktionen der STL genutzt, die mehrere Werte zusammen zurückgeben wollen, unter anderem equal_range() (gibt den Zielbereich des gesuchten Wertes als Paar zurück) und der insert()-Methode von Set und Map (diese gibt ein Paar aus einem Iterator und einem bool zurück, der angibt, ob insert() das Element einfügen konnte).

Die beiden Teile des Paares können direkt über "p.first" bzw. "p.second" angesprochen und modifiziert werden. Außerdem können Paare verschiedener Typen einander zugewiesen werden, solange ihre Elementtypen ineinander umgewandelt werden können.

Die Hilfsfunktion make_pair() ist die schnellste Möglichkeit, zwei Werte zu einem pair zusammenzufassen - sie ist zum Beispiel hilfreich, um Werte in eine (Multi-)Map einzufügen.

1.2 Funktoren

Header:

#include <functional>

Funktoren sind Objekte, die den Operator () überladen haben. Dadurch können sie wie normale Funktionen genutzt werden. Gegenüber einer normalen Funktion haben sie jedoch einige deutliche Vorteile:

• sie können einen internen Status haben - und zwar in verschiedenen Exemplaren unabhängig voneinander.
• sie haben einen eigenen Typ und können deshalb auch als Template-Parameter an STL-Container weitergegeben werden.

Die C++-Bibliothek bietet unter anderem Binder, mit deren Hilfe ein Parameter einer binären Funktion festgelegt werden kann, Wrapperklassen für normale Funktionen und Klassenmethoden und vordefinierte Funktoren für viele C++-Operatoren (zu diesen gehört auch die Klasse less<>, die als Standard-Ordnungskriterium von Sets und Maps verwendet wird).

In der STL werden Funktoren als Vergleichskriterium für assoziative Container und Priority-Queues und als optionale Arbeitsfunktionen für die meisten Algorithmen verwendet.

Zum Beispiel lassen sich die vordefinierten Funktor-Adapter verwenden, um alle Elemente eines Containers mit einem festen Wert zu potenzieren:

vector<double> data;
...
transform(data.begin(),data.end(),bind2nd(ptr_fun(pow),3));
/* Kombination zweier Funktor-Adapter:
  bind2nd - legt den zweiten Parameter eines binären Funktors fest
  ptr_fun - wrappt eine "normale" Funktion in einen Funktor
*/

1.3 Streams

Die Stream-Klassen wurden als Ersatz für die printf()- und scanf()-Familie der C-Standardbibliothek eingeführt. Sie bieten eine typsichere und erweiterbare Möglichkeit, Daten formatiert ein- und auszulesen. Dazu überladen sie die Operatoren << und >>, mit deren Hilfe alle eingebauten Datentypen von C++ aus- bzw. eingegeben werden können.

Entwickler können ihre eigenen Klassen mit demselben Mechanismus verarbeiten, indem sie die geeigneten Operatoren überladen.

Die Ein- und Ausgabe über Streams werde ich in einem späteren Artikel behandeln.

1.4 Locales und Facetten

Locales und Facetten dienen zur Internationalisierung der Ein- und Ausgabe-Operationen und werden sehr intensiv von den IO-Streams verwendet. Eine Facette modelliert einen bestimmten Aspekt der Ein/Ausgabe, wie zum Beispiel die Darstellung von Zahlen oder die Sortierung von landesspezifischen Sonderzeichen (z.B. Umlaute), ein Locale fasst Facetten für alle Einsatzbereiche zu einer Einheit zusammen.

Im Gegensatz zu C, wo nur ein Locale für alle Ein/Ausgabe-Operationen festgelegt werden konnte, kann in C++ jeder Stream sein eigenes Locale übergeben bekommen und verwalten.

1.5 komplexe Zahlen

voller Name:

template<typename T>
class std::complex;

Header:

#include <complex>

Die Klasse complex dient zur Verwendung und Berechnung komplexer Zahlen. Komplexe Zahlen können aus einer reellen Zahl (als Realteil) oder aus zwei reellen Werten (Realteil und Imaginärteil) konstruiert werden. Außerdem sind viele mathematische Operationen und Funktionen (z.B. Potenzen, Logarithmus, Winkelfunktionen,...) für komplexe Zahlen definiert.

Die Standardbibliothek definiert außer der allgemeinen Klasse complex<> auch Spezialisierungen für alle Gleitkommatypen (float, double und long double).

1.6 Valarrays

voller Name:

template<typename T>
class std::valarray;

class slice;  //eindimensionaler "Streifen" aus dem Valarray
class gslice; //mehrdimensionaler "Streifen"

Header:

#include <valarray>

Valarrays sind eine spezielle Form von Containern, die für parallele mathematische Operationen entwickelt wurden. Sie implementieren viele mathematische Operationen und Funktionen so, dass sie parallel auf alle Elemente angewendet werden.

//operator[] (slice)
template<typename T>class std::slice_array;
//operator[] (glice)
template<typename T>class std::gslice_array;
//operator[] (valarray<bool>)
template<typename T>class std::mask_array;
//operator[] (valarray<size_t>)
template<typename T>class std::indirect_array;

Diese Hilfsklassen können nicht direkt erzeugt werden. Sie entstehen bei speziellen Indexoperationen aus einem Valarray und bieten Zugriff auf bestimmte Teile des Arrays. Jede der vier Klassen entspricht einer bestimmten Methode zur Definition des Teilbereiches. Ein Teilarray kann genutzt werden, um eine mathematische Operation nur auf einem Teil der Elemente auszuführen, z.B. nur auf allen geraden Zahlen oder auf jedem vierten Element.

1.7 Bitsets

voller Name:

template<size_t N>
class std::bitset;

Header:

#include <bitset>

Bitsets werden zur Verwaltung von Einzelbits verwendet. Im Gegensatz zu einem vector<bool> steht die Größe des Bitsets bereits zur Compilezeit fest.

Ein Bitset kann zum Beispiel verwendet werden, um eine fixe Gruppe von Flags Platz sparend unterzubringen. Außerdem können sie auch zur Umwandlung von Zahlen in bzw. aus einer Binärdarstellung genutzt werden. Dafür existieren Konstruktoren und Umwandlungsoperatoren sowohl für ganze Zahlen (unsigned long) als auch für Strings (Binärdarstellung).

#include <bitset>
#include <iostream>
#include <limits> //numeric_limits

int main()
{
  //Dezimal nach Binär:
  cout<<"4711 = "<< bitset<numeric_limits<int>::digits>(4711)<<endl;

  //Binär nach Dezimal
  cout<<"1011010110 = "<<bitset<10>(string("1011010110")).to_ulong()<<endl;
  //Achtung: Eine direkte Umwandlung von char* nach bitset ist afaik nicht erlaubt
}

1.8 Auto-Pointer

voller Name:

template<typename T>
class auto_ptr;

Header:

#include <memory>

Die Klasse auto_ptr ist (leider) die einzige Smart-Pointer-Klasse, die im aktuellen C++-Standard vorgesehen ist. Auto-Pointer sorgen dafür, dass ein von ihnen verwaltetes Heap-Objekt automatisch gelöscht wird, wenn sie ihren Scope verlassen. Dazu stellen sie sicher, dass immer genau ein Auto-Pointer auf dieses Objekt verweist - eine Zuweisung zwischen Auto-Pointern entzieht dem Ursprungspointer den Besitz und setzt ihn auf NULL zurück.

Achtung: Auto-Pointer sind nicht dazu geeignet, Heap-Objekte an mehreren Stellen im Programm gemeinsam zu nutzen. Für diesen Zweck sind Smart-Pointer mit Referenzzählung (z.B. Boost::shared_ptr - siehe "Schlaue Pointer" im Magazin) besser geeignet.
Mit dem Technical Report TR1 wurden diese Smart-Pointer übrigens in den Standard aufgenommen.

Achtung: Da die Containerklassen der STL ihre Elemente bei Bedarf kopieren dürfen, sind Auto-Pointer NICHT zum Einsatz in STL-Containern geeignet.

1.9 Exception-Klassen

Header:

#include <stdexcept>
#include <exception> //ecxeption (Basisklasse) und bad_exception
#include <new>       //bad_alloc
#include <typeinfo>  //bad_cast und bad_typeid
#include <ios>       //ios_base::failure

Die Exception-Klassen wurden zur Unterstützung der Exception-Verarbeitung in C++ (try/catch) entworfen. Sie bieten eine eigene Hierarchie von verschiedenen Klassen, die je nach auftretender Fehlersituation verwendet werden können, sowie eine einheitliche Schnittstelle. Auf diese Weise lassen sich auch komplette Kategorien von Fehlern (z.B. alle logischen Fehler) oder sogar alle "Beschwerden" der Standardbibliothek mit einer einzigen catch-Klausel abfangen und auswerten:

try
{
  //etliche Operationen, die Probleme bereiten könnten
}
catch(std::exception& e)
{
  //hier landen alle Standard-Exceptions:
  cerr<<"Wir haben einen Fehler: "<<e.what()<<endl;
}

Die Basisklasse 'exception' definiert zur Fehlerauswertung eine virtuelle Methode what(), mit der die Fehlerursache erfragt werden kann - diese liefert für alle abgeleiteten Klassen einen implementationsspezifischen C-String (const char*). Weitere Zugriffsmöglichkeiten sind jedoch nicht vorgesehen.

In der Standardbibliothek sind folgende Exception-Klassen definiert:

Klasse             Basis          Verwendung

exception          -              Basis für alle Exception-Klassen
bad_alloc          exception      Fehler in new
bad_cast           exception      Fehler in dynamic_cast (Referenzen)
bad_typeid         exception      Fehler bei typeid Operator
ios_base::failure  exception      Fehler bei IO-Streams
bad_exception      exception      throw() Spezifikation umgangen

logic_error        exception      Logische Fehler (könnten vom Programm umgangen werden)
domain_error       logic_error    Domain-Fehler
invalid_argument   logic_error    ungültiges Argument (z.B. "0012" an bitset-Ctor)
length_error       logic_error    Maximallänge überschritten
out_of_range       logic_error    Bereichsüberschreitungen (z.B. bei vector::at())

runtime_error      exception      Laufzeitfehler (i.d.R. nicht abfangbar)
range_error        runtime_error  interner Bereichsfehler
overflow_error     runtime_error  arithmetischer Überlauf
underflow_error    runtime_error  arithmetischer Unterlauf

2 Fehlerbehandlung

Die meisten Methoden und Funktionen der STL sind so entworfen, dass sie möglichst beste Performance bieten. Deshalb wird größtenteils darauf verzichtet, Falscheingaben abzufangen. Wer ungültige Parameter, wie zum Beispiel einen ungültigen Iterator-Bereich, an einen STL-Algorithmus übergibt, erhält im Allgemeinen undefiniertes Verhalten.

Die einzige Funktion der STL, die wirklich ihre Eingabewerte auf Gültigkeit prüft, ist die Methode at() von vector<> und deque<> - diese wirft eine out_of_range Exeption, wenn sie mit einem ungültigen Index aufgerufen wird. In anderen Komponenten der C++-Standard-Bibliothek (z.B. in der string-Klasse oder bei den IO-Streams) erfolgt dagegen eine gründlichere Fehlerkontrolle.

Im Falle einer extern auftretenden Exception (z.B. in den Prädikaten, die an einen Algorithmus übergeben wurden) bieten alle Bestandteile der STL die Garantie, keine Speicherlecks zu produzieren und in einen "sicheren" Zustand zu wechseln. Einige der Container-Operationen bieten darüber hinaus eine "Commit-or-Rollback"-Garantie - entweder die Operation wird erfolgreich durchgeführt oder der Container bleibt unverändert. Andere Operationen gelingen garantiert (solange die Destruktoren der beteiligten Objekte keine Exceptions werfen können).

3 Erweiterungsmöglichkeiten

Die gesamte STL ist nach dem open-closed-Prinzip aufgebaut - offen für Erweiterungen, geschlossen für Modifikationen. Die existierenden Bestandteile der STL sollten als gegeben vorausgesetzt werden, können jedoch problemlos mit eigenen Klassen und Funktionen kombiniert werden
(theoretisch ist es auch möglich, in den STL-Headern rumzupfuschen, aber ich rate dringend davon ab).

3.1. Eigene Container

Um eine eigene Containerklasse für die Zusammenarbeit mit der STL vorzubereiten, gibt es drei mögliche Ansätze:

direkt

Der einfachste Weg, einen Container STL-tauglich zu machen, ist es, einen passenden Iterator für den Container zu finden oder zu definieren und diese Iteratoren den STL-Algorithmen zur Verfügung zu stellen. So dienen zum Beispiel blanke Pointer als "Iterator" für C-Arrays:

int values[100];
generate(values,values+100,rand);// füllen mit Zufallszahlen
sort(values,values+100);         // gesamtes Array sortieren
reverse(values,values+10);       // erste 10 Elemente umdrehen
...

Für andere Datenstrukturen ist es in der Regel notwendig, eine eigene Iteratorklasse zu bauen. Dazu finden sich im Kapitel 3.2 weitere Informationen.

per Wrapper

Etwas stärker ist die Kopplung, wenn um eine bestehende Containerstruktur eine Wrapper-Klasse aufgebaut wird, die die wichtigsten Methoden für STL-Container (z.B. begin(), end(), size(), etc.) implementiert und in Aufrufe der Container-eigenen Methoden übersetzt. Auf diese Weise ließe sich ein STL-Interface um ein Array oder ein Datenbanksystem herum aufbauen.

//Beispiel: Array-Wrapper
template<typename T,size_t N>
class CArray
{
  T vals[N];
public:
  typedef T        value_type;
  typedef T*       iterator;
  typedef const T* const_iterator;
  ...//eventuell einige weitere typedef's

  //Iterator-Erzeugung:
  iterator begin()                  {return vals;}
  const_iterator begin() const      {return vals;}
  iterator end()                    {return vals+N;}
  const_iterator end() const        {return vals+N;}

  //Größe:
  size_t size() const               {return N;}

  //Elementzugriff:
  T& operator[] (int j)             {return vals[j];}
  const T& operator[] (int j) const {return vals[j];}

  //Umwandlung in Array:
  T* as_array()                     {return vals;}
}

invasiv

Die aufwendigste Methode besteht darin, die eigene Containerklasse von Anfang an so zu konzipieren, dass sie ein mehr oder weniger vollständiges STL-Interface bereitstellt. Dieser Ansatz wurde z.B. verwendet, als die string-Klasse entworfen wurde.

3.2 Eigene Iteratoren

Da die gesamte STL auf Templates aufbaut, ist der Entwurf eines neuen Iterators eigentlich recht einfach - alles, was sich wie ein Iterator verhält, ist ein Iterator (und alles, was die Operationen bereitstellt, die von einem Algorithmus verwendet werden, kann diesem Algorithmus übergeben werden).

Als Unterstützung für den Entwickler gibt es trotzdem eine Protokollklasse iterator, die als Basis für eigene Iteratoren verwendet werden kann:

template<typename Cat,typename T,typename Diff=ptrdiff_t,typename Ptr=T*,typename Ref=T&>
struct std::iterator;

struct output_iterator_tag {};
struct input_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

Diese Klasse definiert lediglich die Datentypen, die für die Arbeit mit den iterator_traits benötigt werden.

Die leeren Hilfsklassen (..._tag) können als Parameter 'Cat' verwendet werden und kennzeichnen die Einordnung des eigenen Iteratortyps in eine der Kategorien (siehe Teil 2 der Artikelserie). Die für diese Kategorie nötigen Operationen müssen allerdings selbst bereitgestellt werden. Diese Klassen sind voneinander abgeleitet, um die Austauschbarkeit der einzelnen Kategorien darzustellen - zum Beispiel kann jeder Random-Access-Iterator auch als Input-Iterator genutzt werden.

Achtung: Die Klasse forward_iterator_tag ist nicht von output_iterator_tag abgeleitet, weil Forward-Iteratoren nicht vollständig äquivalent zu Output-Iteratoren sind (siehe Kapitel 2.3 im zweiten Teil der Serie).

Ein Beispiel für eigene Iteratoren wäre ein Spezial-Inserter für assoziative Container. Im Gegensatz zum Inserter der STL benötigt diese Variante keine Einfügeposition und kann dadurch eventuell schneller arbeiten (insert() mit der falschen Zielposition ist üblicherweise langsamer als ein insert() ohne vorgegebene Position):

template<typename Cont>
class ainsert_iterator : public iterator<output_iterator_tag,void,void,void,void>
{
protected:
  Cont& container;
public:
  explicit ainsert_iterator(Cont& c) : container(c) {}

  // Wertzuweisung *it=x
  ainsert_iterator& operator=(const typename Cont::value_type& val)
  {
    container.insert(val);
    return *this;
  }

  //Dereferenzierung
  ainsert_iterator& operator*() {return *this;}

  //Inkrement
  ainsert_iterator& operator++() {return *this;}
  ainsert_iterator& operator++(int) {return *this;}
};

template<typename Cont>
inline ainsert_iterator<Cont> asso_inserter(Cont& c)
{ return ainsert_iterator<Cont>(c); }

operator* und operator= stellen den üblichen Weg dar, mit dem bei einem Output-Iterator die Wertzuweisung realisiert wird. "Höherwertige" Iteratorklassen liefern dagegen meistens eine Referenz auf ihren Elementtyp oder eine Pseudo-Referenz zurück, wenn sie dereferenziert werden.

Folgende Operatoren werden benötigt, um eine vollwertige Iteratorklasse zu erzeugen:

Operator                                   Bedeutung               Kategorien

Iter::Iter(const Iter&)                    Kopierkonstruktor       OIFBR
Iter& Iter::operator=(const Iter&)         Zuweisung                 FBR

Ref Iter::operator*()                      Dereferenzierung        OIFBR
Ptr Iter::operator->()                     Memberzugriff            IFBR
Ref Iter::operator[](Diff)                 Indexzugriff                R

Iter& Iter::operator++()                   Inkrement (Präfix)      OIFBR
Iter Iter::operator++(int)                 Inkrement (Postfix)     OIFBR
Iter& Iter::operator--()                   Dekrement (Präfix)         BR
Iter Iter::operator--(int)                 Dekrement (Postfix)        BR
Iter& Iter::operator+=(Diff)               Inkrement (n Schritte)      R
Iter& Iter::operator-=(Diff)               Dekrement (n Schritte)      R
Iter operator+(Diff,const Iter&)           n't nächste Position        R
Iter operator+(const Iter&,Diff)           n't nächste Position        R
Iter operator-(const Iter&,Diff)           n't vorige Position         R
Diff operator-(const Iter&, const Iter&)   Abstand                     R

bool operator==(const Iter&,const Iter&)   Vergleich (gleich)       IFBR
bool operator!=(const Iter&,const Iter&)   Vergleich (ungleich)     IFBR
bool operator [i]x[/i](const Iter&,const Iter&)   Vergleich (<,<=,>=,>)       R

Dabei ist "Ref" eine Referenz auf den Elementtyp oder eine Klasse, die entsprechende Funktionalität zur Verfügung stellt (für Output-Iteratoren wird ein operator=(T) benötigt, für alle anderen Kategorien auch Elementzugriff und eine Umwandlung nach T), "Ptr" ein Pointer oder Smart-Pointer auf den Elementtyp (benötigt auf jeden Fall einen operator->()) und "Diff" der Differenztyp des Iterators (normalerweise ein vorzeichenbehafteter Ganzzahltyp).

3.3 Eigene Algorithmen

In der Regel ist der schwierigste Teil der Algorithmenentwicklung die Frage, was der Algorithmus eigentlich machen soll. Wenn die Arbeitsweise feststeht, kann der Algorithmus vorübergehend auf einem int-Array implementiert werden.

Wenn feststeht, dass der Algorithmus korrekt funktioniert, kann er in eine Template-Funktion umgewandelt werden, indem alle Vorkommen von 'int*' durch den Template-Parameter 'It' und alle Vorkommen von 'int' (außer Zählvariablen) durch 'typename iterator_traits<It>::value_type' oder einen eigenen Template-Parameter ersetzt werden.

//Ausgangspunkt:
int* worker(int* data, size_t len,...)
{
  ...
}

//Zwischenschritt: Start+Länge -> Start+Ende
int* worker(int* beg, int* end,...)
{
  //ersetze len durch end-beg
  ...
}

//Ergebnis: Template-Funktion
template<typename It,...>
It worker(It beg, It end,...)
{
  typedef typename iterator_traits<It>::value_type val;
  //ersetze int* durch It und int durch val
}

Anmerkung: Wenn möglich, sollten für die Arbeit die Hilfsfunktionen advance() statt Iterator-Addition, difference() statt Iterator-Subtraktion und swap() oder iter_swap() statt Elementaustausch verwendet werden.

Ein Beispiel für einen eigenen Algorithmus wäre eine Funktion, die alle Duplikate aus einer unsortierten Datensammlung entfernt:

//als Quellbereich wird ein Forward-Iterator benötigt, weil Input-Iteratoren nicht sicher kopiert werden können
template<typename FwdIt,typename OutIt>
OutIt unsorted_unique_copy(FwdIt sbeg,FwdIt send,OutIt dbeg)
{
  for(FwdIt pos=sbeg;pos!=send;++pos)
    if(find(sbeg,pos,*pos)==pos) *dbeg++ = *pos;
  return dbeg;
}

template<typename FwdIt>
FwdIt unsorted_unique(FwdIt beg,FwdIt end)
{
  return unsorted_unique_copy(beg,end,beg);
}

Um den Algorithmen die Arbeit zu erleichtern, existiert eine Hilfsklasse "iterator_traits", die einige Typdefinitionen für einen Iterator enthält:

template<typename It>
struct iterator_traits
{
  typedef typename It::value_type        value_type;        // Werttyp
  typedef typename It::iterator_category iterator_category; // Kategorie: Output, Input,...
  typedef typename It::difference_type   difference_type;   // Differenz zwischen Iteratoren
  typedef typename It::pointer           pointer;           // Zeiger auf T
  typedef typename It::reference         reference          // Referenz auf T
};

Die Typdefinitionen dieser Klasse können verwendet werden, um z.B. den Typ einer temporären Variablen passend zum Iterator festzulegen.

template<typename Iter>
void foo_alg(Iter beg,Iter end)
{
  if(beg==end) return;
  typename iterator_traits<Iter>::value_type temp=*beg;
  ...
}

template<typename Iter>
void bar_alg(Iter beg,Iter end)
{
  typename iterator_traits<Iter>::difference_type dist=distance(beg,end);
  ...
}

Die Kategorie des Iterators kann genutzt werden, um einen Algorithmus so zu optimieren, dass er die "besten" Operationen des Iterator-Typs verwendet:

//"öffentliche Version":
//wird vom Nutzer aufgerufen und delegiert die Arbeit weiter
template<typename Iter>
Iter algo(Iter beg,Iter end)
{ return algo(beg,end,iterator_traits<Iter>::iterator_category()); }

//Version für Random Access Iteratoren:
//nutzt die komplette Vielfalt der Iterator-Arithmetik
template<typename RanIt>
RanIt algo(RanIt beg,RanIt end,random_access_iterator_tag)
{
  ...
}

//Version für andere Typen:
//nutzt nur Inkrement-Operator
template<typename InIt>
InIt algo(InIt beg,InIt end,input_iterator_tag)
{
  ...
}

Dank der Vererbungsbeziehung zwischen den Tag-Klassen wird die zweite Version des Algorithmus' auch von Forward- und Bidirektionalen Iteratoren verwendet.

Außer der allgemeinen Version der iterator_traits - die alle benötigten Typdefinitionen in der instanzierten Klasse voraussetzt - gibt es noch Spezialisierungen für Pointer und const-Pointer. Iterator-Klassen, die die benötigten Typen nicht selber bereitstellen können oder wollen - z.B. weil sie aus einer fremden Bibliothek integriert wurden - , dürfen ebenfalls eine Spezialisierung der iterator_traits anlegen.

Anmerkung: Wenn ein eigener Iterator von der Hilfsklasse iterator<> abgeleitet wird (siehe Kapitel 3.2), stellt er automatisch alle nötigen Typdefinitionen für die Iterator-Traits bereit.

3.4 eigene Funktoren

Als Funktor kann theoretisch jede Klasse verwendet werden, die den operator() überladen hat. Für die Zusammenarbeit mit den STL-Funktor-Adaptern ist es jedoch notwendig, die Argument- und Rückgabetypen des eigenen operator() anzugeben. Diese Arbeit können die Protokollklassen unary_function und binary_function für den Entwickler übernehmen:

//Functor: Res f(Arg x);
template<typename Arg,typename Res>
struct unary_function;

//Functor: Res f(Arg1 x,Arg2 y);
template<typename Arg1,typename Arg2,typename Res>
struct binary_function;

Ein Beispiel für einen selbst definierten Funktor ist die mean-Klasse, die ich in Teil 2 vorgestellt habe. Ein anderes Beispiel wäre ein Composer, der mehrere Funktionen zusammenfassen kann (entsprechende Klassen gibt es z.B. in der Boost-Bibliothek):

//c(x,y) = f(g(x),h(y))
template<typename Op1,typename Op2,typename Op3>
class compose_f_gx_hy_t : public binary_function<typename Op2::argument_type,
                                                 typename Op3::argument_type,
                                                 typename Op1::result_type>
{
  Op1 op1;
  Op2 op2;
  Op3 op3;
public:
  compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
  : op1(f), op2(g), op3(h)
  {}

  typename Op1::result_type
  operator() (const typename Op2::argument_type& x,const typename Op3::argument_type& y)
  { return op1(op2(x),op3(y)); }
};

//Hilfsfunktion zur Erzeugung eines Composers
template<typename Op1,typename Op2,typename Op3>
inline compose_f_gx_hy_t<Op1,Op2,Op3>
compose_f_gx_hy(const Op1& f,const Op2& g,const Op3& h)
{ return compose_f_gx_hy_t<Op1,Op2,Op3>(f,g,h); }

Anmerkung: Analog dazu lassen sich alle Kombinationen aus unären und binären Funktionen mit geeigneten Composern darstellen.

4. weitere Informationen

C++ Referenz

Boost C++ Bibliothek

The C++ Standard Library | ISBN: 0201379260 - Nicolai M. Josuttis - The C++ Standard Library
Die C++-Standardbibliothek | ISBN: 3540256938 - Stefan Kuhlins, Martin Schrader - Die C++ Standardbibliothek

[estartu]

Wow, das war zackig.