🗊 Презентация Алгоритмы и контейнеры данных (C++)

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Алгоритмы и контейнеры данных (C++), слайд №1 Алгоритмы и контейнеры данных (C++), слайд №2 Алгоритмы и контейнеры данных (C++), слайд №3 Алгоритмы и контейнеры данных (C++), слайд №4 Алгоритмы и контейнеры данных (C++), слайд №5 Алгоритмы и контейнеры данных (C++), слайд №6 Алгоритмы и контейнеры данных (C++), слайд №7 Алгоритмы и контейнеры данных (C++), слайд №8 Алгоритмы и контейнеры данных (C++), слайд №9 Алгоритмы и контейнеры данных (C++), слайд №10 Алгоритмы и контейнеры данных (C++), слайд №11 Алгоритмы и контейнеры данных (C++), слайд №12 Алгоритмы и контейнеры данных (C++), слайд №13 Алгоритмы и контейнеры данных (C++), слайд №14 Алгоритмы и контейнеры данных (C++), слайд №15 Алгоритмы и контейнеры данных (C++), слайд №16 Алгоритмы и контейнеры данных (C++), слайд №17 Алгоритмы и контейнеры данных (C++), слайд №18 Алгоритмы и контейнеры данных (C++), слайд №19 Алгоритмы и контейнеры данных (C++), слайд №20 Алгоритмы и контейнеры данных (C++), слайд №21 Алгоритмы и контейнеры данных (C++), слайд №22 Алгоритмы и контейнеры данных (C++), слайд №23 Алгоритмы и контейнеры данных (C++), слайд №24 Алгоритмы и контейнеры данных (C++), слайд №25 Алгоритмы и контейнеры данных (C++), слайд №26 Алгоритмы и контейнеры данных (C++), слайд №27 Алгоритмы и контейнеры данных (C++), слайд №28 Алгоритмы и контейнеры данных (C++), слайд №29 Алгоритмы и контейнеры данных (C++), слайд №30 Алгоритмы и контейнеры данных (C++), слайд №31 Алгоритмы и контейнеры данных (C++), слайд №32 Алгоритмы и контейнеры данных (C++), слайд №33 Алгоритмы и контейнеры данных (C++), слайд №34 Алгоритмы и контейнеры данных (C++), слайд №35 Алгоритмы и контейнеры данных (C++), слайд №36 Алгоритмы и контейнеры данных (C++), слайд №37 Алгоритмы и контейнеры данных (C++), слайд №38 Алгоритмы и контейнеры данных (C++), слайд №39 Алгоритмы и контейнеры данных (C++), слайд №40 Алгоритмы и контейнеры данных (C++), слайд №41 Алгоритмы и контейнеры данных (C++), слайд №42 Алгоритмы и контейнеры данных (C++), слайд №43 Алгоритмы и контейнеры данных (C++), слайд №44 Алгоритмы и контейнеры данных (C++), слайд №45 Алгоритмы и контейнеры данных (C++), слайд №46 Алгоритмы и контейнеры данных (C++), слайд №47 Алгоритмы и контейнеры данных (C++), слайд №48 Алгоритмы и контейнеры данных (C++), слайд №49 Алгоритмы и контейнеры данных (C++), слайд №50 Алгоритмы и контейнеры данных (C++), слайд №51 Алгоритмы и контейнеры данных (C++), слайд №52 Алгоритмы и контейнеры данных (C++), слайд №53 Алгоритмы и контейнеры данных (C++), слайд №54 Алгоритмы и контейнеры данных (C++), слайд №55 Алгоритмы и контейнеры данных (C++), слайд №56 Алгоритмы и контейнеры данных (C++), слайд №57 Алгоритмы и контейнеры данных (C++), слайд №58 Алгоритмы и контейнеры данных (C++), слайд №59 Алгоритмы и контейнеры данных (C++), слайд №60 Алгоритмы и контейнеры данных (C++), слайд №61 Алгоритмы и контейнеры данных (C++), слайд №62 Алгоритмы и контейнеры данных (C++), слайд №63 Алгоритмы и контейнеры данных (C++), слайд №64 Алгоритмы и контейнеры данных (C++), слайд №65 Алгоритмы и контейнеры данных (C++), слайд №66 Алгоритмы и контейнеры данных (C++), слайд №67 Алгоритмы и контейнеры данных (C++), слайд №68 Алгоритмы и контейнеры данных (C++), слайд №69 Алгоритмы и контейнеры данных (C++), слайд №70 Алгоритмы и контейнеры данных (C++), слайд №71 Алгоритмы и контейнеры данных (C++), слайд №72 Алгоритмы и контейнеры данных (C++), слайд №73 Алгоритмы и контейнеры данных (C++), слайд №74 Алгоритмы и контейнеры данных (C++), слайд №75 Алгоритмы и контейнеры данных (C++), слайд №76 Алгоритмы и контейнеры данных (C++), слайд №77 Алгоритмы и контейнеры данных (C++), слайд №78 Алгоритмы и контейнеры данных (C++), слайд №79 Алгоритмы и контейнеры данных (C++), слайд №80 Алгоритмы и контейнеры данных (C++), слайд №81 Алгоритмы и контейнеры данных (C++), слайд №82 Алгоритмы и контейнеры данных (C++), слайд №83 Алгоритмы и контейнеры данных (C++), слайд №84 Алгоритмы и контейнеры данных (C++), слайд №85 Алгоритмы и контейнеры данных (C++), слайд №86 Алгоритмы и контейнеры данных (C++), слайд №87 Алгоритмы и контейнеры данных (C++), слайд №88 Алгоритмы и контейнеры данных (C++), слайд №89 Алгоритмы и контейнеры данных (C++), слайд №90 Алгоритмы и контейнеры данных (C++), слайд №91 Алгоритмы и контейнеры данных (C++), слайд №92 Алгоритмы и контейнеры данных (C++), слайд №93 Алгоритмы и контейнеры данных (C++), слайд №94 Алгоритмы и контейнеры данных (C++), слайд №95 Алгоритмы и контейнеры данных (C++), слайд №96 Алгоритмы и контейнеры данных (C++), слайд №97 Алгоритмы и контейнеры данных (C++), слайд №98 Алгоритмы и контейнеры данных (C++), слайд №99 Алгоритмы и контейнеры данных (C++), слайд №100 Алгоритмы и контейнеры данных (C++), слайд №101 Алгоритмы и контейнеры данных (C++), слайд №102 Алгоритмы и контейнеры данных (C++), слайд №103 Алгоритмы и контейнеры данных (C++), слайд №104 Алгоритмы и контейнеры данных (C++), слайд №105 Алгоритмы и контейнеры данных (C++), слайд №106 Алгоритмы и контейнеры данных (C++), слайд №107 Алгоритмы и контейнеры данных (C++), слайд №108 Алгоритмы и контейнеры данных (C++), слайд №109 Алгоритмы и контейнеры данных (C++), слайд №110 Алгоритмы и контейнеры данных (C++), слайд №111 Алгоритмы и контейнеры данных (C++), слайд №112 Алгоритмы и контейнеры данных (C++), слайд №113 Алгоритмы и контейнеры данных (C++), слайд №114 Алгоритмы и контейнеры данных (C++), слайд №115 Алгоритмы и контейнеры данных (C++), слайд №116 Алгоритмы и контейнеры данных (C++), слайд №117 Алгоритмы и контейнеры данных (C++), слайд №118 Алгоритмы и контейнеры данных (C++), слайд №119 Алгоритмы и контейнеры данных (C++), слайд №120 Алгоритмы и контейнеры данных (C++), слайд №121 Алгоритмы и контейнеры данных (C++), слайд №122 Алгоритмы и контейнеры данных (C++), слайд №123 Алгоритмы и контейнеры данных (C++), слайд №124 Алгоритмы и контейнеры данных (C++), слайд №125 Алгоритмы и контейнеры данных (C++), слайд №126 Алгоритмы и контейнеры данных (C++), слайд №127 Алгоритмы и контейнеры данных (C++), слайд №128 Алгоритмы и контейнеры данных (C++), слайд №129 Алгоритмы и контейнеры данных (C++), слайд №130 Алгоритмы и контейнеры данных (C++), слайд №131 Алгоритмы и контейнеры данных (C++), слайд №132 Алгоритмы и контейнеры данных (C++), слайд №133 Алгоритмы и контейнеры данных (C++), слайд №134 Алгоритмы и контейнеры данных (C++), слайд №135 Алгоритмы и контейнеры данных (C++), слайд №136 Алгоритмы и контейнеры данных (C++), слайд №137 Алгоритмы и контейнеры данных (C++), слайд №138 Алгоритмы и контейнеры данных (C++), слайд №139 Алгоритмы и контейнеры данных (C++), слайд №140 Алгоритмы и контейнеры данных (C++), слайд №141 Алгоритмы и контейнеры данных (C++), слайд №142 Алгоритмы и контейнеры данных (C++), слайд №143 Алгоритмы и контейнеры данных (C++), слайд №144 Алгоритмы и контейнеры данных (C++), слайд №145 Алгоритмы и контейнеры данных (C++), слайд №146 Алгоритмы и контейнеры данных (C++), слайд №147 Алгоритмы и контейнеры данных (C++), слайд №148 Алгоритмы и контейнеры данных (C++), слайд №149 Алгоритмы и контейнеры данных (C++), слайд №150 Алгоритмы и контейнеры данных (C++), слайд №151 Алгоритмы и контейнеры данных (C++), слайд №152 Алгоритмы и контейнеры данных (C++), слайд №153 Алгоритмы и контейнеры данных (C++), слайд №154 Алгоритмы и контейнеры данных (C++), слайд №155 Алгоритмы и контейнеры данных (C++), слайд №156 Алгоритмы и контейнеры данных (C++), слайд №157 Алгоритмы и контейнеры данных (C++), слайд №158 Алгоритмы и контейнеры данных (C++), слайд №159 Алгоритмы и контейнеры данных (C++), слайд №160 Алгоритмы и контейнеры данных (C++), слайд №161 Алгоритмы и контейнеры данных (C++), слайд №162 Алгоритмы и контейнеры данных (C++), слайд №163 Алгоритмы и контейнеры данных (C++), слайд №164 Алгоритмы и контейнеры данных (C++), слайд №165 Алгоритмы и контейнеры данных (C++), слайд №166 Алгоритмы и контейнеры данных (C++), слайд №167 Алгоритмы и контейнеры данных (C++), слайд №168 Алгоритмы и контейнеры данных (C++), слайд №169 Алгоритмы и контейнеры данных (C++), слайд №170 Алгоритмы и контейнеры данных (C++), слайд №171 Алгоритмы и контейнеры данных (C++), слайд №172 Алгоритмы и контейнеры данных (C++), слайд №173 Алгоритмы и контейнеры данных (C++), слайд №174 Алгоритмы и контейнеры данных (C++), слайд №175 Алгоритмы и контейнеры данных (C++), слайд №176 Алгоритмы и контейнеры данных (C++), слайд №177 Алгоритмы и контейнеры данных (C++), слайд №178 Алгоритмы и контейнеры данных (C++), слайд №179 Алгоритмы и контейнеры данных (C++), слайд №180 Алгоритмы и контейнеры данных (C++), слайд №181 Алгоритмы и контейнеры данных (C++), слайд №182 Алгоритмы и контейнеры данных (C++), слайд №183 Алгоритмы и контейнеры данных (C++), слайд №184 Алгоритмы и контейнеры данных (C++), слайд №185 Алгоритмы и контейнеры данных (C++), слайд №186 Алгоритмы и контейнеры данных (C++), слайд №187 Алгоритмы и контейнеры данных (C++), слайд №188 Алгоритмы и контейнеры данных (C++), слайд №189 Алгоритмы и контейнеры данных (C++), слайд №190 Алгоритмы и контейнеры данных (C++), слайд №191 Алгоритмы и контейнеры данных (C++), слайд №192 Алгоритмы и контейнеры данных (C++), слайд №193 Алгоритмы и контейнеры данных (C++), слайд №194 Алгоритмы и контейнеры данных (C++), слайд №195 Алгоритмы и контейнеры данных (C++), слайд №196 Алгоритмы и контейнеры данных (C++), слайд №197 Алгоритмы и контейнеры данных (C++), слайд №198 Алгоритмы и контейнеры данных (C++), слайд №199 Алгоритмы и контейнеры данных (C++), слайд №200 Алгоритмы и контейнеры данных (C++), слайд №201 Алгоритмы и контейнеры данных (C++), слайд №202 Алгоритмы и контейнеры данных (C++), слайд №203 Алгоритмы и контейнеры данных (C++), слайд №204 Алгоритмы и контейнеры данных (C++), слайд №205 Алгоритмы и контейнеры данных (C++), слайд №206 Алгоритмы и контейнеры данных (C++), слайд №207 Алгоритмы и контейнеры данных (C++), слайд №208 Алгоритмы и контейнеры данных (C++), слайд №209 Алгоритмы и контейнеры данных (C++), слайд №210 Алгоритмы и контейнеры данных (C++), слайд №211 Алгоритмы и контейнеры данных (C++), слайд №212 Алгоритмы и контейнеры данных (C++), слайд №213 Алгоритмы и контейнеры данных (C++), слайд №214 Алгоритмы и контейнеры данных (C++), слайд №215 Алгоритмы и контейнеры данных (C++), слайд №216 Алгоритмы и контейнеры данных (C++), слайд №217 Алгоритмы и контейнеры данных (C++), слайд №218 Алгоритмы и контейнеры данных (C++), слайд №219 Алгоритмы и контейнеры данных (C++), слайд №220 Алгоритмы и контейнеры данных (C++), слайд №221 Алгоритмы и контейнеры данных (C++), слайд №222 Алгоритмы и контейнеры данных (C++), слайд №223 Алгоритмы и контейнеры данных (C++), слайд №224 Алгоритмы и контейнеры данных (C++), слайд №225 Алгоритмы и контейнеры данных (C++), слайд №226 Алгоритмы и контейнеры данных (C++), слайд №227 Алгоритмы и контейнеры данных (C++), слайд №228 Алгоритмы и контейнеры данных (C++), слайд №229 Алгоритмы и контейнеры данных (C++), слайд №230 Алгоритмы и контейнеры данных (C++), слайд №231 Алгоритмы и контейнеры данных (C++), слайд №232 Алгоритмы и контейнеры данных (C++), слайд №233 Алгоритмы и контейнеры данных (C++), слайд №234 Алгоритмы и контейнеры данных (C++), слайд №235 Алгоритмы и контейнеры данных (C++), слайд №236 Алгоритмы и контейнеры данных (C++), слайд №237 Алгоритмы и контейнеры данных (C++), слайд №238 Алгоритмы и контейнеры данных (C++), слайд №239 Алгоритмы и контейнеры данных (C++), слайд №240 Алгоритмы и контейнеры данных (C++), слайд №241 Алгоритмы и контейнеры данных (C++), слайд №242 Алгоритмы и контейнеры данных (C++), слайд №243 Алгоритмы и контейнеры данных (C++), слайд №244 Алгоритмы и контейнеры данных (C++), слайд №245 Алгоритмы и контейнеры данных (C++), слайд №246 Алгоритмы и контейнеры данных (C++), слайд №247 Алгоритмы и контейнеры данных (C++), слайд №248 Алгоритмы и контейнеры данных (C++), слайд №249 Алгоритмы и контейнеры данных (C++), слайд №250 Алгоритмы и контейнеры данных (C++), слайд №251 Алгоритмы и контейнеры данных (C++), слайд №252 Алгоритмы и контейнеры данных (C++), слайд №253 Алгоритмы и контейнеры данных (C++), слайд №254 Алгоритмы и контейнеры данных (C++), слайд №255 Алгоритмы и контейнеры данных (C++), слайд №256 Алгоритмы и контейнеры данных (C++), слайд №257 Алгоритмы и контейнеры данных (C++), слайд №258 Алгоритмы и контейнеры данных (C++), слайд №259 Алгоритмы и контейнеры данных (C++), слайд №260 Алгоритмы и контейнеры данных (C++), слайд №261 Алгоритмы и контейнеры данных (C++), слайд №262 Алгоритмы и контейнеры данных (C++), слайд №263 Алгоритмы и контейнеры данных (C++), слайд №264 Алгоритмы и контейнеры данных (C++), слайд №265 Алгоритмы и контейнеры данных (C++), слайд №266 Алгоритмы и контейнеры данных (C++), слайд №267 Алгоритмы и контейнеры данных (C++), слайд №268 Алгоритмы и контейнеры данных (C++), слайд №269 Алгоритмы и контейнеры данных (C++), слайд №270 Алгоритмы и контейнеры данных (C++), слайд №271 Алгоритмы и контейнеры данных (C++), слайд №272 Алгоритмы и контейнеры данных (C++), слайд №273 Алгоритмы и контейнеры данных (C++), слайд №274 Алгоритмы и контейнеры данных (C++), слайд №275 Алгоритмы и контейнеры данных (C++), слайд №276 Алгоритмы и контейнеры данных (C++), слайд №277 Алгоритмы и контейнеры данных (C++), слайд №278 Алгоритмы и контейнеры данных (C++), слайд №279 Алгоритмы и контейнеры данных (C++), слайд №280 Алгоритмы и контейнеры данных (C++), слайд №281 Алгоритмы и контейнеры данных (C++), слайд №282 Алгоритмы и контейнеры данных (C++), слайд №283 Алгоритмы и контейнеры данных (C++), слайд №284 Алгоритмы и контейнеры данных (C++), слайд №285 Алгоритмы и контейнеры данных (C++), слайд №286 Алгоритмы и контейнеры данных (C++), слайд №287 Алгоритмы и контейнеры данных (C++), слайд №288 Алгоритмы и контейнеры данных (C++), слайд №289 Алгоритмы и контейнеры данных (C++), слайд №290 Алгоритмы и контейнеры данных (C++), слайд №291 Алгоритмы и контейнеры данных (C++), слайд №292 Алгоритмы и контейнеры данных (C++), слайд №293 Алгоритмы и контейнеры данных (C++), слайд №294 Алгоритмы и контейнеры данных (C++), слайд №295 Алгоритмы и контейнеры данных (C++), слайд №296 Алгоритмы и контейнеры данных (C++), слайд №297 Алгоритмы и контейнеры данных (C++), слайд №298 Алгоритмы и контейнеры данных (C++), слайд №299 Алгоритмы и контейнеры данных (C++), слайд №300 Алгоритмы и контейнеры данных (C++), слайд №301 Алгоритмы и контейнеры данных (C++), слайд №302 Алгоритмы и контейнеры данных (C++), слайд №303 Алгоритмы и контейнеры данных (C++), слайд №304 Алгоритмы и контейнеры данных (C++), слайд №305 Алгоритмы и контейнеры данных (C++), слайд №306 Алгоритмы и контейнеры данных (C++), слайд №307 Алгоритмы и контейнеры данных (C++), слайд №308 Алгоритмы и контейнеры данных (C++), слайд №309 Алгоритмы и контейнеры данных (C++), слайд №310 Алгоритмы и контейнеры данных (C++), слайд №311 Алгоритмы и контейнеры данных (C++), слайд №312 Алгоритмы и контейнеры данных (C++), слайд №313 Алгоритмы и контейнеры данных (C++), слайд №314 Алгоритмы и контейнеры данных (C++), слайд №315 Алгоритмы и контейнеры данных (C++), слайд №316 Алгоритмы и контейнеры данных (C++), слайд №317 Алгоритмы и контейнеры данных (C++), слайд №318 Алгоритмы и контейнеры данных (C++), слайд №319 Алгоритмы и контейнеры данных (C++), слайд №320 Алгоритмы и контейнеры данных (C++), слайд №321 Алгоритмы и контейнеры данных (C++), слайд №322 Алгоритмы и контейнеры данных (C++), слайд №323 Алгоритмы и контейнеры данных (C++), слайд №324 Алгоритмы и контейнеры данных (C++), слайд №325 Алгоритмы и контейнеры данных (C++), слайд №326 Алгоритмы и контейнеры данных (C++), слайд №327 Алгоритмы и контейнеры данных (C++), слайд №328 Алгоритмы и контейнеры данных (C++), слайд №329 Алгоритмы и контейнеры данных (C++), слайд №330 Алгоритмы и контейнеры данных (C++), слайд №331 Алгоритмы и контейнеры данных (C++), слайд №332 Алгоритмы и контейнеры данных (C++), слайд №333 Алгоритмы и контейнеры данных (C++), слайд №334 Алгоритмы и контейнеры данных (C++), слайд №335 Алгоритмы и контейнеры данных (C++), слайд №336 Алгоритмы и контейнеры данных (C++), слайд №337 Алгоритмы и контейнеры данных (C++), слайд №338 Алгоритмы и контейнеры данных (C++), слайд №339 Алгоритмы и контейнеры данных (C++), слайд №340 Алгоритмы и контейнеры данных (C++), слайд №341 Алгоритмы и контейнеры данных (C++), слайд №342 Алгоритмы и контейнеры данных (C++), слайд №343 Алгоритмы и контейнеры данных (C++), слайд №344 Алгоритмы и контейнеры данных (C++), слайд №345 Алгоритмы и контейнеры данных (C++), слайд №346 Алгоритмы и контейнеры данных (C++), слайд №347 Алгоритмы и контейнеры данных (C++), слайд №348 Алгоритмы и контейнеры данных (C++), слайд №349 Алгоритмы и контейнеры данных (C++), слайд №350 Алгоритмы и контейнеры данных (C++), слайд №351 Алгоритмы и контейнеры данных (C++), слайд №352 Алгоритмы и контейнеры данных (C++), слайд №353 Алгоритмы и контейнеры данных (C++), слайд №354 Алгоритмы и контейнеры данных (C++), слайд №355 Алгоритмы и контейнеры данных (C++), слайд №356 Алгоритмы и контейнеры данных (C++), слайд №357 Алгоритмы и контейнеры данных (C++), слайд №358 Алгоритмы и контейнеры данных (C++), слайд №359 Алгоритмы и контейнеры данных (C++), слайд №360 Алгоритмы и контейнеры данных (C++), слайд №361 Алгоритмы и контейнеры данных (C++), слайд №362 Алгоритмы и контейнеры данных (C++), слайд №363 Алгоритмы и контейнеры данных (C++), слайд №364 Алгоритмы и контейнеры данных (C++), слайд №365 Алгоритмы и контейнеры данных (C++), слайд №366 Алгоритмы и контейнеры данных (C++), слайд №367 Алгоритмы и контейнеры данных (C++), слайд №368 Алгоритмы и контейнеры данных (C++), слайд №369 Алгоритмы и контейнеры данных (C++), слайд №370 Алгоритмы и контейнеры данных (C++), слайд №371 Алгоритмы и контейнеры данных (C++), слайд №372 Алгоритмы и контейнеры данных (C++), слайд №373 Алгоритмы и контейнеры данных (C++), слайд №374 Алгоритмы и контейнеры данных (C++), слайд №375 Алгоритмы и контейнеры данных (C++), слайд №376 Алгоритмы и контейнеры данных (C++), слайд №377 Алгоритмы и контейнеры данных (C++), слайд №378 Алгоритмы и контейнеры данных (C++), слайд №379 Алгоритмы и контейнеры данных (C++), слайд №380 Алгоритмы и контейнеры данных (C++), слайд №381 Алгоритмы и контейнеры данных (C++), слайд №382 Алгоритмы и контейнеры данных (C++), слайд №383 Алгоритмы и контейнеры данных (C++), слайд №384 Алгоритмы и контейнеры данных (C++), слайд №385 Алгоритмы и контейнеры данных (C++), слайд №386 Алгоритмы и контейнеры данных (C++), слайд №387 Алгоритмы и контейнеры данных (C++), слайд №388 Алгоритмы и контейнеры данных (C++), слайд №389 Алгоритмы и контейнеры данных (C++), слайд №390 Алгоритмы и контейнеры данных (C++), слайд №391 Алгоритмы и контейнеры данных (C++), слайд №392 Алгоритмы и контейнеры данных (C++), слайд №393 Алгоритмы и контейнеры данных (C++), слайд №394 Алгоритмы и контейнеры данных (C++), слайд №395 Алгоритмы и контейнеры данных (C++), слайд №396 Алгоритмы и контейнеры данных (C++), слайд №397 Алгоритмы и контейнеры данных (C++), слайд №398 Алгоритмы и контейнеры данных (C++), слайд №399 Алгоритмы и контейнеры данных (C++), слайд №400 Алгоритмы и контейнеры данных (C++), слайд №401 Алгоритмы и контейнеры данных (C++), слайд №402 Алгоритмы и контейнеры данных (C++), слайд №403 Алгоритмы и контейнеры данных (C++), слайд №404 Алгоритмы и контейнеры данных (C++), слайд №405 Алгоритмы и контейнеры данных (C++), слайд №406 Алгоритмы и контейнеры данных (C++), слайд №407 Алгоритмы и контейнеры данных (C++), слайд №408 Алгоритмы и контейнеры данных (C++), слайд №409 Алгоритмы и контейнеры данных (C++), слайд №410 Алгоритмы и контейнеры данных (C++), слайд №411 Алгоритмы и контейнеры данных (C++), слайд №412 Алгоритмы и контейнеры данных (C++), слайд №413 Алгоритмы и контейнеры данных (C++), слайд №414 Алгоритмы и контейнеры данных (C++), слайд №415 Алгоритмы и контейнеры данных (C++), слайд №416 Алгоритмы и контейнеры данных (C++), слайд №417 Алгоритмы и контейнеры данных (C++), слайд №418 Алгоритмы и контейнеры данных (C++), слайд №419 Алгоритмы и контейнеры данных (C++), слайд №420 Алгоритмы и контейнеры данных (C++), слайд №421 Алгоритмы и контейнеры данных (C++), слайд №422 Алгоритмы и контейнеры данных (C++), слайд №423 Алгоритмы и контейнеры данных (C++), слайд №424 Алгоритмы и контейнеры данных (C++), слайд №425 Алгоритмы и контейнеры данных (C++), слайд №426 Алгоритмы и контейнеры данных (C++), слайд №427 Алгоритмы и контейнеры данных (C++), слайд №428 Алгоритмы и контейнеры данных (C++), слайд №429 Алгоритмы и контейнеры данных (C++), слайд №430 Алгоритмы и контейнеры данных (C++), слайд №431 Алгоритмы и контейнеры данных (C++), слайд №432 Алгоритмы и контейнеры данных (C++), слайд №433 Алгоритмы и контейнеры данных (C++), слайд №434 Алгоритмы и контейнеры данных (C++), слайд №435 Алгоритмы и контейнеры данных (C++), слайд №436 Алгоритмы и контейнеры данных (C++), слайд №437 Алгоритмы и контейнеры данных (C++), слайд №438 Алгоритмы и контейнеры данных (C++), слайд №439
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритмы и контейнеры данных (C++). Доклад-сообщение содержит 439 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Алгоритмы и контейнеры данных (C++), слайд №1
Описание слайда:

