MPU: klasy cech kontenerów STL

Kolejna notatka z serii MPU, opisująca kilka ciekawych konstrukcji zawartych w mistycznym MetaPrograming-Unit. Tym razem o klasach cech opisujących typy kontenerów zawartych w STL.

Każdy programista C++ zaznajomiony jest z klasami cech (traits) i ich wielkim potencjałem. Dla tych wszystkich, którzy nie do końca łapią temat, dwa zdania wprowadzające. Klasy cech w C++ są specyficznym typem klas szablonów dostarczających w czasie kompilacji informacji o innych typach bądź strukturach danych. Wykorzystywane są głownie w programowaniu generycznym, przez inne obiekty lub algorytmy do określenia polityki działania lub szczegółów implementacji i realizacji. Więcej szczegółów można znaleźć w sieci, chociażby na Dr. Dobb’s Journal, ACCU lub w artykule wynalazcy tej techniki - Nathana C. Myersa.

Jednym z głównych zastosowań klas cech typów jest dostarczanie informacji o typie, które bardzo często wykorzystywane są do wyboru odpowiedniej implementacji danego kawałka kodu lub algorytmu w czasie kompilacji. Bardzo często używane w celach optymalizacyjnych.

Sztandarowym i najpopularniejszym przykładem jest algorytm kopiowania, działający na iteratorach i wskaźnikach. Implementacja algorytmy dla iteratorów korzysta z trywialnego przypisania, a wskaźnikowa wersja kopiuje dane jako kawałek ciągłej pamięci za pomocą memcpy. Szczegółowy opis i analiza tego przypadku można znaleźć na stronach podanych wyżej.

Do niedawna (C++03) biblioteka standardowa C++ zawierała tylko kilka klas cech typów: std::numeric_limits, std::char_traits, std::iterator_traits…

Niemniej boost dostarcza nam cała gamę przydatnych klas cech typów, które wraz z zatwierdzeniem aktualnej wersji standardu (C++11) zostały odziedziczone przez STL i weszły w skład standardowej biblioteki C++. Wykaz dostępnych klas można znaleźć w dokumentacji na cppreference.com lub cplusplus.com, ich definicje zawarte są w nagłówku type_traits.

Niestety ani STL, ani boost nie zawiera żadnych klas cech i innych narzędzi umożliwiających wydedukować, czy podany parametr szablonu jest kontenerem standardowej biblioteki. A takie narzędzie było mi bardzo potrzebne, wiec trzeba było coś takiego napisać.

Powstało kilka wersji, główna bazowała na implementacji boosta, aczkolwiek obecnie możemy wykorzystać elementy dostępne w STL. Idea jest taka sama, należy stworzyć klasę szablonową traitsa i wykonać kilka jej specjalizacji - dla typu (lub typów) spełniającego jej założenia.

Najprościej tego dokonać tworząc strukturę zawierającą stałe statyczne pole value typu boolowskiego, określające wartość cechy. Choć lepszym posunięciem jest skorzystanie z udostępnianych elementów i dziedziczyć po integral_constant lub jeszcze lepiej, po jej aliasach true_type i false_type:

template<typename T>
struct is_vector : public std::false_type {};

template<typename V>
struct is_vector<std::vector<V>> : public std::true_type {};

Implementacja ta “wykryje” tylko typ vectora podanego bez kwalifikatora CV. Aby konstrukcja działała z dowolnym typem vectora, należałoby dodać jeszcze specjalizację dla wersji z const, volatile oraz obu.

Zwiększona liczba specjalizacji wymaga więcej pisania i wprowadza większe zamieszanie w kodzie, dlatego boost ten problem rozwiązuje poprzez zdefiniowane kilku makr helperów, dzięki którym szybko, prosto i przejrzyście można definiować poszczególne definicje i specjalizacje traitsów.

Przydatne nagłówki to:

boost/type_traits/detail/bool_trait_def.hpp
boost/type_traits/detail/bool_trait_undef.hpp

Niestety są one szczegółami implementacji (details), nie są dostępne na “zewnątrz”, toteż lepiej z nich nie korzystać, ponieważ w różnych wersjach mogą się zmienić lub pewnego dnia zniknąć. Warto na bazując na nich, zdefiniować potrzebne makra.

W MPU było ich kilka, tylko, aby pokryć wymagania i typy kontenerów. Wszystkie makra dostępne były w dwóch wersjach dla typu przyjmującego jeden i dwa parametry szablonu (np. dla kontenera vector i map).

Makra definiujące klasę cech:

#define MPU_STD_TRAIT_DEF1(trait, T, value)					\
template<typename T>										\
struct trait : public boost::integral_constant<bool, value> {};

