Lab 03 - Zaawansowane kolekcje, algorithm

Lab 03 - Kontenery oraz algorytmy standardowe, `<vector>`, `<list>`, `<algorithm>`

Typy wyliczeniowe `enum class`

Oprócz typów podstawowych jak short, int, float, double, etc. istnieje możliwość definowania nowych typów z ograniczonym zbiorem dozwolonych wartości: typów wyliczeniowych.

Przykład:

enum class Color {
    White,
    Black,
    Red,
    Green,
    Blue,
};

Typ wyliczeniowy Color definiuje 5 wartości. Zadeklarowanie zmiennej tego typu, umożliwi przypisanie do niej tylko i wyłącznie tych wartości. Np.:

Color color = Color::White;
color = Color::Red;
color = 5; // błąd kompilacji

Wykorzystanie w instrukcjach warunkowych

if (color == Color::Black) {
    std::cout << "Color is black\n";
} else if (color == Color::White) {
    std::cout << "Color is white\n";
}

switch (color) {
    case Color::Red:
        std::cout << "Color is red\n";
        break;
    case Color::Blue:
        std::cout << "Color is blue\n";
        break;

    case Color::Green:
        std::cout << "Color is green\n";
        break;

}

Przekazywanie typu wyliczeniowego do funkcji

void drawBox(int x, int y, int width, int height, Color color) {
    // do sth with `color`
}

drawBox(10, 10, 200, 300, Color::Red);

Wyrażenia lambda

W standardzie języka C++11 został wprowadzony nowy rodzaj funkcji anonimowej, wyrażenia lambda. Składnia wyrażenia lambda jest następująca:

[<capture>](<arguments>) -> <return_type> {
  <body>
}

gdzie:

<capture> – lista zmiennych z zasięgu lokalnego/globalnego jakie mają być przekazane (przechwycone) do wyrażenia lambda.
<arguments> – lista argumentów wyrażenia lambda (funkcji anonimowej), analogiczna jak przy klasycznych funkcjach,
<return_type> – opcjonalnie zdefiniowany typ wartości zwracanej z wyrażenia. Część -> <return_type> jest opcjonalna.
<body> – ciało funkcji, sekwencja instrukcji jakie mają być wykonane podczas wywołania lambdy.

Z racji tego, że wyrażenia lambda są funkcjami anonimowymi, to nie mają swojej nazwy. Jednakże można je przypisać np. do zmiennej lokalnej i za pomocą tego identyfikatora, wyrażenie lambda wywołać. Innym podejściem jest przekazywanie wyrażenia lambdy zdefiniowanego inline jako parametr innej funkcji (np. któregoś algorytmu standardowego).

