Immer Ärger mit init

Wir haben also grade gesehen, dass wir mit reduce wieder unserem alten Problem mit init über den Weg laufen: Wie soll die Initialisierung für beliebige Operatoren und Wertetypen stattfinden?

Konkret fragen wir uns, wie denn ein sinnvoller Wert e von init für den Maximums-Operator überhaupt aussieht — eine Frage, die sich unabhängig von der generischen Implementierung von reduce stellt! Dafür muss ja für alle x gelten: max(x,e) == x, also muss immer e <= x sein. Mathematisch würden wir e gleich -∞ setzen. Da wir es hier mit Datentypen mit endlichen Wertebereichen zu tun haben, reicht es, den jeweils kleinsten Wert des Datentyps zu nehmen. Zum Glück scheint uns die Standard-Bibliothek hier mit numeric_limits zu helfen, denn diese Klasse ist zumindest für die eingebauten arithmetischen Typen spezialisiert und hat min() und max() Funktionen. Leider verhalten sich diese Funktionen für ganzzahlige und Fließkommatypen unterschiedlich: Während für ganzzahlige Typen min() tatsächlich den kleinsten Wert liefert, erhält man für Fließkomma-Typen den kleinsten positiven Wert. Wir müssen also aufpassen:

double ad[N] = { ... };
int    ai[N] = { ... };
double max_ad = reduce(a, a+N, -numeric_limits<double>::max(), std::max<double>);
int    max_ai = reduce(a, a+N,  numeric_limits<int>   ::min(), std::max<int>);

Das ist allerdings nicht so schön, extrem fehleranfällig und in einem generischen Kontext (wenn ich beim Aufruf von reduce eben nicht den konkreten Typ kenne) unbrauchbar. Was können wir also tun?

init und beliebige Operatoren

Zum einen können wir unser Template neutral_element für den Fall des Maximum-Operators ausbauen. Wie vorher schon einmal diskutiert, können auch wir eine Variante ohne init-Argument implementieren, die entweder nur nichtleere Sequenzen behandelt und das erste Element zur Initialisierung nimmt (mit den besprochenen Nachteilen), oder sich auf die grade angerissene Erweiterung von neutral_element stützt. Eine solche Erweiterung wäre dann etwa so zu benutzen:

double ad[N] = { ... };
int    ai[N] = { ... };
double max_ad = reduce(a, a+N, neutral_element<double,std::max<double> >::value(), std::max<double>);
int    max_ai = reduce(a, a+N, neutral_element<int,   std::max<int>    >::value(), std::max<int>);

Schöner wird der Aufruf dadurch jedenfalls nicht (aber immerhin sicherer). Auch stellt sich die Frage, ob der Operator per Template-Argument an neutral_element übergeben wird, oder ob wir ein Operator-spezifisches Template benutzen:

template<typename T> struct neutral_element_addition;
template<typename T> struct neutral_element_max;
// ... etc ...

Für diese Variante spricht, dass das neutrale Element nicht direkt vom konkreten Operatortyp abhängt, sondern nur von der mathematischen Operation, die er definiert (es kann ja durchaus meine, Ihre und weitere Implementierungen eines Maximum-Operators geben). Auf der anderen Seite kommt jetzt wieder das Argument des generischen Kontexts: Wenn ich nicht weiss, welcher mathematische Operator an reduce übergeben wird, kann ich auch nicht die richtige Version von neutral_element_xxx auswählen. Das sinnvollste ist es wohl, beide Varianten zu implementieren, und neutral_element auf neutral_element_xxx zurückzuführen.

Implementierung für das Maximum

Am Beispiel des Maximums heisst das, wir implementieren neutral_element_max als Basis, und führen alle Spezialisierungen für konkrete Maximums-Operatoren werden darauf zurück.

template<typename T> struct neutral_element_max { ... };

template<typename T, typename Op> struct neutral_element {};

template<typename T> 
struct neutral_element<T, std::max<T> > : public neutral_element_max<T> {};

Bei der Implementierung von neutral_element_max können wir uns dann auf std::numeric_limits stützen. Dieses Template enthält zum Glück auch Klassifizierungen, ob es überhaupt für einen Typ spezialisiert ist und ob dieser ganzzahlig ist. Damit sieht unsere Logik für neutral_element_max wie folgt aus:

1. Wenn std::numeric_limits für T spezialisiert ist
   1. Wenn T ein integraler Typ ist: value() liefert std::numeric_limits::min()
   2. Sonst (T ist Fließkomma-Typ): value() liefert -std::numeric_limits::max()
2. Sonst (nicht spezialisiert für T) lassen wir neutral_element_max offen (keine Default-Implementierung).

