Datové kontejnery v C++ - Úvod do STL - Builder.cz - Informacni server o programovani

9. října 2001, 00.00 | Dnes se podíváme na datové kontejnéry z knihovny STL jazyka C++. Datový kontejnér je objekt, který je schopen "skladovat" jiné objekty. Ukážeme si rozdělení a vlastnosti kontejnérů. Na příkladu si ukážeme použití kontejnéru stack a bitset.

STL je zkratka slov Standard Template Library. Jedná se o standardní knihovnu šablon jazyka C++. Knihovna by měla být dodávána s každým překladačem C++. V STL můžeme najít mnoho různých a užitečných šablon. Mimo jiné zde jsou šablony datových kontejnerů, iterátory a šablony algoritmů, které pomocí iterátorů pracují s datovými kontejnery. Kompletní knihovnou STL se zabývat nebudeme. V několika článcích si uděláme něco jako přehled podstatných částí STL.

Pod pojmem datový kontejner si představme něco, co má schopnost "zapamatovat si" nějaké data. Data jsou v kontejneru nějakým způsobem uloženy. kontejnery v STL se dělí na posloupnosti a asociativní kontejnery. Posloupnosti jsou logické posloupnosti dat, které ale nemusejí být v paměti fyzicky za sebou. Asociativní kontejnery jsou kontejnery, kde k datům přistupujeme pomocí nějakého klíče. Způsob uložení dat, přístupu k nim je dán typem kontejneru. V knihovně STL jsem jich napočítal celkem 11. Snad jsem na žádný nezapomněl. Přehled datových kontejnerů je v následující tabulce.

Každý kontejner je šablona třídy. Parametrem této šablony je typ prvků, které mají být v kontejneru uloženy. Pole s libovolným intervalem indexování, které jsem předvedl v minulém článku byl vlastně takový pokus o napsání vlastního datového kontejneru. Každý kontejner v STL obsahuje následující veřejné typy. "Typ" je zde parametr šablony, tedy typ prvků, které jsou v kontejneru uloženy.

Dále každý kontejner má přetížené operátory = == !- < >, má k dispozici bezparametrický a kopírovací konstruktor. Nemusíme se tedy ničeho bát, a klidně jakkoliv kontejner kopírovat, nebo porovnávat. Dále každý kontejner má následující veřejné metody:

Další metody se v různých kontejnerech liší.

U typu, který má být parametrem kontejneru, musíme počítat s tím, že jeho instance budou kopírovány pomocí kopírovacího konstruktoru, případně pomocí operátoru =. U některých kontejnerů, mohou být prvky také porovnávány pomocí relačních operátorů. Proto nemohou-li být použity implicitní operátory je nutné je přetížit.

Dále je nutno upozornit, že všechny kontejnery (Nejen kontejnery, v podstatě vše z STL.) jsou deklarovány v prostoru jmen std.

Chce-li někdo proniknout do "tajů" kontejnerů, může si podrobně prostudovat hlavičkové soubory, ve kterých jsou deklarovány. Je v nich k dispozici úplný zdrojový text šablon. Rovněž se můžete podívat na můj velice jednoduchý ukázkový kontejner array z minulého článku.

Tolik tedy k přehledu o datových kontejnerech z STL jazyka C++. Některými kontejnery se budeme věnovat v samostatných článcích, dnes si letmo jen pro názornou ukázku ukážeme práci s dalšími kontejnery.

Musím ještě pro úplnost upozornit na tak zvané adaptéry. Některé kontejnery, které jsem zde uvedl, nejsou vlastně "skladiště dat". Jsou to třídy, které zapouzdří nějaký jiný kontejner a přizpůsobí (adoptují - adaptéry) ho jiným požadavkům. Například adaptér je stack, který jako svůj druhý parametr šablony vyžaduje nějaký kontejner. Implicitní hodnota tohoto parametru je deque. Adaptér kontejneru poznáme tak, že je u něj možnost jako další parametr šablony zadat jiný kontejner.

A nyní již jednoduchý příklad. Vytvoříme zásobník čísel int. Nějaké čísla do něj vložíme, a potom zase vybereme.

#include <stack>
#include <iostream>

int main()
{
	std::stack<int> zasobnik;	
	for(int i = 0; i < 10; i++)
	{
		zasobnik.push(i); // Metoda push uloží prvek na vrchol zásobníku. 
	}
	std::cout << "Počet prvků je " << zasobnik.size() << endl;
	while (!zasobnik.empty())
	{
		std::cout << zasobnik.top() << endl; 
		// Metoda top vrátí prvek na vrcholu zásobníku.
		zasobnik.pop();
		// Metoda pop odstraní prvek na vrcholu zásobníku.
	}	
	return 0;
}

Kdybychom z nějakých důvodů nechtěli mít jako zásobník (stack) adoptovánu deque, ale například vector, potom by řádek definice objektu zásobník vypadal takto:std::stack<int,std::vector<int> >.

Dalším příkladem bude bitset, tedy posloupnost bitů. Tento kontejner má oproti všem ostatním jednu zvláštnost. Parametrem šablony není typ, ale počet bitů, které budou v kontejneru uloženy. Podívejme se na jednoduchý příklad.

#include <bitset>
#include <iostream>

int main()
{
	std::bitset<32> bity;	
	for(int i = 0; i < 32; i++)
	{
		bity.set(i, (i % 2)); 
		/* Metoda set nastaví bit (jeho pořadí je dáno 1.parametrem) 
		na hodnotu druhého parametru. My zde máme nastaven každý lichý 
		bit na 1, sudý na 0. */ 
	}
	std::cout << bity.to_string() << endl;
	std::cout << (~bity).to_string() << endl; /* Operátor ~ provádí negaci */
	std::cout << bity.to_ulong() << endl; 
	/*Metoda to_ulong vrátí unsigned long, které reprezentují bity v poli. */
	for(int i = 0; i < 32; i++)
	{
		if (bity[i])
		{   /* Vypíši pořadí bitů s hodnotou 1 */
			std::cout << i << endl;
		} 
	}
	try
	{
		std::cout << bity[1000] << endl; 
		/*Pokud indexuji mimo zadanou horni mez indexovaní, bude vyvržena
		vyjimka typu out_of_range. */
	}
	catch (std::out_of_range &vyjimka) 
	{
		std::cerr << vyjimka.why() << endl;
	}
	return 0;
}

Tolik tedy pro úvod ke kontejnerům. V následujících článcích se budu některými kontejnery zabývat podrobněji. Nebudu zde ale uvádět výčet všech metod kontejnerů. Bylo by to naprosto zbytečné. Pro tyto účely slouží dokumentace ke knihovně. Jedna podle mého názoru pěkná dokumentace je na adrese http://www.sgi.com/tech/stl/stl_index_cat.html. Příště se podrobně budeme zabývat kontejnerem vector, což je jednorozměrné pole. V dalších článcích potom asociativním polem, a množinou.