Контейнеры

Все темы C++ Developer

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

1. std::vector:

   • Тип: Динамический массив.

   • Особенности: Быстрый доступ по индексу (O(1)), эффективное добавление элементов в конец.

   • Использование: Подходит для случаев, когда требуется быстрый случайный доступ и частое добавление элементов в конец.

   std::vector<int> vec = {1, 2, 3};

2. std::list:

   • Тип: Двусвязный список.

   • Вставка одного элемента и удаление элемента по уже известному итератору занимают O(1). Поиск нужной позиции требует обхода и может стоить O(n); оператора индексного доступа у std::list нет.

   • Использование: Подходит для случаев, когда важны операции вставки и удаления.

   std::list<int> lst = {1, 2, 3};

3. std::map:

   • Тип: Отсортированный ассоциативный контейнер.

   • Особенности: Хранит пары “ключ-значение” в отсортированном порядке, доступ к элементам и операции вставки/удаления имеют сложность O(log n).

   • Использование: Подходит для случаев, когда важен порядок и требуется быстрый поиск по ключу.

   std::map<int, std::string> mp = {{1, "one"}, {2, "two"}};

4. 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?

1. std::set:

   • Тип: Отсортированный контейнер.

   • Хранение: Хранит уникальные элементы в отсортированном порядке.

   • Доступ: Быстрый поиск, добавление и удаление (O(log n)).

   • Использование: Подходит для хранения уникальных элементов, когда важен порядок.

   std::set<int> s = {1, 2, 3};

2. std::map:

   • Тип: Отсортированный ассоциативный контейнер.

   • Хранение: Хранит пары “ключ-значение” в отсортированном порядке по ключу.

   • Доступ: Быстрый поиск, добавление и удаление по ключу (O(log n)).

   • Использование: Подходит для хранения пар “ключ-значение”, когда важен порядок и уникальность ключей.

   std::map<int, std::string> m = {{1, "one"}, {2, "two"}};

3. 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 и в каких случаях их лучше использовать?

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 обычно требует больше памяти из-за хеш-таблицы.