Algorithmen I

#ifndef OBJECT_H__
#define OBJECT_H__

#include <iostream>
#include <string>

// Makro für Debug-Ausgabe
#ifdef TRACE_METH
    #define TRACE(_T)   std::cout << _T << " Obj-Nr:" << num << std::endl
#else
    #define TRACE(_T)
#endif

// Object Klasse
class Object
{
   std::string text;  // Objektdatum
   static int count;  // Objektzähler
   int num;           // aktuelle Objektnummer
public:
   Object();                   // Standard-ctor
   Object(const char* pText);  // ctor
   Object(const Object& obj);  // copy-ctor
   virtual ~Object();          // dtor
   // Zuweisungsoperator
   Object& operator = (const Object& rhs);
   // Vergleichsoperatoren
   bool operator < (const Object& rhs) const;
   bool operator == (const Object& rhs) const;
   // Restl. Vergleichsops auf Basis von < und == definieren
   bool operator != (const Object& rhs) const
   {
        return !(*this == rhs);
    }
    bool operator > (const Object& rhs) const
    {
        return rhs < *this;
    }
    bool operator <= (const Object& rhs) const
    {
        return !(rhs < *this);
    }
   bool operator >= (const Object& rhs) const
   {
        return !(*this < rhs);
    }
   // Ausgabeoperator
   friend std::ostream& operator << (std::ostream& os, const Object& obj);
};
// Statisches Datum definieren
int Object::count=0;
// ctor-Definitionen
inline Object::Object()
{
   num = ++count;
   TRACE("std-ctor");
}
inline Object::Object(const char* pText)
{
   num = ++count;
   text = pText;
   TRACE("ctor");
}
inline Object::Object(const Object& obj)
{
   num = ++count;
   text = obj.text;
   TRACE("copy-ctor");
}
// dtor Definition
inline Object::~Object()
{
   TRACE("dtor");
}
// Überladene Operatoren definieren
inline Object& Object::operator = (const Object& rhs)
{
   if (&rhs==this)
      return *this;
   text = rhs.text;
   TRACE("operator=");
   return *this;
}
inline bool Object::operator < (const Object& rhs) const
{
   return text < rhs.text;
}
inline bool Object::operator == (const Object& rhs) const
{
   return text == rhs.text;
}
inline std::ostream& operator << (std::ostream& os, const Object& obj)
{
   std::cout << obj.text;
   return os;
}
#endif

// Beispiel zu Algorithmen
// Suchen und Finden

#include <iostream>
// Algorithmen einbinden
#include <algorithm>
// ostream_iterator einbinden
#include <iterator>
// vordefinierte Functors einbinden
#include <functional>
// Listen-Container einbinden
#include <list>

using std::cout;
using std::endl;

// #define TRACE_METH
#include "object.h"

int main()
{
    // Liste definieren
    typedef std::list<Object> cType;
    cType cont;

    // Liste füllen
    cont.push_back(Object("Eins"));
    cont.push_back(Object("Zwei"));
    cont.push_back(Object("Zwei"));
    cont.push_back(Object("Drei"));
    cont.push_back(Object("Zwanzig"));
    // Liste ausgeben
    cout << "Container-Inhalt: ";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout, ", "));
    cout << '\n';

    // Suche nach einem bestimmten Eintrag mit find()
    cType::iterator iter;
    iter = std::find(cont.begin(), cont.end(), Object("Zwei"));
    if (iter != cont.end())
        cout << "'Zwei' an Position " << unsigned long(std::distance(cont.begin(),iter))
             << " gefunden\n";
    else
        cout << "'Zwei' nicht gefunden!\n";

    // Suche nach ersten Objekt dessen Wert größer 'F' ist mit find_if()
    // Da find_if() an das Predicate nur das aktuelle Objekt übergibt,
    // ist hier bind2nd() notwendig. bind2nd() fungiert als Predicate
    // und ruft dann seinerseits den Functor greater<> auf, der dann das
    // aktuelle Objekt und den zusätzlichen Parameter (hier das Objekt
    // mit dem Wert 'F') erhält.
    iter = std::find_if(cont.begin(), cont.end(),
                        std::bind2nd(std::greater<Object>(),Object("F")));
    if (iter != cont.end())
        cout << "1. Eintrag > 'F' an Position "
             << unsigned long(std::distance(cont.begin(),iter))
             << " gefunden\n";
    else
        cout << "Kein Objekt mit einem Wert groesser 'F' gefunden!\n";

    // Suche nach erstem doppelten Eintrag mit adjacent_find()
    iter = std::adjacent_find(cont.begin(),cont.end());
    if (iter != cont.end())
            cout << "Benachbarte gleiche Werte auf Position "
                 << unsigned long(std::distance(cont.begin(),iter)) << " gefunden\n";
    else
            cout << "Keine benachbarten gleiche Werte gefunden!\n";
}

