Контейнеры

Все темы C++ Developer

Расскажите о контейнерах стандартной библиотеки `vector`, `list`, `map`, `unordered_map`

Контейнеры стандартной библиотеки C++:

std::vector:
- Тип: Динамический массив.
- Особенности: Быстрый доступ по индексу (O(1)), эффективное добавление элементов в конец.
- Использование: Подходит для случаев, когда требуется быстрый случайный доступ и частое добавление элементов в конец.
```
std::vector<int> vec = {1, 2, 3};
```
std::list:
- Тип: Двусвязный список.
- Вставка одного элемента и удаление элемента по уже известному итератору занимают O(1). Поиск нужной позиции требует обхода и может стоить O(n); оператора индексного доступа у std::list нет.
- Использование: Подходит для случаев, когда важны операции вставки и удаления.
```
std::list<int> lst = {1, 2, 3};
```
std::map:
- Тип: Отсортированный ассоциативный контейнер.
- Особенности: Хранит пары “ключ-значение” в отсортированном порядке, доступ к элементам и операции вставки/удаления имеют сложность O(log n).
- Использование: Подходит для случаев, когда важен порядок и требуется быстрый поиск по ключу.
```
std::map<int, std::string> mp = {{1, "one"}, {2, "two"}};
```
std::unordered_map:
- Тип: Неотсортированный ассоциативный контейнер (хеш-таблица).
- Поиск одного ключа в std::unordered_map имеет среднюю сложность O(1), в худшем случае O(n). Для вставки и удаления по ключу также важны коллизии и возможное расширение; среднюю оценку нельзя выдавать за гарантию худшего случая.
- Использование: Подходит для случаев, когда важна скорость поиска, но не важен порядок элементов.
```
std::unordered_map<int, std::string> ump = {{1, "one"}, {2, "two"}};
```

Какая разница между `std::set`, `std::map`, `std::unordered_multimap`?

Разница между std::set , std::map , std::unordered_multimap :

std::set:
- Тип: Отсортированный контейнер.
- Хранение: Хранит уникальные элементы в отсортированном порядке.
- Доступ: Быстрый поиск, добавление и удаление (O(log n)).
- Использование: Подходит для хранения уникальных элементов, когда важен порядок.
```
std::set<int> s = {1, 2, 3};
```
std::map:
- Тип: Отсортированный ассоциативный контейнер.
- Хранение: Хранит пары “ключ-значение” в отсортированном порядке по ключу.
- Доступ: Быстрый поиск, добавление и удаление по ключу (O(log n)).
- Использование: Подходит для хранения пар “ключ-значение”, когда важен порядок и уникальность ключей.
```
std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
```
std::unordered_multimap:
- Тип: Неотсортированный ассоциативный контейнер (хеш-таблица).
- Хранение: Хранит пары “ключ-значение” без определённого порядка. Позволяет дублирование ключей.
- Поиск имеет среднюю сложность O(1), в худшем случае O(n). Получение или удаление всех элементов с данным ключом зависит также от числа совпадений; erase(key) не имеет безусловной оценки O(1).
- Использование: Подходит для хранения пар “ключ-значение” с дублирующимися ключами, когда важна скорость поиска, но не важен порядок.
```
std::unordered_multimap<int, std::string> ump = {{1, "one"}, {2, "two"}, {1, "uno"}};
```

В чем разница между `vector` и `list` и в каких случаях их лучше использовать?

Главные отичия между vector и list :

`std::vector`:

Тип: Динамический массив.
Хранение: Элементы хранятся в непрерывной области памяти.
Доступ: Быстрый доступ по индексу ( O(1)).
Операции: Эффективное добавление элементов в конец, но медленное удаление/вставка в середине или начале (O(n)).
Использование: Подходит для случаев, когда требуется быстрый случайный доступ и добавление элементов в конец.
```
std::vector<int> vec = {1, 2, 3};
```

`std::list`:

Тип: Двусвязный список.
Хранение: Элементы хранятся не в непрерывной области памяти, а связаны указателями.
Доступ: Медленный доступ по индексу ( O(n)).
Вставка одного элемента и удаление элемента по уже известному итератору занимают O(1). Поиск нужной позиции требует обхода и может стоить O(n); оператора индексного доступа у std::list нет.
Использование: Подходит для случаев, когда важны операции вставки и удаления в середине или начале, а доступ по индексу не является критичным.
```
std::list<int> lst = {1, 2, 3};
```

Когда использовать:

std::vector: Когда требуется быстрый случайный доступ и частое добавление элементов в конец.
std::list: Когда важны операции вставки и удаления в любом месте, а неэффективный доступ по индексу не является проблемой.

Чем отличаются std::map и std::unordered_map?

В стандартной библиотеке есть std::map и std::unordered_map; типа std::hashmap нет. Их различия:

`std::map`:

Тип: Отсортированный ассоциативный контейнер.
Хранение: Хранит пары “ключ-значение” в отсортированном порядке по ключу.
Доступ: Быстрый поиск, добавление и удаление по ключу ( O(log n)), благодаря реализации на основе сбалансированного бинарного дерева.
Использование: Подходит для случаев, когда важен порядок ключей или требуется последовательный доступ.
```
std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
```

`std::unordered_map`:

Тип: Неотсортированный ассоциативный контейнер (хеш-таблица).
Хранение: Хранит пары “ключ-значение” без определённого порядка.
Поиск одного ключа в std::unordered_map имеет среднюю сложность O(1), в худшем случае O(n). Для вставки и удаления по ключу также важны коллизии и возможное расширение; среднюю оценку нельзя выдавать за гарантию худшего случая.
Использование: Подходит для случаев, когда порядок ключей не важен, а важна максимальная скорость доступа.
```
std::unordered_map<int, std::string> um = {{1, "one"}, {2, "two"}};
```

Основные различия:

Порядок элементов: std::map хранит элементы в отсортированном порядке, std::unordered_map - в произвольном порядке.
Поиск одного ключа в std::unordered_map имеет среднюю сложность O(1), в худшем случае O(n). Для вставки и удаления по ключу также важны коллизии и возможное расширение; среднюю оценку нельзя выдавать за гарантию худшего случая.
Использование памяти: std::unordered_map обычно требует больше памяти из-за хеш-таблицы.