Überladung von Operatoren in C++ (Teil 3) - boost::operators für Fortgeschrittene

pumuckl

Überladung von Operatoren in C++ (Teil 3) - boost::operators für Fortgeschrittene

Willkommen zum dritten Teil der Artikelserie über Operatorüberladung in C++. Nachdem ich im ersten Teil eine Übersicht über die "best practices" bei der Operatorüberladung gegeben habe, habe ich in Teil 2 eine Einführung in die Bibliothek boost::operators gegeben. Neben einem Einblick in die zu Grunde liegenden Konzepte gab es dort auch ein einfaches Beispiel, wie die allgemeinen Mechanismen der Bibliothek genutzt werden können. Im vorliegenden dritten Teil werde ich auf einige weitere Details der Bibliothek eingehen und auch einen Blick in die Implementierung werfen, um das Verständnis der Bibliothek zu vertiefen.

Voraussetzungen

Der Artikel ist als Fortsetzung des zweiten Teils zu verstehen, die dort vorgestellten Konzepte werden daher als bekannt vorausgesetzt. Des Weiteren wird die im zweiten Teil implementierte Klasse Rational weiterentwickelt und erweitert. Für das Kapitel "Hinter den Kulissen" ist ein gewisses Verständnis von Templates und zum Teil anderer, "compilernaher" Begriffe in C++ vonnöten. Eine Liste von Links zu den einzelnen Themen ist am Ende des Artikels zu finden.

Inhalt

1 Gemischte Operatoren
1.1 Gemischte Operatoren und automatische Konvertierungen
1.2 Die einfache Variante: Rational vs. int
1.3 Variante mit Hindernissen: Rational vs. double
2 Iterator-Operatoren und iterator_helpers
2.1 class myvector<T>::iterator
2.2 boost::indexable
3 Hinter den Kulissen
3.1 Der Barton-Nackman Trick
3.2 Base class chaining
3.3 Operatortemplates mit Base class chaining vs. gemischte Operatortemplates
3.4 BOOST_FORCE_SYMMETRIC_OPERATORS und BOOST_HAS_NRVO

1 Gemischte Operatoren

Im vorigen Artikel habe ich die Implementierung der Klasse Rational mit Hilfe von boost::operators vorgestellt. Die Bibliothek wurde dabei für die Operationen von Rational-Objekten untereinander verwendet. Operationen von Ratoinal mit int werden indirekt durch einen impliziten Konvertierungskonstruktor ermöglicht. Das Listing der Klasse ist hier zu finden.

In unseren Rechnungen können wir also Rational-Objekte und ints nach belieben durcheinanderwürfeln, aber was passiert, wenn jetzt float oder double ins Spiel kommen? Es passiert erstmal garnichts, außer dass der Compiler sich beschwert weil er nicht weiß wie Rational und double zusammenhängen. So ganz intuitiv wissen wir das auch nicht unbedingt, also stellen wir erst einmal ein paar Überlegungen an: Eine implizite Konvertierung von double zu Rational ist nicht unbedingt sinnvoll, da der Wertebereich von double viel zu groß ist um ordentliche Konvertierungen zu garantieren. Die umgekehrte Richtung wäre einfach zu machen, allerdings birgt sie gewisse Gefahren: Wenn wir einen Konvertierungsoperator nach double anbieten kann das Probleme bereiten, man weiß nämlich erfahrungsgemäß genau wann der Compiler eine Konvertierung in Betracht zieht: Dann wenn man es am wenigsten erwartet. Wir lassen also den Konvertierungsoperator vorerst aus und schreiben statt dessen eine explizite Konvertierungsfunktion hin, die wir bei gemischten Operationen aufrufen. Schließlich wollen wir im Normalfall nur in den Fällen eine Konvertierung mit Genauigkeitsverlust, wo bei Berechnungen doulbe und Rational aufeinandertreffen.

class Rational /* : boost::operators */
{
  /* ... */

public:
  double toDouble() const
  {
    return static_cast<double>(zaehler)/nenner;
  }
};

Bisher haben wir es im Zusammenhang mit boost::operators nur mit binären Operatoren zu tun gehabt, die zwei Argumente der selben Klasse erwarten. Die Frage ist nun: Kann boost auch mit gemischten Operatoren? Und boost kann. Zu dem Zweck gibts die meisten der genannten Templates für binäre Operatoren auch als zwei-Typ-Version. Beispielsweise sorgt addable<T,U> dafür, dass der operator T operator+ (T const&, U const&) generiert wird, vorausgesetzt der Ausdruck t+=u kompiliert, wenn t und u vom entsprechenden Typ sind. Für die symmetrischen Operatoren werden beide Spielarten generiert, d.h. mit addable<T,U> ist sowohl t+u als auch u+t möglich. Für die asymmetrischen Operatoren gibt es zwei erzeugende Templates, einmal subtractable<T,U> um t-u zu ermöglichen, sowie subtractable2_left<T,U> für u-t . Für letzteres muss allerdings der Ausdruck T(u) kompilieren. Wer den vorigen Artikel aufmerksam gelesen hat wird feststellen, dass sich die Templates für gemischte Operatoren mit denen für das Base class chaining beißen. Die Umsetzung wird im Kapitel "Hinter den Kulissen" genauer besprochen.

1.1 Gemischte Operatoren und automatische Konvertierungen

Bevor wir jetzt drauflostippen und die Operationen zwischen Rational und double einbauen, müssen wir noch auf eines achten: wenn wir gemischte binäre Operatoren für Rational und double haben, können wir uns nicht mehr auf die implizite Konvertierung von ints in Rational verlassen. Bei einer gemischten Operation von int und Rational würde der Compiler die eingebaute Konvertierung von int nach double vorziehen. Das Ergebnis der Operation wäre dann ein double, was wir ja nicht wollen, da Rational genauer als double ist. Also müssen wir die gemischten Operatoren, die wir für double vorgesehen hatten, erstmal für int explizit einbauen.

1.2 Die einfache Variante: Rational vs. int

class Rational : boost::ordered_euclidian_ring_operators<Rational 
               , boost::unit_steppable<Rational           
               , boost::equivalent<Rational              
               , boost::ordered_euclidian_ring_operators<Rational, int //gemischte Operatoren fuer Rational und int
               , boost::equivalent<Rational, int   //gemischter operator== 
               > > > > >
{
  /* ... */

Rational& operator+= (int rhs) 
{ 
  return (*this) += Rational(rhs); 
}

Rational& operator-= (int rhs) 
{ 
  return (*this) -= Rational(rhs); 
}

Rational& operator*= (int rhs) 
{ 
  return (*this) *= Rational(rhs); 
}

Rational& operator/= (int rhs) 
{ 
  return (*this) /= Rational(rhs); 
}
};

//Vergleiche als freie Funktionen:
bool operator < (Rational const& lhs, int rhs)
{ return lhs < Rational(rhs); }

bool operator > (Rational const& lhs, int rhs)
{ return lhs > Rational(rhs); }

Das reicht schon, um sämtliche binären Operationen mit int, die vorher nur durch implizite Konvertierung möglich waren, explizit deklariert und definiert zu haben.

1.3 Variante mit Hindernissen: Rational vs. double

Jetzt können wir uns also den doubles zuwenden, da sieht das Vorgehen ähnlich aus. In unserem Fall ergibt sich allerdings ein kleines Problem: Der Zieltyp von gemischten Operationen mit double und Rational soll double sein, daher müssten wir eigentlich für double den operator+= usw. überladen und double von addable<double, Rational> ableiten. Zusätzlich müsste subtractable2_left<double, Rational> instantiiert werden, andererseits hatten wir uns gegen den Konvertierungsoperator entschieden, so dass ein double nicht mit einem Rational initialisiert werden kann, was aber in den subtractable2_left und dividable2_left -Templates geschieht. Was also tun?

Da wir für double keine Memberfunktionen überladen können, werden operator+= & Co. als freie Funktionen definiert. Da wir double außerdem nicht von den Operatortemplates ableiten können, müssen diese anderweitig instanziiert werden. Wir leiten daher Rational auch von diesen Templates ab.

class Rational : boost::ordered_euclidian_ring_operators<Rational 
               , boost::unit_steppable<Rational           
               , boost::equivalent<Rational              
               , boost::ordered_euclidian_ring_operators<Rational, int
               , boost::equivalent<Rational, int
               , boost::ordered_euclidian_ring_operators<double, Rational   //gemischte Operatoren fuer Rational und double
               , boost::equivalent<double, Rational  //operator== 
               > > > > > > >
{
};

//Freie Opertoren fuer double und Rational
double& operator+= (double& lhs, Rational const& rhs) 
{ 
  return lhs += rhs.toDouble(); 
}

double& operator-= (double& lhs, Rational const& rhs) 
{ 
  return lhs -= rhs.toDouble(); 
}

double& operator*= (double& lhs, Rational const& rhs) 
{ 
  return lhs *= rhs.toDouble(); 
}

double& operator/= (double& lhs, Rational const& rhs) 
{ 
  return lhs /= rhs.toDouble(); 
}

bool operator< (double const& lhs, Rational const& rhs)
{ 
  return lhs < rhs.toDouble(); 
}

bool operator> (double const& lhs, Rational const& rhs)
{ 
  return lhs > rhs.toDouble(); 
}

Damit hätten wir fast alle Operationen zwischen Rational und double abgehakt. Lediglich bei zwei Operatoren wird sich der Compiler beschweren, wenn wir versuchen sie zu verwenden: operator-(Rational, double) und operator/(Rational, double) werden durch die xxx2_left -Templates zwar definiert, bei der Instanziierung stolpert der Compiler aber über die bereits erwähnte Konvertierung von Rational nach double. Die Lösung dafür, ohne einen Konvertierungsoperator public zur Verfügung zu stellen ist, den Konvertierungsoperator private zu machen und die beiden von den Templates definierten Operatoren als friend von Rational zu deklarieren. Der hinzugekommene Code sieht dann wie folgt aus:

#define BOOST_FORCE_SYMMETRIC_OPERATORS
#include <boost/operators.hpp>

class Rational : boost::ordered_euclidian_ring_operators<Rational //Operatoren +, -, *, /, >, >=, <=, !=
               , boost::unit_steppable<Rational           //Postinkrement und -dekrement
               , boost::equivalent<Rational              //operator== 
               , boost::ordered_euclidian_ring_operators<Rational, int
               , boost::equivalent<Rational, int
               , boost::ordered_euclidian_ring_operators<double, Rational
               , boost::equivalent<double, Rational
               > > > > > > >
{
  /* ... */

private: //für boost::XXX2_left<double, Rational>
  operator double() const { return toDouble(); }
public:
  friend double boost::operator/ (Rational const&, double const&);
  friend double boost::operator- (Rational const&, double const&);
};

Das #define vor der Einbindung des boost-Headers ist hier nötig, um ein Problem mit den xxx2_left -Templtes zu beheben. Das Thema wird im Abschnitt "Hinter den Kulissen" ausführlicher besprochen.

Damit ist die Entwicklung unserer Rational-Klasse abgeschlossen. Wir haben mit relativ kleinem Aufwand nur die nötigsten Operatoren für diverse Rechnungen mit Rational, ints und doubles definiert, und durch die 7 Zeilen Templates und zwei friend-Deklarationen haben wir uns mal eben schlappe 47 zusätzliche Operatorüberladungen eingehandelt.

Das endgültige Listing der Klasse Ratoinal ist hier zu sehen, es enthält neben dem besprochenen Code noch die Behandlung der Division durch Null. Die Makros rund um die friend-Deklarationen für operator-(Rational, double) und operator/(Rational, double) berücksichtigen einen Flag, der entscheidet, ob die von boost::operators generierten Operatoren im globalen Namespace oder im Namespace boost liegen.

2 Iterator-Operatoren und iterator_helpers

2.1 class myvector<T>::iterator

In diesem Abschnitt geht es um die Verwendung der Operatortemplates für Iteratorklassen und die iterator_helpers . Zu dem Zweck skizziere ich die Entwicklung einer Iteratorklasse für einen selbstgeschriebenen vector, der ein ähnliches interface und ähnliche Funktionsweise wie ein std::vector haben soll, im Grunde also ein Iterator für C-Arrays. Die Implementierung der Methoden von myvector sei vorgegeben, wir interessieren uns ausschließlich für die Iteratoren.