#define MPU_STD_TRAIT_DEF2(trait, T, U, value)				\
template<typename T, typename U>							\
struct trait : public boost::integral_constant<bool, value> {};

oraz makra służące do specjalizacji:

#define MPU_STD_TRAIT_SPEC1(trait, type, value, cv)			\
template<typename V>										\
struct trait<type<V> cv> : public boost::integral_constant<bool, value> {};

#define MPU_STD_TRAIT_SPEC2(trait, type, value, cv)			\
template<typename K, typename V>							\
struct trait<type<K,V> cv> : public boost::integral_constant<bool, value> {};

Oprócz tego podobnie jak w boost, dodano makra specjalizujące wszystkie kombinacje typu wraz z kwalifikatorami CV:

#define MPU_STD_TRAIT_CV_SPEC1(trait, sp, value)			\
	MPU_STD_TRAIT_SPEC1(trait, sp, value, )					\
	MPU_STD_TRAIT_SPEC1(trait, sp, value, const)			\
	MPU_STD_TRAIT_SPEC1(trait, sp, value, volatile)			\
	MPU_STD_TRAIT_SPEC1(trait, sp, value, const volatile)

#define MPU_STD_TRAIT_CV_SPEC2(trait, sp, value)			\
	MPU_STD_TRAIT_SPEC2(trait, sp, value, )					\
	MPU_STD_TRAIT_SPEC2(trait, sp, value, const)			\
	MPU_STD_TRAIT_SPEC2(trait, sp, value, volatile)			\
	MPU_STD_TRAIT_SPEC2(trait, sp, value, const volatile)

Zastosowaniem w/w makr, definicja klasy cech is_vector sprowadza się do dwóch linijek:

MPU_STD_TRAIT_DEF1(is_vector, T, false)
MPU_STD_TRAIT_CV_SPEC1(is_vector, std::vector, true)

i działa poprawnie:

#define is_vector_test(T) \
	static_assert(is_vector<T>::value, "'" #T "' is not vector")

is_vector_test( std::vector<int> );
is_vector_test( const std::vector<int> );
is_vector_test( std::vector<int> const );
is_vector_test( volatile std::vector<int> );
is_vector_test( const volatile std::vector<int> );
is_vector_test( int );

#undef is_vector_test

Innym sposobem rozwiązania problemów z kwalifikatorami CV jest skorzystanie z innego traitsa, przekształcającego (TransformationTrait) - remove_cv, który jak nazwa wskazuje, usuwa kwalifikatory CV. Implementacja is_vector z zastosowaniem tego sposobu wygląda tak:

template<typename T>
struct is_vector_helper : public std::false_type {};

template<typename V>
struct is_vector_helper<std::vector<V>> : public std::true_type {};

template<typename T>
struct is_vector : public std::integral_constant<bool,
	is_vector_helper<
		typename std::remove_cv<T>::type
	>::value> {};

Mając proste i narzędzie do determinacji typu kontenera, można zdefiniować kolejne klasy cech grupujące kontenery według pewnych cech lub konceptu STL-a:

template<typename T>
struct is_sequence_container {};

template<typename T>
struct is_container_adaptor {};

template<typename T>
struct is_associativie_container {};

template<typename T>
struct is_unordered_associativie_container {};

Definicja takiego “zgrupowania” jest bardzo prosta:

MPU_STD_TRAIT_DEF1(is_sequence_container, T ,
	is_array<T>::value ||
	is_vector<T>::value ||
	is_deque<T>::value ||
	is_forward_list<T>::value ||
	is_list<T>::value
)

Niektóre kompilatory nie radzą sobie dobrze z constant expression, dlatego można zastosować nieco starsze sztuczki “emulujące” operacje logiczne na typach i parametrach szablonu w czasie kompilacji. Ale o tym kiedyś ;)

Oczywiście na koniec należy jeszcze dodać ogólny traits, operujący na w/w grupach, który dedukuje czy parametr jest dowolnym typem kontenera biblioteki standardowej:

template<typename T>
struct is_container {};

Klasy cech, te obecne aktualnie w bibliotece standardowej, boost i MPU, przydają się w wielu sytuacjach. Jedną z nich jest tworzenie bardziej specjalizowanych algorytmów generycznych (w jakimś stopniu podobne do częściowej specjalizacji szablonów), których implementacja dostosowana jest nie do konkretnych typów, ale do pewnej grupy typów spełniających odpowiednie założenia i posiadające wybrane cechy.

Postaram się przedstawić wkrótce, jak traitsy w połączeniu z innymi elementami i konstrukcjami, aktualnie obecnymi już w standardzie, mogą w zwykłym programowaniu pomóc uprościć kod. Czasem wykorzystanie elementów metaprogramiwania, ułatwia, upraszcza, a nawet poprawia czytelność kodu.