3. Standardní knihovna C++

Ve cvičení se seznámíme se zástupci sekvenčních a asociativních kontejnerů.

Vzorové příklady najdete buď v repozitáři v adresáři tut04.

Typickým zástupcem sekvenčního kontejneru je std::vector, který je flexibilní náhradou pole. V následujícím příkladu vytvoříme tři vektory: A bude inicializován na velikost 10 prvků typu int, vektor B nulové velikosti bude připraven na ukládání prvků datového typu float a konečně vektor C bude inicializován třema znaky.

std::vector<int> A(10);
std::vector<float> B;
std::vector<char> C {'a', 'b', 'c'};

Velikost jednotlivých vektorů můžeme ověřit např. pomocí členské metody size.

std::cout << A.size << std::endl;

Výsledek si nebude žádným překvapením, stejně jako u ostatních vektorů. S velikostí vektoru lze ovšem různě pracovat. Kromě automatické realokace při použítím funkce push_back (viz níže), lze pro přímou realokaci využít metodu resize, nebo využít metodu reserve pro vyhrazení prostoru v paměti pro budoucí realokaci - realokace v rezervované paměti by měla být rychlejší, počet prvků rezervované paměti vrátí metoda capacity. A konečně, pokud by bylo z hlediska aplikace důležité, kolik na prvků daného typu lze kontejner zvětšit, poslouží metoda max_size.

std::cout << B.size() << std::endl;
std::cout << B.capacity() << std::endl;
 
B.reserve(100);
std::cout << B.size() << std::endl;
std::cout << B.capacity() << std::endl;
 
std::cout << C.max_size() << std::endl;

Pokud to dává smysl ¹⁾, lze existujícím položkám kontejneru přístupovat přímo, prostřednictvím operátoru [] a metody at, nebo nepřímo s využitím iterátoru. Přímým přístupem lze provádět čtení i zápis, iterátor může být i konstantní, tj. pouze pro čtení.

A[3] = 100;
std::cout << A.at(3);
std::vector<int>::iterator a = A.begin();
std::cout << *(a+3);

Hlavní rozdíl mezi prvními dvěma způsoby je v tom, že u metody at' jsou kontrolovány meze a v případě jejich překročení je vyvolána výjimka std::out_of_range. Při použití operátoru [] meze kontrolovány nejsou.

// vektor B je prázdný
try {
    B.at(0);
} 
catch (std::out_of_range &e) {
    std::cout << e.what();
}

Hlavní výhodou vektoru oproti poli je flexibilita při vkládání nových prvků - vektor v případě potřeby automaticky zvětšuje prostor podle potřeby (a pokud je v paměti místo).

// vložení prvku na konec vektoru
B.push_back (10);
std::cout << B.size() << std::endl;
std::cout << B[0];
 
// vložení prvku na pozici iterátoru, v tomto případě na začátek
B.insert (B.begin(), 20);

// konstatní iterátor, nelze měnit položky vektoru
for (std::vector<char>::const_iterator i = C.begin(); i != C.end(); ++i)
    std::cout << *i << ' ';
 
// protože iterátor je datovým typem, lze využít v C++11 kompilátorech auto
// v tomto případě půjde měnit položky, kompilátor volí nekonstantní iterátor
for (auto i = C.begin(); i != C.end(); ++i)
    std::cout << *i << ' ';
 
// pro zjednodušení zápisu lze využít typedef
typedef std::vector<char> pole;
pole C;
 
for (pole::const_iterator i = C.begin(); i != C.end; ++i)
    std::cout << *i << ' ';

// C++11 range-based for loop
for (auto i : C)
    std::cout << i << ' ';
 
// pro případ, že chceme zajistit nemožnost změny proměnné i uvnitř smyčky
for (const auto i : C)
    std::cout << i << ' ';
 
// při použití reference lze měnit prvky uvnitř kontejneru
for (auto &i : C)
    std::cout << i << ' ';
 
// případně lze vytvořit konstatní referenci - to dává smysl v případě, 
// že nechceme umožnit změnu prvků kontejneru, ale časová režie kopírování 
// prvků z kontejneru je příliš velká
for (const auto &i : C)
    std::cout << i << ' ';

std::copy (C.begin(), C.end(), std::ostream_iterator<char>(std::cout, " "));

// přetížený proudový operátor
std::ostream& operator<< (std::ostream& out, const std::vector<char>& v) {
  if (!v.empty()) {
    out << "[";
    std::copy (v.begin(), v.end(), std::ostream_iterator<int>(out, ", "));
    out << "]\n";
  }
  return out;
}
 
// lze vytvořit i šablonu, která zajistí nezávislost na datovém typu použitém ve vektoru
template <typename T>
std::ostream& operator<< (std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << "[";
    std::copy (v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "]\n";
  }
  return out;
}

Celkem často je třeba položky v kontejneru seřadit. Pro tento účel lze využít např. generickou funkci std::sort. Argumenty funkce jsou iterátory začátku a konce kontejneru.

std::vector<char> R = {'r', 'j', 'l', 'k', 'a'};
std::sort (R.begin(), R.end());

Pokud bychom potřebovali reverzní řazení, lze využít hned několika možností

// reverzní iterátory
std::sort (R.rbegin(), R.rend());
// generická funkce reverse
std::reverse (R.begin(), R.end());

Další možností, která je využívána v případech, kdy není známo třídicí kritérium (např. instance nově definované třídy), lze využít komparátoru - funkce, která bude porovnávat instance mezi sebou. Nejčastěji je komparátor definován jako třída, která obsahuje přetížený operator(), takže je možné anonymní instanci třídy volat jako funkci (funkční objekt, funktor).

struct comp {
     bool operator()(char a, char b) {
          return a > b;
     }
}; 
 
std::sort (R.begin(), R.end(), comp);

Na rozdíl od sekvenčních kontejnerů, které používají jako klíč pro přístup k položkám kladné celé číslo, umožňují asociativní kontejnery použít jako klíč libovolný datový typ. Jak reprezentanta asociativního kontejneru zde použijeme std::map.

Kontejner std::map vytváří páry klíč-hodnota, klíč je v tomto případě unikátní²⁾. Vnitřní implementace je taková, že položka je vlastně proměnnou datového typu std::pair a platí, že první položka páru se jmenuje first a druhá položka se jmenuje second. V příkladu je vytvářen vztah mezi světovými metropolemi a počtem jejich obyvatel.

std::map<std::string, int> D;
D["Tokyo"] = 37833000;
D["Dilli"] = 24953000;
D["Sanghaj"] = 22991000;
D["Maxico City"] = 20843000;
D["Sao Paulo"] = 20831000;

Stejně jako kontejner std::vector je i kontejner std::map možné procházet různými způsoby, např. pomocí iterátoru, který lze opěr nahradit klíčovým slovem auto.

for (auto i : D) {
    std::cout << std::setw(15) << std::left << i.first << i.second << "\n";
}

Za povšimnutí stojí, že jednotlivé prvky kontejneru jsou seřazeny podle kritéria, které je uplatnitelné na klíč. Z toho mimochodem vyplývá, že pokud bude klíčem nový datový typ, definovaný jako třída, je třeba pro tento datový typ vytvořit pravidlo pro porovnávání instancí (tj. přetížený operátor >).

Dilli          24953000
Maxico City    20843000
Sanghaj        22991000
Sao Paulo      20831000
Tokyo          37833000

Díky řazení je možné efektivně implementovat vyhledávací funkci find, jejíž návratovou hodnotou je iterátor nastavený na vyhledaný prvek. V příkladu plná kvalifikace iterátoru, opět lze využít auto.

std::map<std::string, int>::iterator d = D.find("Sanghaj");
std::cout << "found: " << std::left << d->first << " " << d->second << "\n";

Ke vkládání dat do kontejneru std::map slouží kromě přímého přístupu operátorem [] funkce insert. Protože se položky automaticky řadí podle hodnoty klíče, není při vkládání (na rozdíl od vektoru a jiných sekvenčních kontejnerů) nutné používat iterátor, ovšem pokud je známá přibližná budoucí pozice vkládané položky v seřazené kolekci, dá se iterátorem napovědět. Návratovou hodnotou funkce insert je pár tvořící iterátor a logická hodnota, nabývající hodnoty false v případě, že vkládaná položka se již v kontejneru vyskytuje.

std::pair<std::map<std::string, int>::iterator, bool> ret;
// vytvoření instance std::pair přímým voláním konstruktoru 
ret = D.insert(std::pair<std::string, int>("Sanghaj", 22991000));
if (ret.second == false) {
    std::cout << "polozka " << ret.first->first << " jiz v kolekci existuje s hodnotou " << ret.first->second << "\n";
}
 
// vytvoření instance std::pair metodou std::make_pair
// dá se čekat, že položka bude první - použit iterátor 
D.insert (D.begin(), std::make_pair("Beijing", 21707000));
 
// vytvoření páru metodou kontejneru
D.insert (std::map<std::string, int>::value_type ("Jakarta", 31500000));

Aktualizaci hodnot párů je možné provést přímo prostřednictvím operátoru [] nebo s využitím iterátoru (tj. např. vyhledáním páru podle klíče first a změnou hodnoty second).

K odstranění položek z kontejneru lze využít funkci erase ve třech různých variantách

// mazání položky podle klíče
D.erase ("Mexico City");
 
// mazání položky pomocí iterátoru
auto d = D.find ("Mexico City");
D.erase (d);
 
// mazání položky v rozsahu daném dvěma iterátory (v tomto případě všechny položky)
D.erase (D.begin (), D.end ());

Jak už bylo zmíněno v předchozím textu, pokud má být klíčem hodnota uživatelsky definovaného datového typu, je třeba definovat kritérium, podle kterého se instance tohoto typu řadí. To lze zařídit např. dvěma následujícími způsoby.

1. Třída popisující nový datový typ obsahuje přetížený operátor <, který definuje kritérium porovnávání.

class Key {
    int value;
public:
    bool operator< (const Key & src) const {
        return (this->value < src.value);
    }
};

Key k1, k2;
std::map<Key, int> A;
 
A.insert (std::pair<Key, int>(k1, 100));
A.insert (std::pair<Key, int>(k2, 200));

2. Definice komparátoru. Komparátor je třída, která obsahuje přetížený operátor (), takže je možné komparátor volat jako funkci. Takto definovaný komparátor je třetím argumentem předávaným šabloně třídy.

struct PorovnejOsobu;
 
class Osoba {
    std::string jmeno;
public:
    Osoba (std::string j): jmeno(j) {}
    bool operator() (const Osoba &a) {
        return this->jmeno < a.jmeno;
    }
    friend PorovnejOsobu;
};
 
struct PorovnejOsobu {
    bool operator() (const Osoba &a, const Osoba &b) {
        return a.jmeno < b.jmeno;
    }
};
 
std::map<Osoba, int, PorovnejOsobu> B;
B.insert(std::pair<Osoba, int>(Osoba("Jan"), 10));

V C++11 je možné využít ještě lambda funkce. Lambda je zápis funkčního objektu, tj. objektu, který bude možné volat jako funkci. V tomto případě není ovšem aplikace úplne přímočará, příklad je spíše návodem na další zkoumání.

auto comparator = [](const Osoba& a, const Osoba& b) -> bool
{
    return a.jmeno < b.();
};
 
std::map<Osoba, int, decltype(comparator)> B(comparator);