Opublikowano: 15-10-2017



W artykule przedstawiona została koncepcja zakresów (ang. range) wprowadzonych w bibliotece Boost Range. Specyfikacja zakresów (w nowszej odsłonie) ma szansę stać się częścią języka.

Spis treści

  1. Wstęp
    • przyszłość biblioteki Range
    • wprowadzenie do zakresów
  2. Algorytmy
  3. Adaptery

Wstęp

Obecnie w C++ dostępne są zakresy dostarczane przez jedną z zestawu bibliotek Boost - Range v2, jednak nie nadążyła ona za szybkimi zmianami w standardzie. Jej udoskonalona wersja (v3) wykorzystuje nowe elementy języka, co podkreślają jej twórcy [3]:

Why does C++ need another range library? Simply put, the existing solutions haven't kept up with the rapid evolution of C++. Range v3 is a library for the future C++. Not only does it work well with today's C++ -- move semantics, lambdas, automatically deduced types and all -- it also anticipates tomorrow's C++ with Concepts.

Twórcy Range v3 dokładają wszelkich starań, aby obsługa zakresów weszła do standardu [3]:

Range v3 forms the basis of a proposal to add range support to the standard library (N4128: Ranges for the Standard Library). It also will be the reference implementation for an upcoming Technical Specification. These are the first steps toward turning ranges into an international standard.

Wersja trzecia może pojawić się w C++20 [5]. Aktualnie do wyboru mamy zakresy dostarczane w ramach biblioteki Boost Range [1] oraz wersję referencyjną range-v3 dostępną na GitHubie [3]. W tym artykule skupię się na bibliotece Range v2.

W swoim zamyśle zakresy są bardzo podobne do kontenerów STL, jednak nie muszą one być właścicielami elementów, ani obsługiwać operacji kopiowania. O zakresie możemy myśleć jak o obiekcie dostarczającym:

  • iterator do pierwszego elementu
  • iterator wskazujący za ostatni element
  • liczbę dostępnych elementów

Definicję zakresu dobrze omówiono w dokumentacji [6]:

A Range is a concept similar to the STL Container concept. A Range provides iterators for accessing a half-open range [first,one_past_last) of elements and provides information about the number of elements in the Range. However, a Range has fewer requirements than a Container.

The motivation for the Range concept is that there are many useful Container-like types that do not meet the full requirements of Container, and many algorithms that can be written with this reduced set of requirements. In particular, a Range does not necessarily

  • own the elements that can be accessed through it,
  • have copy semantics,

Because of the second requirement, a Range object must be passed by (const or non-const) reference in generic code.

Zobaczmy fragment głównej klasy szablonowej reprezentującej zakres [7]:

Zawarte zostały w niej metody begin() oraz end() zwracające odpowiednio iterator do pierwszego elementu oraz iterator wskazujący za ostatni element. U dołu definicji klasy znajdziemy również metodę size() zwracającą ilość elementów w zakresie. Dostępnych jest także kilka konstruktorów pozwalających na stworzenie zakresu, chociaż najciekawszym jest pierwszy z nich. Warto zauważyć, że dostępność poszczególnych metod zależy od typu iteratora stosowanego podczas tworzenia instancji klasy.

W świetle powyższej definicji kontenery z biblioteki standardowej są również zakresami.

Algorytmy

Biblioteka dostarcza algorytmy współpracujące z zakresami [8]. Głównie są to odmiany algorytmów (nie wszystkich) znanych z biblioteki standardowej, chociaż znajdzie się także kilka nowych [9]. Różnicą pomiędzy wersją z STL a wersją z Boost Range są parametry wejściowe - algorytmy biblioteki standardowej operują na iteratorach, natomiast biblioteka Range na zakresach.

Zobaczmy to na przykładzie funkcji sort() - w liniach 1-2 wersja z STL [9], a w liniach 4-5 wersja z biblioteki Range [10]:

Oczywiście nie może zabraknąć przykładu wykorzystania danej metody:

Na powyższym wydruku możemy zaobserwować, że wersję operującą na zakresach cechuje zwięzłość. Zachęcam do zapoznania się z dostępnymi algorytmami np.:

Adaptery

Adapter (ang. adaptor) jest klasą opakowującą istniejący zakres w nowy zakres. Jak zwykle dokumentacja jest nieoceniona [11]:

A Range Adaptor is a class that wraps an existing Range to provide a new Range with different behaviour. Since the behaviour of Ranges is determined by their associated iterators, a Range Adaptor simply wraps the underlying iterators with new special iterators.

Zobaczmy przykład z użyciem adaptera filtered():

Zapis example_range | boost::adaptors::filtered(is_even) jest adekwatny do wywołania funkcji, podobnie jak zaprezentowano to na poniższym wydruku:

Wynik działania obu programów:

2 4

Funkcja filter() pobiera zakres oraz predykat, a zwraca nowy zakres zawierający iterator, który w trakcie odpytywania przeszukuje wektor w poszukiwaniu elementu spełniającego predykat.

Koncepcyjnie klasę filtered oraz jej iterator możemy przedstawić następująco:

Powyższy pseudokod jest zwięzłym opisem implementacji zawartej w pliku filtered.hpp.

W liniach 1 - 9 zaprezentowano pseudokod klasy filtered() - jest to zakres zawierający specjalny iterator, który będzie użyty do odpytywania kolejnych elementów.

W liniach 14 - 37 przedstawiono pseudokod iteratora - metoda operator++ zwraca iterator do elementu dla którego spełniony został warunek lub iterator końca.

Należy zauważyć, że zakresy działają w oparciu o iteratory, dlatego ważne jest aby element na którym wykonują pracę istniał w trakcie operacji zakresowych. Zobaczmy to na przykładzie:

Podobnie wygląda to z obiektami tymczasowymi:

Zachęcam do zapoznania się z pozostałymi adapterami np.:



Comments powered by Disqus