
Noch mehr Spass mit reduce
Jetzt nochmal zurück zu unseren Strings.
In unserem obigen Beispiel
hätte ich, ehrlich gesagt,
lieber "This is a sentence"
anstelle von "Thisisasentence"
gesehen.
Eigentlich muss man ja nur ein Leerzeichen zwischen 2 Worten einfügen ...
das macht der vordefinierte operator+(std::string const&, std::string const&)
jedoch nicht.
Aber jetzt können wir uns ja unseren eigenen Operator definieren!
(Noch eine Übungsaufgabe).
Wir können unser reduce
auch für Aufgaben einsetzen,
an die man evtl. nicht unmittelbar denkt,
z.B. das Auftreten von Elementen mit bestimmten Eigenschaften zählen (std::count_if
).
Wir hatten
weiter oben
ja schon gesagt,
dass init
durchaus ein anderer Typ als der Wertetyp der Sequenz sein kann.
Der Operator sollte also genau genommen als erstes Argument einen Wert mit dem Typ von init
(oder konvertierbar) akzeptieren,
und als zweites Argument einen Wert vom Sequenz-Wertetyp (oder konvertierbar).
Damit können wir sehr einfach die Funktionalität von std::count_if
mit unserem
reduce
erreichen:
template<typename Pred, typename T>
struct count {
Pred p;
count(Pred p) : p(p) {}
int operator()(int cnt, T t) const { return cnt + (p(t) ? 1 : 0); }
};
struct is_positive { bool operator()(float x) const { return x > 0.0; } };
int cnt_positive = reduce(a, a+N, value<int>(0), count<is_positive,float>());
Relativ lästig ist es, dass diese Operatoren und Prädikate separat definiert werden müssen,
grade wenn sie eher ad hoc sind.
Bibliotheken wie boost.bind
machen es etwas einfacher, vorhandenes anzupassen.
In C++11 liefern lambdas eine allgemeine Lösung:
int cnt_positive = reduce(a, a+N, value<int>(0),
[](int cnt, float x) { return cnt + (x > 0 ? 1 : 0); })
Damit sollte auch klar sein, wie man an Fälle wie den folgenden herangeht:
struct employee {
string name;
float salary;
};
vector<employee> staff;
// ... fill staff ...
float total_salaries = reduce(staff.begin(), staff.end(), ???);
Auch das wird mit Cpp11 durchaus einfacher ...
Spassbremsen
Allerdings ist es schon sinnvoll,
sich Gedanken über die Grenzen des Anwendungsbereichs von reduce
zu machen.
So hat das Beispiel mit string
den Nachteil,
dass bei jeder Addition wieder Speicher allokiert wird,
weil der Ergebnisstring in res
wieder ein Stückchen größer wird.
Effizienter wäre es, den benötigten Speicher vorab zu reservieren.
Aber dazu müssten wir noch erhebliche Arbeit leisten und möglicherweise das Interface ändern.
Der linear wachsende Speicherbedarf ist
ein entscheidender struktureller Unterschied zur Addition von Zahlen,
bei denen das Ergebnis diesselbe Größe hat wie die einzelnen Input-Daten
(auch in den Fällen, in denen ein Ergebnistyp mit größerem Wertebereich gewählt wird, ist die Größe ja fest).
Deswegen macht es wohl Sinn, eine eigene Abstraktion,
etwa concat
einzuführen, die hierauf explizit Rücksicht nimmt.
Übungsaufgabe: Wie würde man concat
generisch implementieren?
Bei der ursprünglichen, auf Addition beschränkten Implementierung von sum
war die (scheinbare, siehe Probleme mit der Initialisierung) Anwendbarkeit auf string
ja auch nur der zufälligen Tatsache geschuldet,
dass beim Sprachentwurf der operator+
bei string
für die String-Verkettung gewählt wurde
— in anderen Sprachen werden andere Operatoren benutzt.
Experten wie Alexander Stepanov halten die Wahl von operator+
hier sogar für einen Fehler,
weil Verkettung eben nicht kommutativ ist,
wie man es bei diesem Operator erwarten würde.
Das macht bei unserem sum
zwar keinen Unterschied,
aber ich kann mir durchaus Fälle vorstellen,
in denen die Reihenfolge geändert wird,
z.B. bei der parallelen Implementierung.
Dies sollte dann zwar klar spezifiziert werden,
aber eine solche unkonventionelle nicht-Kommutativität
bleibt eine Fehlerquelle.
Unsere reduce
-Implementierung ist auch dort nicht optimal,
wo man des Ergebnis erhalten kann, ohne die gesamte Sequenz zu durchlaufen,
z.B. bei der Reduktion einer Sequenz boolscher Werte mit logical_and
oder logical_or
.
Also genügt reduce
auch nicht voll unserer
strengen Definition.
Übungsaufgabe: Kann man das reparieren?
Über den C++ Tellerrand
Was wir hier reduce
genannt haben, ist unter verschiedenen Namen bekannt.
In der C++-Standardbibliothek heißt diese Funktion accumulate
(und sie hat durch das zusätzliche init-Argument das
oben beschriebene Problem des genauen Typs bei Literalen).
In der funktionalen Programmierung nennt man diese higher-order function typischerweise fold bzw. genauer foldl (weil von links geklammert wird: a+b+c = (a+b)+c). Das Gegenstück foldr würde man erhalten, wenn die Sequenz umgekehrt durchlaufen wird, oder, wie in der funktionalen Programmierung üblich, eine rekursive Implementierung gewählt würde:
template<typename Iterator, typename T, typename Op>
T reduce_rec(Iterator begin, Iterator end, value<T> init, Op op)
{ return (begin == end? init : op(*begin, reduce_rec(begin+1, end, init, op))); }
Hier würde übrigens init
erst ganz am Schluss benutzt.