---
title: 'Вежбе 2 - C++ STL'
author: 'Радован Туровић - Бранислав Ристић'
lang: sr-Cyrl
format: 
  revealjs:
    output-file: "presentation.html"
    theme: [white, ../../../custom.scss]
    transition: slide
    navigation-mode: vertical
    controls-layout: bottom-right
    controls-tutorial: true
    slide-number: true
    show-slide-number: all
    scrollable: true
    chalkboard: true
    center: true
  beamer:
    output-file: "presentation.pdf"
    documentclass: beamer
    pdf-engine: lualatex
    mainfont: "DejaVu Serif"
    theme: Szeged
    navigation: horizontal
    aspectratio: 32
    section-titles: true
    geometry:
      - bottom=1.5cm
  pdf:
    output-file: "document.pdf"
    pdf-engine: lualatex
    documentclass: article
    mainfont: "DejaVu Serif"
---

# Тест Ц++ способности

## Задатак 1
* Написати мали алат који узме име датотека са командне линије и пита корисника за ПИН. 
* ПИН је дугачак тачно 1 бајт и може бити број од 1 до 255. 
* Програм треба да генерише нову датотеку која има исто име као унешено али са додатом екстензијом `.enc`
* Та датотека има у себи сваки бајт улазне датотеке XOR-ован ПИН вредношћу. 

## Проширења на З1 - За вежбу
* Проширити тако да корисник може да унесе 32-битну нумеричку вредност која се примењује на сваких 4 бајта улазне датотеке тако да се датотека неадекватне величине проширује бајтовима нулте вредности док величина није умножак броја 4
* Проширити тако да корисник може да унесе било који стринг као лозинку тако да се користе индивидуални бајтови лозинке на индивидуалним бајтовима улаза тако да нема потребе да се датотека прошири било чим. 
* Проширити тако да програм детектује да се користи на шифрованом датотеком и дешифрује је 

## Мера успеха
* Ако не можете да решите задатак 1 у датом времену, потребно је да освежите ваше познавање Ц++ језика иначе ће вам овај предмет бити превише тежак. 
* Ако можете да га решите, вероватно неће бити проблема да пратите градиво. 
* Ако можете да одрадите сва проширења: свака част!

# STL (Стандардна библиотека шаблона)

