PB161 Jazyk C++ - 4

Standardní knihovna C++

(Zpracováno na základě přednášky RNDr. Petra Mejzlíka z r. 1998)

4.11.2009: Doplněn znak "_" do názvu algoritmu for_each

Základní vlastnosti standardní knihovny

Výhody existence standardní knihovny

Neobsahuje však funkce pro grafiku a paralelní zpracování (procesy/proudy)

Historie

Standardní šablonová knihovna je relativní novinkou; ve starších verzích C++ nebyla.
První návrh v roce 1993: Alexander Stepanov (původní motivace: přenést možnosti generické knihovny Ady z r. 85 také do C++)
Obecné principy zkoumány již od konce 70. let: algoritmy lze abstrahovat od konkrétní implementace datových struktur, nad kterými pracují. Záleží především na možnostech rozhraní datové struktury: zda ji lze procházet oběma směry, jak velká je složitost získání i-tého prvku apod. Např. u třídících algoritmů nepotřebujeme znát implementaci tříděné posloupnosti, ale jen mít k dispozici prostředky pro čtení, zápis a porovnávání prvků.
Knihovna je součástí prvního standardu C++ přijatého r.1998
V praxi můžeme narazit i na překladače, které neimplementují normu dokonale

Další informace

Řetězce string

Deklarace jsou v hlavičkovém souboru <string>
Řetězce nahrazují char * používané pro posloupnosti znaků v C

Výhody:

Vstupy a výstupy

Deklarace vstupních a výstupních proudů jsou v hlavičkovém souboru iostream

Výstupy

Vstupy

Kontejnery

Příklad - kontejner vector:

#include <vector>
using namespace std;
...
struct telefon {
  string jmeno;
  int cislo;
};
vector<telefon> seznam(1000);
// Seznam s 1000 tel. čísly. Nezaměňovat
// s vector<telefon> seznam[1000] !!
cout<< seznam[i].jmeno<< seznam[i].cislo<< endl;
// tisk i-té položky

Kontejner typu vector má danou délku. Podobně jako u polí tedy můžeme sáhnout vedle: seznam[1000]. Pro přístup s kontrolou indexů slouží funkce at (zápis seznam.at(1000) ohlásí chybu, zatímco seznam[1000] prostě sáhne mimo hranice vektoru s potenciálně katastrofickým účinkem).

Vektor může měnit svoji délku: buď explicitně:
   seznam.resize(seznam.size()+n);
nebo v důsledku přidání prvku na konec vektoru:
vector<string> ovoce;
// vektor s nulovou délkou
ovoce.push_back("jablka");
ovoce.push_back("hrusky");
ovoce.push_back("pomerance");

Typy kontejnerů

vector<T> vektor proměnné délky
list<T> oboustranně zřetězený seznam
queue<T> fronta 
stack<T> zásobník
deque<T> oboustranná fronta (optimalizována pro přidávání a ubírání na obou koncích, ale lze i uprostřed)
priority_queue<T> fronta setříděná podle hodnot
set<T> množina
multiset<T> multimnožina (s možností opakování téže hodnoty)
map<T /*klíč*/,T /*hodnota*/> asociativní pole - index nemusí být numerický! (operátor [] přetížen)
multimap<klíč,hodnota> asociativní pole s možností několika položek s týmž klíčem

T představuje typ ukládaných hodnot (může jít o typ základní nebo uživatelský).

Kontejnery jsou definovány ve stejnojmenných hlavičkových souborech, pouze multimap a multiset jsou zahrnuty do hlavičkových souborů map a set, podobně dequeue a priority_queue jsou spolu s queue v hlavičkovém souboru queue

Příklad (telefonní seznam):

#include <map>
...
map<string,int> seznam;
string s;
...
if (int i = seznam[s]) // index je string!
cout << s << ' ' << i << endl;

Tiskne telefonní číslo uvedené u jména s.
Operátor [] se indexuje hodnotami prvního typu (zde string) a vrací druhou položku dvojice nebo 0 (obecně implicitní hodnotu druhého typu), pokud příslušná položka neexistuje. V příkladě musíme zaručit, že nikdo nebude mít telefonní číslo 0.

Pozor! Pokud daná položka v seznamu není, bude vytvořena a seznam se tím rozroste. Proto pro zjištění, zda určitá položka v seznamu je, je vhodnější použít metodu find (viz dále v části Algoritmy)

Pro kontejnery je definována řada funkcí (metod) a přetížených operátorů:

Pro map<T1,T2> a multimap<T1,T2> - setříděné asociativní pole (multimap<T1,T2> může obsahovat opakování téže hodnoty) [Vyžadují hlavičkový soubor #include <map>]: Pro set<T> a multiset<T> - setříděná množina (popř. s možností opakování téže hodnoty) [#include <set>]

set<T> a multiset<T> jsou v podstatě implementovány jako map a multimap bez druhé složky. Proto je možno do nich přidávat položky i pomocí operátoru []

Pro queue<T> a priority_queue<T> - fronta (popř. setříděná podle hodnot) [#include <queue>] Pro pair<T1,T2> - dvojice hodnot

Iterátory

Iterátory jsou struktury, které mohou fungovat jako odkaz na libovolnou položku daného kontejnerového typu. V triviálním případě mohou být implementovány prostě jako ukazatele, někdy ještě obsahují nějaké stavové proměnné. Výhodou standardní knihovny je, že se používají stejně bez ohledu na to, jak jsou v konkrétním systému implementovány.

Příklad:

#include <list>
...
list<telefon> seznam;
list<telefon>::iterator t;
...
for (t=seznam.begin(); t!=seznam.end(); ++t)
// seznam.begin() ukazuje na první prvek,
// seznam.end() ZA (nikoli na!) poslední prvek
{
// něco uděláme s hodnotou *t
}

Iterátory lze používat i pro string!

Iterátor kontejneru map a multimap použitý jako ukazatel ukazuje na strukturu složenou z klíče first a asociované hodnoty second. Je-li it iterátor, lze proto psát např. it->first

Algoritmy

Příklad:

#include <algorithm>
#include <vector>
#include <list>

vector<telefon> seznamv(1000);
list<telefon> seznaml;
...
copy(seznamv.begin(), seznamv.end(),
seznaml.begin());

Další algoritmy:

Organizace knihovny

Staré hlavičkové soubory pro C++ (s příponou .h), např. iostream.h: nejsou součástí oficiálního standardu, ale patrně je budou překladače podporovat ještě řadu let.

Nové hlavičkové soubory pro C++ (bez přípony), např. iostream: obsahují prakticky všechno, co jejich předchůdci a další rozšíření. Jejich obsah je uzavřen v prostoru jmen std. Nejsou se starými však zcela kompatibilní ani vzestupně.

Standardní hlavičkové soubory jazyka C, jako je stdio.h (v něm jsou mj. deklarovány procedury printf, scanf) jsou oficiálně podporovány. Obsah těchto hlavičkových souborů není uzavřen v prostoru jmen std.

Nové hlavičkové soubory obsahující funkce a struktury ze standardní knihovny jazyka C, mají místo přípony .h předponu c (např. cmath) a jejich obsah je uzavřen v prostoru jmen std.


Předchozí Předchozí přednáška Další Další přednáška Hlavní stránka Hlavní stránka