Слайд 2


Введение В рамках курса будут изучаться Алгоритмы сортировки и поиска Контейнеры данных Необходимо освоить Реализацию алгоритмов и контейнеров...
Описание слайда:
Введение В рамках курса будут изучаться Алгоритмы сортировки и поиска Контейнеры данных Необходимо освоить Реализацию алгоритмов и контейнеров Рациональный выбор и использование стандартных алгоритмов и контейнеров

Слайд 3


Введение Курс разрабатывался, исходя из использования языка программирования C++ Допускается использование других объектно-ориентированных языков для...
Описание слайда:
Введение Курс разрабатывался, исходя из использования языка программирования C++ Допускается использование других объектно-ориентированных языков для выполнения заданий

Слайд 4


Введение Стандартная схема сдачи курса два задания на разработку алгоритмов (8+15) одно задание на разработку контейнера данных (15) одно задание на...
Описание слайда:
Введение Стандартная схема сдачи курса два задания на разработку алгоритмов (8+15) одно задание на разработку контейнера данных (15) одно задание на разработку программного обеспечения с использованием стандартных алгоритмов и контейнеров данных (20-32) два теста (5+5) Личностные качества (5+5) Экзамен (20)

Слайд 5


Введение Альтернативная схема сдачи курса Есть специальное задание для одного-двоих разработчиков. Желательно знание языка C#.
Описание слайда:
Введение Альтернативная схема сдачи курса Есть специальное задание для одного-двоих разработчиков. Желательно знание языка C#.

Слайд 6


Тема 1.1. Вычислительная сложность алгоритмов. Алгоритмы сортировки и поиска
Описание слайда:
Тема 1.1. Вычислительная сложность алгоритмов. Алгоритмы сортировки и поиска

Слайд 7


Лекция 1. Понятие вычислительной сложности алгоритма Время выполнения программой той или иной вычислительно сложной задачи является ключевой...
Описание слайда:
Лекция 1. Понятие вычислительной сложности алгоритма Время выполнения программой той или иной вычислительно сложной задачи является ключевой характеристикой программы. Следует выбирать алгоритм так, чтобы минимизировать время работы программы. Точно оценить время работы программы при разработке невозможно (неизвестны исходные данные, характеристики компьютера и многое другое)

Слайд 8


Время работы программы Время работы программы зависит от Алгоритма Числа обрабатываемых элементов Конкретного набора элементов Характеристик...
Описание слайда:
Время работы программы Время работы программы зависит от Алгоритма Числа обрабатываемых элементов Конкретного набора элементов Характеристик компьютера Особенностей реализации алгоритма на языке программирования

Слайд 9


Время работы программы Рассмотрим несколько программ, выполняемых на одной машине в одинаковых условиях с входными наборами различной длины В таблице...
Описание слайда:
Время работы программы Рассмотрим несколько программ, выполняемых на одной машине в одинаковых условиях с входными наборами различной длины В таблице иллюстрируется зависимость времени работы программы от размера входных данных

Слайд 10


Изменение времени работы
Описание слайда:
Изменение времени работы

Слайд 11


Время работы программы Можно заметить, что при больших N существенно различие между первыми тремя программами и последними двумя программами. Иными...
Описание слайда:
Время работы программы Можно заметить, что при больших N существенно различие между первыми тремя программами и последними двумя программами. Иными словами, существенно различие между программами, работающими за время «порядка N2» [или O(N2)] и «порядка N3» [или O(N3)].

Слайд 12


