51. Последовательные контейнеры: vector, list, deque. Основные методы и алгоритмы

Операция Метод vector deque list

Вставка в начало push_front - + +

Удаление из начала pop front - + +

Вставка в конец push_back + + +

Операция Метод vector deque list

Удаление из конца pop back + + +

Вставка в произвольное место insert (+) (+) +

Удаление из произвольного места erase (+) (+) +

Произвольный доступ к элементу [ ]. at + + -

Знак + означает, что соответствующая операция реализуется за постоянное время, не зависящее от количества п элементов в контейнере. Знак (+) означает, что соответствующая операция реализуется за время, пропорциональное n. Для малых n время операций, обозначенных +, может превышать время операций, обо-значенных (+), но для большого количества элементов последние могут оказаться очень дорогими.

Как видно из таблицы, такими операциями являются вставка и удаление произвольных элементов очереди и вектора, поскольку при этом все последующие элементы требуется переписывать на новые места.

Вектор — это структура, эффективно реализующая произвольный доступ к элементам, добавление в конец и удаление из конца.

Двусторонняя очередь эффективно реализует произвольный доступ к элементам, добавление в оба конца и удаление из обоих концов.

Список эффективно реализует вставку и удаление элементов в произвольное место, но не имеет произвольного доступа к своим элементам.

Пример работы с вектором. В файле находится произвольное количество целых чисел. Программа считывает их в вектор и выводит на экран в том же порядке.

#include <fstream> #iinclude <vector> using namespace std: int main(){

ifstream in ("inpnum.txt");

vector<int> v; int x; while ( in » x, lin.eofO)

v.push_back(x);

for (vector<int>::iterator i = v.begin(); i != v.end(); ++i)

cout « *i « " ";

Поскольку файл содержит целые числа, используется соответствующая специализация шаблона vector - vector<int>. Для создания вектора v используется конструктор по умолчанию.

52. Ассоциативные контейнеры: set, multiset, map, multimap. Основные методы и алгоритмы.

К ассоциативным контейнерам принадлежат: set, multiset, hash set, hash multiset, map, multimap, hash_map, hash_multimap. Они поддерживают эффективный поиск значений (values), связанных с ключом (key). Они позволяют вставить и удалить элемент, но в отличие от последовательностей не позволяют вставить элемент в заранее определенную и указанную позицию. Различают сортированные ассоциативные контейнеры (set, multiset, map, multimap) и хешированные (hashed) ассоциативные контейнеры (hash_set, hash_multiset, hash_map, hash_ / multimap).

Сортированные контейнеры соблюдают отношение порядка (ordering relation) для своих ключей, причем два ключа считаются эквивалентными, если ни один из них не меньше другого. Например, если отношение порядка не учитывает регистр, то ключ "strict rules" эквивалентен ключу "Strict Rules". Сортированные контейнеры хороши тем, что они гарантируют логарифмическую эффективность (complexity) большинства своих операций. Это гораздо более сильная гарантия, чем та, которую предоставляют хешированные ассоциативные контейнеры. Последние гарантируют постоянную эффективность только в среднем, а в худшем случае — линейную.

set - это ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск ключей.

multiset - это ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск ключей.

map - ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск значений другого типа T, связанных с ключами.

multimар - ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск значений другого типа T, связанных с ключами.