template <class T> 
class myvector
{
  T* data; //dynamisches Array mit dem reservierten Speicher
public:
  typedef /* ??? */ iterator;
  size_t size();
  size_t capacity();
  /* usw. */
};

std::vector::iterator en sind Random-Access-Iteratoren, genauso wie beliebige Pointer. Da dem vector ein dynamisches Array unterliegt, sind die grundlegenden Operationen der Iteratoren leicht auf die entsprechenden Pointer-Operationen abzubilden - im Prinzip könnte man sogar ganz normale Pointer als vector -iteratoren deklarieren.

Da wir aber ein wenig Typsicherheit haben wollen und außerdem ja die iterator_helper einsetzen wollen, schreiben wir uns eine Iterator-Klasse, die einen Pointer wrapped und auf beliebigen Arrays arbeiten kann - daher nennen wir sie array_iterator . Die Implementierung hat keine großartigen Tücken, daher gibts gleich das komplette Listing:

template <class T>
class array_iterator : public boost::random_access_iterator_helper<array_iterator<T>, T>
{
public:
  typedef T* pointer;
  typedef T value_type;
  typedef std::ptrdiff_t difference_type;

  array_iterator() : ptr(0) {}
  explicit array_iterator(pointer p) : ptr(p) {}
  array_iterator(array_iterator const& other) : ptr(other.ptr) {}

  array_iterator& operator= (array_iterator const& other)
  {
    ptr = other.ptr;
    return *this;
  }

  friend bool operator== (array_iterator const& lhs, array_iterator const& rhs)
  { return lhs.ptr == rhs.ptr; }

  value_type& operator* () const
  {
    return *ptr;
  }

  array_iterator& operator++ ()
  {
    ++ptr;
    return *this;
  }

  array_iterator& operator--()
  {
    --ptr;
    return *this;
  }

  array_iterator& operator+= (difference_type diff)
  {
    ptr += diff;
    return *this;
  }

private:
  pointer ptr;
};

template <class T>
bool operator< (array_iterator<T> const& lhs, array_iterator<T> const& rhs)
{
  return (&(*lhs)) < (&(*rhs));
}

template <class T>
typename array_iterator<T>::difference_type operator- (array_iterator<T> const& lhs, array_iterator<T> const& rhs)
{
  return (&(*lhs)) - (&(*rhs));
}

Anders als in der Boost Doku gezeigt sollte die Ableitung public geschehen, da die nötigen typedefs sonst nicht nutzbar sind, die von einigen Implementierungen der STL-Algorithmen verwendet werden.

Mit der gezeigten Implementation sind die entsprechenden typedefs und Implementationen des std::vector -Nachbaus einfach:

template <class T>
class vector
{
  T* data;
public:
  typedef typename boost::add_const<T>::type const_value_type;
  typedef typename pumu::util::array_iterator<T> iterator;
  typedef typename pumu::util::array_iterator<const_value_type> const_iterator;
  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
};

template <class T>
typename vector<T>::iterator vector<T>::begin()
{
  return iterator(data);
}

template <class T>
typename vector<T>::const_iterator vector<T>::begin() const
{
  return const_iterator(data);
}

Das Template add_const stammt aus boost::TypeTraits und fügt dem Templateparameter ein const hinzu, wenn er nicht schon const ist.

2.2 boost::indexable

Eine kleine Falle, in die man vielleicht tappen könnte, ist die Verwendung von boost::indexable . Das Template ist dazu gedacht, einen operator[] zu generieren, allerdings für Iteratorklassen, nicht für Container! operator[] für Iteratoren ist ein eher selten genutzes (und daher nicht besonders bekanntes) Feature und hat die selbe Semantik wie bei Pointern: i[n] == *(i + n) .

3 Hinter den Kulissen

Die Verwendung der boost::operators Templates ist einfach und funktioniert wunderbar. Dennoch nagt vielleicht an dem einen oder anderen die Neugier, wie ein paar unscheinbare Templates das alles bewerkstelligen können. Die wichtigsten Ideen und Techniken werden hier kurz skizziert.

3.1 Der Barton-Nackman Trick

