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
|
# `std::unordered_map` и `std::unordered_set`
## Въведение в `std::unordered_set`
`std::unordered_set` е асоциативен контейнер, който съхранява уникални обекти в произволен ред.
Обикновено е реализиран чрез хеш таблица използваща separate chaining.
При създаване на обект от тип `std::unordered_set`, могат да се зададат следните параметри:
```c++
template<
class Key,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<Key>
> class unordered_set;
```
- **Key**
Типът на обектите, които ще се съхраняват в множеството.
- **Hash**
Хешираща функция, която изчислява хеш стойности за обектите.
*По подразбиране:* Използва се `std::hash<Key>`.
- **KeyEqual**
Функция за сравнение, която проверява дали два обекта са равни.
*По подразбиране:* Използва се `std::equal_to<Key>`.
- **Allocator**
Механизъм за управление на паметта, който определя как ще се разпределя и освобождава паметта за елементите в множеството.
*По подразбиране:* Използва се стандартният алокатор `std::allocator<Key>`.
---
### Операции
- **Добавяне на елементи**: `unordered_set.insert(value)` - Θ(1) (average-case), O(N) (worst-case)
- **Премахване на елементи**: `unordered_set.erase(value)`- Θ(1) (average-case), O(N) (worst-case)
- **Търсене на елементи**: `unordered_set.find(value)` - Θ(1) (average-case), O(N) (worst-case)
- **Проверка на размера**: `unordered_set.size()` - O(1)
---
```c++
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> mySet = {3, 1, 2, 5, 4, 8, 3};
for (auto it = mySet.begin(); it != mySet.end();) {
if (*it % 2 == 0) {
it = mySet.erase(it);
} else {
++it;
}
}
for (auto& el : mySet) {
std::cout << el << ' ';
}
return 0;
}
```
---
## Въведение в `std::unordered_map`
`std::unordered_map` е асоциативен контейнер, който съхранява двойки ключ-стойност в произволен ред. Ключовете са уникални, като всеки ключ съответства на една стойност. Обикновено е реализиран чрез хеш таблица иползващ separate chaining.
---
### Шаблон за декларация
```c++
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_map;
```
- **Key**
Типът на ключовете.
- **T**
Типът на стойностите.
- **Hash**
Хешираща функция, която изчислява хеш стойности за ключовете.
*По подразбиране:* Използва се `std::hash<Key>`.
- **KeyEqual**
Функция за сравнение, която проверява дали два ключа са равни.
*По подразбиране:* Използва се `std::equal_to<Key>`.
- **Allocator**
Механизъм за управление на паметта, който определя как ще се разпределя и освобождава паметта за елементите в контейнера.
*По подразбиране:* Използва се `std::allocator<std::pair<const Key, T>>`.
---
### Операции
- **Добавяне на елементи**: `unordered_map[key] = value` - Θ(1) (average-case), O(N) (worst-case)
- **Достъп до елементи**: `unordered_map[key]` - Θ(1) (average-case), O(N) (worst-case)
- **Премахване на елементи**: `unordered_map.erase(key)` - Θ(1) (average-case), O(N) (worst-case)
- **Търсене на елементи**: `unordered_map.find(key)` - Θ(1) (average-case), O(N) (worst-case)
- **Проверка на размера**: `unordered_map.size()` - O(1)
---
```c++
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> myMap = {
{"Three", 3},
{"One", 1},
{"Two", 2}
};
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << '\n';
}
for (auto& pair : myMap) {
std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';
}
// C++ 17
for (auto& [key, value] : myMap) {
std::cout << "Key: " << key << ", Value: " << value << '\n';
}
return 0;
}
```
----
[Линк към задачите](https://leetcode.com/problem-list/asohzosr/)
В час : №3, №500, №3330
Вкъщи: №49, №859
|
