Kolekcje i algorytmy

STL - Standard Template Library

Standard Template Library Programmer's Guide

Kontenery (kolekcje) STL Containers

vector - tablica o zwiększającym się rozmiarze

forward_list lista jednokierunkowa i |list lista dwukierunkowa, sekwencja elementów o błyskawicznym czasie wstawiania i usuwania elementów

stack stos (kolejka LIFO), queue kolejka FIFO

set zbiór (uporządkowany)

map słownik (uporządkowany względem kluczy)
map<char,int> slownik

STL Algorithms

Wskaźniki na funkcję, funktory i lambdy

nazwa funkcji jest wskaznikiem do tej funkcji

obiekt funkcyjny (funktor), klasa przeciążająca operator wywołania funkcji ()

funkcje anonimowe (lambda)

Wskaźnik do funkcji

bool czy_parzysta(int n) { return (n +1) % 2; } remove_if(lista.begin(), lista.end(), czy_parzysta);

Obiekt funkcyjny

class A { public: bool operator()(int n) { return (n +1) % 2; } }; A a; remove_if(lista.begin(), lista.end(), a);

Funkcje lambda

remove_if(lista.begin(), lista.end(), [ ](int n){ return (n+1)%2; } );

Ćwiczenie: słownik wyrazów

Napisz program, który wypisze w porzadku alfabetycznym słownik wyrazów występujących w pliku tekstowym. Nazwę pliku (lub ścieżkę do pliku) podaje użytkownik na początku działania programu. Jeżeli podany plik udało się otworzyc i przeczytać to program wypisze posortowaną listę wyrazów z pliku wraz z informacją o liczbie wystąpień danego słowa w pliku.

Przykładowe wyjście programu:

Nazwa pliku: tekst.txt
ala 5
kota 2
ma 1

Do realizacji zadania wykorzystaj kontener słownik map, którego elementami jest para (pair) składająca się z wyrazu (klucz słownika) oraz liczby całkowitej określającej liczbę wystąpień wyrazu w tekście. Kolekcja map automatycznie umieszcza elementy w drzewie binarnym posortowanym względem klucza.

Zaimplementuj klasę Wyraz reprezentująca pojedynczy wyraz z tekstu, czyli łańcuchów znakowy składający się z liter 'A-Za-z'. Klasa Wyraz posiada następującą specyfikację:

wykorzystuje kolekcję vector do przechowywania liter (ewentualnie może wykorzystywać tablicę znaków, obiekt string, lub szablon Wektor z poprzednich zajęć).

przeciąża operator << wypisujący przechowywany wyraz w strumieniu wyjściowymstd::ostream

przeciąża operator >> czytający pierwszy napotkany wyraz ze strumienia wejściowego std::istream. Pamiętaj, że wyrazy w strumieniu mogą być oddzielone od siebie dowolną ilością znaków nie będących literami. Przy wczytywaniu napisu należy zignorować wszystkie początkowe znaki nie będące literami. Jeśli nastąpił błąd odczytu lub w strumieniu nie znaleziono wyrazu to wówczas tworzony jest wyraz pusty.

przeciąża operator < porównujący dwa wyrazy alfabetycznie. Przy porównywaniu małe i duże litery traktujemy równoważne, wiec wyraz „Ala”, „ala” i „ALA” będą identyczne.

konstruktor domniemany tworzy pusty wyraz

konstruktor kopiujący

funkcja składowa Dlugosc() zwraca liczbę liter w wyrazie

Przykład działania klasy Wyraz:

std::stringstream ss; // z biblioteki <sstream> ss << "!@&#&*(Ala_ma++kota" << endl; Wyraz w; while(!ss.eof()) { ss >> w; cout << w << endl; }

Wynik działania:

Ala
ma
kota

Przydatne funkcje:

z biblioteki <cctype> :

isalpha - czy znak?

tolower - zamien na małą litrę

toupper - zamień na wielką literę

z biblioteki <iostream> :