Der Barton-Nackman Trick ist im Grunde ein spezielles Feature des Argument Dependent Lookup (ADL). Wenn ein Compiler einen nicht näher qualifizierten Funktionsaufruf (oder Operatoraufruf) findet, schaut er nicht nur in den bekannten Funktionen (Funktionen im aktuellen Namensraum und dessen übergeordneten Namensräumen) nach einer passenden Signatur, sondern auch in den Namensräumen der Argumente. Außerdem werden alle friend-Deklarationen der Argumente und ihrer Basisklassen berücksichtigt. Dieses letzte Feature macht sich boost::operators zunutze. Beispielsweise ist boost::addable<T> in etwa (vereinfacht dargestellt) definiert wie

template <class T>
struct addable
{
  friend operator+ (T const& lhs, T const& rhs)
  {
    T tmp(lhs);
    tmp += rhs;
    return tmp;
  }
};

Wenn der Compiler jetzt einen Aufruf a+b sieht, wo z.B. a und b vom Typ Rational sind, dann schaut der Compiler nach der erfolglosen Suche in den bekannten Namensräumen und den Namensräumen von Rational nach friend-Deklarationen in Rational und deren Basisklassen und findet die friend-Deklarationen in addable<Rational>.

Diese Technik wird ab und zu noch als friend name injection bezeichnet, allerdings ist dies nicht mehr ganz korrekt; friend name injection war ursprünglich das Compiler-Feature, auf dem der Barton-Nackman Trick aufbaute. Dieses Feature ist im Standard nicht mehr enthalten, allerdings wurde die entsprechende ADL-Regel extra für diese Anwendung in den Standard aufgenommen.

3.2 Base class chaining

Das base class chaining wird in boost::operators eingesetzt, um gewisse Unzulänglichkeiten vieler Compiler im Zusammenhang mit der empty base class optimization (EBCO) und Mehrfachvererbung zu vermeiden. Während bei der einfachen Vererbung leere Basisklassen keinen Beitrag zur Größe der abgeleiteten Klasse haben, schaffen die meisten Compiler dies nicht bei Mehrfachvererbung. Die ursprünglich eingesetzte Vererbung von zig Operator-Templates gleichzeitig (siehe vorheriger Artikel) führt in dem Fall dazu, dass die Größe einer kleinen Klasse wie Rational unnötig durch leere Basisklassen aufgebläht wird. Beim base class chaining hat jede Klasse genau eine Basisklasse, die ganzen Operator-Templates werden in einer Art "Vererbungskette" aneinandergereiht.

3.3 Operatortemplates mit Base class chaining vs. gemischte Operatortemplates

Mit der Einführung des base class chaining ergibt sich ein bestimmtes Problem: es ist auf den Ersten Blick nicht feststellbar, ob addable<A, B> den einfachen oparator+(A const&, A const&) erzeugen soll und von B abgeleitet ist, oder ob es den gemischten operator+(A const&, B const&) erzeugen soll. Das Dilemma ist auf trickreiche Art und weise gelöst:

Die eigentlichen Operatortemplates heißen addable1 und addable2 für Operatoren mit einem Typ und gemischte Operatoren, so dass sie gut zu unterscheiden sind. Für die Unterscheidung bei addable wird ein zusätzlicher Templateparameter eingeführt, der per default den Wert is_chained_base<B>::value hat. is_chained_base ist dabei eine Template-Metafunktion, die besagt, ob B als Basisklasse betrachtet werden soll oder nicht. Per default liefert diese Metafunktion den Typ ::boost::detail::false_t zurück. Für die Operatortemplates wird sie allerdings partiell spezialisiert, so dass sie ::boost::detail::true_t liefert. An Hand des zusätzlichen Templateparameters kann also entschieden werden, ob B nun Basisklasse oder zweite Operandenklasse sein soll, und alles ohne dass unsereiner es sieht.

Wenn man allerdings eine eigene Klasse an das obere Ende der Hierarchie stellen möchte, dann muss man das explizit machen: damit das letzte Element im base class chaining nicht fälschlicherweise als gemischtes Template interpretiert wird, muss man statt addable<myType, myBase> eben addable1<myType, myBase> schreiben. Alternativ könnte man theoretisch auch is_chained_base spezialisieren, so dass es für myBase ein true_t liefert, allerdings ist dies ein Implementationsdetail von boost, das sich jederzeit ändern kann - gäbe es ein private für namespaces, dann wäre es hier sicher angebracht.