Утверждение Пусть компьютер соответствует принципу адресности фон Неймана (имеет оперативную память, время обращения к каждой ячейке которой по ее...
Описание слайда:
Утверждение Пусть компьютер соответствует принципу адресности фон Неймана (имеет оперативную память, время обращения к каждой ячейке которой по ее целочисленному адресу одинаково) Пусть компьютер поддерживает принцип программного управления и принцип последовательного исполнения команд (допустима конвейеризация или параллельное исполнение на фиксированном числе процессоров)

Слайд 13


Утверждение Пусть компьютер имеет примерно соответствующий общепринятому набор команд (т.е. в нем нет готовых команд сортировки, например).
Описание слайда:
Утверждение Пусть компьютер имеет примерно соответствующий общепринятому набор команд (т.е. в нем нет готовых команд сортировки, например).

Слайд 14


Утверждение Тогда для большинства задач порядок роста времени работы программы в зависимости от числа элементов определяется алгоритмом. Коэффициенты...
Описание слайда:
Утверждение Тогда для большинства задач порядок роста времени работы программы в зависимости от числа элементов определяется алгоритмом. Коэффициенты в формуле зависимости времени работы программы определяются деталями реализации, характеристиками компьютера и т.д.

Слайд 15


Выводы При разработке программы невозможно точно определить время ее работы в будущем. Для практических нужд, как правило, достаточно знание порядка...
Описание слайда:
Выводы При разработке программы невозможно точно определить время ее работы в будущем. Для практических нужд, как правило, достаточно знание порядка роста времени работы программы в зависимости от числа элементов.

Слайд 16


Выводы Исследование вычислительной сложности алгоритма возможно без знания деталей его реализации на конкретном языке программирования на конкретном...
Описание слайда:
Выводы Исследование вычислительной сложности алгоритма возможно без знания деталей его реализации на конкретном языке программирования на конкретном компьютере. Для большинства алгоритмов при выполнении базовых предположений о компьютере порядок роста времени работы в зависимости от числа элементов не зависит от реализации

Слайд 17


Асимптотическое поведение функции
Описание слайда:
Асимптотическое поведение функции

Слайд 18


Асимптотическое поведение функции
Описание слайда:
Асимптотическое поведение функции

Слайд 19


Асимптотическое поведение функции Верно, что
Описание слайда:
Асимптотическое поведение функции Верно, что

Слайд 20


Асимптотическое поведение функции. Примеры
Описание слайда:
Асимптотическое поведение функции. Примеры

Слайд 21


Асимптотическое поведение функции Для исследования алгоритма работы достаточно выяснить асимптотическое поведение функции, задающей зависимость...
Описание слайда:
Асимптотическое поведение функции Для исследования алгоритма работы достаточно выяснить асимптотическое поведение функции, задающей зависимость времени работы от количества элементов Как правило, эта характеристика определяется алгоритмом, а не реализацией программы

Слайд 22


Асимптотическое поведение функции. мы можем пренебрегать постоянными коэффициентами и меньшими по порядку добавками [o(g(n))] при оценивании времени...
Описание слайда:
Асимптотическое поведение функции. мы можем пренебрегать постоянными коэффициентами и меньшими по порядку добавками [o(g(n))] при оценивании времени работы функции

Слайд 23


Пример max = 0; for ( i = 0 ; i < n ; i++ ) if ( max < A[i] ) max = A[i];
Описание слайда:
Пример max = 0; for ( i = 0 ; i < n ; i++ ) if ( max < A[i] ) max = A[i];

Слайд 24


Пример. Команды процессора SET R1,0 c1 LOAD R2, c2 LOAD R3, c2 SET R4, 0; c1 start: CMP R4,R2 c3 JZ finish c4 LOAD R5, [R3] c2 CMP R1, R5 c3 JZ next...
Описание слайда:
Пример. Команды процессора SET R1,0 c1 LOAD R2, c2 LOAD R3, c2 SET R4, 0; c1 start: CMP R4,R2 c3 JZ finish c4 LOAD R5, [R3] c2 CMP R1, R5 c3 JZ next c4 SET R1, R5 c1 next:ADD R4,R4,1 c5 ADD R3, R3, 4 [sizeof(unsigned int)] c5 JMP start c6 finish: SAVE R4, c7

Слайд 25


Пример: Время работы программы (k – количество раз, когда условие выполнено, 0
Описание слайда:
Пример: Время работы программы (k – количество раз, когда условие выполнено, 0

Слайд 26


Пример max = 0; for ( i = 0 ; i < n ; i++ ) if ( max < A[i] ) max = A[i]; При взгляде на код интуитивно понятно, что сложность алгоритма T=O(n) Мы...
Описание слайда:
Пример max = 0; for ( i = 0 ; i < n ; i++ ) if ( max < A[i] ) max = A[i]; При взгляде на код интуитивно понятно, что сложность алгоритма T=O(n) Мы это доказали строго

Слайд 27


Вычислительная сложность алгоритма Часто время работы алгоритма зависит не только от размера входных данных, но и от их значений. В этом случае можно...
Описание слайда:
Вычислительная сложность алгоритма Часто время работы алгоритма зависит не только от размера входных данных, но и от их значений. В этом случае можно говорить о времени работы: Для наилучших входных данных Для средних входных данных (матожидание времени работы) Для наихудших входных данных

Слайд 28


Вычислительная сложность алгоритма Часто асимптотическая сложность алгоритма для средних и наихудших входных данных совпадает Когда я говорю о...
Описание слайда:
Вычислительная сложность алгоритма Часто асимптотическая сложность алгоритма для средних и наихудших входных данных совпадает Когда я говорю о вычислительной сложности алгоритма, не уточняя детали – я имею в виду, что для этого алгоритма асимптотическая сложность совпадает в среднем и наихудшем случае

Слайд 29


Вычислительная сложность алгоритма Существуют алгоритмы (например, QuickSort), вычислительная сложность которых отличается в среднем O(nlg(n) и...
Описание слайда:
Вычислительная сложность алгоритма Существуют алгоритмы (например, QuickSort), вычислительная сложность которых отличается в среднем O(nlg(n) и наихудшем O(n2) случаях Используя такие алгоритмы, подумайте, не оказывается ли наихудший случай самым распространенным в вашей задаче

Слайд 30


Вычислительная сложность алгоритма Вычислительная сложность алгоритма в наилучшем случае обсуждается реже Подумайте, не можете ли Вы организовать...
Описание слайда:
Вычислительная сложность алгоритма Вычислительная сложность алгоритма в наилучшем случае обсуждается реже Подумайте, не можете ли Вы организовать наилучший случай в своей задаче.

Слайд 31


Выводы Порядок роста времени выполнения программы, как правило, определяется алгоритмом Ключевая характеристика алгоритма – порядок роста...
Описание слайда:
Выводы Порядок роста времени выполнения программы, как правило, определяется алгоритмом Ключевая характеристика алгоритма – порядок роста (асимптотическая сложность) Асимптотическую сложность алгоритма часто можно оценить интуитивно

Слайд 32


Лекция 2. Понятие сортировки и поиска. Обзор основных алгоритмов. Линейный поиск в массиве Бинарный поиск в массиве Сортировка прямым выбором Другие...
Описание слайда:
Лекция 2. Понятие сортировки и поиска. Обзор основных алгоритмов. Линейный поиск в массиве Бинарный поиск в массиве Сортировка прямым выбором Другие квадратичные сортировки Сортировка Merge Sort Другие nlg(n) сортировки

Слайд 33


Методы поиска Линейный поиск Бинарный поиск Другие методы
Описание слайда:
Методы поиска Линейный поиск Бинарный поиск Другие методы

Слайд 34


Линейный поиск в массиве Пусть есть массив A длины n Необходимо найти элемент, равный а. Мы можем просто перебрать все элементы массива, сравнивая их...
Описание слайда:
Линейный поиск в массиве Пусть есть массив A длины n Необходимо найти элемент, равный а. Мы можем просто перебрать все элементы массива, сравнивая их c a

Слайд 35


Линейный поиск в массиве int result = -1; int i = 0; while ( i < n && result < 0 ) { if ( A[ i ] == a ) result = i; i++; }
Описание слайда:
Линейный поиск в массиве int result = -1; int i = 0; while ( i < n && result < 0 ) { if ( A[ i ] == a ) result = i; i++; }

Слайд 36


Линейный поиск в массиве Легко показать, что время работы алгоритма в наихудшем и среднем случае – O(n). Действительно, наихудший случай – когда...
Описание слайда:
Линейный поиск в массиве Легко показать, что время работы алгоритма в наихудшем и среднем случае – O(n). Действительно, наихудший случай – когда элемент не найден, трудоемкость равна с1n+c2 Если элемент найден, трудоемкость в среднем c1(n/2)+c3

Слайд 37


Бинарный поиск в массиве В общем случае реализовать поиск с трудоемкостью, меньшей O(n), невозможно Если мы не делаем предположений о хранении данных...
Описание слайда:
Бинарный поиск в массиве В общем случае реализовать поиск с трудоемкостью, меньшей O(n), невозможно Если мы не делаем предположений о хранении данных в массиве – то любой элемент может оказаться нужным, и проверять необходимо все Предположим, массив был отсортирован. Тогда ситуация меняется

Слайд 38


Поиск в отсортированном массиве
Описание слайда:
Поиск в отсортированном массиве

Слайд 39


Бинарный поиск Количество сравнений – log2N Неудобство хранения данных в отсортированном массиве – дорогая вставка элемента (потребуется переместить...
Описание слайда:
Бинарный поиск Количество сравнений – log2N Неудобство хранения данных в отсортированном массиве – дорогая вставка элемента (потребуется переместить в среднем N/2 элементов) Решение этой проблемы будет рассмотрено в лекции 3, посвященной контейнерам

Слайд 40


Поиск Если мы хотим еще более быстрого поиска – мы должны наложить еще более жесткие ограничения на механизм хранения данных. Подробнее вопрос будет...
Описание слайда:
Поиск Если мы хотим еще более быстрого поиска – мы должны наложить еще более жесткие ограничения на механизм хранения данных. Подробнее вопрос будет рассмотрен в лекции 4, посвященной хэшированию.

Слайд 41


Поиск минимального элемента Задача решается за время, равное O(n) min = 0; for ( i = 0 ; i < n ; i++ ) if (A[i] < min ) min = A[i];
Описание слайда:
Поиск минимального элемента Задача решается за время, равное O(n) min = 0; for ( i = 0 ; i < n ; i++ ) if (A[i] < min ) min = A[i];

Слайд 42


Методы сортировки Сортировка за O(n2) Сортировка за O(nlg(n))
Описание слайда:
Методы сортировки Сортировка за O(n2) Сортировка за O(nlg(n))

Слайд 43


Сортировка прямым выбором На первом шаге выбирается минимальный элемент и ставится первым После этого мы решаем ту же задачу для N-1 элемента –...
Описание слайда:
Сортировка прямым выбором На первом шаге выбирается минимальный элемент и ставится первым После этого мы решаем ту же задачу для N-1 элемента – начиная со второго Так пока число сортируемых элементов не станет 1

Слайд 44


Пример Демонстрационная программа SortStraightSel
Описание слайда:
Пример Демонстрационная программа SortStraightSel

Слайд 45


Пример работы
Описание слайда:
Пример работы

Слайд 46


Сортировка прямым выбором Мы просматриваем на первом шаге N элементов, на втором – N-1, и так далее. Всего – N + N-1 + … + 1 = (N2 + N)/2 Время...
Описание слайда:
Сортировка прямым выбором Мы просматриваем на первом шаге N элементов, на втором – N-1, и так далее. Всего – N + N-1 + … + 1 = (N2 + N)/2 Время работы алгоритма - O(N2)

Слайд 47


Сортировка пузырьком На каждом шаге перебираются все пары соседних элементов, и если меньший элемент стоит позже – элементы меняются местами Таким...
Описание слайда:
Сортировка пузырьком На каждом шаге перебираются все пары соседних элементов, и если меньший элемент стоит позже – элементы меняются местами Таким образом, малые значения «всплывают» в начало массива, а большие «опускаются» в конец Нужно выполнить N-1 шаг, чтобы массив стал отсортированным

Слайд 48


Пример
Описание слайда:
Пример

Слайд 49


Пример
Описание слайда:
Пример

Слайд 50


Пример
Описание слайда:
Пример

Слайд 51


Пример
Описание слайда:
Пример

Слайд 52


Сортировка пузырьком Необходимо N-1 шагов. На каждом шаге – N-1 сравнение (и, при необходимости, перестановка). Итого – (N-1)2, т.е. O(N2) шагов Если...
Описание слайда:
Сортировка пузырьком Необходимо N-1 шагов. На каждом шаге – N-1 сравнение (и, при необходимости, перестановка). Итого – (N-1)2, т.е. O(N2) шагов Если не делать лишних сравнений – (N2 - N)/2

Слайд 53


Быстрые алгоритмы сортировки Алгоритм сортировки MergeSort Представим себе, что левая и правая половина массива отсортированы. Тогда отсортировать...
Описание слайда:
Быстрые алгоритмы сортировки Алгоритм сортировки MergeSort Представим себе, что левая и правая половина массива отсортированы. Тогда отсортировать весь массив можно за N шагов. Как?

Слайд 54


Merge Sort
Описание слайда:
Merge Sort

Слайд 55


Merge Sort
Описание слайда:
Merge Sort

Слайд 56


Merge Sort
Описание слайда:
Merge Sort

Слайд 57


Merge Sort Как же сделать половинки массива отсортированными? В массиве из двух элементов половинки отсортированы всегда Отсортировав все фрагменты...
Описание слайда:
Merge Sort Как же сделать половинки массива отсортированными? В массиве из двух элементов половинки отсортированы всегда Отсортировав все фрагменты массива из двух элементов каждый, можно сортировать фрагменты из четырех – и так до конца Если длина массива – не 2n, ничего страшного – просто один из двух массивов будет короче

Слайд 58


Merge Sort. Неотсортированый массив
Описание слайда:
Merge Sort. Неотсортированый массив

Слайд 59


MergeSort Алгоритм MergeSort позволяет нам решить задачу сортировки массива за время, пропорциональное Nlog2N Мы знаем, что log2N = logaN * log2a =...
Описание слайда:
MergeSort Алгоритм MergeSort позволяет нам решить задачу сортировки массива за время, пропорциональное Nlog2N Мы знаем, что log2N = logaN * log2a = KlogaN Следовательно, если время работы алгоритма – O(log2N), то оно равно и O(logaN) Поэтому часто говорят просто O(NlogN), не уточняя основание логарифма

Слайд 60


Пирамидальная сортировка Основана на помещении значений в пирамиду и извлечении их из пирамиды
Описание слайда:
Пирамидальная сортировка Основана на помещении значений в пирамиду и извлечении их из пирамиды

Слайд 61


QuickSort
Описание слайда:
QuickSort

Слайд 62


QuickSort Как выполнить QuickSort без использования дополнительной памяти?
Описание слайда:
QuickSort Как выполнить QuickSort без использования дополнительной памяти?

Слайд 63


CombSort В сортировке пузырьком мы сравниваем соседние элементы и меняем их местами Эффективнее на первых шагах сравнивать более удаленные друг от...
Описание слайда:
CombSort В сортировке пузырьком мы сравниваем соседние элементы и меняем их местами Эффективнее на первых шагах сравнивать более удаленные друг от друга элементы Постепенно снижаем расстояние между сравниваемыми элементами На последнем шаге повторим пузырек, но проходов потребуется немного

Слайд 64


CombSort Начальный шаг – длина массива, деленная на 1.3 Уменьшение шага – в 1.3 раза
Описание слайда:
CombSort Начальный шаг – длина массива, деленная на 1.3 Уменьшение шага – в 1.3 раза

Слайд 65


CombSort
Описание слайда:
CombSort

Слайд 66


IntroSort Сочетание пирамидальной и быстрой сортировки Быстрая сортировка лучше в среднем случае, пирамидальная – в наихудшем При достижении...
Описание слайда:
IntroSort Сочетание пирамидальной и быстрой сортировки Быстрая сортировка лучше в среднем случае, пирамидальная – в наихудшем При достижении предельной глубины быстрой сортировки переходим на пирамидальную

Слайд 67


Методы сортировки за O(N) Сортировка подсчетом Цифровая сортировка Карманная сортировка
Описание слайда:
Методы сортировки за O(N) Сортировка подсчетом Цифровая сортировка Карманная сортировка

Слайд 68


Сортировка подсчетом Предположим, в массиве лежат значения, равные 0, 1 и 2 Как выполнить его сортировку за время O(N)?
Описание слайда:
Сортировка подсчетом Предположим, в массиве лежат значения, равные 0, 1 и 2 Как выполнить его сортировку за время O(N)?

Слайд 69


Сортировка подсчетом
Описание слайда:
Сортировка подсчетом

Слайд 70


Сортировка подсчетом
Описание слайда:
Сортировка подсчетом

Слайд 71


Сортировка подсчетом
Описание слайда:
Сортировка подсчетом

Слайд 72


Сортировка подсчетом
Описание слайда:
Сортировка подсчетом

Слайд 73


Сортировка подсчетом
Описание слайда:
Сортировка подсчетом

Слайд 74


Сортировка подсчетом
Описание слайда:
Сортировка подсчетом

Слайд 75


Сортировка подсчетом
Описание слайда:
Сортировка подсчетом

Слайд 76


Сортировка подсчетом Работает за время O(N+K), где N – число значений в массиве, K – число возможных значений Требует дополнительной памяти в объеме...
Описание слайда:
Сортировка подсчетом Работает за время O(N+K), где N – число значений в массиве, K – число возможных значений Требует дополнительной памяти в объеме O(N+K)

Слайд 77


Сортировка подсчетом
Описание слайда:
Сортировка подсчетом

Слайд 78


Сортировка подсчетом Порядок студентов был алфавитным Мы отсортировали список по номеру курса. Порядок студентов внутри курса остался алфавитным
Описание слайда:
Сортировка подсчетом Порядок студентов был алфавитным Мы отсортировали список по номеру курса. Порядок студентов внутри курса остался алфавитным

Слайд 79


Цифровая сортировка Для массивов с большим диапазоном значений сортировка подсчетом не годится Учитывая сохранение порядка элементов с равными...
Описание слайда:
Цифровая сортировка Для массивов с большим диапазоном значений сортировка подсчетом не годится Учитывая сохранение порядка элементов с равными значениями в сортировке подсчетом, можно ее использовать и в этом случае

Слайд 80


Цифровая сортировка Последовательно сортируем по цифрам, начиная с последней. Трудоемкость O(R*(N+K)), где R – число цифр, K – число значений цифры,...
Описание слайда:
Цифровая сортировка Последовательно сортируем по цифрам, начиная с последней. Трудоемкость O(R*(N+K)), где R – число цифр, K – число значений цифры, N – число значений в массиве. Дополнительная память - O(N+K)

Слайд 81


Карманная сортировка Пусть есть массив N вещественных значений от 0 до 1. Создадим N списков. В список K будем помещать значения из диапазона [ K/N ,...
Описание слайда:
Карманная сортировка Пусть есть массив N вещественных значений от 0 до 1. Создадим N списков. В список K будем помещать значения из диапазона [ K/N , (K+1)/N ) Любым методом отсортируем списки (они будут очень короткими) Объединим списки в результирующий массив

Слайд 82


Другие алгоритмы сортировки Быстрая сортировка (Quick Sort) Сортировка Шелла Сортировка Шейкером Сортировка подсчетом Цифровая сортировка (по...
Описание слайда:
Другие алгоритмы сортировки Быстрая сортировка (Quick Sort) Сортировка Шелла Сортировка Шейкером Сортировка подсчетом Цифровая сортировка (по младшему разряду, потом по старшему и т.д.) Пирамидальная сортировка (Heap Sort)

Слайд 83


Другие алгоритмы сортировки Сортировка расческой (Comb Sort) Плавная сортировка (Smooth Sort) Блочная сортировка Patience sorting Introsort
Описание слайда:
Другие алгоритмы сортировки Сортировка расческой (Comb Sort) Плавная сортировка (Smooth Sort) Блочная сортировка Patience sorting Introsort

Слайд 84


Лабораторная работа №1. Реализация алгоритмов сортировки и поиска.
Описание слайда:
Лабораторная работа №1. Реализация алгоритмов сортировки и поиска.

Слайд 85


Реализация алгоритмов сортировки и поиска Предлагаются индивидуальные варианты заданий, связанные с реализацией алгоритмов Предпочтительна реализация...
Описание слайда:
Реализация алгоритмов сортировки и поиска Предлагаются индивидуальные варианты заданий, связанные с реализацией алгоритмов Предпочтительна реализация алгоритма, сопровождаемая подготовкой доклада об алгоритме Доклады целесообразны для алгоритмов повышенной сложности

Слайд 86


Варианты заданий Реализовать бинарный поиск в массиве Реализовать сортировку Шелла Реализовать сортировку шейкером Реализовать сортировку подсчетом...
Описание слайда:
Варианты заданий Реализовать бинарный поиск в массиве Реализовать сортировку Шелла Реализовать сортировку шейкером Реализовать сортировку подсчетом (данные типа char) Реализовать сортировку расческой (CombSort)

Слайд 87


Варианты заданий Реализовать метод IntroSort Реализовать цифровую сортировку значений типа int по их двоичной записи Реализовать цифровую сортировку...
Описание слайда:
Варианты заданий Реализовать метод IntroSort Реализовать цифровую сортировку значений типа int по их двоичной записи Реализовать цифровую сортировку значений типа int по их восьмеричной записи Реализовать цифровую сортировку значений типа int по их десятичной записи Реализовать цифровую сортировку значений типа int по их шестнадцатеричной записи

Слайд 88


Варианты заданий повышенной сложности Реализовать пирамидальную сортировку Реализовать плавную сортировку (Smooth Sort) Реализовать быструю...
Описание слайда:
Варианты заданий повышенной сложности Реализовать пирамидальную сортировку Реализовать плавную сортировку (Smooth Sort) Реализовать быструю сортировку (QuickSort) Реализовать рандомизированную быструю сортировку

Слайд 89


Варианты заданий повышенной сложности Реализовать карманную (bucket) сортировку Реализовать алфавитную сортировку M строк суммарной длиной N символов...
Описание слайда:
Варианты заданий повышенной сложности Реализовать карманную (bucket) сортировку Реализовать алфавитную сортировку M строк суммарной длиной N символов за время O(N)

Слайд 90


Варианты заданий повышенной сложности Реализовать поиск i-ой порядковой статистики [i-ого по величине числа] методом RandomizedSelect (за O(N) в...
Описание слайда:
Варианты заданий повышенной сложности Реализовать поиск i-ой порядковой статистики [i-ого по величине числа] методом RandomizedSelect (за O(N) в среднем). Реализовать поиск i-ой порядковой статистики [i-ого по величине числа] за время O(N) в наихудшем случае Реализовать поиск наибольшей возрастающей подпоследовательности (Patience Sorting)

Слайд 91


Понятие порядковой статистики 1-ая порядковая статистика – 0 2-ая – 1 3-я – 2 4-ая – 3 5-ая – 4 6-ая – 7 7-ая - 9
Описание слайда:
Понятие порядковой статистики 1-ая порядковая статистика – 0 2-ая – 1 3-я – 2 4-ая – 3 5-ая – 4 6-ая – 7 7-ая - 9

Слайд 92


Тема 1.2. Контейнеры данных. Идея хэширования
Описание слайда:
Тема 1.2. Контейнеры данных. Идея хэширования

Слайд 93


Лекция 3. Понятие контейнера данных. Основные типы контейнеров
Описание слайда:
Лекция 3. Понятие контейнера данных. Основные типы контейнеров

Слайд 94


Понятие контейнера данных Контейнер – программный объект, отвечающий за хранение набора однотипных данных (элементов контейнера) и организацию...
Описание слайда:
Понятие контейнера данных Контейнер – программный объект, отвечающий за хранение набора однотипных данных (элементов контейнера) и организацию доступа к ним

Слайд 95


Контейнеры в языках программирования Контейнер может быть Стандартным объектом языка программирования (массивы фиксированной длины в C) Объектом...
Описание слайда:
Контейнеры в языках программирования Контейнер может быть Стандартным объектом языка программирования (массивы фиксированной длины в C) Объектом класса, разработанного пользователем Объектом класса стандартной библиотеки

Слайд 96


Виды контейнеров Массивы Списки Деревья Словари Стеки и очереди Пирамиды. Очереди с приоритетами
Описание слайда:
Виды контейнеров Массивы Списки Деревья Словари Стеки и очереди Пирамиды. Очереди с приоритетами

Слайд 97


Массивы Массивом называется контейнер, в котором элементы лежат в памяти компьютера подряд Размер массива из N элементов, каждый из которых занимает...
Описание слайда:
Массивы Массивом называется контейнер, в котором элементы лежат в памяти компьютера подряд Размер массива из N элементов, каждый из которых занимает M байт – NM. Если адрес начала массива в памяти – A, то адрес i-ого элемента – A+iM

Слайд 98


Массивы
Описание слайда:
Массивы

Слайд 99


Массивы. Ключевые свойства Быстрый поиск элемента по индексу (за O(1)) На C/C++ &(A[n])=&(A)+n Медленная вставка элемента в середину (важно для...
Описание слайда:
Массивы. Ключевые свойства Быстрый поиск элемента по индексу (за O(1)) На C/C++ &(A[n])=&(A)+n Медленная вставка элемента в середину (важно для отсортированного массива) – за O(N) Проблемы при росте массива сверх заранее запланированного размера

Слайд 100


Массив. Рост сверх планового размера
Описание слайда:
Массив. Рост сверх планового размера

Слайд 101


Массивы Запрещая «переезд» массива, мы ограничиваем рост его размера Разрешая «переезд», мы лишаем себя права запоминать адреса объектов массива
Описание слайда:
Массивы Запрещая «переезд» массива, мы ограничиваем рост его размера Разрешая «переезд», мы лишаем себя права запоминать адреса объектов массива

Слайд 102


Пример std::vector< int > array; … int* ptr = &(array[0]); //Запомнили адрес array.push_back( 7 ); //Добавили элемент //Возможен «переезд» std::cout
Описание слайда:
Пример std::vector< int > array; … int* ptr = &(array[0]); //Запомнили адрес array.push_back( 7 ); //Добавили элемент //Возможен «переезд» std::cout

Слайд 103


Списки Существенным ограничением массива является хранение элементов подряд Оно приводит к сложности расширения массива и вставки элемента в середину...
Описание слайда:
Списки Существенным ограничением массива является хранение элементов подряд Оно приводит к сложности расширения массива и вставки элемента в середину Попробуем от него отказаться

Слайд 104


Списки Пусть каждый элемент помнит, где лежит следующий (хранит его адрес) Тогда достаточно запомнить адрес нулевого элемента, и мы легко найдем...
Описание слайда:
Списки Пусть каждый элемент помнит, где лежит следующий (хранит его адрес) Тогда достаточно запомнить адрес нулевого элемента, и мы легко найдем любой Пример списка приведен на слайде

Слайд 105


Списки
Описание слайда:
Списки

Слайд 106


Список: вставка элемента
Описание слайда:
Список: вставка элемента

Слайд 107


Список: вставка элемента Время вставки элемента в середину списка – O(1), т.е. не зависит от размера списка Время поиска i-ого элемента по индексу –...
Описание слайда:
Список: вставка элемента Время вставки элемента в середину списка – O(1), т.е. не зависит от размера списка Время поиска i-ого элемента по индексу – O(i)

Слайд 108


Списки Недостаток списка: в нем, даже отсортированном, нельзя реализовать бинарный поиск (слишком дорого искать середину списка)
Описание слайда:
Списки Недостаток списка: в нем, даже отсортированном, нельзя реализовать бинарный поиск (слишком дорого искать середину списка)

Слайд 109


Списки Бывают: Однонаправленными (каждый элемент знает следующий) Двунаправленными (каждый элемент знает следующий и предыдущий)
Описание слайда:
Списки Бывают: Однонаправленными (каждый элемент знает следующий) Двунаправленными (каждый элемент знает следующий и предыдущий)

Слайд 110


Деревья Отсортированный массив хорош, поскольку позволяет бинарный поиск за время O(logN) Добавление нового элемента при этом занимает время O(N) Мы...
Описание слайда:
Деревья Отсортированный массив хорош, поскольку позволяет бинарный поиск за время O(logN) Добавление нового элемента при этом занимает время O(N) Мы попробуем с этим справиться Начнем с краткого экскурса в теорию графов

Слайд 111


Граф Рассмотрим множество A из N элементов и множество B, состоящее из пар элементов множества A и не содержащее повторяющихся пар A: {0, 1, 2, 3, 4}...
Описание слайда:
Граф Рассмотрим множество A из N элементов и множество B, состоящее из пар элементов множества A и не содержащее повторяющихся пар A: {0, 1, 2, 3, 4} B: {{0,1},{0,2},{2,3},{2,4}}

Слайд 112


Граф Это множество называется графом и может быть представлено в виде
Описание слайда:
Граф Это множество называется графом и может быть представлено в виде

Слайд 113


Граф Элементы A – узлы графа Элементы B – ребра графа. Ребро задается своим начальным и конечным узлом
Описание слайда:
Граф Элементы A – узлы графа Элементы B – ребра графа. Ребро задается своим начальным и конечным узлом

Слайд 114


Граф Граф называется неориентированным, если для любого ребра {a,b}, входящего в граф, ребро {b,a} тоже входит в граф
Описание слайда:
Граф Граф называется неориентированным, если для любого ребра {a,b}, входящего в граф, ребро {b,a} тоже входит в граф

Слайд 115


Неориентированный граф?
Описание слайда:
Неориентированный граф?

Слайд 116


Неориентированный граф?
Описание слайда:
Неориентированный граф?

Слайд 117


Упрощенное изображение неориентированного графа
Описание слайда:
Упрощенное изображение неориентированного графа

Слайд 118


Неориентированные графы Неориентированный граф является связным, если из любого узла a можно попасть в любой узел b Т.е. для любых a и b существует...
Описание слайда:
Неориентированные графы Неориентированный граф является связным, если из любого узла a можно попасть в любой узел b Т.е. для любых a и b существует набор ребер графа {a,x0}, {x0,x1}, …, {xn-1,xn}, {xn,b}

Слайд 119


Связный граф?
Описание слайда:
Связный граф?

Слайд 120


Связный граф?
Описание слайда:
Связный граф?

Слайд 121


Неориентированные графы Неориентированный граф является ациклическим, если в нем не существует маршрутов без повторения ребер, которые начинаются и...
Описание слайда:
Неориентированные графы Неориентированный граф является ациклическим, если в нем не существует маршрутов без повторения ребер, которые начинаются и заканчиваются в одной точке

Слайд 122


Ациклический граф?
Описание слайда:
Ациклический граф?

Слайд 123


Ациклический граф?
Описание слайда:
Ациклический граф?

Слайд 124


Деревья Деревом называется связный ациклический неориентированный граф Если ациклический неориентированный граф – не связный, то это лес...
Описание слайда:
Деревья Деревом называется связный ациклический неориентированный граф Если ациклический неориентированный граф – не связный, то это лес (совокупность нескольких деревьев – компонент связности)

Слайд 125


Утверждение В любом дереве можно ввести отношение предок-потомок со следующими свойствами Предок соединен с потомком ребром дерева Если элементы...
Описание слайда:
Утверждение В любом дереве можно ввести отношение предок-потомок со следующими свойствами Предок соединен с потомком ребром дерева Если элементы соединены ребром – один из них предок другого У каждого элемента 0 или 1 предок У элемента может быть любое число потомков Отношение предок-потомок не имеет циклов (т.е. нельзя быть потомком своего потомка, потомком потомка своего потомка и т.д.) Элемент, не имеющий предков, только один – корень дерева.

Слайд 126


Доказательство Возьмем произвольный узел и объявим его корнем. Все соединенные с ним узлы – его потомки и узлы 1-ого уровня Все узлы, соединенные с...
Описание слайда:
Доказательство Возьмем произвольный узел и объявим его корнем. Все соединенные с ним узлы – его потомки и узлы 1-ого уровня Все узлы, соединенные с узлами первого уровня, кроме корня – их потомки и узлы 2-ого уровня … Поскольку граф ациклический, отношение предок-потомок не будет иметь циклов

Слайд 127


Иллюстрация
Описание слайда:
Иллюстрация

Слайд 128


Дерево Итак, деревом называется контейнер, в котором Элементы связаны отношением предок-потомок У каждого элемента 0 или 1 предок. Как правило,...
Описание слайда:
Дерево Итак, деревом называется контейнер, в котором Элементы связаны отношением предок-потомок У каждого элемента 0 или 1 предок. Как правило, элемент знает его адрес. У каждого элемента могут быть потомки, и он знает их адреса Отношение предок-потомок не имеет циклов (т.е. нельзя быть потомком своего потомка, потомком потомка своего потомка и т.д.) Элемент, не имеющий предков, только один – корень дерева. Он один (иначе это лес, а не дерево) Концевые (не имеющие потомков) элементы - листья

Слайд 129


Дерево
Описание слайда:
Дерево

Слайд 130


Бинарное дерево Бинарным называется дерево, в котором у каждого элемента не более 2 потомков Один из них называется левым, другой правым
Описание слайда:
Бинарное дерево Бинарным называется дерево, в котором у каждого элемента не более 2 потомков Один из них называется левым, другой правым

Слайд 131


Бинарное дерево
Описание слайда:
Бинарное дерево

Слайд 132


Бинарное дерево поиска Бинарное дерево называется деревом поиска, если Левый потомок любого элемента и все элементы поддерева, растущего из левого...
Описание слайда:
Бинарное дерево поиска Бинарное дерево называется деревом поиска, если Левый потомок любого элемента и все элементы поддерева, растущего из левого потомка, меньше данного элемента Правый потомок любого элемента и все элементы поддерева, растущего из правого потомка, больше данного элемента

Слайд 133


Бинарное дерево поиска
Описание слайда:
Бинарное дерево поиска

Слайд 134


Бинарное дерево. Поиск
Описание слайда:
Бинарное дерево. Поиск

Слайд 135


Бинарное дерево. Добавление элемента
Описание слайда:
Бинарное дерево. Добавление элемента

Слайд 136


Бинарное дерево поиска Как и отсортированный массив, поддерживает поиск за log(N) В отличие от отсортированного массива, поддерживает добавление...
Описание слайда:
Бинарное дерево поиска Как и отсортированный массив, поддерживает поиск за log(N) В отличие от отсортированного массива, поддерживает добавление элемента за log(N)

Слайд 137


Сбалансированное дерево Дерево является сбалансированным, если разница между его максимальной и минимальной глубиной (количеством элементов от корня...
Описание слайда:
Сбалансированное дерево Дерево является сбалансированным, если разница между его максимальной и минимальной глубиной (количеством элементов от корня до листа) не больше 1.

Слайд 138


Сбалансированное дерево
Описание слайда:
Сбалансированное дерево

Слайд 139


Сбалансированное дерево
Описание слайда:
Сбалансированное дерево

Слайд 140


Несбалансированное дерево
Описание слайда:
Несбалансированное дерево

Слайд 141


Сбалансированное дерево Дерево должно быть сбалансированным, чтобы поддерживать поиск и добавление элемента за log(N) Существуют различные алгоритмы...
Описание слайда:
Сбалансированное дерево Дерево должно быть сбалансированным, чтобы поддерживать поиск и добавление элемента за log(N) Существуют различные алгоритмы реализации бинарных деревьев поиска Они отличаются способом обеспечения сбалансированности дерева

Слайд 142


Сбалансированное дерево Варианты: Красно-черные деревья AVL-деревья
Описание слайда:
Сбалансированное дерево Варианты: Красно-черные деревья AVL-деревья

Слайд 143


Словари Словарь – структура данных, в которой ключам сопоставляются значения (как в толковом словаре словам сопоставляются определения) Словарь...
Описание слайда:
Словари Словарь – структура данных, в которой ключам сопоставляются значения (как в толковом словаре словам сопоставляются определения) Словарь должен поддерживать быстрый поиск по ключу и быстрое добавление значения Словарь строят на основе бинарного дерева поиска

Слайд 144


Словарь
Описание слайда:
Словарь

Слайд 145


Словарь Ключи (в данном случае строковые) отсортированы по алфавиту Значения (в данном случае целочисленные) не влияют на сортировку
Описание слайда:
Словарь Ключи (в данном случае строковые) отсортированы по алфавиту Значения (в данном случае целочисленные) не влияют на сортировку

Слайд 146


Пирамиды Пирамида – это бинарное дерево со следующими свойствами Все уровни дерева, возможно кроме последнего, полностью заполнены...
Описание слайда:
Пирамиды Пирамида – это бинарное дерево со следующими свойствами Все уровни дерева, возможно кроме последнего, полностью заполнены (сбалансированность дерева) На последнем уровне заполнены несколько элементов, начиная с самого левого

Слайд 147


Пирамида?
Описание слайда:
Пирамида?

Слайд 148


Пирамида?
Описание слайда:
Пирамида?

Слайд 149


Пирамида?
Описание слайда:
Пирамида?

Слайд 150


Пирамида?
Описание слайда:
Пирамида?

Слайд 151


Пирамида?
Описание слайда:
Пирамида?

Слайд 152


Пирамида Пирамида называется невозрастающей, если любой родительский элемент больше (либо равен) обоих дочерних элементов Пирамида называется...
Описание слайда:
Пирамида Пирамида называется невозрастающей, если любой родительский элемент больше (либо равен) обоих дочерних элементов Пирамида называется неубывающей, если любой родительский элемент меньше (либо равен) обоих дочерних элементов

Слайд 153


Невозрастающая пирамида
Описание слайда:
Невозрастающая пирамида

Слайд 154


Неубывающая пирамида
Описание слайда:
Неубывающая пирамида

Слайд 155


Операции над невозрастающей пирамидой Из невозрастающей пирамиды можно извлечь максимальный элемент за время O(logN) так, чтобы она осталась...
Описание слайда:
Операции над невозрастающей пирамидой Из невозрастающей пирамиды можно извлечь максимальный элемент за время O(logN) так, чтобы она осталась невозрастающей В невозрастающую пирамиду можно добавить элемент за время O(logN) так, чтобы она осталась невозрастающей

Слайд 156


Извлечение элемента из пирамиды
Описание слайда:
Извлечение элемента из пирамиды

Слайд 157


Извлечение элемента из пирамиды
Описание слайда:
Извлечение элемента из пирамиды

Слайд 158


Извлечение элемента из пирамиды
Описание слайда:
Извлечение элемента из пирамиды

Слайд 159


Извлечение элемента из пирамиды
Описание слайда:
Извлечение элемента из пирамиды

Слайд 160


Извлечение элемента из пирамиды
Описание слайда:
Извлечение элемента из пирамиды

Слайд 161


Извлечение элемента из пирамиды
Описание слайда:
Извлечение элемента из пирамиды

Слайд 162


Добавление элемента в пирамиду
Описание слайда:
Добавление элемента в пирамиду

Слайд 163


Добавление элемента в пирамиду
Описание слайда:
Добавление элемента в пирамиду

Слайд 164


Добавление элемента в пирамиду
Описание слайда:
Добавление элемента в пирамиду

Слайд 165


Добавление элемента в пирамиду
Описание слайда:
Добавление элемента в пирамиду

Слайд 166


Применение пирамиды Пирамида используется в пирамидальной сортировке – построив пирамиду и извлекая из нее элементы, мы реализуем сортировку за...
Описание слайда:
Применение пирамиды Пирамида используется в пирамидальной сортировке – построив пирамиду и извлекая из нее элементы, мы реализуем сортировку за O(NlogN) Пирамида может рассматриваться как очередь с приоритетами. В ней можно выполнить за O(logN) операции Выборки максимального элемента Добавления нового элемента в очередь Повышения приоритета элемента

Слайд 167


Хранение пирамиды Мы можем хранить пирамиду как обычное бинарное дерево (каждый узел представляется как структура, состоящая из значения элемента,...
Описание слайда:
Хранение пирамиды Мы можем хранить пирамиду как обычное бинарное дерево (каждый узел представляется как структура, состоящая из значения элемента, указателей на дочерние узлы и родительский узел) Этот механизм требует использовать дополнительную память для хранения указателей

Слайд 168


Хранение пирамиды Пирамиду можно хранить без выделения дополнительной памяти Для этого пирамида представляется как массив
Описание слайда:
Хранение пирамиды Пирамиду можно хранить без выделения дополнительной памяти Для этого пирамида представляется как массив

Слайд 169


Хранение пирамиды Уровень K пирамиды занимает в массиве позиции от 2K-1 до 2K+1-2 Например, уровень 0 (корень) находится в позиции 0 Уровень 1 (2...
Описание слайда:
Хранение пирамиды Уровень K пирамиды занимает в массиве позиции от 2K-1 до 2K+1-2 Например, уровень 0 (корень) находится в позиции 0 Уровень 1 (2 элемента)– в позициях от 1 до 2 Уровень 3 (8 элементов) – в позициях от 7 до 14

Слайд 170


Хранение пирамиды
Описание слайда:
Хранение пирамиды

Слайд 171


Хранение пирамиды Потомками элемента A[ K ] являются A[ 2 * K + 1 ] – левый потомок A[ 2 * K + 2 ] – правый потомок Например, у элемента 4 (2-ой...
Описание слайда:
Хранение пирамиды Потомками элемента A[ K ] являются A[ 2 * K + 1 ] – левый потомок A[ 2 * K + 2 ] – правый потомок Например, у элемента 4 (2-ой слева элемент на 3-ем уровне) потомками будут Элемент 9 – 3-ий слева элемент 4-ого уровня, левый потомок Элемент 10 – 4-ый слева элемент 4-ого уровня, правый потомок

Слайд 172


Задание Как выглядит код, проверяющий массив на то, что он является невозрастающей пирамидой?
Описание слайда:
Задание Как выглядит код, проверяющий массив на то, что он является невозрастающей пирамидой?

Слайд 173


Стек Стеком называется контейнер, поддерживающий принцип Last In – First Out Мы можем в любой момент добавить новый элемент, посмотреть последний...
Описание слайда:
Стек Стеком называется контейнер, поддерживающий принцип Last In – First Out Мы можем в любой момент добавить новый элемент, посмотреть последний добавленный элемент, удалить последний добавленный элемент

Слайд 174


Стек
Описание слайда:
Стек

Слайд 175


Стек Стек может быть построен на базе практически другого контейнера, например массива Стек ограничивает количество операций контейнера
Описание слайда:
Стек Стек может быть построен на базе практически другого контейнера, например массива Стек ограничивает количество операций контейнера

Слайд 176


Очередь Очередь – это контейнер, поддерживающий принцип First In – First Out Существуют операции добавления элемента в очередь и удаления элемента,...
Описание слайда:
Очередь Очередь – это контейнер, поддерживающий принцип First In – First Out Существуют операции добавления элемента в очередь и удаления элемента, который был добавлен раньше всех

Слайд 177


Очередь
Описание слайда:
Очередь

Слайд 178


Очередь Очередь также легко реализуется на базе другого контейнера (например, массива)
Описание слайда:
Очередь Очередь также легко реализуется на базе другого контейнера (например, массива)

Слайд 179


Лекция 4. Хэш-таблицы. Понятие о хэш-функции. Идея хэширования.
Описание слайда:
Лекция 4. Хэш-таблицы. Понятие о хэш-функции. Идея хэширования.

Слайд 180


Хэш-таблицы. Постановка задачи. Бинарные деревья поиска позволили реализовать поиск элемента в контейнере за O(logN) Это правило удалось реализовать,...
Описание слайда:
Хэш-таблицы. Постановка задачи. Бинарные деревья поиска позволили реализовать поиск элемента в контейнере за O(logN) Это правило удалось реализовать, введя ограничения на структуру контейнера (не любой элемент не в любую ячейку можно положить) Может, если ограничения сделать больше, удастся повысить результат?

Слайд 181


Хэш-таблицы – прямая адресация Пусть в контейнере планируется хранить целые числа от 0 до 232-1 Для упрощения скажем, что числа могут быть только...
Описание слайда:
Хэш-таблицы – прямая адресация Пусть в контейнере планируется хранить целые числа от 0 до 232-1 Для упрощения скажем, что числа могут быть только разные Если бы мы могли завести массив длиной 232 - проблема была бы решена Хранить каждый элемент только в ячейке, номер которой совпадает с его значением

Слайд 182


Хэш-таблицы – прямая адресация
Описание слайда:
Хэш-таблицы – прямая адресация

Слайд 183


Хэш-таблицы – прямая адресация
Описание слайда:
Хэш-таблицы – прямая адресация

Слайд 184


О достоинствах и недостатках схемы Поиск любого элемента выполняется за фиксированное время (O(1)) Добавление нового элемента выполняется за...
Описание слайда:
О достоинствах и недостатках схемы Поиск любого элемента выполняется за фиксированное время (O(1)) Добавление нового элемента выполняется за фиксированное время (O(1)) Количество требуемой памяти пропорционально количеству возможных значений ключа

Слайд 185


Идея хэш-функции Обеспечить поиск и добавление элемента за время, равное O(1), возможно, если позиция полностью определяется значением (например, в...
Описание слайда:
Идея хэш-функции Обеспечить поиск и добавление элемента за время, равное O(1), возможно, если позиция полностью определяется значением (например, в рассмотренном методе прямой адресации – совпадает со значением). Тогда время вычисления позиции по значению фиксировано и не зависит от количества элементов Простое правило: «номер совпадает со значением» возможно только для целых чисел и приводит к перерасходу памяти

Слайд 186


Идея хэш-функции Итак, необходимо, чтобы элемент со значением x сохранялся в позиции h(x). h(x) – хэш-функция (от to hash – перемешивать) Тогда поиск...
Описание слайда:
Идея хэш-функции Итак, необходимо, чтобы элемент со значением x сохранялся в позиции h(x). h(x) – хэш-функция (от to hash – перемешивать) Тогда поиск и добавление элемента выполняются за время O(1)

Слайд 187


Пример Рассмотрим контейнер целых чисел Для хранения – массив из 11 элементов h(x) = x % 11 (остаток от деления на 11) Начальное состояние –...
Описание слайда:
Пример Рассмотрим контейнер целых чисел Для хранения – массив из 11 элементов h(x) = x % 11 (остаток от деления на 11) Начальное состояние – контейнер пустой. Поскольку в памяти что-то должно быть – заполняем невозможными (вообще или в данной клетке) значениями.

Слайд 188


Пример хэш-таблицы
Описание слайда:
Пример хэш-таблицы

Слайд 189


Пример хэш-таблицы
Описание слайда:
Пример хэш-таблицы

Слайд 190


Пример хэш-таблицы
Описание слайда:
Пример хэш-таблицы

Слайд 191


Коллизии Мы не хотим выделять память на каждое возможное значение элемента (реально встретившихся значений обычно много меньше, чем возможных)...
Описание слайда:
Коллизии Мы не хотим выделять память на каждое возможное значение элемента (реально встретившихся значений обычно много меньше, чем возможных) Значит, возможных значений h(x) меньше, чем возможных значений x И существуют такие x1, x2, что h(x1)=h(x2)

Слайд 192


Коллизии Значит, возможна ситуация, когда мы пытаемся добавить элемент, а место занято. Эта ситуация называется коллизией Вернемся к примеру
Описание слайда:
Коллизии Значит, возможна ситуация, когда мы пытаемся добавить элемент, а место занято. Эта ситуация называется коллизией Вернемся к примеру

Слайд 193


Пример коллизии
Описание слайда:
Пример коллизии

Слайд 194


Необходимо разрешение коллизий Правила разрешения коллизий должны определять, что делать при коллизии (куда поместить полученный элемент) Важно...
Описание слайда:
Необходимо разрешение коллизий Правила разрешения коллизий должны определять, что делать при коллизии (куда поместить полученный элемент) Важно обеспечить, чтобы: Правила разрешения коллизий позволяли бы разместить в контейнере любой набор значений Правила поиска позволяли найти любой элемент, размещенный по правилам разрешения коллизий

Слайд 195


Разрешение коллизий: хранение списков Будем хранить в каждом элементе массива не значение, а список значений Новое значение добавляем в конец списка...
Описание слайда:
Разрешение коллизий: хранение списков Будем хранить в каждом элементе массива не значение, а список значений Новое значение добавляем в конец списка Поиск выполняется по списку

Слайд 196


Разрешение коллизий: хранение списков, h(x) = x % 11, добавление
Описание слайда:
Разрешение коллизий: хранение списков, h(x) = x % 11, добавление

Слайд 197


Разрешение коллизий: хранение списков, h(x) = x % 11, поиск
Описание слайда:
Разрешение коллизий: хранение списков, h(x) = x % 11, поиск

Слайд 198


Разрешение коллизий хранением списков В наихудшем случае время поиска O(N) – если возникнет один список Время добавления элемента в наихудшем случае...
Описание слайда:
Разрешение коллизий хранением списков В наихудшем случае время поиска O(N) – если возникнет один список Время добавления элемента в наихудшем случае – O(N) или O(1) [если хранить адрес последнего элемента списка]

Слайд 199


Разрешение коллизий хранением списков Предположим, что Вероятности попадания элемента в любую ячейку равны Количество ячеек M равно количеству...
Описание слайда:
Разрешение коллизий хранением списков Предположим, что Вероятности попадания элемента в любую ячейку равны Количество ячеек M равно количеству элементов N (или хотя бы пропорционально) Тогда средняя длина списка – 1, среднее время поиска и добавления элемента – O(1)

Слайд 200


Разрешение коллизий методом сдвига Достаточно легко удалить элемент – просто удаляем его из списка. Время удаления - O(1)
Описание слайда:
Разрешение коллизий методом сдвига Достаточно легко удалить элемент – просто удаляем его из списка. Время удаления - O(1)

Слайд 201


Разрешение коллизий методом сдвига Часто хочется упростить структуру и не хранить массив списков В этом случае можно применить разрешение коллизий...
Описание слайда:
Разрешение коллизий методом сдвига Часто хочется упростить структуру и не хранить массив списков В этом случае можно применить разрешение коллизий методом сдвига (хэширование с открытой адресацией, метод линейного исследования)

Слайд 202


Разрешение коллизий методом сдвига Если мы не можем положить элемент в нужную ячейку – пытаемся положить в следующую, и так пока не найдется...
Описание слайда:
Разрешение коллизий методом сдвига Если мы не можем положить элемент в нужную ячейку – пытаемся положить в следующую, и так пока не найдется свободная При поиске перебираем элементы, пока не встретим пустую ячейку Встретив конец массива – переходим на первый элемент

Слайд 203


Почему линейное исследование? При попытке № i поместить значение k мы пробуем ячейку h( k , i ) h( k , i ) = ( h’(k) + i ) % m Функция - линейная
Описание слайда:
Почему линейное исследование? При попытке № i поместить значение k мы пробуем ячейку h( k , i ) h( k , i ) = ( h’(k) + i ) % m Функция - линейная

Слайд 204


Разрешение коллизий методом сдвига , h(x) = x % 11, добавление
Описание слайда:
Разрешение коллизий методом сдвига , h(x) = x % 11, добавление

Слайд 205


Разрешение коллизий методом сдвига , h(x) = x % 11, поиск
Описание слайда:
Разрешение коллизий методом сдвига , h(x) = x % 11, поиск

Слайд 206


Разрешение коллизий методом сдвига Метод работает, только если длина массива не меньше числа элементов Когда элементов в массиве становится...
Описание слайда:
Разрешение коллизий методом сдвига Метод работает, только если длина массива не меньше числа элементов Когда элементов в массиве становится достаточно много, эффективность хэширования мала (приходится перебирать множество элементов) Этот эффект называется кластеризацией (возникает кластер из занятых элементов)

Слайд 207


Разрешение коллизий: квадратичное исследование При попытке № i поместить значение k мы пробуем ячейку h( k , i ) h( k , i ) = ( h’(k) + c1i + c2i2) %...
Описание слайда:
Разрешение коллизий: квадратичное исследование При попытке № i поместить значение k мы пробуем ячейку h( k , i ) h( k , i ) = ( h’(k) + c1i + c2i2) % m В отличие от линейного исследования, кластеризация слабее

Слайд 208


Квадратичное исследование, h(x, i) = ( x % 11 + i + i2 ) % 11)
Описание слайда:
Квадратичное исследование, h(x, i) = ( x % 11 + i + i2 ) % 11)

Слайд 209


Квадратичное исследование, h(x, i) = ( x % 11 + i + i2 ) % 11)
Описание слайда:
Квадратичное исследование, h(x, i) = ( x % 11 + i + i2 ) % 11)

Слайд 210


Квадратичное исследование, h(x, i) = ( x % 11 + i + i2 ) % 11)
Описание слайда:
Квадратичное исследование, h(x, i) = ( x % 11 + i + i2 ) % 11)

Слайд 211


Квадратичное исследование, h(x, i) =( x % 8 + i / 2+ i2 / 2) % 8)
Описание слайда:
Квадратичное исследование, h(x, i) =( x % 8 + i / 2+ i2 / 2) % 8)

Слайд 212


Выводы: Квадратичное исследование менее подвержено опасности кластеризации, чем линейное. При квадратичном исследовании важен выбор функции так,...
Описание слайда:
Выводы: Квадратичное исследование менее подвержено опасности кластеризации, чем линейное. При квадратичном исследовании важен выбор функции так, чтобы перебрать все ячейки. Докажите, что при выборе функции вида ( h(x) + i / 2+ i2 / 2) % 2m ), мы попробуем все ячейки (от 0 до 2m – 1).

Слайд 213


Двойное хэширование Методы линейного и квадратичного исследования неприемлемы при большом числе коллизий Если мы добавляем N элементов с одинаковым...
Описание слайда:
Двойное хэширование Методы линейного и квадратичного исследования неприемлемы при большом числе коллизий Если мы добавляем N элементов с одинаковым значением хэш-функции, то для последнего элемента придется сделать N попыток его размещения Эту проблему может решить метод двойного хэширования

Слайд 214


Двойное хэширование Идея двойного хэширования в том, чтобы использовать вторую хэш-функцию для определения смещения h( k , i ) = ( h1(k) + ih2(k))...
Описание слайда:
Двойное хэширование Идея двойного хэширования в том, чтобы использовать вторую хэш-функцию для определения смещения h( k , i ) = ( h1(k) + ih2(k)) mod m Важно, чтобы для любого k h2(k) было взаимно простым с m

Слайд 215


Варианты: m – степень двойки h2(k) – нечетная для любого k, h2(k)= 2h3(k)+1 m – простое число h2(k) строго меньше m, например h1(k) = k % m h2(k) = 1...
Описание слайда:
Варианты: m – степень двойки h2(k) – нечетная для любого k, h2(k)= 2h3(k)+1 m – простое число h2(k) строго меньше m, например h1(k) = k % m h2(k) = 1 + ( k % m – 1 )

Слайд 216


Двойное хэширование, h1(x) = x % 11, h2(x) = 1 + x % 10
Описание слайда:
Двойное хэширование, h1(x) = x % 11, h2(x) = 1 + x % 10

Слайд 217


Двойное хэширование, h1(x) = x % 11, h2(x) = 1 + x % 10, поиск
Описание слайда:
Двойное хэширование, h1(x) = x % 11, h2(x) = 1 + x % 10, поиск

Слайд 218


Двойное хэширование: выводы Двойное хэширование – лучший из методов с открытой адресацией (т.е. с хранением значений непосредственно в массиве)
Описание слайда:
Двойное хэширование: выводы Двойное хэширование – лучший из методов с открытой адресацией (т.е. с хранением значений непосредственно в массиве)

Слайд 219


Удаление элементов из хэш-таблицы с открытой адресацией h1(x) = x % 11, h2(x) = 1 + x % 10
Описание слайда:
Удаление элементов из хэш-таблицы с открытой адресацией h1(x) = x % 11, h2(x) = 1 + x % 10

Слайд 220


Удаление элементов Просто удалить элемент нельзя – нарушится поиск тех, которые были добавлены после него Можно заменить значение на пометку Deleted
Описание слайда:
Удаление элементов Просто удалить элемент нельзя – нарушится поиск тех, которые были добавлены после него Можно заменить значение на пометку Deleted

Слайд 221


Удаление элементов из хэш-таблицы с открытой адресацией h1(x) = x % 11, h2(x) = 1 + x % 10
Описание слайда:
Удаление элементов из хэш-таблицы с открытой адресацией h1(x) = x % 11, h2(x) = 1 + x % 10

Слайд 222


Удаление элементов Специальное значение Deleted позволяет удалить элемент Но позиция в таблице после этого остается занятой и замедляет поиск Этот...
Описание слайда:
Удаление элементов Специальное значение Deleted позволяет удалить элемент Но позиция в таблице после этого остается занятой и замедляет поиск Этот подход годится, если потребность удалить элемент возникает в результате крайне экзотической ситуации Если действительно нужно удалять – используйте разрешение коллизий методом списков

Слайд 223


Выбор хэш-функции Мы будем считать, что элементы массива – целые числа Если они не целые числа – их всегда можно сделать целыми (возможно, очень...
Описание слайда:
Выбор хэш-функции Мы будем считать, что элементы массива – целые числа Если они не целые числа – их всегда можно сделать целыми (возможно, очень большими) Приведем примеры

Слайд 224


Пример: строки ANSI «Alexey» В памяти -
Описание слайда:
Пример: строки ANSI «Alexey» В памяти -

Слайд 225


Варианты хэш-функции Метод деления Метод умножения Универсальное хэширование
Описание слайда:
Варианты хэш-функции Метод деления Метод умножения Универсальное хэширование

Слайд 226


Метод деления h( k ) = k % m m – число позиций в хэш-таблице Преимущество – простота Недостаток – ограничения на величину m (нежелательна степень...
Описание слайда:
Метод деления h( k ) = k % m m – число позиций в хэш-таблице Преимущество – простота Недостаток – ограничения на величину m (нежелательна степень двойки – тогда на позицию влияют только младшие биты числа) Оптимально – простое число, далекое от степени двойки

Слайд 227


Метод умножения h( k ) = [ m ( kA - [ kA ] ) ] [x] – целая часть x Кнут предложил Можно избежать вещественных вычислений.
Описание слайда:
Метод умножения h( k ) = [ m ( kA - [ kA ] ) ] [x] – целая часть x Кнут предложил Можно избежать вещественных вычислений.

Слайд 228


Метод умножения Можно избежать вещественных вычислений. m=2w, A=s/2w, 0
Описание слайда:
Метод умножения Можно избежать вещественных вычислений. m=2w, A=s/2w, 0

Слайд 229


Универсальное хэширование Ясно, что для любой хэш-функции можно подобрать значения, при которых она работает плохо (коллизии на каждом шаге)....
Описание слайда:
Универсальное хэширование Ясно, что для любой хэш-функции можно подобрать значения, при которых она работает плохо (коллизии на каждом шаге). Злоумышленник может посылать нам такие значения и спровоцировать неработоспособность нашей программы.

Слайд 230


Универсальное хэширование Идея универсального хэширования – случайный выбор хэш-функции так, чтобы для любой сгенерированной злоумышленником...
Описание слайда:
Универсальное хэширование Идея универсального хэширования – случайный выбор хэш-функции так, чтобы для любой сгенерированной злоумышленником последовательности вероятность проблем была мала

Слайд 231


Универсальное хэширование Множество N хэш-функций hn(k) универсально, если для любых ключей k, l существует не больше N/m таких i, что hi(k)= hi(l)...
Описание слайда:
Универсальное хэширование Множество N хэш-функций hn(k) универсально, если для любых ключей k, l существует не больше N/m таких i, что hi(k)= hi(l) Т.е. для любой пары ключей вероятность коллизии не больше, чем вероятность совпадения двух случайных значений

Слайд 232


Универсальное хэширование Пример функции Пусть p – простое число, ключи – от 0 до p – 1 m – размер таблицы, h(k) – от 0 до m – 1 Рассмотрим семейство...
Описание слайда:
Универсальное хэширование Пример функции Пусть p – простое число, ключи – от 0 до p – 1 m – размер таблицы, h(k) – от 0 до m – 1 Рассмотрим семейство функций вида ha,b(k)=((ak+b)mod p )mod m a={ 1, …, p – 1 }, b = { 0, …, p – 1 } Оно является универсальным

Слайд 233


Другие применения хэш-функций Криптография. Криптография с закрытым ключом – зная ключ, можно построить хэш-функции для шифрования и расшифровки...
Описание слайда:
Другие применения хэш-функций Криптография. Криптография с закрытым ключом – зная ключ, можно построить хэш-функции для шифрования и расшифровки Криптография с открытым ключом. Кто угодно может зашифровать сообщение открытым ключом, а для расшифровки нужно знать секретный закрытый Электронная цифровая подпись. Кто угодно может открытым ключом расшифровать сообщение, а зашифровать – нужно знать закрытый. Если расшифровалось – значит, автор знает закрытый ключ

Слайд 234


Лабораторная работа №2. Реализация контейнеров данных.
Описание слайда:
Лабораторная работа №2. Реализация контейнеров данных.

Слайд 235


Реализация контейнеров данных Предлагаются индивидуальные варианты заданий, связанные с реализацией контейнеров Предпочтительна реализация...
Описание слайда:
Реализация контейнеров данных Предлагаются индивидуальные варианты заданий, связанные с реализацией контейнеров Предпочтительна реализация контейнера, сопровождаемая подготовкой доклада об контейнере Доклады целесообразны для контейнеров повышенной сложности

Слайд 236


Варианты заданий Реализовать класс списка с операциями добавления элемента, удаления элемента, доступа к первому элементу, доступа к следующему за...
Описание слайда:
Варианты заданий Реализовать класс списка с операциями добавления элемента, удаления элемента, доступа к первому элементу, доступа к следующему за данным. ([1], раздел 10.2) Реализовать класс бинарного дерева с операциями поиска, добавления и удаления элемента. ([1], раздел 12) Реализовать класс ассоциативного массива. ([1], раздел 12)

Слайд 237


Варианты заданий Реализовать класс массива элементов, значение которых может быть 0 или 1, с выделением 1 бита на каждый элемент (т.е. если мы храним...
Описание слайда:
Варианты заданий Реализовать класс массива элементов, значение которых может быть 0 или 1, с выделением 1 бита на каждый элемент (т.е. если мы храним 32 элемента – внутри должна лежать одна переменная типа int). Реализовать класс стека с операциями добавления элемента, удаления элемента, доступа к первому элементу. ([1], раздел 10.1) Реализовать класс очереди с операциями добавления элемента, удаления элемента, доступа к первому элементу. ([1], раздел 10.1)

Слайд 238


Варианты заданий повышенной сложности Реализовать класс АВЛ-дерева с операциями добавления элемента, удаления элемента, доступа к первому элементу...
Описание слайда:
Варианты заданий повышенной сложности Реализовать класс АВЛ-дерева с операциями добавления элемента, удаления элемента, доступа к первому элементу ([1], раздел 13, задача 13-3) Красно-черное дерево с операциями добавления элемента, удаления элемента, доступа к первому элементу ([1], раздел 13) Реализовать класс очереди с приоритетами на базе пирамиды с операциями добавления элемента, извлечения очередного элемента ([1], раздел 6.5).

Слайд 239


Тема 2.1. Библиотека STL как пример стандартной библиотеки языка программирования. Использование контейнеров и алгоритмов STL.
Описание слайда:
Тема 2.1. Библиотека STL как пример стандартной библиотеки языка программирования. Использование контейнеров и алгоритмов STL.

Слайд 240


Лекция 5. Шаблоны и пространства имен в C++
Описание слайда:
Лекция 5. Шаблоны и пространства имен в C++

Слайд 241


Шаблоны Рассмотрим функцию сортировки массива целых чисел и функцию сортировки телефонной книги (программа Sort). Они очень похожи. Но объединить их...
Описание слайда:
Шаблоны Рассмотрим функцию сортировки массива целых чисел и функцию сортировки телефонной книги (программа Sort). Они очень похожи. Но объединить их в одну функцию мы не можем – разные типы параметров.

Слайд 242


Шаблоны Для решения этой проблемы придуманы шаблоны. Шаблон – это «заготовка» функции, которая может быть конкретизирована несколькими способами....
Описание слайда:
Шаблоны Для решения этой проблемы придуманы шаблоны. Шаблон – это «заготовка» функции, которая может быть конкретизирована несколькими способами. Например, заготовка функции сортировки в SortTemplates

Слайд 243


SortTemplates Мы определили заготовку функции сортировки для произвольного типа. Когда компилятор видит попытку вызова Sort для массива целого типа,...
Описание слайда:
SortTemplates Мы определили заготовку функции сортировки для произвольного типа. Когда компилятор видит попытку вызова Sort для массива целого типа, он генерирует функцию, в которой вместо T подставлено int, включает ее в программу и вызывает ее. Потом компилятор видит Sort для TelephoneRecord, генерирует из заготовки еще одну функцию, и включает ее в программу.

Слайд 244


Шаблоны Параметром шаблона может быть не только тип данных, но и число (режим работы функции) Пример работы – функция Print в SortTemplates.
Описание слайда:
Шаблоны Параметром шаблона может быть не только тип данных, но и число (режим работы функции) Пример работы – функция Print в SortTemplates.

Слайд 245


Синтаксис определения функции-шаблона template < параметры шаблона > имя функции( параметры функции) { тело функции } Для параметра шаблона...
Описание слайда:
Синтаксис определения функции-шаблона template < параметры шаблона > имя функции( параметры функции) { тело функции } Для параметра шаблона указывается его тип (int, typename, class – что должно быть параметром) и имя. Имя параметра шаблона может использоваться в списке параметров функции и в теле функции.

Слайд 246


Вопрос Медленнее ли работа шаблона, чем работа нормальной функции?
Описание слайда:
Вопрос Медленнее ли работа шаблона, чем работа нормальной функции?

Слайд 247


Ответ Нет, не медленнее – это механизм уровня компиляции. Еще при сборке шаблон заменяется на несколько обычных функций, и вызов функции-шаблона...
Описание слайда:
Ответ Нет, не медленнее – это механизм уровня компиляции. Еще при сборке шаблон заменяется на несколько обычных функций, и вызов функции-шаблона заменяется на вызов одной из них.

Слайд 248


Шаблоны классов Точно так же, как функция, шаблоном может быть и класс. Шаблоны классов часто используются для классов векторов и других подобных...
Описание слайда:
Шаблоны классов Точно так же, как функция, шаблоном может быть и класс. Шаблоны классов часто используются для классов векторов и других подобных объектов, работающих с произвольным типом данных (например, int, float, double, TComplex_ - для вектора).

Слайд 249


Синтаксис определения класса-шаблона template class имя { //Определение класса. В нем могут //использоваться параметры шаблона … }; template имя...
Описание слайда:
Синтаксис определения класса-шаблона template class имя { //Определение класса. В нем могут //использоваться параметры шаблона … }; template имя класса:: имя метода (параметры метода ) { … }

Слайд 250


Пример шаблона класса Класс комплексного числа, работающего с типами double, float - ComplexTemplate
Описание слайда:
Пример шаблона класса Класс комплексного числа, работающего с типами double, float - ComplexTemplate

Слайд 251


Задание Написать класс вектора, который сможет работать как с вещественными, так и с комплексными числами. Также написать класс комплексного числа.
Описание слайда:
Задание Написать класс вектора, который сможет работать как с вещественными, так и с комплексными числами. Также написать класс комплексного числа.

Слайд 252


Частичная спецификация шаблона Предположим, некоторый класс работает одинаково для всех типов данных При этом для одного типа данных он работает...
Описание слайда:
Частичная спецификация шаблона Предположим, некоторый класс работает одинаково для всех типов данных При этом для одного типа данных он работает иначе (применения обсуждаются в лекции алгоритмы STL) Хочется использовать шаблон – но как это сделать?

Слайд 253


Частичная спецификация шаблона template < class T > class TemplateClass { }; template class TemplateClass < int > { };
Описание слайда:
Частичная спецификация шаблона template < class T > class TemplateClass { }; template class TemplateClass < int > { };

Слайд 254


Пространства имен В большой программе велик риск, что имена классов и функций будут повторяться. Для борьбы с этим придуманы пространства имен...
Описание слайда:
Пространства имен В большой программе велик риск, что имена классов и функций будут повторяться. Для борьбы с этим придуманы пространства имен (namespace).

Слайд 255


Пространства имен. Пример namespace N1 { class A { …}; } namespace N2 { class A { …}; } N1::A a1; N2::A a2;
Описание слайда:
Пространства имен. Пример namespace N1 { class A { …}; } namespace N2 { class A { …}; } N1::A a1; N2::A a2;

Слайд 256


Пространства имен Как видно на предыдущем слайде, заключив классы в пространство имен, мы можем не бояться совпадения имен двух классов и при...
Описание слайда:
Пространства имен Как видно на предыдущем слайде, заключив классы в пространство имен, мы можем не бояться совпадения имен двух классов и при обращении четко указать, с каким именно классом мы работаем. Если разработчик класса спрятал его в пространство имен, а нам писать везде имя пространства имен не хочется, можно написать один раз using namespace N1; Тогда после этой строчки можно к классам и функциям из N1 обращаться просто по имени, без N1::

Слайд 257


Лекция 6. Контейнеры STL – общие принципы
Описание слайда:
Лекция 6. Контейнеры STL – общие принципы

Слайд 258


Основные контейнеры vector – массив list – список valarray – вектор (массив с арифметическими операциями) set – упорядоченное множество. map –...
Описание слайда:
Основные контейнеры vector – массив list – список valarray – вектор (массив с арифметическими операциями) set – упорядоченное множество. map – ассоциативный массив

Слайд 259


Требования к реализации контейнеров Независимость реализации контейнера от типа используемых данных (могут предъявляться минимальные требования к...
Описание слайда:
Требования к реализации контейнеров Независимость реализации контейнера от типа используемых данных (могут предъявляться минимальные требования к типу – наличие копирования и проверки на равенство) Возможность одновременной работы с контейнером из нескольких потоков

Слайд 260


Требования к реализации контейнеров Возможность единообразной реализации операций (например, перебора) для нескольких контейнеров Константность...
Описание слайда:
Требования к реализации контейнеров Возможность единообразной реализации операций (например, перебора) для нескольких контейнеров Константность логически константных методов контейнера Независимость от используемых механизмов оперативной памяти Возможность хранения данных одного типа с сортировкой по разным критериям (для пирамид и деревьев поиска)

Слайд 261


Решения Для обеспечения независимости от типа элемента используем шаблоны C++ Для обеспечения независимости контейнера от конкретного способа...
Описание слайда:
Решения Для обеспечения независимости от типа элемента используем шаблоны C++ Для обеспечения независимости контейнера от конкретного способа выделения памяти передаем контейнеру объект-аллокатор, отвечающий за выделение и освобождение памяти (контейнер не использует new-delete, malloc-free). Существует аллокатор по умолчанию, работающий через new-delete.

Слайд 262


Решения Для возможности сортировки данных одного типа по разным критериям контейнер не использует оператор сравнения у объекта (т.е. нигде в...
Описание слайда:
Решения Для возможности сортировки данных одного типа по разным критериям контейнер не использует оператор сравнения у объекта (т.е. нигде в реализации контейнера нет кода if (a

Слайд 263


Решения Для обеспечения константности логически константных операций, устойчивости к многопоточности и возможности единообразной работы с несколькими...
Описание слайда:
Решения Для обеспечения константности логически константных операций, устойчивости к многопоточности и возможности единообразной работы с несколькими контейнерами вводим понятие итератора.

Слайд 264


Итераторы Итератором называется программный объект со следующими свойствами Объект связан с определенным объектом-контейнером и указывает на...
Описание слайда:
Итераторы Итератором называется программный объект со следующими свойствами Объект связан с определенным объектом-контейнером и указывает на конкретный элемент этого контейнера. У объекта можно вызвать оператор++ и он станет указывать на следующий элемент того же контейнера. Если ++ вызывается у итератора, указывающего на последний элемент, он переходит в состояние «ни на что не указывающего итератора» и мы можем проверить, находится ли итератор в этом состоянии

Слайд 265


Итераторы Каждому типу контейнера соответствует свой тип итератора. Для контейнеров STL этот тип можно получить как ContainerType::iterator...
Описание слайда:
Итераторы Каждому типу контейнера соответствует свой тип итератора. Для контейнеров STL этот тип можно получить как ContainerType::iterator (например, std::vector::iterator).

Слайд 266


Итераторы. Контрольный массив Есть массив в стиле C int a[100]; Существует ли итератор у этого конттейнера?
Описание слайда:
Итераторы. Контрольный массив Есть массив в стиле C int a[100]; Существует ли итератор у этого конттейнера?

Слайд 267


Итераторы. Контрольный вопрос. Да! Это переменная типа int*, указывающая на любой его элемент. Указывает на элемент контейнера Переходит к следующему...
Описание слайда:
Итераторы. Контрольный вопрос. Да! Это переменная типа int*, указывающая на любой его элемент. Указывает на элемент контейнера Переходит к следующему элементу вызовом ++. Если элементы закончились – переходит в невалидное состояние. Можно проверить состояние if ( ptr < a + 100 )

Слайд 268


Простейшее применение итераторов Практически все контейнеры STL имеют Метод begin() – возвращает итератор, указывающий на первый элемент Метод end()...
Описание слайда:
Простейшее применение итераторов Практически все контейнеры STL имеют Метод begin() – возвращает итератор, указывающий на первый элемент Метод end() – возвращает итератор, указывающий на элемент, следующий за последним. Пусть есть контейнер STL типа A с элементами типа T. Необходимо распечатать все элементы контейнера

Слайд 269


Простейшее применение итераторов void Print ( T element ) void PrintAll( A container ) { for ( A::iterator iter = container.begin() ; iter !=...
Описание слайда:
Простейшее применение итераторов void Print ( T element ) void PrintAll( A container ) { for ( A::iterator iter = container.begin() ; iter != container.end() ; iter++ ) { Print (*iter ); } }

Слайд 270


Простейшее применение итераторов Код работоспособен для любого контейнера STL и любого типа элемента (если для него существует функция Print)
Описание слайда:
Простейшее применение итераторов Код работоспособен для любого контейнера STL и любого типа элемента (если для него существует функция Print)

Слайд 271


Классификация итераторов Итератор всегда имеет оператор ++ Кроме того, он может иметь (а может – не иметь) еще ряд операций Доступ к объекту на...
Описание слайда:
Классификация итераторов Итератор всегда имеет оператор ++ Кроме того, он может иметь (а может – не иметь) еще ряд операций Доступ к объекту на чтение ( A=*iter) Доступ к объекту на запись ( *A=iter ) Доступ к полям объекта ( iter->field ) Методы итерации (iter--, iter+=N, iter -=N) Сравнение на равенство (iter1 == iter2, iter1 != iter 2) Сравнение на неравенство (iter1 < iter2)

Слайд 272


Классификация итераторов Мы хотим иметь возможность применять итераторы для чтения данных из потока ввода (например, из файла). Мы можем создать...
Описание слайда:
Классификация итераторов Мы хотим иметь возможность применять итераторы для чтения данных из потока ввода (например, из файла). Мы можем создать итератор файла целых чисел std::ifstream file_in( “in.txt” ); std::istream_iterator< int > iter_in ( file_in ); У такого оператора есть только две операции – итерация (++) и доступ к элементу на чтение Это итератор чтения

Слайд 273


Классификация итераторов Мы хотим использовать итераторы для записи данных в файл. std::ofstream file_out( “out.txt” ); std::ostream_iterator< int >...
Описание слайда:
Классификация итераторов Мы хотим использовать итераторы для записи данных в файл. std::ofstream file_out( “out.txt” ); std::ostream_iterator< int > iter_out ( file_out ); У такого итератора две операции – доступ на запись и переход к следующему элементу. Это итератор записи

Слайд 274


Классификация итераторов Любой итератор контейнера имеет Операцию доступа к объекту на чтение Операцию доступа к объекту на запись Операцию доступа к...
Описание слайда:
Классификация итераторов Любой итератор контейнера имеет Операцию доступа к объекту на чтение Операцию доступа к объекту на запись Операцию доступа к полям объекта Операцию сравнения на равенство Операцию ++ Если набор операций ограничивается этим, итератор называется однонаправленным итератором Например, однонаправленным является итератор однонаправленного списка

Слайд 275


Классификация итераторов Если к набору операций однонаправленного итератора добавить операцию – (переход к предыдущему элементу), мы получим...
Описание слайда:
Классификация итераторов Если к набору операций однонаправленного итератора добавить операцию – (переход к предыдущему элементу), мы получим двунаправленный итератор Двунаправленный итератор реализуется для бинарных деревьев поиска, словарей, двунаправленных списков

Слайд 276


Классификация итераторов Если к набору операций двунаправленного итератора добавить возможность сдвига на N позиций вперед или назад по контейнеру и...
Описание слайда:
Классификация итераторов Если к набору операций двунаправленного итератора добавить возможность сдвига на N позиций вперед или назад по контейнеру и возможность сравнения на неравенство, мы получим итератор с произвольным доступом Итератор с произвольным доступом реализуется для массива, двусторонней очереди

Слайд 277


Вопрос Ясно, что технически возможно реализовать сдвиг по списку или бинарному дереву поиска на N позиций вперед или назад Почему для них не...
Описание слайда:
Вопрос Ясно, что технически возможно реализовать сдвиг по списку или бинарному дереву поиска на N позиций вперед или назад Почему для них не реализуется итератор с произвольным доступом?

Слайд 278


Ответ Сдвиг на N позиций работал бы за время O(N) для списка и бинарного дерева Пользователь привык к тому, что для массива сдвиг работает за время...
Описание слайда:
Ответ Сдвиг на N позиций работал бы за время O(N) для списка и бинарного дерева Пользователь привык к тому, что для массива сдвиг работает за время O(1) Не следует вводить его в заблуждение Смещение на N реализуется как метод итераторов только для контейнеров, для которых оно работает за время O(1).

Слайд 279


Классификация итераторов
Описание слайда:
Классификация итераторов

Слайд 280


Компараторы Вспомним алгоритм сортировки пузырьком void sort ( T* A , int N ) { for ( i = 0 ; i < N – 1 ; i++ ) for ( j = 0 ; j < N – i ; j++ ) if (...
Описание слайда:
Компараторы Вспомним алгоритм сортировки пузырьком void sort ( T* A , int N ) { for ( i = 0 ; i < N – 1 ; i++ ) for ( j = 0 ; j < N – i ; j++ ) if ( A[ j ] < A[ j+1 ] ) { swap ( A[ j ] , A[ j + 1 ] ); } }

Слайд 281


Компараторы Мы можем применить этот алгоритм для любого типа, имеющего оператор сравнения Предположим, у нас есть два массива элементов одного типа T...
Описание слайда:
Компараторы Мы можем применить этот алгоритм для любого типа, имеющего оператор сравнения Предположим, у нас есть два массива элементов одного типа T – A и B. Мы хотим отсортировать их по разным критериям (список студентов по алфавиту и по успеваемости)

Слайд 282


Компараторы Использовать приведенный выше код мы не сможем Что делать?
Описание слайда:
Компараторы Использовать приведенный выше код мы не сможем Что делать?

Слайд 283


Компараторы Мы должны передать критерий сортировки как параметр функции или параметр шаблона Значит, критерий сортировки может быть либо типом, либо...
Описание слайда:
Компараторы Мы должны передать критерий сортировки как параметр функции или параметр шаблона Значит, критерий сортировки может быть либо типом, либо объектом Можно разрешить критерию сортировки быть и типом, и объектом

Слайд 284


Компараторы template < class TComparator > void sort ( T* A , int N , TComparator comparator ) { for ( i = 0 ; i < N – 1 ; i++ ) for ( j = 0 ; j < N...
Описание слайда:
Компараторы template < class TComparator > void sort ( T* A , int N , TComparator comparator ) { for ( i = 0 ; i < N – 1 ; i++ ) for ( j = 0 ; j < N – i ; j++ ) if ( comparator ( A[ j ] , A[ j+1 ] ) ) { swap ( A[ j ] , A[ j + 1 ] ); } }

Слайд 285


Компараторы class UsualComparator { bool operator()( T a , T b ) { return a < b; } }; T a[50]; sort ( a , 50 , UsualComparator() );
Описание слайда:
Компараторы class UsualComparator { bool operator()( T a , T b ) { return a < b; } }; T a[50]; sort ( a , 50 , UsualComparator() );

Слайд 286


Компараторы Код на предыдущем слайде приводит к обычной сортировке с использованием оператора сравнения. В функцию sort в качестве третьего параметра...
Описание слайда:
Компараторы Код на предыдущем слайде приводит к обычной сортировке с использованием оператора сравнения. В функцию sort в качестве третьего параметра придет созданный конструктором по умолчанию объект UsualComparator При необходимости сравнить два элемента массива они будут передаваться методу operator() этого объекта и сравниваться обычным образом

Слайд 287


Компараторы Мы можем реализовать другие типы компараторов и создать другие объекты компараторы Передавая их в качестве параметров функции, мы...
Описание слайда:
Компараторы Мы можем реализовать другие типы компараторов и создать другие объекты компараторы Передавая их в качестве параметров функции, мы настраиваем используемый функцией метод сравнения.

Слайд 288


Компараторы Компаратор можно передать и контейнеру, нуждающемуся в упорядочении своих элементов (неубывающей пирамиде, дереву поиска, словарю). Все...
Описание слайда:
Компараторы Компаратор можно передать и контейнеру, нуждающемуся в упорядочении своих элементов (неубывающей пирамиде, дереву поиска, словарю). Все контейнеры STL могут использовать компараторы. Компаратор по умолчанию – std::less, использует обычное сравнение (реализован примерно как приведенный выше Usual Comparator)

Слайд 289


Аллокаторы Компараторы позволяют настроить метод сравнения объекта Аналогично аллокаторы позволяют настроить метод выделения и освобождения памяти...
Описание слайда:
Аллокаторы Компараторы позволяют настроить метод сравнения объекта Аналогично аллокаторы позволяют настроить метод выделения и освобождения памяти для хранения объектов.

Слайд 290


Лекция 7. Контейнеры STL - реализация
Описание слайда:
Лекция 7. Контейнеры STL - реализация

Слайд 291


Массивы в STL - std::vector Реализует массив Тип элемента задается как параметр шаблона. Тип элемента должен иметь конструктор по умолчанию и...
Описание слайда:
Массивы в STL - std::vector Реализует массив Тип элемента задается как параметр шаблона. Тип элемента должен иметь конструктор по умолчанию и конструктор копирования Есть доступ по индексу с естественным синтаксисом за время O(1) vector a; … a[i]=3;

Слайд 292


Массивы в STL - std::vector Метод at – доступ по индексу с проверкой корректности, также за время O(1) Методы front(), back() предоставляют доступ к...
Описание слайда:
Массивы в STL - std::vector Метод at – доступ по индексу с проверкой корректности, также за время O(1) Методы front(), back() предоставляют доступ к первому и последнему элементу контейнера за время O(1). Методы push_back, pop_back позволяют добавлять и удалять последний элемент в среднем за время O(1). Работа push_back() в наихудшем случае медленнее из-за необходимости перевыделения памяти.

Слайд 293


Массивы в STL - std::vector std::vector определяет тип итератора std::vector::iterator. Этот итератор является итератором с произвольным доступом и...
Описание слайда:
Массивы в STL - std::vector std::vector определяет тип итератора std::vector::iterator. Этот итератор является итератором с произвольным доступом и имеет полный набор операций, характерных для итератора с произвольным доступом. Вектор определяет константный итератор, итератор с обратным порядком и константный итератор с обратным порядком. Вектор имеет функции begin(), end(), rbegin(), rend() для доступа к началу и концу последовательности при прямой и обратной итерации.

Слайд 294


Массивы в STL - std::vector
Описание слайда:
Массивы в STL - std::vector

Слайд 295


Массивы в STL - std::vector Для размещения элементов в памяти std::vector использует аллокатор. Тип аллокатора задается вторым параметром шаблона....
Описание слайда:
Массивы в STL - std::vector Для размещения элементов в памяти std::vector использует аллокатор. Тип аллокатора задается вторым параметром шаблона. Ссылка на конкретный экземпляр аллокатора, который следует использовать, может быть передана в конструктор вектора. По умолчанию используется стандартный класс STL std::allocator. Операции вставки элемента после заданного элемента (insert) и удаления элемента (erase) работают за линейное время.

Слайд 296


Списки в STL – std::list std::list реализует стратегию работы со списками независимо от типа хранимых элементов. Тип элемента задается как параметр...
Описание слайда:
Списки в STL – std::list std::list реализует стратегию работы со списками независимо от типа хранимых элементов. Тип элемента задается как параметр шаблона. Тип элемента должен иметь конструктор по умолчанию и конструктор копирования

Слайд 297


Списки в STL – std::list Методы front(), back() предоставляют доступ к первому и последнему элементу контейнера за время O(1). Методы push_back,...
Описание слайда:
Списки в STL – std::list Методы front(), back() предоставляют доступ к первому и последнему элементу контейнера за время O(1). Методы push_back, pop_back позволяют добавлять и удалять последний элемент за время O(1). Аналогично работают операции push_front, pop_front

Слайд 298


Списки в STL – std::list std::list определяет тип итератора std::list::iterator. Этот итератор является двунаправленным итератором и предоставляет...
Описание слайда:
Списки в STL – std::list std::list определяет тип итератора std::list::iterator. Этот итератор является двунаправленным итератором и предоставляет соответствующий набор операций. Список определяет константный итератор, итератор с обратным порядком и константный итератор с обратным порядком. Список имеет функции begin(), end(), rbegin(), rend() для доступа к началу и концу последовательности при прямой и обратной итерации.

Слайд 299


Списки в STL – std::list Используются аллокаторы так же, как в массиве. Операции вставки элемента в середину (после заданного элемента) и удаления...
Описание слайда:
Списки в STL – std::list Используются аллокаторы так же, как в массиве. Операции вставки элемента в середину (после заданного элемента) и удаления элемента работают за время O(1). Список определяет дополнительные операции, такие как merge (сортировка двух объединяемых списков), splice (перемещение элемента одного списка в другой без физического копирования, простой перестановкой указателей).

Слайд 300


Бинарное дерево поиска в STL – std::set std::set реализует работу с бинарным деревом поиска независимо от типа хранимых элементов. Тип элемента...
Описание слайда:
Бинарное дерево поиска в STL – std::set std::set реализует работу с бинарным деревом поиска независимо от типа хранимых элементов. Тип элемента задается как параметр шаблона. Тип элемента должен иметь конструктор по умолчанию и конструктор копирования. Необходим компаратор. Компаратор по умолчанию std::less использует оператор сравнения.

Слайд 301


Бинарное дерево поиска в STL – std::set Бинарный поиск реализуется методом find, работает за время O(logN) Доступны и работают за время O(logN)...
Описание слайда:
Бинарное дерево поиска в STL – std::set Бинарный поиск реализуется методом find, работает за время O(logN) Доступны и работают за время O(logN) операции lower_bound (поиск минимального элемента, больше либо равного данного) upper_bound (поиск минмального элемента, большего данного) equal_range (одновременный поиск lower_bound и upper_bound)

Слайд 302


Бинарное дерево поиска в STL – std::set Добавление элемента реализуется методом insert. Результатом добавления является итератор, указывающий на...
Описание слайда:
Бинарное дерево поиска в STL – std::set Добавление элемента реализуется методом insert. Результатом добавления является итератор, указывающий на добавленный элемент, и флаг, говорящий об успехе добавления. Для возврата двух значений используется std::pair Удаление элемента реализуется методом erase

Слайд 303


Бинарное дерево поиска в STL – std::set std::set определяет тип итератора std::set::iterator. Этот итератор является двунаправленным итератором и...
Описание слайда:
Бинарное дерево поиска в STL – std::set std::set определяет тип итератора std::set::iterator. Этот итератор является двунаправленным итератором и перебирает элементы в порядке возрастания. std::set определяет константный итератор, итератор с обратным порядком и константный итератор с обратным порядком. std::set имеет функции begin(), end(), rbegin(), rend()

Слайд 304


Бинарное дерево поиска в STL – std::set Используются аллокаторы так же, как в массиве Хранить несколько одинаковых значений нельзя (insert вернет...
Описание слайда:
Бинарное дерево поиска в STL – std::set Используются аллокаторы так же, как в массиве Хранить несколько одинаковых значений нельзя (insert вернет false). Если необходимо – используйте multi_set

Слайд 305


std::multi_set Набор операций аналогичен std::set find возвращает первый элемент, равный данному insert возвращает только итератор. Успех добавления...
Описание слайда:
std::multi_set Набор операций аналогичен std::set find возвращает первый элемент, равный данному insert возвращает только итератор. Успех добавления элемента гарантируется.

Слайд 306


std::multi_set Перебор элементов, равных данному: for ( TContainer::iterator iter = Container.lower_bound( x ) ; iter != Container.upper_bound( x ) ;...
Описание слайда:
std::multi_set Перебор элементов, равных данному: for ( TContainer::iterator iter = Container.lower_bound( x ) ; iter != Container.upper_bound( x ) ; iter ++ ) { … }

Слайд 307


Словарь в STL – std::map std::map реализует работу со словарем, имеющим произвольный тип ключа и произвольный тип значения. Тип ключа и тип значения...
Описание слайда:
Словарь в STL – std::map std::map реализует работу со словарем, имеющим произвольный тип ключа и произвольный тип значения. Тип ключа и тип значения – два первых параметра шаблона. Типы ключа и значения должны иметь конструктор по умолчанию и конструктор копирования. Необходима реализация компаратора – объекта, обеспечивающего сравнение ключей

Слайд 308


Словарь в STL – std::map Методы find, lower_bound, upper_bound, equal_range, insert, erase – аналогичны std::set Доступ на чтение и запись к...
Описание слайда:
Словарь в STL – std::map Методы find, lower_bound, upper_bound, equal_range, insert, erase – аналогичны std::set Доступ на чтение и запись к значению, соответствующему ключу, можно получить вот так: … = Map[ key ] Map[ key ] = … Словарь называют ассоциативным массивом Если элемента с таким ключом нет – он конструируется со значением по умолчанию

Слайд 309


Словарь в STL – std::map std::map определяет тип итератора std::map::iterator. Этот итератор является двунаправленным итератором и перебирает...
Описание слайда:
Словарь в STL – std::map std::map определяет тип итератора std::map::iterator. Этот итератор является двунаправленным итератором и перебирает элементы в порядке возрастания. Итератор указывает на пару (std::pair) ключ-значение std::map определяет константный итератор, итератор с обратным порядком и константный итератор с обратным порядком. std::map имеет функции begin(), end(), rbegin(), rend()

Слайд 310


Словарь в STL – std::map Используются аллокаторы так же, как в массиве Хранить несколько значений для одного ключа нельзя (insert вернет false). Если...
Описание слайда:
Словарь в STL – std::map Используются аллокаторы так же, как в массиве Хранить несколько значений для одного ключа нельзя (insert вернет false). Если необходимо – используйте multi_map

Слайд 311


std::multi_map Аналогичен std::map Не реализуется обращение по индексу map[ key ]. Как и в std::multiset, метод find выдает первый (в порядке...
Описание слайда:
std::multi_map Аналогичен std::map Не реализуется обращение по индексу map[ key ]. Как и в std::multiset, метод find выдает первый (в порядке итерации) из элементов с данным ключом; insert возвращает не пару (итератор, флаг успеха), а только итератор

Слайд 312


Двусторонняя очередь – std::deque std::deque реализует поведение двусторонней очереди std::deque позволяет задать тип элемента как параметр шаблона....
Описание слайда:
Двусторонняя очередь – std::deque std::deque реализует поведение двусторонней очереди std::deque позволяет задать тип элемента как параметр шаблона. Тип элемента должен иметь конструктор по умолчанию и конструктор копирования, необходимые для работы с ним.

Слайд 313


Двусторонняя очередь – std::deque Быстрый доступ по индексу – как в std::vector Deq[ i ] Deq.at( i ) Напомните, в чем разница?
Описание слайда:
Двусторонняя очередь – std::deque Быстрый доступ по индексу – как в std::vector Deq[ i ] Deq.at( i ) Напомните, в чем разница?

Слайд 314


Двусторонняя очередь – std::deque Методы front(), back() предоставляют доступ к первому и последнему элементу контейнера за время O(1). Методы...
Описание слайда:
Двусторонняя очередь – std::deque Методы front(), back() предоставляют доступ к первому и последнему элементу контейнера за время O(1). Методы push_back, pop_back позволяют добавлять и удалять последний элемент в среднем за время O(1). Работа push_back() в наихудшем случае медленнее из-за необходимости перевыделения памяти. Аналогичные операции с началом очереди – push_front, pop_front()

Слайд 315


Двусторонняя очередь – std::deque std::deque определяет тип итератора std::deque::iterator. Этот итератор является итератором с произвольным...
Описание слайда:
Двусторонняя очередь – std::deque std::deque определяет тип итератора std::deque::iterator. Этот итератор является итератором с произвольным доступом. Двусторонняя очередь определяет константный итератор, итератор с обратным порядком и константный итератор с обратным порядком. Двусторонняя очередь имеет функции begin(), end(), rbegin(), rend()

Слайд 316


Двусторонняя очередь – std::deque Для размещения элементов в памяти std::deque использует аллокатор так же, как массив. Операции вставки элемента в...
Описание слайда:
Двусторонняя очередь – std::deque Для размещения элементов в памяти std::deque использует аллокатор так же, как массив. Операции вставки элемента в середину (после заданного элемента) и удаления элемента работают за линейное время.

Слайд 317


Очередь – std::queue Реализует очередь Тип элемента задается как параметр шаблона. Необходимо существование конструктора по умолчанию и конструктора...
Описание слайда:
Очередь – std::queue Реализует очередь Тип элемента задается как параметр шаблона. Необходимо существование конструктора по умолчанию и конструктора копирования для элемента.

Слайд 318


Очередь – std::queue Набор операций включает методы push (добавить элемент в конец очереди) pop (извлечь элемент из начала) front (доступ к...
Описание слайда:
Очередь – std::queue Набор операций включает методы push (добавить элемент в конец очереди) pop (извлечь элемент из начала) front (доступ к начальному элементу) back (доступ к конечному элементу) size (доступ к количеству элементов) empty( проверка на пустоту) Все операции должны выполняться за время O(1).

Слайд 319


Очередь – std::queue Очередь может эффективно работать при различных стратегиях размещения данных в памяти, поэтому не навязывает одну стратегию Для...
Описание слайда:
Очередь – std::queue Очередь может эффективно работать при различных стратегиях размещения данных в памяти, поэтому не навязывает одну стратегию Для хранения своих данных std::queue создает контейнер какого-либо другого типа (либо использует готовый контейнер, заданный ей как параметр конструктора).

Слайд 320


Очередь – std::queue Тип внутреннего контейнера задается как второй параметр шаблона std::queue. Этот внутренний контейнер должен иметь операции...
Описание слайда:
Очередь – std::queue Тип внутреннего контейнера задается как второй параметр шаблона std::queue. Этот внутренний контейнер должен иметь операции size(), back(), front(), push_back() и pop_front(). Несложно убедиться, что из рассмотренных выше контейнеров нас устраивают std::deque и std::list.

Слайд 321


Стек – std::stack Реализует стек Тип элемента задается как параметр шаблона. Необходимо существование конструктора по умолчанию и конструктора...
Описание слайда:
Стек – std::stack Реализует стек Тип элемента задается как параметр шаблона. Необходимо существование конструктора по умолчанию и конструктора копирования для элемента.

Слайд 322


Стек – std::stack Набор операций включает push (добавить элемент) pop (извлечь последний добавленный элемент) back (доступ к последнему добавленному...
Описание слайда:
Стек – std::stack Набор операций включает push (добавить элемент) pop (извлечь последний добавленный элемент) back (доступ к последнему добавленному элементу) size (доступ к количеству элементов) empty( проверка на пустоту). Все операции должны выполняться за время O(1).

Слайд 323


Стек – std::stack Стек может быть реализован на базе различных контейнеров. Базовый контейнер может быть задан как параметр шаблона. От него...
Описание слайда:
Стек – std::stack Стек может быть реализован на базе различных контейнеров. Базовый контейнер может быть задан как параметр шаблона. От него требуется наличие методов size(), push_back(), pop_back(), back(). Базовым контейнером может быть std::vector, std::list, std::deque

Слайд 324


Очередь с приоритетами – std::priority_queue Очередь с приоритетами – это очередь, в которой элементам сопоставлен приоритет и первым в очереди...
Описание слайда:
Очередь с приоритетами – std::priority_queue Очередь с приоритетами – это очередь, в которой элементам сопоставлен приоритет и первым в очереди считается элемент с максимальным приоритетом

Слайд 325


Очередь с приоритетами – std::priority_queue Тип элемента задается как первый параметр шаблона. Необходимо существование конструктора по умолчанию и...
Описание слайда:
Очередь с приоритетами – std::priority_queue Тип элемента задается как первый параметр шаблона. Необходимо существование конструктора по умолчанию и конструктора копирования для элемента. Для сравнения двух элементов и проверки, какой из них больше (т.е. имеет больший приоритет) используется компаратор, задаваемый как третий параметр шаблона. По умолчанию используется компаратор std::less

Слайд 326


Очередь с приоритетами – std::priority_queue Набор операций включает push (добавить элемент) pop (извлечь элемент с максимальным приоритетом) top...
Описание слайда:
Очередь с приоритетами – std::priority_queue Набор операций включает push (добавить элемент) pop (извлечь элемент с максимальным приоритетом) top (доступ к элементу с максимальным приоритетом) size (доступ к количеству элементов) empty( проверка на пустоту). push и pop выполняются за время O(logN), остальные операции за время O(1).

Слайд 327


Очередь с приоритетами – std::priority_queue Как реализуется очередь с приоритетами?
Описание слайда:
Очередь с приоритетами – std::priority_queue Как реализуется очередь с приоритетами?

Слайд 328


Очередь с приоритетами – std::priority_queue Очередь с приоритетами строится на базе невозрастающей пирамиды Используется хранение пирамиды в виде...
Описание слайда:
Очередь с приоритетами – std::priority_queue Очередь с приоритетами строится на базе невозрастающей пирамиды Используется хранение пирамиды в виде массива

Слайд 329


Очередь с приоритетами – std::priority_queue Для хранения «пирамиды как массива» может использоваться любой контейнер, имеющий итератор с...
Описание слайда:
Очередь с приоритетами – std::priority_queue Для хранения «пирамиды как массива» может использоваться любой контейнер, имеющий итератор с произвольным доступом, т.е. std::vector или std::deque Тип используемого контейнера задается как параметр шаблона.

Слайд 330


Хэш-таблица – std::hash_map Класс std::hash_map реализует хэш-таблицу Как и std::map, std::hash_map хранит пары ключ-значение и требует уникальности...
Описание слайда:
Хэш-таблица – std::hash_map Класс std::hash_map реализует хэш-таблицу Как и std::map, std::hash_map хранит пары ключ-значение и требует уникальности ключа. Если уникальность не требуется или требуется хранение только ключей существуют классы std::hash_multimap, std::hash_set, std::hash_multiset. Типы ключа и значения задаются как параметры шаблона. Должны иметь конструкторы по умолчанию и конструкторы копирования

Слайд 331


Хэш-таблица – std::hash_map За вычисление хэш-функции и проверки на равенство отвечает специальный объект – хэш-компаратор. Он способен как вычислять...
Описание слайда:
Хэш-таблица – std::hash_map За вычисление хэш-функции и проверки на равенство отвечает специальный объект – хэш-компаратор. Он способен как вычислять значение хэш-функции, так и проверять два значения на равенство.

Слайд 332


Хэш-таблица – std::hash_map Необходимый размер хэш-таблицы вычисляется и динамически меняется. Задаваемая пользователем хэш-функция должна лишь...
Описание слайда:
Хэш-таблица – std::hash_map Необходимый размер хэш-таблицы вычисляется и динамически меняется. Задаваемая пользователем хэш-функция должна лишь вычислять требуемый индекс в диапазоне (в данный момент) от 0 до 232-1. Индекс особым преобразованием (зависящим от текущего размера массива) превращается в реальный индекс. Естественно, при изменении размера хэш-таблицы и преобразования гарантируется сохранение доступности ранее добавленных элементов. Для выделения памяти используется аллокатор, задаваемый как четвертый параметр шаблона.

Слайд 333


Не совсем контейнеры Существуют объекты библиотеки STL, которые не являются контейнерами но реализуют определенные возможности контейнеров Это...
Описание слайда:
Не совсем контейнеры Существуют объекты библиотеки STL, которые не являются контейнерами но реализуют определенные возможности контейнеров Это строки, вектора (valarray), битовые массивы, потоки ввода-вывода

Слайд 334


Строка – std::basic_string Строка является массивом символов Для представления символов могут использоваться различные типы данных (char, wchar_t,...
Описание слайда:
Строка – std::basic_string Строка является массивом символов Для представления символов могут использоваться различные типы данных (char, wchar_t, unsigned short, …) Не любой массив можно рассматривать как строку Строка реализуется в STL классом std::basic_string

Слайд 335


Строка как массив std::basic_string определяет тип итераторов с произвольным доступом – std::basic_string::iterator. std::basic_string имеет методы...
Описание слайда:
Строка как массив std::basic_string определяет тип итераторов с произвольным доступом – std::basic_string::iterator. std::basic_string имеет методы begin, end, rbegin, rend. Для строки возможно обращение к символу по индексу (operator [] и метод at() ). Существует метод push_back(). Есть возможность задания аллокаторов, используемых строкой для выделения памяти.

Слайд 336


Отличия строки std::basic_string требует от используемого типа символов расширенного набора операций См. char_traits std::basic_string определяет...
Описание слайда:
Отличия строки std::basic_string требует от используемого типа символов расширенного набора операций См. char_traits std::basic_string определяет дополнительные операции, характерные для строк (выдача null-terminated строки c_str, выдача подстроки substr, …)

Слайд 337


Вектор – std::val_array Есть доступ по индексу [] Есть метод size Реализует маетматические операции над векторами
Описание слайда:
Вектор – std::val_array Есть доступ по индексу [] Есть метод size Реализует маетматические операции над векторами

Слайд 338


Битовый массив – std::bit_set Возможен доступ к биту с помощью оператора [] Дополнительно реализуются побитовые операции
Описание слайда:
Битовый массив – std::bit_set Возможен доступ к биту с помощью оператора [] Дополнительно реализуются побитовые операции

Слайд 339


Потоки ввода-вывода и итераторы Основным инструментом ввода-вывода в STL являются потоки ввода-вывода Поток ввода – это объект, из которого можно...
Описание слайда:
Потоки ввода-вывода и итераторы Основным инструментом ввода-вывода в STL являются потоки ввода-вывода Поток ввода – это объект, из которого можно прочитать значения различных типов Потоком ввода может быть файл, строка, датчик, ввод с экрана консольного приложения Большинство потоков ввода в STL наследуются от std::basic_iostream

Слайд 340


Потоки ввода-вывода и итераторы Поток вывода – это устройство, в которое можно вывести значение того или иного типа Это может быть экран, строка,...
Описание слайда:
Потоки ввода-вывода и итераторы Поток вывода – это устройство, в которое можно вывести значение того или иного типа Это может быть экран, строка, файл,…

Слайд 341


Потоки ввода-вывода и итераторы Если мы читаем из потока или записываем в поток однотипные значения, целесообразно использовать для чтения и записи в...
Описание слайда:
Потоки ввода-вывода и итераторы Если мы читаем из потока или записываем в поток однотипные значения, целесообразно использовать для чтения и записи в поток итераторы. Для ввода данных из потока используется итератор чтения Для вывода данных в поток используется итератор записи

Слайд 342


Задание Напишите программу, читающую набор целых чисел из файла и записывающую их в другой файл Используйте итераторы чтения и записи Не забудьте...
Описание слайда:
Задание Напишите программу, читающую набор целых чисел из файла и записывающую их в другой файл Используйте итераторы чтения и записи Не забудьте решить проблему разделителей

Слайд 343


Лабораторная работа №3. Использование стандартных контейнеров данных
Описание слайда:
Лабораторная работа №3. Использование стандартных контейнеров данных

Слайд 344


Задание Разработать программу на языке C++, реализующую функциональность в соответствии с вариантом задания. Настоятельно рекомендуется использование...
Описание слайда:
Задание Разработать программу на языке C++, реализующую функциональность в соответствии с вариантом задания. Настоятельно рекомендуется использование стандартных контейнеров из библиотеки STL.

Слайд 345


Варианты задания Реализовать программу, хранящую совокупность многоугольников на плоскости и позволяющую организовать быстрый поиск многоугольников,...
Описание слайда:
Варианты задания Реализовать программу, хранящую совокупность многоугольников на плоскости и позволяющую организовать быстрый поиск многоугольников, попадающих в заданный прямоугольник Необходимо обеспечить добавление многоугольника и поиск многоугольников, попадающих в прямоугольник. Предложение: Храните один массив многоугольников и 4 массива или бинарных дерева номеров многоугольников, упорядоченных по самой левой, самой правой, самой верхней и самой нижней точке многоугольника. Это позволит быстро отфильтровать многоугольники, лежащие заведомо выше, ниже, левее или правее данного прямоугольника, и только для оставшихся реализовывать медленные алгоритмы содержательной проверки пересечения прямоугольника.

Слайд 346


Варианты задания Реализовать программу, хранящую совокупность отрезков на плоскости и поддерживающую добавление отрезка и быстрый поиск отрезков,...
Описание слайда:
Варианты задания Реализовать программу, хранящую совокупность отрезков на плоскости и поддерживающую добавление отрезка и быстрый поиск отрезков, попадающих в прямоугольник Предложение: Храните один массив отрезков и 4 массива или бинарных дерева номеров отрезков многоугольников, упорядоченных по самой левой, самой правой, самой верхней и самой нижней точке отрезка. Это позволит быстро отфильтровать отрезки, лежащие заведомо выше, ниже, левее или правее данного прямоугольника, и только для оставшихся реализовывать медленные алгоритмы содержательной проверки пересечения прямоугольника.

Слайд 347


Варианты задания Реализовать программу, хранящую множество шариков, летающих в комнате, поддерживающих добавление и удаление шарика и выдающей...
Описание слайда:
Варианты задания Реализовать программу, хранящую множество шариков, летающих в комнате, поддерживающих добавление и удаление шарика и выдающей информацию о 5 ближайших столкновениях шарика со стенкой. Движение шарика равномерное и прямолинейное, удар упругий, возможностью столкновения шариков друг с другом пренебречь. При добавлении шарика указываются его положение, скорость и время начала полета. В электронной картотеке библиотеки для каждой книги хранится номер зала, стеллажа и полки. При этом необходим быстрый поиск книги по фамилии автора (считаем, что автор один) и по слову из названия (падежами и т.д. пренебрегаем, считаем, что слово должно быть в названии точно таким же, как его вводит пользователь). Разработать программу электронной картотеки с операциями добавления книги и поиска.

Слайд 348


Варианты задания Реализовать систему регистрации сделок на бирже. Для каждой сделки указывается, какой товар продан, в какой день, какое количество и...
Описание слайда:
Варианты задания Реализовать систему регистрации сделок на бирже. Для каждой сделки указывается, какой товар продан, в какой день, какое количество и по какой цене. Необходимо по запросу выводить среднюю цену на данный товар в данный день. Реализовать систему, хранящую информацию о доходах налогоплательщиков (для каждого налогоплательщика указывается его заработок в каждом году). Система должна быть в состоянии дать отчет о доходах данного налогоплательщика в данные годы и отчет о среднем уровне дохода в каждом году.

Слайд 349


Варианты задания Реализовать программу электронного магазина, поддерживающую три операции Добавление информации о появлении в продаже очередной...
Описание слайда:
Варианты задания Реализовать программу электронного магазина, поддерживающую три операции Добавление информации о появлении в продаже очередной партии товара (указывается цена, количество и наименование). Покупку партии товара. Формирование отчета об имеющихся на складе товарах. Реализовать программу, хранящую информацию о вкладчиках банка. Для каждого вкладчика указывается фамилия и номер паспорта, и для каждого из его вкладов – сумма, валюта и срок возврата. Поддерживать операции добавления и снятия вклада, отчета о всех вкладах и об отдельном вкладчике.

Слайд 350


Варианты задания Реализовать программу, которая получает результаты измерений одной и той же меняющейся величины 10 датчиками. Если больше 3 значений...
Описание слайда:
Варианты задания Реализовать программу, которая получает результаты измерений одной и той же меняющейся величины 10 датчиками. Если больше 3 значений подряд, приходящих с одного датчика не соответствуют значениям с остальных – объявить датчик испортившимся и более не учитывать. Операции Добавить результат очередных измерений (10 чисел) Вывести среднее значение величины по итогам последнего измерения. Вывести информацию об исправных датчиках.

Слайд 351


Варианты задания При голосовании приходят результаты в виде «На участке № такой-то такая-то партия получила столько-то голосов.» Система должна в...
Описание слайда:
Варианты задания При голосовании приходят результаты в виде «На участке № такой-то такая-то партия получила столько-то голосов.» Система должна в любой момент выдать информацию о доступных результатах по данному участку и о суммарном количестве проголосовавших за партию. Несколько датчиков установлены в разных местах планеты и присылают свои результаты измерения температуры (указывая номер датчика, температуру и время). Необходимо по запросу пользователя выводить отчет о любом датчике (все его измерения), или данные со всех датчиков, говорящие о температуре в заданном интервале времени.

Слайд 352


Варианты задания Корабли присылают в каждый момент времени данные о своей скорости и направлении и свои координаты. Необходимо предупредить...
Описание слайда:
Варианты задания Корабли присылают в каждый момент времени данные о своей скорости и направлении и свои координаты. Необходимо предупредить пользователя, если данные не согласованы (т.е. если изменение координат не соответствует скорости и направлению движения корабля). Землю считать плоской. В базу данных вводятся результаты футбольных матчей. По запросу пользователя выдать турнирную таблицу чемпионата (количество побед, ничьих, поражений, очков и разницу мячей у каждой команды)

Слайд 353


Варианты задания Завод по сборке автомобилей покупает комплекты комплектующих и производит автомобили из них. Необходимо хранить информацию о...
Описание слайда:
Варианты задания Завод по сборке автомобилей покупает комплекты комплектующих и производит автомобили из них. Необходимо хранить информацию о количестве комплектов на складе комплектующих и количестве готовых к отгрузке автомобилей. Основные действия – это покупка N комплектов комплектующих, производство N автомобилей, продажа N автомобилей, выдача отчета о количестве комплектующих и автомобилей на складах. В базе данных животных в зоопарке хранится информация о виде животного, кличке и количестве потребляемой в день еды (сколько килограммов какого продукта необходимо в неделю). Необходимо формировать отчеты о потребностях данного животного, о потребностях всех животных данного вида и сообщать о суммарной потребности в данном продукте в неделю.

Слайд 354


Варианты задания Подразделения фирмы, нуждающиеся в покупке компьютеров, вносят заказы в базу данных. Отдел закупок вносит информацию о ценах на...
Описание слайда:
Варианты задания Подразделения фирмы, нуждающиеся в покупке компьютеров, вносят заказы в базу данных. Отдел закупок вносит информацию о ценах на соответствующее оборудование. Необходимо иметь возможность вывести всю информацию о потребностях каждого подразделения и о данном виде оборудования. Предприятие хранит базу данных о сотрудниках. Фамилия, №паспорта, должность, зарплата. Основные операции – прием на работу, увольнение, перевод на другую должность, изменение зарплаты, отчет о всех сотрудниках, выдача информации о конкретном сотруднике.

Слайд 355


Варианты задания Операционная система хранит базу данных процессов. Процесс имеет постоянный приоритет (константа, задается пользователем) и...
Описание слайда:
Варианты задания Операционная система хранит базу данных процессов. Процесс имеет постоянный приоритет (константа, задается пользователем) и дополнительный приоритет (у каждого следующего процесса на 1 меньше, чем у предыдущего – чтобы те, кто дольше ждал, имели преимущество). Набор поддерживаемых операций: Добавить процесс с данным именем и постоянным приоритетом Выбрать из очереди процесс с наибольшим приоритетом (суммой постоянного и дополнительного). Он отработает и завершится. Выбрать из очереди процесс с наибольшим приоритетом (суммой постоянного и дополнительного). Он отработает, после этого нужно снова поставить его в очередь (уже с новым дополнительным приоритетом). Все операции должны работать за логарифмическое время. Указание: priority_queue.

Слайд 356


Лекция 8. Стандартные алгоритмы STL. Простейший стандартный алгоритм for_each Возможности применения алгоритмов на примере for_each Другие алгоритмы...
Описание слайда:
Лекция 8. Стандартные алгоритмы STL. Простейший стандартный алгоритм for_each Возможности применения алгоритмов на примере for_each Другие алгоритмы STL.

Слайд 357


std::for_each Алгоритм std::for_each заключается в вызове заданной функции для каждого элемента контейнера for_each не делает предположений о типе...
Описание слайда:
std::for_each Алгоритм std::for_each заключается в вызове заданной функции для каждого элемента контейнера for_each не делает предположений о типе контейнера – достаточно, чтобы у него был итератор чтения for_each не модифицирует перебираемые элементы

Слайд 358


std::for_each - пример for_each( v1.begin() , v1.end() , Print ) эквивалентно for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) {...
Описание слайда:
std::for_each - пример for_each( v1.begin() , v1.end() , Print ) эквивалентно for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { Print( *iter ); }

Слайд 359


std::for_each В приведенном примере мы вызывали функцию Print, единственным параметром которой был элемент контейнера, для которого она вызывалась...
Описание слайда:
std::for_each В приведенном примере мы вызывали функцию Print, единственным параметром которой был элемент контейнера, для которого она вызывалась Это простейший случай Чаще встречаются другие ситуации

Слайд 360


Пример – вызов функции с несколькими параметрами for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { Print( *iter , file ); }
Описание слайда:
Пример – вызов функции с несколькими параметрами for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { Print( *iter , file ); }

Слайд 361


Пример – вызов метода класса с несколькими параметрами for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { Processor.Process( *iter...
Описание слайда:
Пример – вызов метода класса с несколькими параметрами for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { Processor.Process( *iter , param2 ); }

Слайд 362


std::for_each Ясно, что мы должны уметь применять for_each для таких ситуаций – иначе этот механизм бесполезен
Описание слайда:
std::for_each Ясно, что мы должны уметь применять for_each для таких ситуаций – иначе этот механизм бесполезен

Слайд 363


Шаблоны. Взаимозаменяемость классов и функций for_each – это шаблон функции. Шаблоны C++ являются механизмом времени компиляции. Это означает, что...
Описание слайда:
Шаблоны. Взаимозаменяемость классов и функций for_each – это шаблон функции. Шаблоны C++ являются механизмом времени компиляции. Это означает, что еще до компиляции происходит замена for_each на соответствующий код (примерно такая, как показано выше)

Слайд 364


Шаблоны. Взаимозаменяемость классов и функций Но это означает, что с точки зрения for_each не важно, что такое Print Это может быть функция с одним...
Описание слайда:
Шаблоны. Взаимозаменяемость классов и функций Но это означает, что с точки зрения for_each не важно, что такое Print Это может быть функция с одним параметром Это может быть класс, имеющий метод operator() с одним параметром

Слайд 365


Класс-функция class Printer { public: Printer( std::ostream& stream ) :Stream(stream) {} void operator()(int a ) { Print( Stream , a ); } private:...
Описание слайда:
Класс-функция class Printer { public: Printer( std::ostream& stream ) :Stream(stream) {} void operator()(int a ) { Print( Stream , a ); } private: std::ostream& Stream; };

Слайд 366


Класс-функция С точки зрения шаблона for_each, объект класса Printer – полный аналог функции, имеющей один параметр. И мы можем дать указание...
Описание слайда:
Класс-функция С точки зрения шаблона for_each, объект класса Printer – полный аналог функции, имеющей один параметр. И мы можем дать указание for_each вызвать этот объект (т.е. его метод operator() ) для всех элементов контейнера

Слайд 367


Класс-функция Printer printer( stream1 ); std::for_each( v1.begin() , v1.end() , printer ); эквивалентно for ( v1::iterator iter = v1.begin() ; iter...
Описание слайда:
Класс-функция Printer printer( stream1 ); std::for_each( v1.begin() , v1.end() , printer ); эквивалентно for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { printer( *iter ); //или printer.operator()(*iter) }

Слайд 368


Класс-функция И это уже эквивалентно for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { Print( *iter , stream1 ); }
Описание слайда:
Класс-функция И это уже эквивалентно for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { Print( *iter , stream1 ); }

Слайд 369


Вызов метода класса for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { processor.Process( *iter ); }
Описание слайда:
Вызов метода класса for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { processor.Process( *iter ); }

Слайд 370


Вызов метода класса class ProcessorAdapter { public: ProcessorAdapter ( Processor& processor ) :Proc( processor ) {} void operator()( int cur ) {...
Описание слайда:
Вызов метода класса class ProcessorAdapter { public: ProcessorAdapter ( Processor& processor ) :Proc( processor ) {} void operator()( int cur ) { Proc.Process( cur ); } private: Processor& Proc; };

Слайд 371


Вызов метода класса ProcessorAdapter adapter( processor ); std::for_each( int_vector.begin() , int_vector.end() , adapter ); эквивалентно for (...
Описание слайда:
Вызов метода класса ProcessorAdapter adapter( processor ); std::for_each( int_vector.begin() , int_vector.end() , adapter ); эквивалентно for ( v1::iterator iter = v1.begin() ; iter != v1.end() ; iter++ ) { adapter.operator()( *iter ); }

Слайд 372


Возвращаемое значение for_each Функция for_each возвращает тот объект, метод operator() которого она вызвала для всех элементов контейнера Это...
Описание слайда:
Возвращаемое значение for_each Функция for_each возвращает тот объект, метод operator() которого она вызвала для всех элементов контейнера Это означает, что если вызов метода приводил к изменению состояния объекта, то измененное состояние нам доступно

Слайд 373


Задание Реализуйте поиск максимума массива вещественных чисел через for_each
Описание слайда:
Задание Реализуйте поиск максимума массива вещественных чисел через for_each

Слайд 374


Решение class MaxSearch { public: MaxSearch( double first ) :CurMax( first ) {} void operatorI()( double cur ) { if ( cur > CurMax ) CurMax= cur; }...
Описание слайда:
Решение class MaxSearch { public: MaxSearch( double first ) :CurMax( first ) {} void operatorI()( double cur ) { if ( cur > CurMax ) CurMax= cur; } double GetMax() { return CurMax; } private: double CurMax; };

Слайд 375


Решение std::vector < double > double _vector; … MaxSearch search(*double _vector.begin() ); search = std::for_each( double_vector.begin() ,...
Описание слайда:
Решение std::vector < double > double _vector; … MaxSearch search(*double _vector.begin() ); search = std::for_each( double_vector.begin() , double_vector.end() , search ); double max = search.GetMax();

Слайд 376


Вызовы функций с параметрами – готовые механизмы Если мы хотим вызвать для всех методов контейнера функцию void Print ( std::istream& stream , int a...
Описание слайда:
Вызовы функций с параметрами – готовые механизмы Если мы хотим вызвать для всех методов контейнера функцию void Print ( std::istream& stream , int a ) { stream

Слайд 377


Вызовы функций с параметрами – готовые механизмы Другие готовые механизмы для вызова функций и методов классов из for_each есть в библиотеке Boost...
Описание слайда:
Вызовы функций с параметрами – готовые механизмы Другие готовые механизмы для вызова функций и методов классов из for_each есть в библиотеке Boost (boost::bind)

Слайд 378


Методы поиска Все методы принимают два итератора (указывающие на начало последовательности и на следующий за последним элемент) Возвращают итератор,...
Описание слайда:
Методы поиска Все методы принимают два итератора (указывающие на начало последовательности и на следующий за последним элемент) Возвращают итератор, указывающий на найденный элемент (или на следующий за последним, если элемент не найден)

Слайд 379


Методы поиска find – поиск равного данному find_if – поиск соответствующего условию find_first_of – поиск в первой последовательности первого...
Описание слайда:
Методы поиска find – поиск равного данному find_if – поиск соответствующего условию find_first_of – поиск в первой последовательности первого символа, присутствующего во второй(задается компаратор) adjacent_find – поиск двух равных последовательных символов (задается компаратор)

Слайд 380


Задание Как найти первый символ, больший квадрата предыдущего? Предложите два метода
Описание слайда:
Задание Как найти первый символ, больший квадрата предыдущего? Предложите два метода

Слайд 381


Поиск нарушения порядка в массиве в стиле C bool Test( double a , double b ) { return a > b; } … double array[4]={3,5,35,27}; … double* ptr =...
Описание слайда:
Поиск нарушения порядка в массиве в стиле C bool Test( double a , double b ) { return a > b; } … double array[4]={3,5,35,27}; … double* ptr = std::adjacent_find( array , array+4 , Test );

Слайд 382


Методы подсчета count – подсчет элементов, равных данному count_if – подсчет количества элементов, соответствующих условию Входные параметры – два...
Описание слайда:
Методы подсчета count – подсчет элементов, равных данному count_if – подсчет количества элементов, соответствующих условию Входные параметры – два итератора и условие для count_if Возвращаемое значение?

Слайд 383


Методы подсчета Фиксированный тип – не годится. Вариант: template < class TIterator , class TValue > TIterator::difference_type count( TIterator...
Описание слайда:
Методы подсчета Фиксированный тип – не годится. Вариант: template < class TIterator , class TValue > TIterator::difference_type count( TIterator begin , TIterator end , TValue value )

Слайд 384


Методы подсчета В данном случае в классе TIterator должно быть что-то вроде class TIterator { public: typedef int difference_type; }; Ваша оценка...
Описание слайда:
Методы подсчета В данном случае в классе TIterator должно быть что-то вроде class TIterator { public: typedef int difference_type; }; Ваша оценка решения?

Слайд 385


Методы подсчета В этом случае мы не сможем использовать указатель как итератор массива в стиле C и нам не удастся написать int A[ 5 ]; … int n =...
Описание слайда:
Методы подсчета В этом случае мы не сможем использовать указатель как итератор массива в стиле C и нам не удастся написать int A[ 5 ]; … int n = std::count( A , A+5 , 3 );

Слайд 386


Методы подсчета - решение Определим шаблонный класс iterator_traits вида template < class TIterator > class iterator_traits { typedef...
Описание слайда:
Методы подсчета - решение Определим шаблонный класс iterator_traits вида template < class TIterator > class iterator_traits { typedef TIterator::difference_type difference_type; };

Слайд 387


Методы подсчета - решение template < class TIterator , class TValue > iterator_traits::difference_type count( TIterator begin , TIterator end ,...
Описание слайда:
Методы подсчета - решение template < class TIterator , class TValue > iterator_traits::difference_type count( TIterator begin , TIterator end , TValue value )

Слайд 388


Методы подсчета - решение Внешне кажется, что ничего не изменилось iterator_traits::difference_type это эквивалент TIterator::difference_type Но...
Описание слайда:
Методы подсчета - решение Внешне кажется, что ничего не изменилось iterator_traits::difference_type это эквивалент TIterator::difference_type Но теперь пользователь может воспользоваться частичной спецификацией шаблонов

Слайд 389


Методы подсчета - решение Определим частичную спецификацию шаблона iterator_traits вида template< > class iterator_traits { typedef int...
Описание слайда:
Методы подсчета - решение Определим частичную спецификацию шаблона iterator_traits вида template< > class iterator_traits { typedef int difference_type; };

Слайд 390


Методы подсчета - решение int A[ 5 ]; … int n = std::count( A , A+5 , 3 ); A и A+5 имеет тип int* Поэтому тип возвращаемого значения –...
Описание слайда:
Методы подсчета - решение int A[ 5 ]; … int n = std::count( A , A+5 , 3 ); A и A+5 имеет тип int* Поэтому тип возвращаемого значения – Iterator_traits::difference_type

Слайд 391


Минимумы и максимумы max_element и min_element ищут максимальный или минимальный элемент последовательности Принимают итераторы, указывающие на...
Описание слайда:
Минимумы и максимумы max_element и min_element ищут максимальный или минимальный элемент последовательности Принимают итераторы, указывающие на начало и конец, и функцию сравнения (или объект-компаратор)

Слайд 392


Сравнение последовательностей equal – проверка на равенство mismatch – поиск первого различия lexicographical_compare Задается объект-компаратор Типы...
Описание слайда:
Сравнение последовательностей equal – проверка на равенство mismatch – поиск первого различия lexicographical_compare Задается объект-компаратор Типы элементов могут различаться.

Слайд 393


Сравнение последовательностей В одном массиве строки, в другом числа Нужно проверить, что длина строки номер i в первом массиве равна числу номер i...
Описание слайда:
Сравнение последовательностей В одном массиве строки, в другом числа Нужно проверить, что длина строки номер i в первом массиве равна числу номер i во втором

Слайд 394


Подпоследовательности search - поиск первого вхождения подпоследовательности в последовательность. Задаются 4 итератора и компаратор find_end - поиск...
Описание слайда:
Подпоследовательности search - поиск первого вхождения подпоследовательности в последовательность. Задаются 4 итератора и компаратор find_end - поиск последнего вхождения подпоследовательности в последовательность. Задаются 4 итератора и компаратор search_n – поиск в последовательности идущих подряд n чисел, равных данному. Задаются два итератора, значение и компаратор

Слайд 395


Задание Предложите два способа поиска трех нечетных чисел подряд – с помощью search и search_n
Описание слайда:
Задание Предложите два способа поиска трех нечетных чисел подряд – с помощью search и search_n

Слайд 396


Копирование сopy копирует одну последовательность в другую Задаются 3 итератора – начало и конец первой последовательности и начало второй Первые –...
Описание слайда:
Копирование сopy копирует одну последовательность в другую Задаются 3 итератора – начало и конец первой последовательности и начало второй Первые – итераторы чтения, второй – итератор записи Пользователь отвечает за то, чтобы во второй последовательности было достаточно места

Слайд 397


Копирование vector2.resize( vector1.size() ); std::copy( vector1.begin() , vector1.end() , vector2.begin() ); или std::copy( vector1.begin() ,...
Описание слайда:
Копирование vector2.resize( vector1.size() ); std::copy( vector1.begin() , vector1.end() , vector2.begin() ); или std::copy( vector1.begin() , vector1.end() , std::back_inserter( vector2 ) );

Слайд 398


Вопрос Корректен ли код, копирующий 5 первых элементов последовательности в конец? const int N = …; double a[N]; … std::copy( a , a+5 , a+N-5 );
Описание слайда:
Вопрос Корректен ли код, копирующий 5 первых элементов последовательности в конец? const int N = …; double a[N]; … std::copy( a , a+5 , a+N-5 );

Слайд 399


Копирование Не корректен, если N < 10. Мы затрем элементы до того, как их копировать. Если есть двунаправленный итератор, можно использовать const...
Описание слайда:
Копирование Не корректен, если N < 10. Мы затрем элементы до того, как их копировать. Если есть двунаправленный итератор, можно использовать const int N = …; double a[N]; … std::copy_backward( a , a+5 , a+N-5 );

Слайд 400


Преобразование Преобразование последовательности double TransformT( double c ) { return 1.8 * c + 32; } std::vector temperatures; … std::transform(...
Описание слайда:
Преобразование Преобразование последовательности double TransformT( double c ) { return 1.8 * c + 32; } std::vector temperatures; … std::transform( temperatures.begin() , temperatures.end() , temperatures.begin() , TransformT )

Слайд 401


Преобразование двух последовательностей Результат преобразования записывается в третью. double Fib( double a , double b ) { return a + b; } …...
Описание слайда:
Преобразование двух последовательностей Результат преобразования записывается в третью. double Fib( double a , double b ) { return a + b; } … std::vector < int > vec_fib; vec_fib.push_back( 0 ); vec_fib.push_back( 1 ); vec_fib.resize( 42 ); transform( vec_fib.begin() , vec_fib.begin() + 40 , vec_fib.begin() + 1 , vec_fib.begin() + 2 , Fib );

Слайд 402


Удаление
Описание слайда:
Удаление

Слайд 403


Удаление
Описание слайда:
Удаление

Слайд 404


Удаление Результатом remove является итератор, указывающий на элемент, следующий за последним оставшимся После remove следует специфичным для...
Описание слайда:
Удаление Результатом remove является итератор, указывающий на элемент, следующий за последним оставшимся После remove следует специфичным для контейнера способом освободить память из-под всех элементов, начиная с возвращенного значения. std::vector vec; … std::vector::iterator iter = std::remove

Слайд 405


Удаление remove_if – удаление элементов, соответствующих условию Задача: удалить первые 10 отрицательных чисел unique – встретив несколько идущих...
Описание слайда:
Удаление remove_if – удаление элементов, соответствующих условию Задача: удалить первые 10 отрицательных чисел unique – встретив несколько идущих подряд равных элементов, заменяет их на один. Может получать компаратор.

Слайд 406


Удаление remove_copy – копирует элементы во вторую последовательность, удаляя равные данному remove_copy_if - копирует элементы во вторую...
Описание слайда:
Удаление remove_copy – копирует элементы во вторую последовательность, удаляя равные данному remove_copy_if - копирует элементы во вторую последовательность, удаляя соответствующие условию unique_copy - копирует элементы во вторую последовательность, заменяя последовательности равных на один элемент

Слайд 407


Замена Аналогично удалению, но заменяет на заданное значение std:replace std::replace_if std::replace_copy std::replace_copy_if
Описание слайда:
Замена Аналогично удалению, но заменяет на заданное значение std:replace std::replace_if std::replace_copy std::replace_copy_if

Слайд 408


Заполнение std::fill – принимает начальный и конечный итераторы, значение std::fill_n – принимает итератор вывода, значение и количество элементов,...
Описание слайда:
Заполнение std::fill – принимает начальный и конечный итераторы, значение std::fill_n – принимает итератор вывода, значение и количество элементов, которое необходимо вывести

Слайд 409


Заполнение. Примеры std::vector< int> int_vector; int_vector.resize( 100 ); std::fill( int_vector.begin() , int_vector.end() , 0 ); std::vector< int>...
Описание слайда:
Заполнение. Примеры std::vector< int> int_vector; int_vector.resize( 100 ); std::fill( int_vector.begin() , int_vector.end() , 0 ); std::vector< int> int_vector; std::fill_n( back_inserter( int_vector.begin() ), 100 , 0 ); std::ostream_iterator outiter( std::cout ); std::fill_n( outiter , 100 , 0 );

Слайд 410


Заполнение Можно задать не значение, а функцию (которая будет вызвана для каждого элемента контейнера и ее возвращаемое значение записано в элемент)...
Описание слайда:
Заполнение Можно задать не значение, а функцию (которая будет вызвана для каждого элемента контейнера и ее возвращаемое значение записано в элемент) или объект-генератор (имеющий оператор () ). std::generate std::generate_n

Слайд 411


Заполнение class FibonacciGenerator { public: FibonacciGenerator() :First( 0 ),Second( 1 ) {} int operator()() { int val = First; First = Second;...
Описание слайда:
Заполнение class FibonacciGenerator { public: FibonacciGenerator() :First( 0 ),Second( 1 ) {} int operator()() { int val = First; First = Second; Second = Second + val; return val; } private: int First; int Second; }; std::ostream_iterator outiter( std::cout ); std::generate_n( outiter , 40 , FibonacciGenerator() );

Слайд 412


Перестановки std::swap – меняет местами два значения, принимая ссылки std::iter_swap – меняет местами значения, на которые указывают заданные...
Описание слайда:
Перестановки std::swap – меняет местами два значения, принимая ссылки std::iter_swap – меняет местами значения, на которые указывают заданные итераторы std::swap_ranges – меняет местами две последовательности

Слайд 413


Перестановки Какой иетратор требуется для выполнения swap_ranges?
Описание слайда:
Перестановки Какой иетратор требуется для выполнения swap_ranges?

Слайд 414


Перестановки std::reverse, std::reverse_copy – переставляет в обратном порядке std::rotate, std::rotate_copy – циклический сдвиг std::random_shuffle...
Описание слайда:
Перестановки std::reverse, std::reverse_copy – переставляет в обратном порядке std::rotate, std::rotate_copy – циклический сдвиг std::random_shuffle – случайные перестановки

Слайд 415


Лексикографические перестановки abc acb bac bca cab cba
Описание слайда:
Лексикографические перестановки abc acb bac bca cab cba

Слайд 416


Лексикографические перестановки prev_permutation – предыдущая перестановка next_permutation – следующая перестановка Принимает два двунаправленных...
Описание слайда:
Лексикографические перестановки prev_permutation – предыдущая перестановка next_permutation – следующая перестановка Принимает два двунаправленных итератора и объект-компаратор

Слайд 417


Сортировки std::sort – сортировка (обычно быстрая сортировка) std::stable_sort – сортировка с сохранением порядка равных элементов std::partial_sort...
Описание слайда:
Сортировки std::sort – сортировка (обычно быстрая сортировка) std::stable_sort – сортировка с сохранением порядка равных элементов std::partial_sort – сортирует первые N элементов std::partial_sort_copy – копирует заданное число минимальных элементов во вторую последовательность

Слайд 418


Сортировки vector2.resize( 10 ); std::partial_sort_copy( vector1.begin() , vector1.end() , vector2.begin() , vector2.end() );
Описание слайда:
Сортировки vector2.resize( 10 ); std::partial_sort_copy( vector1.begin() , vector1.end() , vector2.begin() , vector2.end() );

Слайд 419


Сортировки std::nth_element – поиск порядковой статистики (гарантирует, что на позиции N будет тот элемент, который был бы там в отсортированном...
Описание слайда:
Сортировки std::nth_element – поиск порядковой статистики (гарантирует, что на позиции N будет тот элемент, который был бы там в отсортированном массиве, меньшие левее, большие правее)

Слайд 420


Сортировки class Student { public: double AverageGrade() const; }; class StudentComparator { public: bool operator( const Student& a , const Student&...
Описание слайда:
Сортировки class Student { public: double AverageGrade() const; }; class StudentComparator { public: bool operator( const Student& a , const Student& b ) { return a.AverageGrade() > b.AverageGrade(); } }; std::vector vec_studs; … vec_studs.nth_element( vec_studs.begin() , vec_studs.begin() + 10 , vec_studs.end() );

Слайд 421


Бинарный поиск std::binary_search – бинарный поиск в отсортированной последовательности (true, если найден) std::lower_bound - первый элемент,...
Описание слайда:
Бинарный поиск std::binary_search – бинарный поиск в отсортированной последовательности (true, если найден) std::lower_bound - первый элемент, больший либо равный данному. std::upper_bound - первый элемент, больший данного. std::equal_range - оба этих элемента. Достаточно однонаправленного итератора, осмысленно только для итератора с произвольным доступом

Слайд 422


Слияние std::merge – объединяет две отсортированные последовательности в одну std::inplace_merge – объединение двух отсортированных половин...
Описание слайда:
Слияние std::merge – объединяет две отсортированные последовательности в одну std::inplace_merge – объединение двух отсортированных половин последовательности на месте

Слайд 423


Слияние for ( int k = 1 ; k < n; k *= 2 ) { for ( int i = 0 ; i + k < n ; i+= 2 * k ) { int last = std::min( i + 2 * k , n ); std::inplace_merge(...
Описание слайда:
Слияние for ( int k = 1 ; k < n; k *= 2 ) { for ( int i = 0 ; i + k < n ; i+= 2 * k ) { int last = std::min( i + 2 * k , n ); std::inplace_merge( array + i , array + i + k , array + last ); } }

Слайд 424


Разделение Делим последовательность на группы, соответствующие условию и не соответствующие ему - partition Если нужно сохранить порядок внутри групп...
Описание слайда:
Разделение Делим последовательность на группы, соответствующие условию и не соответствующие ему - partition Если нужно сохранить порядок внутри групп – stable_partition Результат – итератор, указывающий на начало второй группы.

Слайд 425


Пирамиды std::make_heap – расставляет элементы в последовательности так, как они лежали бы в невозрастающей пирамиде в виде массива push_heap –...
Описание слайда:
Пирамиды std::make_heap – расставляет элементы в последовательности так, как они лежали бы в невозрастающей пирамиде в виде массива push_heap – включает элемент в пирамиду pop_heap – извдлекает из пирамиды максимальный элемент и ставит последним sort_heap – преобразует пирамиду в отсортированный массив

Слайд 426


make_heap
Описание слайда:
make_heap

Слайд 427


Вопрос Как реализовать пирамидальную сортировку вектора?
Описание слайда:
Вопрос Как реализовать пирамидальную сортировку вектора?

Слайд 428


Пирамидальная сортировка std::make_heap ( vec.begin() , vec.end() ); std::sort_heap( vec.begin() , vec.end() )
Описание слайда:
Пирамидальная сортировка std::make_heap ( vec.begin() , vec.end() ); std::sort_heap( vec.begin() , vec.end() )

Слайд 429


Множественные операции Реализуются над отсортированными последовательностями std::includes – проверка включения std::set_union - объединение...
Описание слайда:
Множественные операции Реализуются над отсортированными последовательностями std::includes – проверка включения std::set_union - объединение std::set_intersection - пересечение std::set_difference – множественная разность std::set_symmetric_difference – присутствующие в одном и олько одном множестве элементы

Слайд 430


Лабораторная работа №4. Использование стандартных алгоритмов STL.
Описание слайда:
Лабораторная работа №4. Использование стандартных алгоритмов STL.

Слайд 431


Задание Разработать программу на языке C++, реализующую функциональность в соответствии с вариантом задания. Настоятельно рекомендуется использование...
Описание слайда:
Задание Разработать программу на языке C++, реализующую функциональность в соответствии с вариантом задания. Настоятельно рекомендуется использование стандартных алгоритмов из библиотеки STL.

Слайд 432


Варианты задания Реализовать программу хранения массива геометрических фигур в двумерном пространстве. Фигура – это окружность или N-угольник....
Описание слайда:
Варианты задания Реализовать программу хранения массива геометрических фигур в двумерном пространстве. Фигура – это окружность или N-угольник. Программа должна поддерживать поворот и растяжение/сжатие всех фигур относительно заданного пользователем центра. Необходима устойчивость программы к выбору контейнера данных.

Слайд 433


Варианты задания Реализовать программу, хранящую в отсортированном массиве список пользователей операционной системы с информацией об имени и пароле....
Описание слайда:
Варианты задания Реализовать программу, хранящую в отсортированном массиве список пользователей операционной системы с информацией об имени и пароле. Пользователь вводит имя и пароль, программа сообщает, правильный ли пароль. Указание: используйте функцию binary_search Пожелание: Чтобы не хранить пароль в открытом виде, придумайте хэш-функцию, и храните имя и хэш-значение пароля. При проверке применяйте хэш-функцию к паролю и сравнивайте хэш-значения.

Слайд 434


Варианты задания Разработайте программу, хранящую базу данных телефонной компании (фамилия, номер, остаток денег на счету) и по запросу пользователя...
Описание слайда:
Варианты задания Разработайте программу, хранящую базу данных телефонной компании (фамилия, номер, остаток денег на счету) и по запросу пользователя выдающую количество пользователей с отрицательным остатком и их список. Указание: можно использовать count_if, remove_copy_if, for_each…, equal_range

Слайд 435


Варианты задания Реализуйте программу, заполняющую массив фиксированной длины прочитанными из файла значениями или случайными значениями (по выбору...
Описание слайда:
Варианты задания Реализуйте программу, заполняющую массив фиксированной длины прочитанными из файла значениями или случайными значениями (по выбору пользователя). Указание: generate Пожелание: используя стандартную библиотеку boost и функцию boost::bind, реализуйте чтение из файла в generate, не открывая файл каждый раз и не завождя глобальных переменных.

Слайд 436


Варианты задания Реализуйте программу, считывающие из двух файлов два набора строчек и проверяющую их на совпадение. Указание: generate, equal...
Описание слайда:
Варианты задания Реализуйте программу, считывающие из двух файлов два набора строчек и проверяющую их на совпадение. Указание: generate, equal Пожелание: используя стандартную библиотеку boost и функцию boost::bind, реализуйте чтение из файла в generate, не открывая файл каждый раз и не заводя глобальных переменных.

Слайд 437


Варианты задания База данных телефонной компании реализована в форме отсортированного массива. Периодически приходит дополнение к базе – также...
Описание слайда:
Варианты задания База данных телефонной компании реализована в форме отсортированного массива. Периодически приходит дополнение к базе – также отсортированный массив, который необходимо включить в главный. Указание: используйте merge или inplace_merge. В словаре – пары слово + объяснение. Напечатать список статей об отраслях науки, в которых слово заканчивается на «логия». Указание: Например, remove_copy_if или for_each.

Слайд 438


Варианты задания Прочитайте из файла последовательность чисел и выведите все возможные их перестановки в лексикографическом порядке (первая – по...
Описание слайда:
Варианты задания Прочитайте из файла последовательность чисел и выведите все возможные их перестановки в лексикографическом порядке (первая – по возрастанию, последняя – по убыванию). Указание: sort, next_permutation В текстовом файле – список сотрудников фирмы. Распечатайте списки сотрудников, принятых на работу до и после 01.01.2005. Указание: partition

Слайд 439


Литература Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. 2-ое издание. : Пер.с англ. –М.: ИД «Вильямс», 2007. Б....
Описание слайда:
Литература Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. 2-ое издание. : Пер.с англ. –М.: ИД «Вильямс», 2007. Б. Страуструп. Язык программирования C++. Специальное издание. Пер. с англ. –М.: ООО «Бином-Пресс», 2005 г. - 1104с.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию