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

• úspora času při programování
• přenositelnost
• knihovna C++ je velmi rozsáhlá (formální popis asi 300 stran. ale není nutné znát všechny prostředky - a málokdo je zná)
• podstatné je porozumění základním pojmům, na kterých je knihovna vybudována: kontejner, iterátor, generický algoritmus
• většina knihovny je vybudována na používání tzv. šablon; ty umožňují a usnadňují jednotné vytváření a používání analogických prvků pro různé datové typy

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

• Kniha Dirk Louis, Petr Mejzlík, Miroslav Virius: Jazyky C a C++ podle normy ANSI/ISO - kompletní kapesní průvodce. GRADA, Praha 1999
• SGI STL (je součástí GNU překladačů g++)
• Dinkumware

Řetězce string

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

Výhody:

• nemají omezenou délku (v principu)
• jsou pro ně definovány užitečné operace:
string s1 = "Hello";
string s2 = "world";
string s3 = s1 + ", " + s2 + "!\n";
s1 += '\n'; // s3 obsahuje "Hello, world!\n"
char posledni = s2[s2.size()-1] // operátor [] přetížen i pro string!
int pos = s3.find("ll") // Vrati pozici zacatku podretezce ll v s3, tj. 2
int pos = s3.find_first_of(",ow")
   // Vrati pozici prvniho z uvedenych znaku, tj. 4; prvni je 'o' na pozici 4
   // Funkce find_first_not_of naopak najde první znak neobsazeny v danem retezci
   // U obou techto funkci muze byt parametrem znak, pole znaku i string;
   // pokud se retezec nebo znak nenajde, vrati cislo vetsi nez delka retezce
s3 = s1.substr(0,4); // 4 znaky počínaje nultým, tj. "Hell"
s1.replace(0,5,"Ahoj"); // Nahradit lze i podřetězcem jiné délky"
• lze je porovnávat s textem v uvozovkách a konvertovat na "staré" řetězce:
  string s;
if (s == "ano") {
// ...
}
printf("%s\n", s.c_str()); // c_str() konvertuje string na char*

Vstupy a výstupy

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

Výstupy

• Standardním výstupním proudem je cout, standardním proudem pro chybový výstup (nebo obecně oznámení určená uživateli, např. výzvu k zadávání dat) je cerr.

• Je k dispozici přetížený operátor << (přetížený operátor je totéž jako přetížená funkce, jen jeho argumenty se nezapisují do závorek, ale infixově). Operátor vrací výsledek výstupní operace (v podstatě ukazatel do výstupního proudu), takže je možné vypsat více hodnot jedním příkazem:
  cout << "Pocet bodu: " << n;

• Tištěná data lze formátovat podobně jako v příkazu printf. Definice potřebných manipulátorů jsou v hlavičkovém souboru <iomanip>.
#include <iostream>
#include <iomanip>
using namespace std;
//...
double angle=0.1234569;
cout << angle << endl;
// vytiskne se 0.123457
cout << setprecision(4) << angle << endl;
// vzhledem k použití manipulátoru setprecision
// se vytiskne 0.1235
cout << angle << endl;
// vytiskne se opět 0.1235 !
cout << setprecision(8) << angle << endl;
// vytiskne se 0.1234569
cout << setw(10) << angle
// zarovná šířku na 10 znaků (tisk tabulek)

• Většina manipulátorů působí až do další změny (manipulátor setw však platí jen pro následující položku)!

Vstupy

• Standardním vstupním proudem je cin.

• Je k dispozici přetížený operátor >> (analogicky jako << pro výstup]
  int i; double d;
cin >> i >> d;

• Uvádějí se přímo názvy proměnných, nikoli ukazatele na ně. Píšeme tedy sice
    scanf("%d %lf",&i,&d)
ale NE
    cin >> &i >> &d;

• Posloupnost znaků bez oddělovačů lze načítat přímo do proměnné typu string:
  string str;
cout << "Napis krestni jmeno\n";
cin >> str;

• Celý řádek i s mezerami a tabulátory lze načíst do pole znaků (céčkovského řetězce) pomocí funkce getline():
  #include <iostream>
#include <cstring>
char *str[81];
cout << "Napis svoje jmeno a prijmeni\n";
cin.getline(str, /*maxdelka:*/40);

  nebo do řetězce typu string stejnojmennou funkcí z hlavičkového souboru string:
  #include <string>
string str;
getline(cin, str);

• Číst a psát znak po znaku můžeme pomocí funkcí get a put:

  Program pro kopírování vstupu na výstup:

  int main()
{
char c;
while (cin.get(c) ) cout.put(c);
}

• Lze definovat vlastní verze operátorů << a >> pro tisk/načítání objektů, které potřebujeme zpracovávat v programu!

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ů

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ů:

• .count(x) - počet prvků, jejichž klíčová hodnota (T1) je x
• .empty() - test na prázdnost
• .insert() - vložit prvek
• .size() - velikost
• .begin(), .end() - iterátory
• ->first, ->second - zpřístupnění první (klíč) a druhé (hodnota) složky
• [x] - zpřístupnění druhé (hodnota) složky prvku s klíčem x

• .count(x), .empty(), .insert(), .size(), .begin(), .end() - význam stejný jako u (multi)map

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 []

• .empty() - test na prázdnost
• .pop() - odebrání prvku z fronty
• .push() - přidání prvku do fronty
• .size() - velikost
• .top() - zpřístupnění prvku na vrcholu fronty (pouze priority_queue)

• .first, .second - zpřístupnění první a druhé složky
• ==, < - přetížené operátory podle první složky

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:

• for_each(začátek, konec, funkce): zavolá funkce(*p) pro všechna p v zadaném rozsahu.
• find(začátek, konec, hodnota): vrací odkaz (iterátor) na položku obsahující danou hodnotu.
• count(začátek, konec, hodnota): počítá výskyty dané hodnoty.
• equal(začátek, konec, začátek2): porovnává dvě posloupnosti.
• sort(začátek, konec): třídění.
• sort(začátek, konec, cmp): třídění podle třídícího kritéria cmp. Volá cmp(p1,p2), kde p1 a p2 jsou odkazy (iterátory) na položky daného typu kontejneru.
• min_element(začátek, konec)
max_element(začátek, konec): nalezení nejmenšího (největšího) prvku v daném rozmezí.
• min_element(začátek, konec, cmp)
max_element(začátek, konec, cmp): nalezení nejmenšího (největšího) prvku v daném rozmezí podle uživatelem definovaného kritéria.
• set_union, set_intersection, ...: operace definované na množinách.
• a další.

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řednáška

Další přednáška

Hlavní stránka