## Документација 
* Док се бавите употребом стандардне библиотеке, обавезно се служите документацијом
* [cppreference](https://en.cppreference.com) је нешто што може бити од користи
* [cplusplus](https://cplusplus.com/reference/) је такође добар извор документације

## Шта је STL? 
* _Standard Template Library_ - стандардна библиотека шаблона 
* Део стандардне библиотеке C++ који се односи на структуре података и најчешће алгоритме
* Оно што нарочито карактерише STL је увођење контејнера као концепта и _итератора._ 

## Општа идеја иза итератора
* Итератор је апстракција на свим типовима који служе да показују унутар структура података
* То обухвата индексе, кључеве, и кључно __показиваче.__ 
* омогућава да се, рецимо, имплементирају алгоритми који раде са било којом структуром података

## Општа идеја иза итератора
* То је зато што уместо да проследите целу структуру, ви пошаљете итератор који показује на почетак и итератор који показује на крај
* Итератор садржи информацију о типу садржаја и интерфејс који нам дозвољава да добавимо текућу вредност, пређемо на следећу, и проверимо да ли су итератори еквивалентни и пар сличних једноставних операција. 
* СА тим може да се направи алгоритам који се несметано креће кроз структуру, а да не зна баш ништа о томе како је она дизајнирана.  

## Контејнери STL-а
+ Контејнери STL-а се деле на:
  - Секвенцијалне
  - Асоцијативне
  - Неуређене асоцијативне
  - Адаптере

## Секвенцијални контејнери
* Секвенцијални контејнери су они чији је садржај поређан у некакав дефинитиван редослед
* Разликују се по томе какве гаранције нуде и како им је садржај распоређен у меморији што има утицај на перформансе

## Секвенцијални контејнери
* `array` - низ статичке величине континуалан у меморији
* `vector` - низ динамичке величине континуалан у меморији
* `deque` - не-континуална структура која је таква да је додавање на њен крај и почетак брзо и никада не инвалидира итераторе који показују у унутрашњост
* `forward_list` - једноструко спрегнута листа
* `list` - двоструко спрегнута листа

## Пример: вектор
```c++
  vector<int> v = {3, 1, 4, 1, 5, 9, 2};
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << endl;
  }
  v.push_back(99);
  v.push_back(98);
  v.insert(v.begin() + 2, 77);
  v.pop_back();
  for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << endl;
  }
```

## Пример: вектор
* Приметите да се STL контејнери могу статички иницијализовати
* Такође приметите да имамо потпуну контролу над садржајем вектора: једино је проблем што је убацивање као ово које смо урадили _споро._ 
* Приказан је идиоматски начин на који се ради са итераторима: обратите пажњу на 'auto'; тиме дајемо компајлеру прилику да сам закључи који је тип: ово се зове 'type inference' (откривање типа) и представља јако корисну особину будући да је стварни тип `vector<int>::iterator`

## Асоцијативни контејнери
* Асоцијативни контејнери су контејнери где уместо да елемент има место које је дефинисано редоследом, елемент се адресира кроз некакву произвољну вредност која се зове _кључ_ 
* За разлику од сваког другог језика са којим имате искуства, у C++-у асоцијативни контејнери _нису_ базирани на хеш структурама но се једноставно чувају _сортирани_ по кључу што гарантује $log(n)$ време претраге 

## Асоцијативни контејнери
* `set` - Колекција јединствених кључева и ничег више
* `map` - Колекција парова типа кључ-вредност, кључеви су јединствени
* `multiset` - Као `set` али кључеви нису јединствени 
* `multimap` - Као `map` али кључеви нису јединствени 

## Пример: мапа
```c++
  map<string, int> m = {{"abc", 1}, {"def", 2}, 
  {"xyz", 907}};
  for (const auto &n : m) {
    cout << "m[" << n.first << "] = " 
    << n.second << endl;
  }
  m["abc"] = 5;
  m["qux"] = 9;

  for (const auto &n : m) {
    cout << "m[" << n.first << "] = " 
    << n.second << endl;
  }
```
## Нова for петља
* Уместо да директно користимо итераторе (будући да је пролажење кроз све елементе толико често) можемо да користимо `for-each` верзију for петље као овде
* Приметите да добијамо и кључ (то је овде `.first`) и вредност (то је овде `.second`)
* Ово може, ако вам је верзија компајлера довољно свежа (пробајте!) и елегантније кроз _деструктуирање_

## For са деструктуирањем
```c++
for (const auto& [k, v] : m){
  cout << "m[" << k << "] = "
  << v << endl;
}
```

## Неуређени асоцијативни контејнери
* Ово су исте структуре као и већ поменуте само што су `unordered_set`, `unordered_map`, `unordered_multiset` и `unordered_multimap` такве да чувају кључеве преко хеш вредности.
* Ово даје јако добро просечно време (ефективно $O(1)$) са ризиком да ће бити $O(n)$ у најгорем могућем случају. 

## Адаптери
* Адаптери служе да секвенцијалним контејнерима пруже другачији интерфејс такав да одговара ограничењима неких добро познатих структура података
* Примери су `stack`, `queue`, и `priority_queue`

## Primer: Stek
```c++
  stack<int> s;
  s.push(3);
  s.push(1);
  s.push(4);
  s.push(1);
  s.push(5);
  s.push(9);
  s.push(2);
  s.push(6);
  while (!s.empty()) {
    cout << s.top() << endl;
    s.pop();
  }
```

# Алгоритми

## Сврха библиотеке алгоритама 
* Врло је чест случај да решење програмерског проблема може да се састави из градивних елемената (елементарних алгоритама) који се стално понављају
* Сврха ове библиотеке јесте да се ти максимално генерички алгоритми издвоје на једно место, имплементирају јако квалитетно и користе у решењима
* Немогуће је проћи све алгоритме: зато служи документација; уместо тога можемо да погледамо пример 

## Пример: Сума свих бројева дељивих са 3 до 1024
```c++
bool div_three(int i) { return i % 3 == 0; }
void algo_primer() {
  vector<int> v(1024);
  vector<int> vv(1024);
  iota(v.begin(), v.end(), 1);
  copy_if(v.begin(), v.end(), vv.begin(), div_three);
  int r = accumulate(vv.begin(), vv.end(), 0);
  cout << r << endl;
}
```

## Пример
* Овде се користи `iota` алгоритам да напуни неку структуру са (редом) елементима од неке почетне вредности, овде то су вредности почевши од 1; знамо да ће ићи до 1024 зато што смо направили да буде толика структура 
* `copy_if` копира у нову структуру све оне елементе који задовољавају неки предикат - овде то је експлицитна функција: у пракси много вероватније би се користила _lambda_ функција. 
* `accumulate` је аутоматски алгоритам за сумирање структуре који може да се адаптира да ради са било којом бинарном операцијом