3.4 BOOST_FORCE_SYMMETRIC_OPERATORS und BOOST_HAS_NRVO

Boost hat für die Implementierung der kommutativen (+, *, ^, &, |) und nichtkommutativen (-, /, Operatoren jeweils zwei Alternativen, die durch #define s ausgewählt werden:

#if defined(BOOST_HAS_NRVO) || defined(BOOST_FORCE_SYMMETRIC_OPERATORS)
//symmetrische, NRVO-freundliche Implementierung
#else
//asymmetrische Implementierung
#endif

Dabei ist BOOST_HAS_NRVO ein Flag, das durch den Boost Config-Header gesetzt wird in Abhängigkeit von Compilerversion und Debug-/Releasemodus. Dieser Header weiß bei den meisten gängigen Compilern, ob sie die Named Return Value Optimization (NRVO) unterstützen oder nicht. Für die kommutativen Operatoren sind beide Implementierungen ohne größere Überraschung, für addable1<T> siehts beispielsweise so aus:

//symmetrische Implementierung:
T operator+(T const& lhs, T const& rhs)
{ T nrv(lhs); nrv += rhs; return nrv; }
//asymmetrische Implementierung:
T operator+(T lhs, T const& rhs) //Linkes Argument wird kopiert!
{ return lhs += rhs; }

Die Implementierung der von addable2<T,U> generierten Operatoren sieht sehr ähnlich aus, dabei wird in der asymmetrischen Implementierung immer das T-Argument per Value übergeben, das U-Argument per const Referenz.

Für die nichtkommutativen Operatortemplates ist das Schema ähnlich. subtractable1<T> und subtractable2<T,U> (d.h. T operator-(T,U) ) liefern keine Überraschung. Der einzige Knackpunkt ist subtractable2_left<T,U> , also T operator-(U, T) . Hier sehen die Implementierungen wie folgt aus:

//symmetrische Implementierung:
T operator-(U const& lhs, T const& rhs)
{ T nrv(lhs); nrv -= rhs; return nrv; }
//asymmetrische Implementierung:
T operator-(U const& lhs, T const& rhs)
{ return T(lhs) -= rhs; }

Zu beachten ist hierbei, dass bei beiden Versionen lhs vom Typ U ist und explizit in ein T gewandelt wird - daher die Umstände mit dem Konvertierungsoperator von Rational nach double in Abschnitt 1.3. Die Macher von Boost haben für die asymmetrische Implementierung noch einen kleinen Kommentar spendiert:

operators.hpp schrieb:

Note that the implementation of BOOST_OPERATOR2_LEFT(NAME) only looks cool, but doesn't provide optimization opportunities to the compiler

Bei der Umsetzung der gemischten Operatoren von Rational und double stellt uns diese "coole" Implementierung vor ein Problem: Das Ergebnis der Konvertierung T(lhs) ist ein r-Value. Wenn operator-= ein Member von T ist (was bei jeder vernünftig implementierten Klasse der Fall ist), macht das nichts weiter. Im Fall von double ist der Operator aber eine freie Funktion, für die laut Standard der linke Operand ein l-Value sein muss. Aus dem Grund waren wir für die Implementierung der Rational-Klasse gezwungen, vor der Einbindung von boost::operators das #define BOOST_FORCE_SYMMETRIC_OPERATORS zu setzen. Der MSVC 2008 beispielsweise hat im Debugmodus keine NRVO und spuckt daher ohne das #define bei der Instantiierung von subtractable2_left<double, Rational> und dividable2_left<double, Rational> Fehlermeldungen.

Quellen und Links

Teil 2 der Artikelserie - Einführung in boost::operators: http://magazin.c-plusplus.net/artikel/�berladung von Operatoren in CPlusPlus (Teil 2) - Einf�hrung in boost%3A%3Aoperators

boost::operators Dokumentation: http://www.boost.org/doc/libs/1_39_0/libs/utility/operators.htm

Barton-Nackman Trick: http://en.wikipedia.org/wiki/Barton-Nackman_trick

und natürlich google