get(char z) - weź znak ze strumienia wejściowego

put(char z) - połóż znak w strumieniu wyjściowym

eof() - czy koniec pliku?

Dodatkowe ćwiczenia:

wypisz 3 najczęściej występujące wrazy. Wykorzystaj w tum celu algorytm sort oraz dodatkową funkcję porównującą dwa elementy słownika ze względu na liczbę wystąpień

wypisz najdłuższy wyraz ze słownika. Wykorzystaj w tym celu algorytm max_element oraz obiekt funkcyjny służący do porównania dwóch wyrazów ze względu na długość

wypisz w osobnych grupach wyrazy o liczbie znaków n=1, 2, 3, ... aż do najdłuższego wyrazu. Wykorzystaj w tym celu funkcję find_if oraz funkcję lambda sprawdzającą warunek, czy wyraz posiada długość n

Przykładowe działanie programu dla pliku containers.txt zawierającego treść: The STL contains sequence containers and associative containers. The containers are objects that store data.

Podaj nazwe pliku: containers.txt
and 1
are 1
associative 1
containers 3
contains 1
data 1
objects 1
sequence 1
STL 1
store 1
that 1
The 2
Trzy najdluzsze wyrazy
3 : containers
2 : The
1 : and
Najdluzszy wyraz to: associative, liczba znakow: 11
Wyrazy pogrupowane wzgledem liczby znakow:
3 : and, are, STL, The,
4 : data, that,
5 : store,
7 : objects,
8 : contains, sequence,
10 : containers,
11 : associative,

Zadanie 10: Liczba PI

Napisz program, który wyznaczy przybliżoną wartość liczby za pomocą całkowania Monte Carlo. Metoda Monte Carlo sprowadza się do wyznaczenia pola powierzchni ćwiartki koła o promieniu za pomocą procesu losowego, w którym wykonujemy losowań punktów w obszaru kwadratu o boku 1. Przybliżona wartość pola ćwiartki koła będzie równa , gdzie to liczba trafień w tarczę koła (ćwiartki) a to liczba wszystkich losowań.

Ćwiartka koła na odcinku opisana jest funkcją

Z wzoru na pole koła wynika że pole ćwiartki koła , stąd przybliżona wartość .

Program działa w następujący sposób:

użytkownik podaje wartość całkowitą n określającą liczbę strzałów do tarczy

tworzony jest pojemnik o rozmiarze n zawierający jako elementy punty na płaszczyźnie. W roli pojemnika wykorzystaj kolekcję vector, forward_list lub list. Pojemnik przechowuje punkty na płaszczyźnie określone wpółrzędnymi o wartościach rzeczywistych. Utwórz klasę reprezentującą punkt lub wykorzystaj szablon pair<T1, T2>

wypełnij pojemnik punktami o losowych współrzędnych z zakresu . Wykorzystaj w tym celu szablon funkcji generate. Trzecim argumentem tej funkcji jest generator, czyli funkcja zwracająca pojedynczy punkt o losowych współrzędnych. Zrealizuj ten generator za pomocą funkcji, obiektu funkcyjnego lub funkcji lambda. Losowanie wartości z zakresu możesz zrealizowac za pomocą funkcji rand, która zwraca losową wartość całkowitą z zakresu od 0 do RAND_MAX.

policz liczbę punktów w pojemniku spełniających warunek , czyli liczbę trafień w tarczę. W tym celu wykorzystaj algorytm count_if, który wyznacza liczbę elementów kolekcji spełniających określony warunek. Trzecim argumentem tej funkcji jest predykat, czyli funkcja, której argumentem jest element kolekcji a wynikiem jest wartość typu bool.

wypisz uzyskaną wyżej liczbę trafień k oraz przybliżoną wartość liczby równą .

Przykładowy wynik działania programu

n=100000
Liczba trafien: 78538
pi=3.14152

Rozwiązanie w postaci plików nagłówkowych *.h i źródłowych *.cpp umieść w Moodle Zadanie 10