Для std::set (основан на сбалансированном двоичном дереве поиска):
Для list, vector, set и unordered_set назовите сложность поиска элемента по значению и удаления найденного элемента, а также правила инвалидирования итераторов.
Для std::set (основан на сбалансированном двоичном дереве поиска):
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Для std::set (основан на сбалансированном двоичном дереве поиска):
- Вставка (
insertодного элемента): O(log N) - Удаление (
eraseодного элемента): O(log N) - Поиск (
find): O(log N)
Для std::unordered_set (основан на хеш-таблице):
-
В среднем:
- Вставка (
insertодного элемента): O(1) - Удаление (
eraseодного элемента): O(1) - Поиск (
find): O(1)
- Вставка (
-
В худшем случае (при сильных коллизиях в хеш-таблице):
- Вставка (
insertодного элемента): O(N) - Удаление (
eraseодного элемента): O(N) - Поиск (
find): O(N)
- Вставка (
Таблица сравнения:
| Операция | std::set |
std::unordered_set (в среднем) |
std::unordered_set (в худшем случае) |
|---|---|---|---|
| Вставка единичного элемента | O(log N) | O(1) | O(N) |
| Удаление единичного элемента | O(log N) | O(1) | O(N) |
| Поиск единичного элемента | O(log N) | O(1) | O(N) |