// Beispiel zu Algorithmen
// Zählen und Minimum/Maximum

#include <iostream>
// Algorithmen einbinden
#include <algorithm>
// ostream_iterator einbinden
#include <iterator>
// vordefinierte Functors einbinden
#include <functional>
// Vektor-Container einbinden
#include <vector>

using std::cout;
using std::endl;

// #define TRACE_METH
#include "object.h"

int main()
{
    // Vektor definieren
    typedef std::vector<Object> cType;
    cType cont;

    // Für Optimierung, verhindert die erneute Speicherreservierung
    // bei jedem neu hinzugefügten Objekt
    cont.reserve(10);
    // Vektor vorbelegen
    cont.push_back(Object("Eins"));
    cont.push_back(Object("Zwei"));
    cont.push_back(Object("Drei"));
    cont.push_back(Object("Zwanzig"));
    cont.push_back(Object("Zwei"));
    cout << "Container-Inhalt: ";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Anzahl der Objekte mit dem Wert "Zwei" zählen
    cType::iterator::difference_type result;
    result = std::count(cont.begin(), cont.end(),Object("Zwei"));
    cout << "Objekte mit dem Wert 'Zwei': " << unsigned long(result) << endl;

    // Anzahl der Objekte zählen die größer/gleich "Z" sind
    result = std::count_if(cont.begin(), cont.end(),
                           std::bind2nd(std::greater_equal<Object>(),Object("Z")));
    cout << "Objekte mit dem Wert >= 'Z': " << unsigned long(result) << endl;
    
    // Kleinstes und größtes Objekt finden
    cType::iterator iterMin, iterMax;
    iterMin = std::min_element(cont.begin(), cont.end());
    iterMax = std::max_element(cont.begin(), cont.end());
    cout << "Kleinstes Element: '" << *iterMin
         << "', groesstes Element: '" << *iterMax << "'\n";
}

// Beispiel zu Algorithmen
// Container-Vergleich

#include <iostream>
// Algorithmen einbinden
#include <algorithm>
// ostream_iterator einbinden
#include <iterator>
// vordefinierte Functors einbinden
#include <functional>
// Vektor-Container einbinden
#include <vector>

using std::cout;
using std::endl;

// #define TRACE_METH
#include "object.h"

int main()
{
    // Container definieren und initialisieren
    typedef std::vector<Object> cType;
    cType cont;
    cont.push_back(Object("Eins"));
    cont.push_back(Object("Zwei"));
    cont.push_back(Object("Zwei"));
    cont.push_back(Object("Drei"));
    cont.push_back(Object("Zwanzig"));
    cout << "Container-Inhalt: ";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Zweiten Container definieren und mit dem Inhalt des
    // ersten Containers initialisieren
    cType toCmp(cont);
    // Viertes Element überschreiben
    // Die String-Zuweisung erstellt über den ctor Object(const char*)
    // ein neues Objekt und übernimmt dieses in den Container
    toCmp.at(3) = "Null";
    cout << "Vergleichs-Container: ";
    std::copy(toCmp.begin(), toCmp.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Vergleiche nun die ersten 3 Elemente der Container miteinander
    bool bRet;
    bRet = std::equal(cont.begin(),cont.begin()+3,toCmp.begin());
    if (bRet)
        cout << "Bereich [0..3) der Container identisch\n";
    else
        cout << "Bereich [0..3) der Container nicht identisch\n";

    // Suche nun die erste Position, an der die beiden Container
    // unterschiedliche Wert haben. Da der Vergleich auf unterschiedlichen
    // Positionen in den Containern beginnen kann, liefert mismatch()
    // zwei Iteratoren zurück, einen für die Position im ersten Container
    // und einen fuer die im zweiten Container
    // pair fuer die die beiden Positionen definieren
    std::pair<cType::iterator, cType::iterator> iterMissed;
    iterMissed = std::mismatch(cont.begin(),cont.end(),toCmp.begin());
    if (iterMissed.first != cont.end())
        cout << "Container weichen ab Position "
             << unsigned long(std::distance(cont.begin(),iterMissed.first))
             << " im ersten Container voneinander ab\n";
    else
        cout << "Container haben identischen Inhalt";

}

// Beispiel zu Algorithmen
// Modifizierende Algorithmen

#include <iostream>
// Algorithmen einbinden
#include <algorithm>
// ostream_iterator einbinden
#include <iterator>
// vordefinierte Functors einbinden
#include <functional>
// Container einbinden
#include <deque>
#include <vector>

using std::cout;
using std::endl;

// #define TRACE_METH
#include "object.h"

// Functor zur Erzeugung von Zufallszahlen
// mit einer Obergrenze
class Randomize
{
    int upperLimit;
  public:
    Randomize(int limit): upperLimit(limit)
    {}
    int operator ()()
    {
        return rand() % upperLimit;
    }
};

int main()
{
    // Container definieren/initialisieren
    typedef std::vector<Object> cType;
    cType cont;
    cont.push_back(Object("Eins"));
    cont.push_back(Object("Zwei"));
    cont.push_back(Object("Drei"));
    cont.push_back(Object("Vier"));
    cout << "Container-Inhalt: ";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Container umgekehrt in einen anderen Containertyp umkopieren
    // Der Ziel-Container enthält am Anfang keine Elemente, deshalb
    // muss für den Kopiervorgang ein entsprechender Inserter
    // verwendet werden
    std::deque<Object> revCont;
    std::copy(cont.begin(), cont.end(), std::front_inserter(revCont));
    cout << "Kopie in umgekehrter Reihenfolge: ";
    std::copy(revCont.begin(), revCont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Tausche die ersten beiden Elemente des Ausgangs-Containers und
    // seiner umgekehrten Kopie gegeneinander aus
    std::swap_ranges(cont.begin(),cont.begin()+2,revCont.begin());
    cout << "Vertausche die beiden ersten Elemente der Container:\n"
         << "Ausgangs-Container: ";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << "\nContainer-Kopie: ";
    std::copy(revCont.begin(), revCont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Leeren Vektor definieren
    std::vector<int> intVect;
    // Vektor mit 5 Zufallszahlen füllen. generate_n() erzeugt die Zahlen
    // über Functor Randomize(). Da der Vektor noch leer ist, müssen die
    // die erzeugten Zahlen über einen Inserter eingefügt werden
    std::generate_n(std::back_inserter(intVect),5,Randomize(100));
    cout << "Vektor mit 5 Zufallszahlen: ";
    std::copy(intVect.begin(),intVect.end(),std::ostream_iterator<int>(cout,", "));
    cout << '\n';

    // Vektor fuer Differenzen definieren
    std::vector<int> diffVect;
    // Differenzen zwischen benachbarten Werten bilden und in neuem
    // Vektor ablegen. Der Trick dabei besteht darin, dass die Start-
    // positionen der beiden Input-Iteratoren um eins verschoben sind.
    // Damit wird die auszuführende Operation minus<> mit den Elementen
    // vector(n) und vector(n+1) aufgerufen. minus<> bildet dann aus diesen
    // beiden Werten die Differenz, die dann mit dem back_inserter in
    // den Differenz-Vektor übernommen wird.
    std::transform(intVect.begin(),intVect.end()-1,
                   intVect.begin()+1,
                   std::back_inserter(diffVect),std::minus<int>());
    cout << "Differenzen der benachbarten Elemente: ";
    std::copy(diffVect.begin(),diffVect.end(),std::ostream_iterator<int>(cout,", "));
    cout << '\n';

    // Differenzen kleiner < 0 durch 0 ersetzen
    std::replace_if(diffVect.begin(),diffVect.end(),std::bind2nd(std::less<int>(),0),0);
    cout << "Differenzen kleiner 0 durch 0 ersetzt: ";
    std::copy(diffVect.begin(),diffVect.end(),std::ostream_iterator<int>(cout,", "));
    cout << '\n';

    // int-Vektor leeren
    intVect.clear();
    // Differenzen umkopieren, 0 Differenzen dabei aber überspringen
    std::remove_copy(diffVect.begin(),diffVect.end(),std::back_inserter(intVect),0);
    cout << "Umkopierte Differenzen, ohne 0 Differenzen: ";
    std::copy(intVect.begin(),intVect.end(),std::ostream_iterator<int>(cout,", "));
    cout << '\n';
}

// Beispiel zu Algorithmen
// Löschende Algorithmen

#include <iostream>
// Algorithmen einbinden
#include <algorithm>
// ostream_iterator einbinden
#include <iterator>
// vordefinierte Functors einbinden
#include <functional>
// Container einbinden
#include <vector>
#include <set>

using std::cout;
using std::endl;

// #define TRACE_METH
#include "object.h"

int main()
{
    // Container definieren/initialisieren
    typedef std::vector<Object> cType;
    cType cont;
    cont.push_back(Object("Eins"));
    cont.push_back(Object("Zwei"));
    cont.push_back(Object("Drei"));
    cont.push_back(Object("Vier"));
    cont.push_back(Object("Fuenf"));
    // Container spiegeln
    // Hier dürfen keine Iteratoren verwendet werden, da beim Spiegeln
    // des Containers eventuell neuer Speicher angefordert wird und
    // dies die Iteratoren ungültig macht!
    for (size_t index=cont.size(); index>0; index--)
        cont.push_back(cont[index-1]);
    cout << "Container-Inhalt:\n";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Entferne alle Elemente mit dem Wert 'Drei'
    // remove() liefert neues logisches Ende des Containers zurück
    // Die Anzahl der Elemente bleibt nach dem Entfernen der Elemente
    // zunächst gleich
    // Iterator für neues logisches definieren
    cType::iterator newEnd;
    newEnd = std::remove(cont.begin(), cont.end(), Object("Drei"));
    cout << "Elemente mit dem Wert 'Drei' entfernt:\n";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';
    // Jetzt alle Elemente hinter dem neuen logischen Ende entfernen
    // (phyikalisches entfernen)
    cont.erase(newEnd,cont.end());
    cout << "Container auf neues logisches Ende verkuerzt:\n";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Entferne alle unmittelbar aufeinander folgenden Elemente
    // die den gleichen Wert besitzen
    newEnd = std::unique(cont.begin(), cont.end());
    // Elemente physikalisch entfernen
    cont.erase(newEnd, cont.end());
    cout << "Alle unmittelbar aufeinander folgenden Werte entfernt:\n";
    std::copy(cont.begin(), cont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';

    // Neuen Container definieren
    cType newCont;
    // Kopiere alle Elemente in einen neuen Container deren Wert
    // kleiner 'M' ist
    std::remove_copy_if(cont.begin(), cont.end(), std::back_inserter(newCont),
                        std::bind2nd(std::greater<Object>(),Object("M")));
    cout << "Element mit einem Wert kleiner 'M' umkopiert:\n";
    std::copy(newCont.begin(), newCont.end(), std::ostream_iterator<Object>(cout,", "));
    cout << '\n';
}