| Вектор | Дек | Список | Множество | Мультимножество | Отображение | Мультиотображение | |
|---|---|---|---|---|---|---|---|
| Типичная внутренняя реализация | Динамический массив | Массив массивов | Двусвязный список | Бинарное дерево | Бинарное дерево | Бинарное дерево | Бинарное дерево |
| Элементы | Значение | Значение | Значение | Значение | Значение | Пара "ключ/значение" | Пара "ключ/значение" |
| Возможность существования дубликатов | Да | Да | Да | Нет | Да | Не для ключа | Да |
| Поддержка произвольного доступа | Да | Да | Нет | Нет | Нет | С ключом | Нет |
| Категория итератора | Произвольный доступ | Произвольный доступ | Двунаправленный | Двунаправленный (константные элементы) | Двунаправленный (константные элементы) | Двунаправленный (константные ключи) | Двунаправленный (константные ключи) |
| Скорость поиска | Медленная | Медленная | Очень медленная | Быстрая | Быстрая | Быстрая для ключа | Быстрая для ключа |
| Быстрая вставка/удаление | В конце | В начале и в конце | Где угодно | - | - | - | - |
| Недействительность итераторов, ссылок и указателей при вставке/удалени | При перераспределении памяти | Всегда | Никогда | Никогда | Никогда | Никогда | Никогда |
| Освобождение памяти от удаленных элементов | Никогда | Иногда | Всегда | Всегда | Всегда | Всегда | Всегда |
| Возможность резервирования памяти | Да | Нет | - | - | - | - | - |
| Транзакционная безопасность (успешное выполнение или отсутствие изменений) | Присоединение/удаление в конце | Присоединение/удаление в начале и в конце | Все операции кроме sort() и присваивания | Все операции, кроме вставки нескольких элементов | Все операции, кроме вставки нескольких элементов | Все операции, кроме вставки нескольких элементов | Все операции, кроме вставки нескольких элементов |