Das übersetzt sich jetzt in ein etwas längliches Stück C++ Template code, mit ausgiebigem Gebrauch partieller Spezialisierung (Übungsaufgabe!). Für manche Fälle, die nicht durch std::numeric_limits erledigt werden, können wir darüber hinaus eigene Spezialisierungen von neutral_element_max anbieten. Z.b. ist für std::string der leere String das neutrale Element bzgl. der Maximums-Bildung.

... und wenn wir kein neutrales Element finden?

Natürlich wird es nicht für alle Kombinationen von Typen und Operatoren gelingen, ein sinnvolles neutrales Element zu finden. Zum Beispiel bei der Minimums-Bildung auf Strings: Hier ist das neutrale Element der maximale String, dieser müsste das Zeichen mit maximalem ASCII-Code maximal oft (also std::string::max_size() oft) enthalten und sprengt damit den Hauptspeicher. Wenn keine Spezialisierung von neutral_element für die Kombination von Wertetyp und Operator vorliegt, muss eine Implementierung von reduce daraus folgern, dass es kein neutrales Element gibt. In diesen Fällen sollte also zur Compilezeit eine Implementierung ausgewählt werden, die das erste Element zur Initialisierung benutzt und damit eine nicht-leere Input-Sequenz erfordert (so wie wir das schon diskutiert haben).

Reduce mit automatischem init

Damit haben wir im Prinzip alle Bausteine zusammen, um eine Version von reduce mit automatischer Initialisierung zu implementieren:

// Wenn die Kombination von BinOp und value_type kein neutrales Element hat,
// dann muss begin != end gelten, also ein nicht-leerer Inputbereich vorliegen.
template<class Iterator, class BinOp>
typename value_type<Iterator>::result
reduce(Iterator begin, Iterator end, BinOp op);

Zunächst definieren wir 2 Varianten reduce_non_empty (falls kein neutrales Element bekannt ist) und reduce_neutral_element (falls neutrales Element bekannt ist). Wir setzen voraus, dass wir mit neutral_element<T,Op>::is_specialized eben dies abfragen können (das kann man einfach in die oben erwähnte Implementierung von neutral_element einbauen). Um bequem zwischen beiden Versionen auswählen zu können, definieren wir noch eine Hilfsklasse reduce_select mit einem boolschen Template-Parameter (neutral_element spezialisiert oder nicht).

// Version requiring a non-empty range [begin,end)
template<typename Iterator, typename BinOp>
typename value_type<Iterator>::result
reduce_non_empty(Iterator begin, Iterator end, BinOp op)
{ 
  typename value_type<Iterator>::result res = *begin;
  ++begin;
  while(begin != end) {
    res = op(res, *begin);
    ++begin;
  } 
  return res;
}

// Version relying on neutral_element<value_t, BinOp> being specialized
template<class Iterator, class BinOp>
typename value_type<Iterator>::result
reduce_has_neutral_element(Iterator begin, Iterator end, BinOp op)
{ 
  typedef typename value_type<Iterator>::result value_t;
  return reduce(begin, end, neutral_element<value_t, BinOp>::value(), op); 
}


// helper class to select:
// reduce_non_empty           (IsSpecialized = false)
// reduce_has_neutral_element (IsSpecialized = true)
template<bool IsSpecialized> struct reduce_select;

// select reduce_non_empty
template<> struct reduce_select<false>
{ 
  template<typename Iterator, typename BinOp>
  static typename value_type<Iterator>::result
  reduce(Iterator begin, Iterator end, BinOp op) 
  {  
    return reduce_non_empty(begin, end, op); 
  }
};

// select reduce_has_neutral_element
template<> struct reduce_select<true>
{ 
  template<typename Iterator, typename BinOp>
  static typename value_type<Iterator>::result
  reduce(Iterator begin, Iterator end, BinOp op) 
  {  
    typedef typename value_type<Iterator>::result value_t;
    return reduce(begin, end, neutral_element<value_t, BinOp>::value(), op); 
  }
};


// Select either reduce_non_empty or reduce_has_neutral_element
template<class Iterator, class BinOp>
typename value_type<Iterator>::result
reduce(Iterator begin, Iterator end, BinOp op) 
{ 
  typedef typename value_type<Iterator>::result value_t;
  return reduce_select<neutral_element<value_t, BinOp>::is_specialized>::reduce(begin, end, op);
}

Das wirkt jetzt schon ganz schön verwickelt, obwohl im Prinzip nicht viel passiert. Allerdings war das jetzt auch die "Fußgänger-Version"; mit speziellen Bibliotheken für die generische Programmierung wie boost::enable_if läßt sich das deutlich straffen. Zum Glück braucht ein Nutzer nur die eigentliche reduce Funktion zu sehen (und die Variante ohne init-Argument). Gibt es noch etwas zu reduce zu sagen?

• <<<Vorherige Seite
• Nächste Seite >>>