Intro
Wszyscy programujący w C++ w końcu natrafiają na nagłówek
#include <algorithm>
, są tam bardzo przydane algorytmy uogólnione. Niestety mimo iż najczęściej używa się ich dla kontenerów, to zawsze trzeba podać zakres od i zakres do. Jest to co prawda łatwe dzięki wprowadzonym w C++11 funkcjom
std::begin
i
std::end
, które dla każdego kontenera standardowego oraz tablicy statycznej zwracają iterator odpowiednio na początek i za koniec kolekcji danych. Wraz z C++17 algorytmy uogólnione zyskały jeszcze możliwość wykonywania równoległego, jednakże wciąż pozostawała konieczność podawania zakresu od i do. Na szczęście dzięki Ericowi Nieblerowi, który zaimplementował bibliotekę
ranges-v3, która weszła do standardu
C++20 (niestety w wersji okrojonej), mamy możliwość podania tylko kontenera, bez używania
std::begin
i
std::end
.
Poza możliwością wywołania algorytmów uogólnionych podając obiekt biblioteka
ranges-v3 ma znacznie większe możliwości. W tym artykule jednak skupię się na tym, co weszło do standardu C++20 w postaci nagłówka
#include <ranges>
.
Jakby się ktoś zastanawiał, kim jest Eric Niebler polecam zobaczyć jak wielu
komponentów biblioteki boost jest autorem.
Przypomnienie algorytmów standardowych
Aby czytanie tego artykułu miało sens, należy zapoznać się z
algorytmami standardowymi dostępnymi w poprzednich wersjach C++. Dodam, że jest też kilka algorytmów numerycznych dostępnych w
#include <numeric>
(
link, tych na razie nie jest dużo). Oczywiście w zapoznawaniu się z algorytmami należy zwrócić uwagę na kilka rzeczy:
Algorytmy standardowe działają z iteratorami, do pracy z którymi przydają się
adaptery iteratorów w nagłówku
#include <iterator>
np.
std::back_inserter.
Przykłady użycia algorytmów uogólnionych
Zacznijmy od prostego przykładu wyszukiwania elementu w kontenerze:
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
const std::vector < int > v = { 1, 1, 2, 3, 3, 3, 4, 4 };
const decltype( v )::value_type needle = 4;
auto findResult = find( begin( v ), end( v ), needle );
if( findResult != end( v ) )
{
cout << "Znaleziono: " << needle << ", na pozycji: " << distance( begin( v ), findResult ) << endl;
}
else
{
cout << "Nie znaleziono: " << needle << ", w kontenerze: {";
copy( begin( v ), end( v ), ostream_iterator < decltype( v )::value_type >( cout, ", " ) );
cout << "}" << endl;
}
}
W powyższym przykładzie używamy
std::find
do znalezienia elementu, używamy również
ostream_iterator < T >
do wyświetlenia na ekran elementów z kontenera.
Na potrzeby algorytmów zdarza się, że musimy przekazać do nich funktor, który zostanie zawołany dla każdego elementu kolekcji (z pewnymi wyjątkami, gdyż są algorytmy uogólnione, które przekazują inną ilość elementów). Zamiast funktorów można użyć wyrażeń lambda, ewentualnie bardziej konserwatywne osoby mogą się pokusić o użycie
std::bind
, które zostało zainspirowane implementacją w bibliotece boost zastępując przestarzałe
std::bind2st
i
std::bind2nd
, niestety nie wszystkie udogodnienia
boost::bind
zostały przeniesione do standardu. Poniżej przykładowy kod szablonu funkcji, która zwraca liczby ujemne z kolekcji przy pomocy:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;
template < typename Container >
auto getSortedNegativeNumbersFromCollection( const Container & container )
{
using value_type = typename Container::value_type;
decay_t < decltype( container ) > vNegatives;
auto isNegative = bind( std::less < value_type >(), placeholders::_1, 0 );
std::copy_if( begin( container ), end( container ), back_inserter( vNegatives ), isNegative );
std::sort( begin( vNegatives ), end( vNegatives ) );
return vNegatives;
}
int main()
{
const std::vector < int > v = { 1, - 1, 2, - 3, 3, - 3, - 4, 4, 0 };
auto vNegatives = getSortedNegativeNumbersFromCollection( v );
cout << "Liczby ujemne: {";
copy( begin( vNegatives ), end( vNegatives ), ostream_iterator < decltype( vNegatives )::value_type >( cout, ", " ) );
cout << "}" << endl;
}
Przy pomocy iteratorów można również skopiować pliki, oto przykład (
źródło):
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
using namespace std;
auto copyFile( const char * sourceFileName, const char * destinationFileName )
{
ifstream sourceFile( sourceFileName );
ofstream destinationFile( destinationFileName );
if( !sourceFile || !destinationFile )
{
cerr << "One of files can't be opened: " << sourceFileName << " or " << destinationFileName << endl;
exit( 1 );
}
copy( istreambuf_iterator < char >( sourceFile ),
istreambuf_iterator < char >(),
ostreambuf_iterator < char >( destinationFile ) );
}
int main( int argc, char * argv[ ] )
{
if( argc < 3 )
{
cout << "Usage: " << argv[ 0 ] << " sourceFile destinationFile" << endl;
return 0;
}
auto sourceFile = argv[ 1 ];
auto destinationFile = argv[ 2 ];
copyFile( sourceFile, destinationFile );
}
std::ranges
Wstęp mamy już za sobą, czas na bibliotekę
std::ranges
. Biblioteka ta stosuje dość wysoki poziom abstrakcji, a dzięki przeciążonym operatorom alternatywy bitowej umożliwia czytelne łączenie wielu algorytmów w jeden ciąg instrukcji - wygląda to jak potokowanie. Biblioteka ta skupia się na trzech filarach:
Widoki i akcje można "potokować" w sposób:
zakres | view1 | view2 | view3
Pozwolę sobie na unikanie tłumaczenia powyższych filarów w dalszej części artykułu.
Odpowiedniki std::algorithm dostarczone przez std::ranges
Pierwszym ułatwieniem algorytmów z
std::ranges
jest podawanie instancji obiektu/tablicy bez konieczności jawnego wywoływania
std::begin
i
std::end
. Przykład tego widać poniżej:
#include <iostream>
#include <string>
#include <ranges>
#include <algorithm>
#include <cctype>
using namespace std;
int main()
{
string text( "Lubie C++ najbardziej ze wszystkich jezykow." );
std::ranges::transform( text, begin( text ), static_cast < int( * )( int ) >(::toupper ) );
cout << text << endl;
}
Dodam też, że jeśli ktoś woli podawać zakresy od, do to również ma taką możliwość przy użyciu std::ranges. Zobaczmy to na przykładzie funkcji
for_each
:
#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <functional>
struct Fraction
{
void print() const
{
std::cout << numerator << "/" << denominator << '\n';
}
double numerator, denominator;
};
int main()
{
const std::vector < Fraction > fractions =
{
{ 1, 3 },
{ 3, 4 }
};
std::for_each( fractions.begin(), fractions.end(), std::mem_fn( & Fraction::print ) );
std::ranges::for_each( fractions.begin(), fractions.end(), & Fraction::print );
std::ranges::for_each( fractions, & Fraction::print );
}
Wydruk:
1/3
3/4
1/3
3/4
1/3
3/4
Jak widać biblioteka
std::ranges
umożliwia podawanie wskaźników do funkcji bez jawnego użycia wrappera
std::mem_fn
.
Projection w std::ranges
Kolejnym udogodnieniem jest mechanizm opisany przez autora w języku angielskim "projection", który umożliwia podane funktora, który będzie miał zastosowanie do elementów z kolekcji. Widać to poniżej przy sortowaniu standardem przed i z uwzględnieniem możliwości C++20:
#include <iostream>
#include <vector>
#include <iterator>
#include <ranges>
#include <algorithm>
#include <functional>
using namespace std;
struct Person
{
friend std::ostream & operator <<( std::ostream & os, const Person & p )
{
return os << p.firstname << " " << p.lastname;
}
std::string firstname, lastname;
};
int main()
{
std::vector < Person > wellKnownNeighbours =
{
{ "Ferdynand", "Kiepski" },
{ "Arnold", "Boczek" },
{ "Marian", "Pazdzioch" }
};
auto sortPersonByLastname = bind( less < string >(), bind( mem_fn( & Person::lastname ), placeholders::_1 ), bind( mem_fn( & Person::lastname ), placeholders::_2 ) );
std::sort( begin( wellKnownNeighbours ), end( wellKnownNeighbours ), sortPersonByLastname );
std::copy( begin( wellKnownNeighbours ), end( wellKnownNeighbours ), std::ostream_iterator < Person >( cout, "\n" ) );
std::ranges::sort( begin( wellKnownNeighbours ), end( wellKnownNeighbours ), ranges::less { }, & Person::lastname );
std::ranges::sort( wellKnownNeighbours, ranges::less { }, & Person::lastname );
std::ranges::copy( wellKnownNeighbours, std::ostream_iterator < Person >( cout, "\n" ) );
}
Kolejny przykład na projekcje, na bazie powyższego:
int main()
{
const Person wellKnownNeighbours[ ] =
{
{ "Ferdynand", "Kiepski" },
{ "Arnold", "Boczek" },
{ "Marian", "Pazdzioch" }
};
auto it = ranges::find( wellKnownNeighbours, "Boczek", & Person::lastname );
if( it != ranges::end( wellKnownNeighbours ) )
{
cout << "Znaleziono: " << * it << endl;
}
else
{
cout << "Osoby o takim nazwisku nie znaleziono! Mamy tylko:" << endl;
std::ranges::copy( wellKnownNeighbours, std::ostream_iterator < Person >( cout, "\n" ) );
}
}
Jak widać nie trzeba tworzyć wrapperów składowych klasy, nie trzeba robić lambd, tylko do algorytmów z
std::ranges::
można podać wartość i wskazać składową klasy/struktury.
Należy też mieć na uwadze, że pewne rzeczy, dostarczone przez
std::ranges::
mogą mieć inne zachowanie niż algorytmy uogólnione w wersjach przed C++20, poniżej przykład dla
std::ranges::unique
, gdzie w inny sposób usywamy duplikaty z kontenera:
#include <iostream>
#include <vector>
#include <iterator>
#include <ranges>
#include <algorithm>
using namespace std;
int main()
{
std::vector < int > numbers = { 1, 1, 2, 3, 3, 3, 4, 4 };
numbers.erase( std::unique( begin( numbers ), end( numbers ) ), end( numbers ) );
auto[ iteratorBegin, iteratorEnd ] = std::ranges::unique( numbers );
numbers.erase( iteratorBegin, iteratorEnd );
std::ranges::copy( numbers, std::ostream_iterator < decltype( numbers[ 0 ] ) >( cout, "\n" ) );
}
Zasadniczo powyższe przykłady powinny wystarczyć, żeby zamiast
#include <algorithm>
przerzucić się w pełni na
#include <ranges>
. Osoby jeszcze nie przekonane mogą zobaczyć
więcej przykładów.
Views (widoki)
W końcu zabawa się zaczyna - jak w wygodny i czytelny sposób otrzymać z kolekcji elementy, które chcemy, oraz przekształcić je jak chcemy, a wszystko element po elemencie. Zanim jednak wezmę się za opis, zacznijmy od przykładu:
#include <iostream>
#include <ranges>
#include <algorithm>
using namespace std;
int main()
{
auto isOdd =[ ]( auto n ) { return n & 1; };
const vector < int > numbers = { 1, 4, 5, 2, 7, 8, 2, 29 };
vector < int > numbers2;
std::copy_if( begin( numbers ), end( numbers ), back_inserter( numbers2 ), isOdd );
numbers2.resize( numbers2.size() - 1 );
std::reverse( begin( numbers2 ), end( numbers2 ) );
numbers2.resize( 2 );
for( auto n: numbers2 )
cout << n << ", ";
cout << endl;
for( auto n: numbers | std::views::filter( isOdd ) | std::views::reverse | std::views::drop( 1 ) | std::views::take( 2 ) )
cout << n << ", ";
cout << endl;
}
Jak widzimy możemy w łatwy sposób sobie "potokować" kolekcje danych. Dane są generowane w locie, a wyliczanie odbywa się w sposób "leniwy", aby nie wykonywać niepotrzebnej pracy za wcześnie, a najpóźniej jak się da. Jak widzimy oryginalny kontener nie jest modyfikowany. Dane nie są przejmowane (ang. not-owning). Dzięki temu wszystkiemu cała implementacja jest lekka obliczeniowo.
Dostępne operacje na widokach
W powyższym przykładzie przedstawiłem kilka operacji, czas jednak na wymienienie ich wszystkich. Widoki można wołać na dwa sposoby - jak funkcja oraz przez "potokowanie".
W poniższej tabeli
r
może być instancją kontenera standardowego, tablicy statycznej lub innego widoku:
Powyżej wylistowałem dostępne w standardzie widoki, dodam, że można je wywoływać na wiele sposobów, przykładowo
r | view::reverse
można wołać też:
std::ranges::reverse_view( r )
- można stosować formę wg preferencji.
Widoki + algorytmy z std::ranges
Bezcennym ułatwieniem jest to, iż można widoki łączyć z pozostałymi algorytmami standardowymi z
ranges::
. Przykładowo aby skopiować vector z pominięciem liczb parzystych oraz podwajając je w odwrotnej kolejności, możemy użyć:
#include <iostream>
#include <ranges>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
auto isOdd =[ ]( auto n ) { return n & 1; };
auto square =[ ]( auto n ) { return n * n; };
const vector < int > numbers = { 1, 4, 5, 2, 7, 8, 2, 29 };
remove_cv_t < decltype( numbers ) > numbers2;
ranges::copy( numbers | views::filter( isOdd ) | views::transform( square ) | views::reverse, back_inserter( numbers2 ) );
ranges::copy( numbers2, ostream_iterator < int >( cout, ", " ) );
cout << endl;
ranges::copy( numbers | views::filter( isOdd ) | views::transform( square ) | views::reverse, ostream_iterator < int >( cout, ", " ) );
cout << endl;
}
Generowanie widoków
Jak widzieliśmy wcześniej, możliwość spojrzenia na kolekcje danych łatwo można zmieniać. Kolekcją danych może być dowolny kontener standardowy, lub tablica statyczna, a także inny widok, zakres. Kolejnym udogodnieniem jest to, iż wejść do widoków nie trzeba tworzyć przez żmudne tworzenie np. vectora i zapełnianie go danymi, gdyż wraz z nagłówkiem
#include <ranges>
są dostarczone generatory zakresów. Poniżej mamy listę dostępnych generatorów:
Przykład na generowanie widoków
Samo generowanie widoków nie jest na tyle fajne, aby na nim poprzestać, dlatego poniższy przykład będzie zawierał wszystko powyższe:
#include <iostream>
#include <ranges>
#if __has_include(<format>)
#include <format>
#else
#define FMT_HEADER_ONLY
#include <fmt/format.h>
using fmt::format;
#endif
using namespace std;
int main()
{
auto isOdd =[ ]( auto n ) { return n & 1; };
auto toStringPaddedWithZeroes =[ ]( auto a ) { return format( "{:06}", a ); };
ranges::copy( views::iota( 1 ) | views::filter( isOdd ) | views::transform( toStringPaddedWithZeroes ) | views::take( 10 ),
ostream_iterator < string >( cout, ", " ) );
cout << endl;
}
W powyższym przykładzie generujemy zakres [1, nieskończoność], filtrujemy z tego liczby nieparzyste, które zamieniamy na tekst 6-znakowy poprzedzony zerami, z tego wszystkiego bierzemy pierwsze 10 elementów, poniżej wydruk:
000001, 000003, 000005, 000007, 000009, 000011, 000013, 000015, 000017, 000019,
Powyższy kod używa również biblioteki
std::format, gdyby jednak nie działało używamy
fmt::format z makrem aktywującym tryb heder-only.
Jako ciekawostkę można wspomnieć, że oryginalna biblioteka ranges-v3 zawierała również możliwość przekazania widoku bezpośrednio na strumień wyjściowy. Oto przykład pobrany
ze strony tworcy:
using namespace ranges;
auto letters = view::iota( 'a', 'g' );
std::cout << letters << '\n';
std::cout <<( letters | view::slice( 2, 5 ) ) << '\n';
Akcje (niewciągnięte do standardu C++20)
Jak pamiętamy z powyższych przykładów, aby np. usunąć duplikaty przy użyciu biblioteki
ranges
musieliśmy zrobić to tak:
std::vector < int > numbers = { 1, 1, 2, 3, 3, 3, 4, 4 };
auto[ iteratorBegin, iteratorEnd ] = std::ranges::unique( numbers );
numbers.erase( iteratorBegin, iteratorEnd );
A teraz "prawie" miła niespodzianka - można takie częste akcje zrobić łatwiej, niestety nie jest to jeszcze włączone w ramach propozycji
P0896R4 do standardu C++20, dlatego poniższy przykład będzie w oparciu o
ranges-v3:
#include "range/v3/action.hpp"
std::vector < int > v = { 1, 1, 2, 3, 3, 3, 4, 4 };
v = move( v ) | ranges::actions::sort | ranges::actions::unique;
W związku z nieobecnością w standardzie pominę możliwości dogłębne opisanie możliwości akcji, natomiast osoby chcące wiedzieć więcej mogą zagłębić się w
dokumentacji biblioteki ranges-v3.
Inne elementy dostarczone wraz z std::ranges
W standardzie wraz z nagłówkiem
#include <ranges>
znajdują się jeszcze pewne udogodnienia, które mogą się przydać:
Najlepiej przyjrzeć się tym funkcjom w akcji:
#include <iostream>
#include <vector>
#include <ranges>
using namespace std;
template < typename Data >
void printCollectionDetails( const Data & data )
{
if( !ranges::empty( data ) )
{
std::cout << "Data(size:" << ranges::size( data )
<< "),dataBeginPtr=" << ranges::cdata( data )
<< ",firstElement=" << * ranges::begin( data )
<< ",lastElement=" << *( ranges::end( data ) - 1 )
<< ")\n";
}
}
int main()
{
const vector < string > workingDays = { "Poniedzialek", "Wtorek", "Piatek" };
printCollectionDetails( workingDays );
const double numbers[ ] = { 3.14, 2.71 };
printCollectionDetails( numbers );
ranges::ref_view rv( workingDays );
printCollectionDetails( rv );
}
Wydruk:
Data(size:3),dataBeginPtr=0x55c560749eb0,firstElement=Poniedzialek,lastElement=Piatek)
Data(size:2),dataBeginPtr=0x7ffc7e7d5f60,firstElement=3.14,lastElement=2.71)
Data(size:3),dataBeginPtr=0x55c560749eb0,firstElement=Poniedzialek,lastElement=Piatek)
Powyższe funkcje z
std::ranges::
są bardziej przemyślane niż ich dotyczasowe odpowiedniki z
std::
, natomiast dociekliwi mogą zagłębić się
w jakich sytuacjach są one lepsze.
Funkcjonalności dostarczone przez ranges-v3, które nie znalazły się w standardziej C++20
Z wcześniej wymienionych są:
Z przydatnych rzeczy jest jeszcze możliwość konwertowania zakresu na kontener np.
std::vector
, poniżej przykład zacytowany z
przykładów biblioteki ranges:
#include <iostream>
#include <vector>
#include <range/v3/range/conversion.hpp>
#include <range/v3/view/for_each.hpp>
#include <range/v3/view/iota.hpp>
#include <range/v3/view/repeat_n.hpp>
using std::cout;
int main()
{
using namespace ranges;
auto vi = views::for_each( views::ints( 1, 6 ),
[ ]( int i ) { return yield_from( views::repeat_n( i, i ) ); } ) |
to < std::vector >();
cout << views::all( vi ) << '\n';
}
Poniżej mamy przykład akcji, dzięki którym możemy w miejscu usunąć duplikaty z kontenera (
pobrane z przykładów biblioteki range-v3):
#include <iostream>
#include <vector>
#include <range/v3/action/sort.hpp>
#include <range/v3/action/unique.hpp>
#include <range/v3/view/all.hpp>
using std::cout;
int main()
{
std::vector < int > vi { 9, 4, 5, 2, 9, 1, 0, 2, 6, 7, 4, 5, 6, 5, 9, 2, 7,
1, 4, 5, 3, 8, 5, 0, 2, 9, 3, 7, 5, 7, 5, 5, 6, 1,
4, 3, 1, 8, 4, 0, 7, 8, 8, 2, 6, 5, 3, 4, 5 };
using namespace ranges;
vi |= actions::sort | actions::unique;
cout << views::all( vi ) << '\n';
}
Na zakończenie dodam, że zarówno
#include <ranges>
oraz ranges-v3 są header-only, więc wystarczy zaincludować i używać, oczywiście należy pamiętać o odpowiedniej fladze kompilacji, aby włączyć dany standard c++ (np. dla gcc:
--std=c++20
).
Bibliografia