Ponadto, w odróżnieniu od funkcji klasycznych, mogą być zdefiniowane wewnątrz innej funkcji (jej widoczność jest wtedy ograniczona odpowiednim blokiem instrukcji (nawiasami {}).

Przykłady:

int x = 5;
int y = 10;

// definiujemy proste wyrażenie, które dodaje dwie liczby
// i przypisujemy do zmiennej `add'
// ponieważ w czasie pisania programu nie jesteśmy w stanie
// określić typu funkcji anonimowej, należy skorzystać ze
// słow kluczowego `auto'
auto add = [](int a1, int a2) { return a1 + a2; };

int z = add(x, y); // wywołuje się tak jak każdą inną funkcję.

powyższa lambda jest równoważna funkcji:

int add(int a1, int a2) {
     return a1 + a2;
}


// lista argumentów jest definiowana tak samo jak
// w klasycznych funkcjach.
auto inc = [](int &a) { a++; };
inc(x); // inkrementuje zmienną `x'
        // (parametr przekazany przez referencję)

const int M = 5;

// do wyrażenia można przekazać również inne zmienne,
// obiekty z lokalnego zasięgu. Poniżej przekazuje
// stałą `M' przez sekcję <capture>.
auto mulM = [M](int &x) { x *= M; };

mulM(y); // wartość zmiennej `y' zostanie pomnożona
         // przez `M', czyli przez 5

Lambda inc jest równoważna funkcji:

void inc(int &a) {
    a++;
}

ale dla mulM nie jesteśmy już w stanie zdefiniować równoważnej funkcji ponieważ dodatkowo przechwytujemy zmienną lokalną M, do której dostępu w przypadku zwykłej funkcji nie będziemy mieć.

Złożone przykłady wykorzystania wyrażeń lambda

enum class SwordType { Bastard, Great, Short, Katana };
struct Sword {
    SwordType type;
    float length;
};

std::vector<Sword> swords;

auto is_bastard = [](const Sword &sword) {
                        return sword.type == SwordType::Bastard;
                    };

// zliczanie ile mieczy bastardowych jest zawartych w kontenerze
auto number_of_bastard_swords = std::count_if(swords.begin(), swords.end(),
                                              is_bastard);

// czy istnieje co najmniej jedna katana?
bool contain_katana = std::any_of(swords.begin(), swords.end(),
                                  [](const auto &sword) {
                                     sword.type == SwordType::Katana;
                                  });

const float m2ft = 3.28084f; \\ 1 metr = 3.24084 stopy
auto metric_to_imperial = [m2ft](Sword sword) {
                                sword.length *= m2ft;
                                return sword;
                            };

// konwersja długości mieczy z metrycznej na imperialną.
std::transform(swords.begin(), swords.end(), swords.begin(),
               metric_to_imperial);

Algorytmy

Przeglądanie obu kolekcji można realizować na dwa sposoby:

za pomocą iteratorów,

for (auto it = imiona.begin(); it != imiona.end(), ++it)
    std::cout << *it << std::endl;

korzystając z pętli for-range.

for (const auto &ocena : Oceny)
  std::cout << "Przedmiot" << ocena.first << " - ocena: "
          << ocena.second  << std::endl;

Większość algorytmów standardowych (http://en.cppreference.com/w/cpp/algorithm) jako pierwsze argumenty przyjmuje iteratory początkowe oraz końcowe zakresu, który chcemy wykorzystać. Kolejnym argumentem jest często jakiś predykat, który w zależności od przeznaczenia algorytmu jest predykatem warunkowym (zwraca wartość prawda-fałsz), albo przekształca element kontenera lub dokonuje innych obliczeń.

Przykładowo algorytm std::any_of

template< class InputIt, class UnaryPredicate >
bool any_of(InputIt first, InputIt last, UnaryPredicate p);

przyjmuje dwa argumenty będące iteratorami oraz trzeci predykat jednoargumentowy zwracający wartość typu bool. Predykatem może być dowolna funkcja, funktor lub wyrażenie lambda spełniające wymagania.

Np.:

// sprawdzamy czy istnieje produkt tanszy niz 2 zł.
std::any_of(cennik.begin(), cennik.end(),
            [](auto &cena) { return cena.second < 2.0; })

Wykorzystanie algorytmów standardowych jest dużo bardziej ekspresyjne (wyrażające intencje programisty), aniżeli pisanie bezpośrednio pętli for. Co z kolei wiąże się ze wzrostem czytelności kodu zarówno dla nas jak i dla innych programistów.

Porównaj:

std::string text = "...";
{
    int liczba_cyfr = 0;
    for (auto &znak : text) {
        if (std::isdigit(znak) {
            liczba_cyfr++;
        }
    }
}
{
    int liczba_cyfr = std::count_if(test.begin(), test.end(), std::isdigit);
}

std::vector<Oceny> oceny;
{
    bool czy_zaliczone = true;
    for (auto &ocena : oceny) {
        if (ocena == 2) {
            czy_zaliczone = false;
            break;
        }
    }
}
{
    bool czy_zaliczone = std::none_of(oceny.begin(), oceny.end(),
                                [](Ocena &ocena) { return ocena == 2; });
}
{ // lub
    bool czy_zaliczone = !std::find(oceny.begin(), oceny.end(), 2);
}

#include <random>
#include <ctime>

// Losuje wartości zmiennoprzecinkowe z przedziału 0..1.
float randomFloat01() {
  static std::default_random_engine e{static_cast<long unsigned int>(time(0))};
  std::uniform_real_distribution<float> d{0.0f, 1.0f};
  return d(e);
}

int main() {
    const int N = 100;
    {
        std::vector<float> numbers;
        for (int i = 0; i< N; ++i){
            numbers.push_back(randomFloat01());
        }
    }
    {
        std::vector<float> numbers(N);
        std::generate(numbers.begin(), numbers.end(), randomFloat01); // Zwróć uwagę na brak nawiasów () po `randomFloat01`.
    }
}

Przykłady wykorzystania predykatów dwu-argumentowych:


bool lessThan(float x, float y) {
    return x < y;
}

bool greaterThan(float x, float y) {
    return x > y;
}

void print(const std::vector<float> &vector) {
    for (auto number : numbers) {
        std::cout << number << '\n';
    }
}

int main() {
    const int N = 100;
    std::vector<float> numbers(N);
    std::generate(numbers.begin(), numbers.end(), randomFloat01); // Zwróć uwagę na brak nawiasów () po `randomFloat01`.

    // 1
    std::sort(numbers.begin(), numbers.end()); // Sortuje w kolejności rosnącej
    print(numbers);
    // 2 - równoważne z 1
    std::sort(numbers.begin(), numbers.end(), lessThan); // Sortuje w kolejności rosnącej 
    print(numbers);

    // 3
    std::sort(numbers.begin(), numbers.end(), [](float x, float y) {// Sortuje w kolejności malejącej
        return x > y;
    });
    print(numbers);

    // 4 - równoważne z 3
    std::sort(numbers.begin(), numbers.end(), greaterThan);// Sortuje w kolejności malejącej 
    print(numbers);

    // 5 - równoważne z 3 i 4
    auto greaterThan2 = [](float x, float y) {
        return x > y;
    };
    std::sort(numbers.begin(), numbers.end(), greaterThan2);// Sortuje w kolejności malejącej
    print(numbers);

}

🛠🔥 Zadania do samodzielnego wykonania 🛠🔥

🛠 Zadanie 1

Wykorzystując tablicę std::vector z biblioteki standardowej STL zaimplementuj poniższą funkcjonalność:

wylosuj n liczb całkowitych z przedziału <-20; 20> i umieść je w tablicy,
z wykorzystaniem zwykłego operator indeksowania wyświetl cała zawartość tablicy na konsoli,
z wykorzystaniem iteratorów wyświetl cała zawartość tablicy na konsoli,
z wykorzystaniem iteratorów wyszukaj w tablicy wartości wskazanej przez użytkownika, a następnie ją usuń.

Do wygenerowania liczb losowych, możesz wykorzystać następującą funkcję:

#include <random>
#include <ctime>

int randomInt(int min, int max) {
  static std::default_random_engine e{static_cast<long unsigned int>(time(0))};
  std::uniform_int_distribution<int> d{min, max};
  return d(e);
}

🛠 Zadanie 2

Zaimplementują funkcjonalność z zadania poprzedniego z wykorzystaniem std::list ze standardowej biblioteki.

🛠 Zadanie 3

Z wykorzystaniem algorytmu standardowego std::find przeimplementuj odpowiednie fragmenty z poprzednich zadań.

🛠 Zadanie 4

Wykorzystaj algorytmy standardowe std::min_element oraz std::max_element i znajdź w kolejcach z poprzednich zadań wartości najmniejsze i największe. Wykorzystaj również funkcję std::minmax_element.

🛠 Zadanie 5

Wykorzystaj algorytm standardowy sort, Odpowiednio std::sort lub std::list::sort, do posortowania obu kolekcji:

rosnąco
malejąco
od największej wartości bezwzględnej do najmniejszej (skorzystaj z wyrażenia lambda by przekazać sposób porządkowania elementów).

🛠 Zadanie 6

Wykorzystując algorytm standardowy std::count, zlicz wystąpienia każdej liczby w kolekcji.

🛠 Zadanie 7

Małgosia stwierdziła, że pora odwiedzić swoją babcię w głębokim lesie. W związku z tym, zaczęła pakować do koszyka różne owoce i warzywa by podarować je babci. Rozpoczęła tę operację od stworzenia nowej struktury reprezentującej odpowiednie rośliny:

enum class TypRosliny { Owoc, Warzywo };

struct Roslina {
    TypRosliny typ;
    std::string nazwa;
};

Później, przygotowała sobie koszyk jako implementację zbioru:

using Koszyk = std::vector<Roslina>;

oraz utworzyła swój wymarzony kolorowy koszyk:

Koszyk koszyk;

i zaczęła do niego wkładać różne warzywa i owoce, po jednym z każdego rodzaju. Pomóż Małgosi umieścić warzywa i owoce w koszyku. Spróbuj tego dokonać na wiele sposobów.

WYJAŚNIENIE:

Za pomocą using definiujemy alias nazwy dla jakiegoś bardziej skomplikowanego typu. W przykładzie mamy using Koszyk = std::vector<Roslina>, co umieszczamy poza funkcją (tak samo jak enum, class i struct), pozwala to zdefiniować typ Koszyk, który jest wektorem roślin. Jest to tylko przykrycie łatwiejszą w użyciu nazwą, długiego i niewygodnego w użyciu typu.

🛠 Zadanie 8

Po zapakowaniu koszyka Małgosia postanowiła sprawdzić co takiego się w tym koszyku znajduje. Zaimplementuj operatory

std::ostream& operator<<(std::ostream &out, const Roslina &roslina) { }
std::ostream& operator<<(std::ostream &out, const Koszyk &koszyk) { }

by ułatwić Małgosi to sprawdzanie i zademonstruj działanie.

🛠 Zadanie 9

Marta spytała się Małgosi czy zapakowała ulubione przez babcię gruszki. Korzystając z algorytmu std::find_if zaimplementuj funkcję:

bool czy_jest_gruszka(const Koszyk &koszyk)  { }

oraz odpowiedz na pytanie Marty.

🛠 Zadanie 10

Nagle do Małgosi podchodzi jej mama, zerka do koszyka i pyta się Czy naprawdę zanosisz Babci same owoce? Małgosia zaprzeczyła i pokazała na to dowód.

Napisz funkcje, które sprawdzają czy w koszyku są: same owoce, same warzywa, co najmniej jeden owoc, co najmniej jedno warzywo, żadnego owocu, żadnego warzywa. Skorzystaj z algorytmów standardowych std::any_of, std::none_of, std::all_of (http://en.cppreference.com/w/cpp/algorithm/all_any_none_of).

Przykładowa funkcja:

bool czy_same_owoce(const Koszyk &koszyk) {
    return std::all_of(koszyk.begin(), koszyk.end(),
        [](const Roslina &roslina){ return roslina.typ == TypRosliny::Owoc; }
        );
}

🛠 Zadanie 11

Koszyk Małgosi wydaje się bardzo ciężki. Policz ile sztuk owoców oraz ile sztuk warzyw zostało do niego zapakowane. Zaimplementuj dwie funkcje zlicz_owoce, zlicz_warzywa. Skorzystaj z funkcji std::count_if (http://en.cppreference.com/w/cpp/algorithm/count).

int zlicz_rosliny_na_litere_m(const Koszyk &koszyk) {
    return std::count_if(koszyk.begin(), koszyk.end(),
            [](const Roslina &roslina) { return roslina.nazwa[0] == 'M'
                                        || roslina.nazwa[0] == 'm'; }
            );
}

🛠 Zadanie 12

Marta bardzo lubi wszystkie owoce na literę G. W związku z tym ukradkiem wyciągnęła wszystkie swoje ulubione smakołyki z koszyka oraz je zjadła. Korzystając z funkcji erase (http://en.cppreference.com/w/cpp/container/vector/erase) i remove_if, (http://en.cppreference.com/w/cpp/algorithm/remove), zaimplementuj funkcję usun_zaczynajace_sie_od usuwającą wszystkie elementy danego typu zaczynające się na podaną literę z koszyka.

🛠 Zadanie 13

Okazało się jednakże, że brakuje możliwości rozróżnienia i porządkowania poszczególnych roślin. Siostra Małgosi, Marta, podpowiedziała jej by dodatkowo zaimplementowała operator porównania.

bool operator<(const Roslina &r1, const Roslina &r2)  {  ... }

Pomóż go zaimplementować.

Implementacja tego operatora jest potrzebna przy korzystaniu z algorytmów z kolejnych zadań.

🛠 Zadanie 14

Marta stwierdziła, że również odwiedzi swoją kochaną Babcię i też zaczęła przygotowywać swój koszyk. Po zakończeniu przygotowań siostry zaczęły porównywać co takiego włożyły do koszyków. Zaczęły od sprawdzenia jakie owoce i warzywa znajdują się w obu koszykach.

Marta skorzystała w tym celu z algorytmu std::set_intersection (http://en.cppreference.com/w/cpp/algorithm/set_intersection):

Koszyk koszyk_wspolne;
std::set_intersection(koszyk.begin(), koszyk.end(),
                koszyk2.begin(), koszyk2.end(),
                std::back_inserter(koszyk_wspolne));

std::cout << koszyk_wspolne << std::endl;

Małgosia też chciała się pochwalić i pokazała czym koszyki się różnią (std::set_difference - http://en.cppreference.com/w/cpp/algorithm/set_difference). Zaimplementuj odpowiednią funkcjonalność.

Uwaga! Jak można wyczytać w dokumentacji, wymagane jest by funkcje std::set_intersection i std::set_difference operowały na posortowanym zakresie. W tym celu należy wpierw posortować uporządkować oba koszyki. Można skorzystać z funkcji std::sort (http://en.cppreference.com/w/cpp/algorithm/sort).

🛠 Zadanie 15

Mama, widząc jak długo zajmuje dzieciom zabawa w pakowanie koszyków, kazała zawartość obu koszyków umieścić w jednym wielkim.

Zaimplementuj funkcjonalność korzystając z algorytmu std::set_union (http://en.cppreference.com/w/cpp/algorithm/set_union).

🛠 Zadanie 16

Zrealizuje zadanie nr 8 (Kursy walut) z Lab02 z wykorzystaniem algorytmów STL i zdefiniowanych przez Ciebie predykatów. W wersji minimalnej należy użyć co najmniej algorytmów std::sort oraz algorytmu binary search (std::equal_range).

Autor: Przemysław Walkowiak

Lab 03 - Kontenery oraz algorytmy standardowe, <vector>, <list>, <algorithm>

Typy wyliczeniowe enum class