--- title: Контейнеры seo: title: Контейнеры — C++ Developer description: "Тема «Контейнеры» для собеседования C++ Developer. Расскажите о контейнерах стандартной библиотеки vector, list, map, unordered_map. Какая разница между std::set, std::map, std::unordered_multimap?" --- [Все темы C++ Developer](/c-developer) ## Расскажите о контейнерах стандартной библиотеки vector, list, map, unordered_map [#q-14bee738d69b818e8ca7c4592dd36aff] Контейнеры стандартной библиотеки C++: {/* prettier-ignore */} 1. std::vector: - Тип: Динамический массив. - Особенности: Быстрый доступ по индексу (O(1)), эффективное добавление элементов в конец. - Использование: Подходит для случаев, когда требуется быстрый случайный доступ и частое добавление элементов в конец. ```cpp std::vector vec = {1, 2, 3}; ``` 1. std::list: - Тип: Двусвязный список. - Вставка одного элемента и удаление элемента по уже известному итератору занимают O(1). Поиск нужной позиции требует обхода и может стоить O(n); оператора индексного доступа у std::list нет. - Использование: Подходит для случаев, когда важны операции вставки и удаления. ```cpp std::list lst = {1, 2, 3}; ``` 1. std::map: - Тип: Отсортированный ассоциативный контейнер. - Особенности: Хранит пары "ключ-значение" в отсортированном порядке, доступ к элементам и операции вставки/удаления имеют сложность O(log n). - Использование: Подходит для случаев, когда важен порядок и требуется быстрый поиск по ключу. ```cpp std::map mp = {{1, "one"}, {2, "two"}}; ``` 1. std::unordered_map: - Тип: Неотсортированный ассоциативный контейнер (хеш-таблица). - Поиск одного ключа в std::unordered\_map имеет среднюю сложность O(1), в худшем случае O(n). Для вставки и удаления по ключу также важны коллизии и возможное расширение; среднюю оценку нельзя выдавать за гарантию худшего случая. - Использование: Подходит для случаев, когда важна скорость поиска, но не важен порядок элементов. ```cpp std::unordered_map ump = {{1, "one"}, {2, "two"}}; ``` :::note[Ссылки для изучения] 1. [Типы контейнеров в C++](https://metanit.com/cpp/tutorial/7.1.php) ::: --- ## Какая разница между std::set, std::map, std::unordered_multimap? [#q-14bee738d69b811688d4ef86b08b71f0] Разница между std::set , std::map , std::unordered_multimap : {/* prettier-ignore */} 1. std::set: - Тип: Отсортированный контейнер. - Хранение: Хранит уникальные элементы в отсортированном порядке. - Доступ: Быстрый поиск, добавление и удаление (O(log n)). - Использование: Подходит для хранения уникальных элементов, когда важен порядок. ```cpp std::set s = {1, 2, 3}; ``` 1. std::map: - Тип: Отсортированный ассоциативный контейнер. - Хранение: Хранит пары "ключ-значение" в отсортированном порядке по ключу. - Доступ: Быстрый поиск, добавление и удаление по ключу (O(log n)). - Использование: Подходит для хранения пар "ключ-значение", когда важен порядок и уникальность ключей. ```cpp std::map m = {{1, "one"}, {2, "two"}}; ``` 1. std::unordered_multimap: - Тип: Неотсортированный ассоциативный контейнер (хеш-таблица). - Хранение: Хранит пары "ключ-значение" без определённого порядка. Позволяет дублирование ключей. - Поиск имеет среднюю сложность O(1), в худшем случае O(n). Получение или удаление всех элементов с данным ключом зависит также от числа совпадений; erase(key) не имеет безусловной оценки O(1). - Использование: Подходит для хранения пар "ключ-значение" с дублирующимися ключами, когда важна скорость поиска, но не важен порядок. ```cpp std::unordered_multimap ump = {{1, "one"}, {2, "two"}, {1, "uno"}}; ``` :::note[Ссылки для изучения] 1. [Типы контейнеров в C++](https://metanit.com/cpp/tutorial/7.1.php) ::: --- ## В чем разница между vector и list и в каких случаях их лучше использовать? [#q-14bee738d69b8196a683dc34a81ed2a9] Главные отичия между vector и list : #### std::vector: - Тип: Динамический массив. - Хранение: Элементы хранятся в непрерывной области памяти. - Доступ: Быстрый доступ по индексу ( O(1)). - Операции: Эффективное добавление элементов в конец, но медленное удаление/вставка в середине или начале (O(n)). - Использование: Подходит для случаев, когда требуется быстрый случайный доступ и добавление элементов в конец. ```cpp std::vector vec = {1, 2, 3}; ``` #### std::list: - Тип: Двусвязный список. - Хранение: Элементы хранятся не в непрерывной области памяти, а связаны указателями. - Доступ: Медленный доступ по индексу ( O(n)). - Вставка одного элемента и удаление элемента по уже известному итератору занимают O(1). Поиск нужной позиции требует обхода и может стоить O(n); оператора индексного доступа у std::list нет. - Использование: Подходит для случаев, когда важны операции вставки и удаления в середине или начале, а доступ по индексу не является критичным. ```cpp std::list lst = {1, 2, 3}; ``` #### Когда использовать: - std::vector: Когда требуется быстрый случайный доступ и частое добавление элементов в конец. - std::list: Когда важны операции вставки и удаления в любом месте, а неэффективный доступ по индексу не является проблемой. :::note[Ссылки для изучения] 1. [Типы контейнеров в C++](https://metanit.com/cpp/tutorial/7.1.php) ::: --- ## Чем отличаются std::map и std::unordered_map? [#q-14bee738d69b81db878be680d9836437] В стандартной библиотеке есть std::map и std::unordered_map; типа std::hashmap нет. Их различия: #### std::map: - Тип: Отсортированный ассоциативный контейнер. - Хранение: Хранит пары "ключ-значение" в отсортированном порядке по ключу. - Доступ: Быстрый поиск, добавление и удаление по ключу ( O(log n)), благодаря реализации на основе сбалансированного бинарного дерева. - Использование: Подходит для случаев, когда важен порядок ключей или требуется последовательный доступ. ```cpp std::map m = {{1, "one"}, {2, "two"}}; ``` #### std::unordered_map: - Тип: Неотсортированный ассоциативный контейнер (хеш-таблица). - Хранение: Хранит пары "ключ-значение" без определённого порядка. - Поиск одного ключа в std::unordered_map имеет среднюю сложность O(1), в худшем случае O(n). Для вставки и удаления по ключу также важны коллизии и возможное расширение; среднюю оценку нельзя выдавать за гарантию худшего случая. - Использование: Подходит для случаев, когда порядок ключей не важен, а важна максимальная скорость доступа. ```cpp std::unordered_map um = {{1, "one"}, {2, "two"}}; ``` #### Основные различия: - Порядок элементов: std::map хранит элементы в отсортированном порядке, std::unordered_map - в произвольном порядке. - Поиск одного ключа в std::unordered_map имеет среднюю сложность O(1), в худшем случае O(n). Для вставки и удаления по ключу также важны коллизии и возможное расширение; среднюю оценку нельзя выдавать за гарантию худшего случая. - Использование памяти: std::unordered_map обычно требует больше памяти из-за хеш-таблицы. :::note[Ссылки для изучения] 1. [Типы контейнеров в C++](https://metanit.com/cpp/tutorial/7.1.php) :::