Wprowadzenie
Wybierając C++ w projekcie zależy nam na wydajności, wydajność raczej dotyczy większego projektu, w którym na pewno będą agregowane dane podobnego typu w liczbie nie do końca znanej na etapie programowania - wtedy właśnie potrzebujemy dane przechować w kontenerze. Wtedy pojawia się pytanie,
w którym kontenerze trzymać dane.
Standard C++ w kolejnych wersjach jest wzbogacany o kolejne kontenery standardowe.
Wg
strony dokumentacji również
std::string
i
std::wstring
(czyli w praktyce
std::basic_string
) są traktowane jako kontenery. Niektórzy uważają, ze
std::pair
i
std::tuple
też pełnią rolę kontenerów. Nie zapominajmy też o podstawie kontenerów - tablicach.
Na pierwszy rzut oka wydaje się, że mamy dużo kontenerów, bo (zależnie jak liczyć) jest to 13-25 kontenerów w standardzie.
Kontenery będące w standardzie mają bardzo spójny interfejs. Analogiczne metody mają taką samą nazwę. Każdy z kontenerów można przeglądać w sposób niezależny od kontenera przy pomocy iteratorów mimo różnych implementacji. W poświęconym kontenerom
artykule portalu cppreference.com znajduje się zestawienie wszystkich kontenerów dostępnych w standardzie, a także tabelaryczne zestawienie metod dostępnych w każdym ze standardowych kontenerów.
Zakładamy, Drogi Czytelniku, że znasz kontenery dostępne w standardzie C++, na tyle biegle, że jesteś w stanie dobrać najoptymalniejszy. W dalszej części artykułu skupimy się na tych, których nie ma w standardzie.
Kontenery biblioteki boost
Poza kontenerami dostępnymi w bibliotece standardowej STD znać kontenery dostępne w
bibliotece boost. Biblioteka ta jest używana w tak dużej liczbie projektów C++, że aż czasami określa się ją "poczekalnią do standardu" (
lista składowych biblioteki boost). Określenie to ma pewne uzasadnienie, gdyż wiele rozwiązań w nowych kolejnych standardach C++ wywodzi się z tej biblioteki np.
boost::unordered_map
i inne kontenery hashujące, a także
boost::array
, czy
boost::string_view
. Kolejną zaletą kontenerów dostępnych w bibliotece boost jest zgodność nazw metod z nazwami metod dostępnymi w kontenerach dostępnych w standardzie. Pełna
lista składowych biblioteki boost zakwalifikowanych przez twórców jako kontenery będzie opisana poniżej, jednakże w poniższym wylistowaniu kontenerów biblioteki boost pominąłem kontenery, które weszły do standardów C++23 włącznie.
boost.container
Boost.container udostępnia mechanizmy dostępne w nowszych standardach C++ dla starszych kompilatorów oraz kilka dodatkowych kontenerów, poza tym reimplementuje kontenery standardowe lekko je rozszerzając. Te funkcje obejmują zarządzanie pamięcią, optymalizację alokacji, wsparcie dla kontenerów typu
tuple
, oraz dodatkowe kontenery takie jak
small_vector
.
Przykładowe kontenery niedostępne jeszcze w standardzie
Kontenery dostępne w standardzie, ale rozszerzone
boost.bimap
Boost.bimap zawiera kontener
boost: bimap
, podobny do
std::map
, w którym mapowanie klucz-wartość odbywa się w dwie strony, czyli działa to jak połączenie
std::map
i
std::map
.
boost.Circular Buffer
Circular Buffer z biblioteki Boost to struktura danych, zwana również buforem cyklicznym, służąca do przechowywania danych w obszarze pamięci o stałym rozmiarze, w której dane są przechowywane w sposób zapętlony: nowe dane zastępują najstarsze, utrzymując stały rozmiar bufora.
Dostępne są kontenery
| circular_buffer |
Kontener przechowujący nie więcej niż określoną liczbę elementów, zapewniający przy tym optymalną gospodarkę pamięci. (szablon klasy) |
poza powyższym jeszcze
boost::circular_buffer_space_optimized
. Ten pierwszy ma możliwość zmiany capacity po utworzeniu (na jawne żądanie, nie zwiększa się automatycznie), natomiast ten drugi alokuje pamięć gdy jest ona potrzebna (nie więcej niż zadany capacity).
boost.unordered
Boost.unordered są to kontenery hashujące jakie znamy ze standardu C++ z nagłówków
unordered_map
i
unordered_set
, ale zawierają też inne kontenery hashujące:
Kontenery o zamkniętym adresowaniu, oparte na wierzchołkach
Są to odpowiedniki kontenerów dostępnych w C++ od wersji C++11, czyli:
Kontenery o zamkniętym adresowaniu
Mamy zarówna oparte na wierzchołkach:
jak i oparte na "płaskich" strukturach danych (ang. "flat"):
Wg
dokumentacji boost.unordered są one o wiele szybsze w standardowym zastosowaniu (najszybsze są te "płaskie" implementacje).
Kontenery hashujące dla zastosowań wielowątkowych
Dedykowane do tego celu, przez autorów biblioteki, są to kontenery "płaskie" (ang. flat):
Kontenery
concurrent_flat_ *
zapewniają bezpieczny odczyt i modyfikację kontenera z wielu wątków bez potrzeby synchronizacji dostępu do całego kontenera. Kontener sam synchronizuje między sobą operacje odczytu/modyfikacji, potencjalnie wykonując je całkowicie równolegle.
boost.dynamic_bitset
Boost Dynamic Bitset zawiera kontener
boost::dynamic_bitset
, który jest jak
std::bitset
, z tą różnicą, że w przeciwieństwie do standardowego odpowiednika rozmiar jego jest dynamicznie zmienialny (nie stały jak w przypadku
std::bitset
).
boost.Icl
Boost.Icl są to kontenery odpowiadające
std::set
i
std::map
, które trzymają wartości jako zakresy, co ciekawe można jako zakresy podawać daty, poniżej przykład zaczerpnięty z
dokumentacji Boost.Icl:
interval < seconds >::type news( make_seconds( "20:00:00" ), make_seconds( "20:15:00" ) );
interval < seconds >::type talk_show( make_seconds( "22:45:30" ), make_seconds( "23:30:50" ) );
interval_set < seconds > myTvProgram;
myTvProgram.add( news ).add( talk_show );
for( interval_set < seconds >::iterator telecast = myTvProgram.begin();
telecast != myTvProgram.end(); ++telecast )
TV.switch_on( * telecast );
a także:
typedef std::set < string > guests;
interval_map < time, guests > party;
party += make_pair( interval < time >::right_open( time( "20:00" ), time( "22:00" ) ), guests( "Mary" ) );
party += make_pair( interval < time >::right_open( time( "21:00" ), time( "23:00" ) ), guests( "Harry" ) );
[ 20: 00, 21: 00 )->{ "Mary" }
[ 21: 00, 22: 00 )->{ "Harry", "Mary" } [ 22: 00, 23: 00 )->{ "Harry" }
Na uwagę zasługuje fakt, że zakresy można dodawać i odejmować od siebie.
boost.Intrusive
Boost.Intrusive to biblioteka w języku C++, która umożliwia efektywne operacje na kontenerach, umożliwiając bezpośrednią manipulację struktur danych. Pozwala na umieszczenie obiektów w kontenerach w sposób "intrusive" poprzez dodanie hooków (haczyków) do klas, co pozwala na bezpośrednie zarządzanie strukturami danych w kontenerach. Przykładowa lista z
dokumentacji boost.Intrusive:
class MyClass
{
MyClass * next;
MyClass * previous;
};
int main()
{
acme_intrusive_list < MyClass > list;
MyClass myclass;
list.push_back( myclass );
assert( & myclass == & list.front() );
return 0;
}
Wg
dokumentacji boost.Intrusive kontenery "intrusive" są szybsze, o lepszym zarządzaniu pamięcią, o lepszej gwarancji wyjątków niż kontenery "non-intrusive" (czyli te dostępne standardzie).
Mamy następujące kontenery:
Aby nasz typ spełniał wymagania (zawierał odpowiednie składowe) wystarczy dziedziczyć po odpowiednim szablonie, zwanym "haczykiem" (ang. hook) np.
slist_base_hook < >
.
Kontenery AVL mają inną implementacje niż te stosowane w
std::set
i
std::multiset
. Charakteryzują się bardziej zbalansowaną strukturą, przez co dodawanie i usuwanie jest wolniejsze, ale przeszukiwanie szybsze niż w standardowych implementacjach zbioru i mapy.
Z kolei
kontenery SPLAY są używane w cachowaniu najczęściej używanych wartości, przez to odbywa się rebalansowanie drzewa przy odczycie.
Kontenery
"scapegoat" (sg_*) charakteryzują się w najgorszym przypadku czasem wyszukiwania O(logN), ale również zamortyzowanym czasem wstawiania i usuwania O(logN).
Kontenery "treap" łączą w sobie drzewo i stertę - używają one drzew sortowanych zarówno po kluczu jak i priorytecie atrybutów.
Na uwagę zasługują dostępne na
stronie boost.intrusive testy benchmarkowe porównujące kontenery intrusive ze standardowymi kontenerami.
boost.MultiArray
boost.MultiArray dostarcza funkcjonalność tablicy wielowymiarowej, która jest trzymana w ciągłym obszarze pamięci. W ramach tego modułu biblioteki boost są zaimplementowane następujące kontenery:
Przykład skopiowany z
dokumentacji boost.MultiArray:
#include "boost/multi_array.hpp"
#include <cassert>
int
main() {
typedef boost::multi_array < double, 3 > array_type;
typedef array_type::index index;
array_type A( boost::extents[ 3 ][ 4 ][ 2 ] );
int values = 0;
for( index i = 0; i != 3; ++i )
for( index j = 0; j != 4; ++j )
for( index k = 0; k != 2; ++k )
A[ i ][ j ][ k ] = values++;
int verify = 0;
for( index i = 0; i != 3; ++i )
for( index j = 0; j != 4; ++j )
for( index k = 0; k != 2; ++k )
assert( A[ i ][ j ][ k ] == verify++ );
return 0;
}
Boost.multi_index
Boost.Multi_index dostarcza kontenera jak
std::map
, który to umożliwia dostęp do wartości po wielu indeksach (nie muszą być unikalne), jest to zainspirowane bazą danych, gdzie możemy do wartości dostawać się nie tylko po kluczu, ale tworzyć różne indeksy. Oto szablon klasy z
dokumentacji:
namespace boost {
namespace multi_index {
template <
typename Value,
typename IndexSpecifierList = indexed_by < ordered_unique < identity < Value > > >,
typename Allocator = std::allocator < Value > >
class multi_index_container;
} using multi_index::multi_index_container;
}
A poniżej przykład użycia ze
strony dokumentacji boost.multi_index:
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
struct employee
{
int id;
std::string name;
employee( int id, const std::string & name )
: id( id )
, name( name )
{ }
bool operator <( const employee & e ) const { return id < e.id; }
};
typedef multi_index_container <
employee,
indexed_by <
ordered_unique < identity < employee > >,
ordered_non_unique < member < employee, std::string, & employee::name > >
>
> employee_set;
void print_out_by_name( const employee_set & es )
{
const employee_set::nth_index < 1 >::type & name_index = es.get < 1 >();
std::copy(
name_index.begin(), name_index.end(),
std::ostream_iterator < employee >( std::cout ) );
}
Wspomnę, że
boost::bimap
używa pod spodem właśnie tego szablonu klasy.
Boost.ptr_container
Boost.ptr_container zawiera implementacje kontenerów, które zamiast elementów przez wartość przechowują je przez wskaźnik. Innymi słowy jest to implementacja odpowiadająca trzymaniu elementów przez inteligentne wskaźniki w kontenerach standardowych. Kontenery te zwolnią pamięć zalokowanych elementów w momencie gdy same będą zwalniane. Kontenery te to:
| ptr_vector |
Kontener reprezentujący tablicę wskaźników danego typu. (szablon klasy) |
| ptr_list |
Kontener reprezentujący listę przechowującą wskaźniki danego typu. (szablon klasy) |
| ptr_deque |
Kontener reprezentujący tablicę wskaźników danego typu, analogiczną do kontenera std::deque. (szablon klasy) |
| ptr_map |
Kontener reprezentujący zrównoważoną mapę powiązań klucz-wartość bez powtórzeń, którego wartości są wskaźniki danego typu. (szablon klasy) |
| ptr_multimap |
Kontener reprezentujący zrównoważoną mapę powiązań klucz-wartość z powtórzeniami, którego wartości są wskaźniki danego typu. (szablon klasy) |
| ptr_set |
Kontener reprezentujący zrównoważone drzewo binarne bez powtórzeń, którego elementami są wskaźniki danego typu. (szablon klasy) |
| ptr_multiset |
Kontener reprezentujący zrównoważone drzewo binarne z powtórzeniami, którego elementami są wskaźniki danego typu. (szablon klasy) |
Boost.poly_collection
Boost.poly_collection zawiera kontenery nadające się do wydajniejszego przechowywania obiektów polimorficznych optymalizując pamięć - zapewniając ciągłość obszaru pamięci i pakowanie elementów zgodnie z ich rzeczywistym typem. Umożliwia to szybsze przetwarzanie dużych ilości obiektów polimorficznych, co jest szczególnie użyteczne w przypadku złożonych algorytmów, gdzie wydajność odgrywa kluczową rolę.
Na rysunku poniżej przedstawiono stosowanie polimorfizmu bez użycia tych kontenerów
(ze strony boost).
Stosowanie polimorfizmu z użyciem tych kontenerów
(ze strony boost).
Biblioteka zawiera następujące kontenery:
Ciekawą możliwością jest możliwość iterowania po wszystkich elementach, ale również po elementach danego typu np.:
for( auto first = c.begin( typeid( warrior ) ), last = c.end( typeid( warrior ) ); first != last; ++first )
Dla osób nieprzekonanych są dostępne
testy performance'owe.
Boost.property_map i boost.property_map_parallel
Boost.property_map umożliwia dodanie pewnych własności do obiektów, stosowane jest to w
bibliotece grafów (BGL), przykładowo nazw do wierzchołków grafu. Na
StackOferflow jest wątek gdzie trwa dyskusja czy się to faktycznie przydaje. Wspominam o tym, gdyż Boost.property_map jest w kategorii kontenerów biblioteki boost. Dodam, że biblioteka zawiera również wersję
wielowątkową (boost.property_map_parallel).
Boost.property_tree
Boost.property_tree jest reprezentacją drzewa, w której każdy wierzchołek może zawierać dowolną liczbę dzieci. Innymi słowy jest to "kontener", który trzyma dane jak w popularnych formatach XML, JSON, czy INI. Dużą zaletą boost.property_tree jest możliwość generowania jak również parsowania danych w formatach: XML, JSON, INI, czy INFO. Wg
dokumentacji może to być traktowane jako kontener, natomiast nie ma możliwości iteracji jedną pętlą po całym drzewie (da się iterować po całym drzewie, ale wymaga to ciut więcej niż jednej pętli ranged-based-for). Elementy w drzewie nie są posortowane po jakimkolwiek kluczu ale odpowiadają kolejności wstawienia.
Biblioteka zawiera szablon klasy
boost::basic_ptree
, a oprócz tego jego przezwiska dla konkretnych typów (podobnie zresztą jak
std::basic_string
):
Boost.Lockfree
Boost.Lockfree zawiera implementacje adapterów kontenerów, jak te dostępne w standardzie, ale dedykowane do zastosowań wielowątkowych. Poza tym są to implementacje nie zawierające blokad. Moduł biblioteki boost zawiera następujące adaptery kontenerów:
Struktury danych są "wait-free" (wolne od oczekiwania), jeśli każda równoczesna (concurent) operacja jest zapewniona, że zostanie zakończona w skończonej liczbie kroków. To pozwala na udzielenie gwarancji co do najgorszego przypadku liczby operacji.
Boost.Fusion
Boost.Fusion nie jest wg twórców biblioteki Boost zakwalifikowany jako moduł zawierający kontenery, jednakże implementuje kontenery podobne do tych w standardzie, z elementami-tuplami. Są to kontenery:
Poniżej przykłady użycia powyższych kontenerów:
#include <boost/fusion/include/vector.hpp>
#include <boost/fusion/container/list.hpp>
#include <boost/fusion/container/list/cons.hpp>
vector < int, float > v( 12, 5.5f );
std::cout << at_c < 0 >( v ) << std::endl;
std::cout << at_c < 1 >( v ) << std::endl;
list < int, float, string > l( 12, 5.5f, "text" );
std::cout << at_c < 0 >( l ) << std::endl;
std::cout << at_c < 1 >( l ) << std::endl;
std::cout << at_c < 2 >( l ) << std::endl;
cons < int, cons < float > > c( 12, cons < float >( 5.5f ) );
std::cout << at_c < 0 >( c ) << std::endl;
std::cout << at_c < 1 >( c ) << std::endl;
Boost.Heap
Boost.Heap jest bardziej rozbudowaną implementacją
std::priority_queue
. Jest ona rozszerzona o:
Oto lista szablonów kontenerów, dostarczonych przez Boost.Heap:
Kontenery, które weszły do standardu z biblioteki boost
Na początku artykułu wspomniałem, że wiele kontenerów dostępnych w standardzie ma swoje pochodzenie w bibliotece boost. W niektórych projektach może nie być możliwe użycie najnowszego standardu C++, dostarczające wymaganych kontenerów, wtedy możemy użyć odpowiedników z biblioteki boost:
Instalacja kontenerów biblioteki boost
Biblioteka boost jest ogromna i zawiera
bardzo dużą liczbę modułów, na szczęście wszystkie wyżej wymienione "kontenery" są header-only, czyli wystarczy je zaincludować w projekcie. To nie jest jednak tak proste jak się wydaje, gdyż biblioteki boosta są ze sobą mocno powiązane. Na szczęście nie trzeba kopiować wszystkich nagłówków bibilioteki boost, gdyż twórcy udostępnili narzędzie
boostdep, które dla wskazanej biblioteki wskaże tylko te pliki, które faktycznie potrzebujemy.
Alternatywne implementacje kontenerów w C++ poza biblioteką standardową i biblioteką boost
Pomimo bogatej zawartości biblioteki Boost, często tworzone są nowe kontenery lub powstają alternatywne implementacje standardowych kontenerów. Przykładowo, implementacja zabezpieczeń wielowątkowych dla kontenerów standardowych istnieje w
Concurrent Data Structures (CDS). Choć ponowna implementacja standardowych kontenerów bez wyraźnego powodu jest niezalecana, popularna biblioteka Qt zawiera własne wersje tych kontenerów (
QVector,
QList,
QString,
QMap, itp.). Dodatkowo, w środowisku game developmentu popularne są implementacje kontenerów, np.
EASTL. Niektóre biblioteki prezentują alternatywne wersje kontenerów, jak np.
folly::fbvector, które według twórców oferują lepsze zarządzanie pamięcią podczas realokacji. ALternatywę dla standardowych zbiorów i map oferuje biblioteka
Abseil, która implementuje je w oparciu o
b-drzewa. Istnieją też implementacje kontenerów standardowych korzystające z metaprogramowania (z danymi constexpr lub consteval), są to m.in.:
Frozen czy
immer. Również biblioteki
Plf::list,
Plf::queue,
Plf::stack deklarują się lepszą wydajnością niż ich odpowiedniki ze standardu C++. W ramach propozycji do kolejnych standardów C++, powstają nowe funkcjonalności, m.in. kontener
Plf Colony, który zaprojektowano jako szybki, nie unieważniający iteratorów w różnych operacjach. W naszym projekcie możemy operować na danych, które nie zmieszczą się w pamięci RAM, w tym celu powstała biblioteka
STXXL, która dostarcza kontenery jak standard C++, ale operujące na danych na dyskach twardych. Wreszcie istnieją implementacje konkurencyjne do implementacji biblioteki boost np.
https://github.com/tinloaf/ygg zawiera kontenery "intrusive".
Bibliografia
Autorzy artykułu