Подводные камни: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
Строка 13: | Строка 13: | ||
3) Детерминированность | 3) Детерминированность | ||
− | Также отдельно стоит заметить, что у <code>set</code> есть свой собственный бинпоиск - не рекомендуется использовать <code>lower_bound(set.begin(), set.end())< | + | Также отдельно стоит заметить, что у <code>set</code> есть свой собственный бинпоиск - не рекомендуется использовать <code>lower_bound(set.begin(), set.end())</code>, так как он работает за размер сета |
+ | |||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 13:43, 22 октября 2019
Особенности multiset
и map
: удаление элементов, count(x)
работает за $log(size) + amount(x)$.
swap
контейнеров за $O(1)$ a.swap(b)
list.size()
работает за $O(size)$
Компаратор должен удовлетворять следующим условиям :
1) Антисимметричность
2) Транзитивность
3) Детерминированность
Также отдельно стоит заметить, что у set
есть свой собственный бинпоиск - не рекомендуется использовать lower_bound(set.begin(), set.end())
, так как он работает за размер сета
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin