Bereichsfunktionen in C++
Unter einer Bereichsfunktion verstehen wir hier eine Funktion, die einen Bereich akzeptiert. Jener Bereich wird durch zwei Argumente der Bereichsfunktion angegeben: Die Anfangs- und die Deckelposition.
Binäres Suchen
Die binäre Suche ist besonders effizient und in der Regel schneller als eine lineare Suche, die bei einer nicht-sortierten Folge nötig ist.
Das folgende Beispiel zeigt die Implementation einer binären Suche mit »lower_bound«.
Wir benötigen »#include <algorithm>«.
Die Funktion »binary_find« akzeptiert einen Bereich, der zu einer aufsteigend sortierten Folge gehört, und einen Wert und ergibt, ob der Wert im Bereich vorkommt.
Die Funktion »binary_find« soll den Inhalt des ihr übergebenen Bereichs nicht verändern. Die Funktion »::std::binary_search« benötigt daher keine Schreibpositionen (also Positionen, über welche sie die Folge verändern könnte). Wir können also »cbegin« und »cend« verwenden; es Qist nicht nötig, »begin« und »end« zu verwenden.
main.cpp#include <algorithm>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>template< class ForwardIterator, class T >
ForwardIterator binary_find( ForwardIterator first, ForwardIterator last, const T& value )
{ ForwardIterator iter = lower_bound( first, last, value );
if( iter !=last && *iter == value )return iter;
return last; }int main()
{ ::std::string str{ "abcdefghijklmnopqrstuvwxyz" };
::std::cout << binary_find( cbegin( str ), cend( str ), 'c' )- cbegin( str )<< '\n';
::std::cout << binary_find( cbegin( str ), cend( str ), '#' )- cbegin( str )<< '\n'; }- transcript
2
26
Die Standardfunktion »::std::binary_search« ergibt hingegen keine Fundstelle, sondern nur, ob der Wert gefunden wurde.
main.cpp#include <algorithm>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>int main()
{ ::std::string str{ "abcdefghijklmnopqrstuvwxyz" };
::std::cout << binary_search( cbegin( str ), cend( str ), 'c' )<< '\n';
::std::cout << binary_search( cbegin( str ), cend( str ), '#' )<< '\n'; }transcript1
0
Ausgeben eines Initialisierungslistenobjekts
Die Funktion »::std::for_each« ruft ihr drittes Argument für jede Position eines Objektes des Bereiches auf. Dabei wird der Funktion der Inhalt jenes Objektes übergeben.
main.cpp#include <algorithm>
#include <initializer_list>
#include <iterator>
#include <ostream>
#include <iostream>void print( char const c ){ ::std::cout << c << '\n'; }
int main()
{ ::std::initializer_list< char >l{ 'a', 'b', 'c' };
::std::for_each( cbegin( l ), cend( l ), print ); }transcripta
b
c
Die Positionen einer Initialisierungsliste werden – wie bei einer Reihung – durch Adressen der Objekte angegeben. Die Objekte haben hier den Typ »char«. Daher findet ADL im Typ »char *« keinen Hinweis auf den Namensraum »::std«.
Erst durch Verwendung von Positionen könnnen wir Initialisierungslistenobjekte überhaupt ausgeben.
Das Besondere an den Bereichsfunktionen ist es, daß sie für alle möglichen Bereiche in einheitlicher Weise verwendet werden können, egal wo diese herkommen.
Wir können das eben gezeigte Verfahren zur Ausgabe eines Bereichs also genauso gut auch für Zeichenfolgen, Vektoren oder Reihungen verwenden!
main.cpp#include <algorithm>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <ostream>static void print( char const c ){ ::std::cout << c << '\n'; }
int main()
{ using ::std::cbegin;
using ::std::cend;
::std::initializer_list< char > l{ 'a', 'b', ' ' };
::std::string s{ 'c', 'd', ' ' };
::std::vector< char > v{ 'e', 'f', ' ' };
char a[] = "gh ";
::std::for_each( cbegin( l ), cend( l ), print );
::std::for_each( cbegin( s ), cend( s ), print );
::std::for_each( cbegin( v ), cend( v ), print );
::std::for_each( cbegin( a ), cend( a ), print ); }transcripta
b
c
d
e
f
g
h
»using« wurde oben zur Vereinheitlichung der Schreibweise für die Reihung verwendet.
Weitere Beispiele
Verwürfeln und Sortieren
Im folgenden Programm wird ein Bereich mit »::std::shuffle« verwürfelt und danach mit »::std::sort« sortiert.
main.cpp#include <iostream>
#include <ostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <initializer_list>
#include <random> // std::default_random_engine
#include <chrono> // std::chrono::system_clockint main()
{ auto const seed{ ::std::chrono::system_clock::now().time_since_epoch().count() };
auto engine{ ::std::default_random_engine( seed )};::std::string str{ "abcdefghijklmnopqrstuvwxyz" }; ::std::cout << str << "\n";
shuffle( begin( str ), end( str ), engine ); ::std::cout << str << "\n";
sort( begin( str ), end( str )); ::std::cout << str << "\n"; }transcriptabcdefghijklmnopqrstuvwxyz
mnjibtkceqdfswxvgzauropylh
abcdefghijklmnopqrstuvwxyz
Beispiel 6 aus 49
main.cpp#include <algorithm> // ::std::random_shuffle, ::std::copy_n
#include <array>
#include <iostream>
#include <iterator> // ::std::ostream_iterator
#include <numeric> // ::std::iota
#include <ostream>
#include <random>
int main()
{ using num = int;
using size_type = ::std::vector< num >::size_type;
auto output = ::std::ostream_iterator< int >( ::std::cout, " " );constexpr size_type total_size = 49;
constexpr size_type selection_size = 6;::std::array< num, total_size >a;
{ constexpr num offset = 1; ::std::iota( begin( a ), end( a ), offset ); }
copy_n( begin( a ), selection_size, output ); ::std::cout << '\n';
shuffle( begin( a ), end( a ), ::std::mt19937{} );
copy_n( begin( a ), selection_size, output ); ::std::cout << '\n'; }transcript1 2 3 4 5 6
33 44 27 35 32 3
Wird »::std::mt19937{}« durch »::std::mt19937{ ::std::random_device{}() }« ersetzt, verwendet man Zufallszahlen mit einem umgebungsabhängigen Startwert. (Dies ist aber 2016 unter MinGW gestört. Dort kann ersatzweise »::std::mt19937( ::std::time( 0 )* ::std::time( 0 ))« verwendet werden.)
UEBUNG E (nach der Behandlung von Bereichsfunktionen)
Schreiben Sie eine Funktion, die einen Vektor von int-Werten als Argument akzeptiert und unter Verwendung der Bereichsfunktion »accumulate« die Summe aller Werte des Vektors zurückgibt. Hierzu können Sie alle möglichen Informationsquellen heranziehen (Web, Bücher), um sich über die Verwendung dieser Funktion zu informieren.