Kapitel 29. Boost.Algorithm

Boost.Algorithm stellt Algorithmen zur Verfügung, die die Algorithmen aus der Standardbibliothek ergänzen. Dabei versucht Boost.Algorithm nicht, neue Konzepte einzuführen, wie es zum Beispiel Boost.Range macht. Die von Boost.Algorithm angebotenen Algorithmen ähneln denen aus der Standardbibliothek und erwarten zum Beispiel ebenfalls üblicherweise mindestens zwei Iteratoren.

Beachten Sie, dass es zahlreiche Algorithmen in anderen Boost-Bibliotheken gibt. So finden Sie beispielsweise Algorithmen zum Bearbeiten von Strings in Boost.StringAlgorithms. Die von Boost.Algorithm angebotenen Algorithmen sind nicht an bestimmte Klassen wie beispielsweise std::string gebunden, sondern können wie die Algorithmen aus der Standardbibliothek mit beliebigen Containern verwendet werden.

#include <boost/algorithm/cxx11/one_of.hpp>
#include <array>
#include <iostream>

using namespace boost::algorithm;

int main()
{
  std::array<int, 6> a{{0, 5, 2, 1, 4, 3}};
  auto predicate = [](int i){ return i == 4; };
  std::cout.setf(std::ios::boolalpha);
  std::cout << one_of(a.begin(), a.end(), predicate) << '\n';
  std::cout << one_of_equal(a.begin(), a.end(), 4) << '\n';
}

Boost.Algorithm stellt mit boost::algorithm::one_of() einen Algorithmus zur Verfügung, um zu überprüfen, ob eine Bedingung genau einmal wahr ist. Die zu überprüfende Bedingung wird dabei als Prädikat an die Funktion übergeben. So gibt der Aufruf von boost::algorithm::one_of() im Beispiel 29.1 true zurück, weil sich die Zahl 4 genau einmal in a befindet.

Wenn Sie Werte in einem Container auf Gleichheit überprüfen möchten, können Sie auf die Funktion boost::algorithm::one_of_equal() zugreifen. Sie übergeben dann kein Prädikat, sondern den auf Gleichheit zu überprüfenden Wert. So gibt der Aufruf von boost::algorithm::one_of_equal() im Beispiel 29.1 ebenfalls true zurück.

boost::algorithm::one_of() ergänzt die Algorithmen std::all_of(), std::any_of() und std::none_of() aus der Standardbibliothek. Da diese Algorithmen erst mit C++11 in die Standardbibliothek aufgenommen wurden, stellt Boost.Algorithm mit boost::algorithm::all_of(), boost::algorithm::any_of() und boost::algorithm::none_of() die Algorithmen auch Entwicklern zur Verfügung, die nicht mit C++11 arbeiten. Sie finden diese Algorithmen in den Headerdateien boost/algorithm/cxx11/all_of.hpp, boost/algorithm/cxx11/any_of.hpp und boost/algorithm/cxx11/none_of.hpp.

Neben den Algorithmen boost::algorithm::all_of(), boost::algorithm::any_of() und boost::algorithm::none_of() bietet Boost.Algorithm auch boost::algorithm::all_of_equal(), boost::algorithm::any_of_equal() und boost::algorithm::none_of_equal() an.

Boost.Algorithm bietet weitere Algorithmen aus der C++11-Standardbibliothek an. So können Sie zum Beispiel auf boost::algorithm::is_partitioned(), boost::algorithm::is_permutation(), boost::algorithm::copy_n(), boost::algorithm::find_if_not() oder boost::algorithm::iota() zugreifen. Diese Funktionen verhalten sich genauso wie die Funktionen aus der C++11-Standardbibliothek und richten sich vor allem an Entwickler, die nicht mit C++11 arbeiten. Boost.Algorithm bietet jedoch einige Varianten der Funktionen an, die auch für C++11-Entwickler interessant sein können.

#include <boost/algorithm/cxx11/iota.hpp>
#include <boost/algorithm/cxx11/is_sorted.hpp>
#include <boost/algorithm/cxx11/copy_if.hpp>
#include <vector>
#include <iterator>
#include <iostream>

using namespace boost::algorithm;

int main()
{
  std::vector<int> v;
  iota_n(std::back_inserter(v), 10, 5);
  std::cout.setf(std::ios::boolalpha);
  std::cout << is_increasing(v) << '\n';
  std::ostream_iterator<int> out{std::cout, ","};
  copy_until(v, out, [](int i){ return i > 12; });
}

Boost.Algorithm bietet in der Headerdatei boost/algorithm/cxx11/iota.hpp den C++11-Algorithmus boost::algorithm::iota() an, der aufsteigende Zahlen generiert. Dazu müssen dieser Funktion zwei Iteratoren auf den Anfang und das Ende eines Containers übergeben werden. Die Elemente im Container werden daraufhin mit aufsteigenden Zahlen überschrieben.

Im Beispiel 29.2 kommt nicht boost::algorithm::iota(), sondern boost::algorithm::iota_n() zum Einsatz. Diese Funktion erwartet lediglich einen Iterator, auf den zu generierende Zahlen ausgegeben werden sollen. Die Anzahl der zu generierenden Zahlen wird als dritter Parameter an boost::algorithm::iota_n() übergeben.

boost::algorithm::is_increasing() ist in der Headerdatei boost/algorithm/cxx11/is_sorted.hpp definiert, in der Sie auch den C++11-Algorithmus boost::algorithm::is_sorted() finden. boost::algorithm::is_increasing() ist gleichbedeutend mit boost::algorithm::is_sorted(). Der Funktionsname drückt jedoch klar aus, dass auf eine aufsteigende Sortierung überprüft wird. Neben boost::algorithm::is_increasing() definiert die Headerdatei auch eine Funktion boost::algorithm::is_decreasing().

Beachten Sie, dass im Beispiel 29.2 v direkt an boost::algorithm::is_increasing() übergeben wird. Die von Boost.Algorithm angebotenen Funktionen liegen auch in einer range-basierten Variante vor, so dass Sie Container direkt übergeben können und nicht wie bei Algorithmen aus der Standardbibliothek zwei Iteratoren einzeln übergeben müssen.

boost::algorithm::copy_until() finden Sie in der Headerdatei boost/algorithm/cxx11/copy_if.hpp. Es handelt sich hierbei um eine weitere Variante von std::copy(). So steht neben boost::algorithm::copy_until() auch die Funktion boost::algorithm::copy_while() zur Verfügung.

Wenn Sie Beispiel 29.2 ausführen, wird true als Ergebnis von boost::algorithm::is_increasing() ausgegeben. Außerdem werden mit boost::algorithm::copy_until() die Zahlen 10, 11 und 12 in die Standardausgabe geschrieben.

#include <boost/algorithm/cxx14/equal.hpp>
#include <boost/algorithm/cxx14/mismatch.hpp>
#include <vector>
#include <iostream>

using namespace boost::algorithm;

int main()
{
  std::vector<int> v{1, 2};
  std::vector<int> w{1, 2, 3};
  std::cout.setf(std::ios::boolalpha);
  std::cout << equal(v.begin(), v.end(), w.begin(), w.end()) << '\n';
  auto pair = mismatch(v.begin(), v.end(), w.begin(), w.end());
  if (pair.first != v.end())
    std::cout << *pair.first << '\n';
  if (pair.second != w.end())
    std::cout << *pair.second << '\n';
}

Boost.Algorithm bietet nicht nur Algorithmen aus der C++11-Standardbibliothek an. Es stehen auch Algorithmen zur Verfügung, die mit C++14 in die Standardbibliothek aufgenommen wurden. So greift Beispiel 29.3 auf zwei Funktionen boost::algorithm::equal() und boost::algorithm::mismatch() zu, die erst seit C++14 zur Standardbibliothek gehören. Im Gegensatz zu den gleichnamigen Funktionen, die seit C++98 Teil der Standardbibliothek sind, werden den neuen Funktionen vier und nicht drei Iteratoren übergeben. Die Algorithmen im Beispiel 29.3 erwarten nicht, dass die zweite Sequenz mindestens so viele Elemente wie die erste Sequenz besitzt.

Während boost::algorithm::equal() einen Rückgabewert vom Typ bool hat, gibt boost::algorithm::mismatch() zwei Iteratoren in einem std::pair zurück. first und second zeigen auf die beiden Elemente in der ersten und zweiten Sequenz, die die ersten sind, die sich unterscheiden. Beachten Sie, dass die entsprechenden Iteratoren auch auf das Ende einer Sequenz zeigen können.

Wenn Sie Beispiel 29.3 ausführen, wird false und 3 ausgegeben. false ist der Rückgabewert von boost::algorithm::equal(), 3 das dritte Elemente in w. Da die ersten beiden Elemente in v und w gleich sind, gibt boost::algorithm::mismatch() in first einen Iterator auf das Ende von v und in second einen Iterator auf das dritte Element in w zurück. Da first auf das Ende von v zeigt, wird der Iterator nicht dereferenziert, und es findet keine Ausgabe statt.

#include <boost/algorithm/hex.hpp>
#include <vector>
#include <string>
#include <iterator>
#include <iostream>

using namespace boost::algorithm;

int main()
{
  std::vector<char> v{'C', '+', '+'};
  hex(v, std::ostream_iterator<char>{std::cout, ""});
  std::cout << '\n';

  std::string s = "C++";
  std::cout << hex(s) << '\n';

  std::vector<char> w{'4', '3', '2', 'b', '2', 'b'};
  unhex(w, std::ostream_iterator<char>{std::cout, ""});
  std::cout << '\n';

  std::string t = "432b2b";
  std::cout << unhex(t) << '\n';
}

Im Beispiel 29.4 kommen die beiden Funktionen boost::algorithm::hex() und boost::algorithm::unhex() zum Einsatz. Sie sind den gleichnamigen Funktionen aus der Datenbank MySQL nachempfunden und wandeln Zeichen in Hexadezimalwerte oder Hexadezimalwerte in Zeichen um.

Im Beispiel wird der Vektor v mit den drei Zeichen „C“, „+“ und „+“ an boost::algorithm::hex() übergeben. Die Funktion erwartet als zweiten Parameter einen Iterator, um die Hexadezimalzahlen ausgeben zu können. Wenn Sie das Programm ausführen, wird für „C“ 43 und für „+“ zweimal 2B ausgegeben. Beim zweiten Aufruf von boost::algorithm::hex() geschieht das Gleiche, nur dass „C++“ als String übergeben und „432B2B“ als String zurückgegeben wird.

boost::algorithm::unhex() funktioniert ähnlich wie boost::algorithm::hex(), macht aber das Gegenteil. Wenn wie im Beispiel das Array w mit sechs Hexadezimalzeichen übergeben wird, werden jeweils zwei Zeichen als ASCII-Code interpretiert. Das Gleiche geschieht beim zweiten Aufruf von boost::algorithm::unhex(), dem sechs Hexadezimalzeichen in einem String übergeben werden. In beiden Fällen wird C++ in die Standardausgabe geschrieben.

Boost.Algorithm bietet weitere Algorithmen an. So stehen mehrere String-Matching-Algorithmen zur Verfügung, um effizient in Texten zu suchen. Die Dokumentation enthält eine Referenz mit einer Übersicht über alle verfügbaren Algorithmen.