-
Notifications
You must be signed in to change notification settings - Fork 0
/
tri_list_tresc.txt
153 lines (113 loc) · 6.49 KB
/
tri_list_tresc.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
= Zadanie 7, programowanie funkcyjne w C++ =
Biblioteka STL oferuje wiele standardowych kontenerów. Cechą wspólną tych
kontenerów jest to, że pozwalają one na przechowywanie wartości tylko jednego
typu. Inną cechą jest gorliwe wyliczanie wszystkich operacji wykonywanych na
tych kontenerach. W tym zadaniu przyjrzymy się, jak mógłby wyglądać kontener nie
mający takich ograniczeń. Jednocześnie wykorzystamy także ostatnią z głównych
nowości w C++20: bibliotekę ranges.
= Wartościowanie gorliwe a leniwe =
Gdy wykonywany jest kod danego programu, kolejność wykonywania operacji w nim
zawartych może być zdefiniowana na różne sposoby. Dwa najpopularniejsze z nich
to wartościowanie gorliwe oraz leniwe.
Wartościowanie gorliwe jest podejściem stosowanym w większości konstrukcji wielu
języków programowania, w tym także w C++. Polega ono na wykonywaniu operacji
dokładnie w takiej kolejności, w jakiej zostały one wyspecyfikowane przez
programistę, nawet jeśli ich wynik nie jest potrzebny.
Przeciwieństwem jest wartościowanie leniwe – instrukcje programu są wykonywane
dopiero wtedy i tylko wtedy, gdy ich wartość jest już potrzebna. W języku C++
przykładem konstrukcji z takim wartościowaniem są operatory logiczne && oraz ||.
Wykonują one swoją prawą gałąź tylko wtedy, gdy na podstawie wyniku lewej gałęzi
nie da się wyznaczyć wyniku całej operacji. Innym przykładem wartościowania
leniwego w C++ jest operator warunkowy ?:.
W gorliwym języku można jednak symulować wartościowanie leniwe poprzez
odpowiednie struktury danych, które często wykorzystują konstrukcje funkcyjne.
To właśnie będziemy robić w tym zadaniu.
W C++20 biblioteka std::ranges dodaje do języka więcej leniwości w postaci
widoków. Pozwalają one na składanie ze sobą wielu modyfikacji zakresów
wykonywanych dopiero w momencie dostępu do elementów widoku. Więcej informacji
na ten temat można znaleźć w czytankach.
= Typy wariantowe =
Wiele języków programowania pozwala na typy, których wartościami mogą być
wartości wielu różnych, określonych, typów. Takie typy po angielsku nazywa się
sum types, ze względu na to, że zbiór wartości typu wariantowego jest sumą
zbiorów wartości poszczególnych typów, z których jest on zbudowany.
Typy wariantowe powinny pozwalać na dwie podstawowe operacje:
- włożenie:
konstrukcja wartości typu wariantowego z wartości typu podrzędnego,
- dopasowanie wzorca:
wykonanie różnych akcji w zależności od faktycznego typu
podrzędnego danej wartości.
W C++ (a także i w C) dostępny jest podstawowy typ wariantowy znany pod nazwą
union. Ma on jednak pewną poważną wadę: nie udostępnia żadnych mechanizmów
pozwalających na stwierdzenie, który z typów podrzędnych jest aktywny.
Wymusza to na programiście nie tylko każdorazową implementację operacji
dopasowania wzorca, ale też dyscypliny, by uniknąć korzystania z wartości
innego typu niż aktywny (w celu uniknięcia niezdefiniowanego zachowania).
W C++17 z pomocą przychodzi std::variant, będący już silnie otypowanym typem
wariantowym. Niestety, mimo trwających prac nad standaryzacją, w C++ wciąż nie
ma mechanizmu dopasowania wzorca na poziomie języka, więc ta operacja musi wciąż
się odbywać przy użyciu szablonów. Na nasze szczęście jednak C++20 przynosi
zmiany w funkcjach lambda znacznie ułatwiające korzystanie z tej operacji, co
okaże się przydatne przy implementacji tego zadania.
= Treść zadania =
Uwaga: Koncept modifier, który jest wymieniony w treści zadania, oraz koncept
is_tri_list_correct, który powinna spełniać implementacja, znajdują się w pliku
tri_list_concepts.h.
Celem zadania jest zaimplementowanie szablonu klasy tri_list:
template <typename T1, typename T2, typename T3>
class tri_list;
Powinna ona udostępniać następującą funkcjonalność:
- domyślny konstruktor tworzący pustą listę;
- konstruktor przyjmujący obiekt typu std::initializer_list;
- szablon metody
template <typename T> void push_back<T>(const T& t),
która dodaje na koniec listy element t;
- szablon metody
template <typename T, modifier<T> F> void modify_only<T>(F m = F{}),
która leniwie modyfikuje wszystkie elementy typu T za pomocą modyfikatora m,
włącznie z tymi, które zostaną dodane do kontenera później;
- szablon metody
template <typename T> void reset(),
która niweluje działanie wszystkich dotychczasowych modyfikacji elementów
typu T;
- szablon metody
template <typename T> auto range_over(),
która udostępnia widok na te elementy listy, które są typu T;
- metody begin() oraz end() zaimplementowane tak, by klasa spełniała
koncept std::viewable_range.
Oprócz tego należy zdefiniować poniższe dwa symbole:
- identity:
wywołane z wartością dowolnego typu powinno obliczać się do tej samej
wartości, powinno spełniać koncept modifier;
- compose:
wywołane z dwoma argumentami spełniającymi modifier<T> dla pewnego T powinno
potraktować obie wartości jak funkcje i zwrócić funkcję będącą ich złożeniem
(w tej samej kolejności, co matematyczny operator ∘), spełniającą modifier<T>
dla tego samego T. W szczególności nie jest wymagane, by dało się wywołać
compose z argumentami, które takiego warunku nie spełniają.
Ponadto:
- złożoność czasowa wszystkich metod klasy tri_list powinna być O(1);
- próba skompilowania któregokolwiek z szablonów metod z argumentem niebędącym
jednym z (lub będącym więcej niż jednym z) T1, T2, T3 powinna zakończyć się
błędem.
= Przykład użycia =
Przykład wykorzystania szablonu tri_list znajduje się w pliku
tri_list_example.cc. Wykonanie tego przykładu powinno spowodować
wypisanie na standardowe wyjście:
0.858407
This, is, a, string,
3
12
= Ustalenia techniczne =
Ze względu na relatywnie nowe elementy języka wykorzystywane w zadaniu,
należy używać kompilatora GCC w wersji 11.2 z następującymi opcjami:
-std=c++20 -Wall -Wextra -O2
Środowisko students (tak samo jak w zadaniu 6 z modułami):
- kompilator: /opt/gcc-11.2/bin/g++-11.2
- przy uruchamianiu należy ustawić: export LD_LIBRARY_PATH=/opt/gcc-11.2/lib64
Rozwiązanie należy umieścić w pliku tri_list.h w repozytorium w katalogu
grupaN/zadanie7/ab123456
gdzie N jest numerem grupy, a ab123456 jest identyfikatorem osoby umieszczającej
to rozwiązanie. Katalog z rozwiązaniem nie powinien zawierać innych plików. Nie
wolno umieszczać w repozytorium plików dużych, binarnych, tymczasowych (np. *.o)
ani innych zbędnych.