Особенности использования vector

Используется как замена массиву.

Но вектор может изменять размер самостоятельно. Также нет необходимости ручного освобождения памяти.

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

List

Устройство

list<T> - последовательный контейнер, двусвязный список, элементы которого хранятся в произвольных областях памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти.

Каждый элемент списка хранит информацию о том, где найти следующий или предыдущий элемент (обычно с помощью указателей).

Итераторы, используемые для работы со списками, относятся к категории двунаправленных, а не произвольного доступа, как итераторы, работающие с векторами. Это означает, что list-итераторы нельзя подвергать сложению и вычитанию, а также другим операциям, характерным для арифметики указателей.

Подобно декам, но в отличие от векторов, списки не открывают базовую модель управления памятью. Другими словами, списки поддерживают методы size() и empty(), но не reserve() или capacity().

Основные операции и их стоимость

· begin() end() - O(1)

· empty() - O(1)

· size() - O(1)

· max_size() - O(1)

· resize (n , value=0) - O(n)

· front() back() - O(1)

· push_front() pop_front() - O(1)

· push_back() pop_back() - O(1)

· insert() - O(1) для вставки в начало или конец. O(n) – вставка в произв участок списка

· erase() - O(n)

· swap() - O(1)

· clear() - O(n)

· reverse() - O(n)

· remove() – удаляет элемент с определенным значением - O(n)

· unique() – удаляетповторения

· merge() – совмещает отсортированные списки - O(n+m)

· sort() – сортирует элементы

Особенности использования

Быстрая вставка и удаление, медленный доступ к n-му эл-ту и поиск.

При вставке или удалении элементов итераторы не теряют своей актуальности.

Например, при реализации интерактивной переписки необходимо где-то хранить имена всех текущих участников "разговора" – подойдет список. Состав участников переписки часто меняется, поэтому нужно быстро вставку и удаление. С другой стороны, поиск участников разговора требуется проводить не очень часто, поэтому время его выполнения не слишком важно в данном случае.

Deque

(doubleendqueue)

deque<T> - последовательный контейнер, похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за о(1). Реализован в виде двусвязанного списка линейных массивов. С другой стороны, в отличие от vector, дек не гарантирует расположение всех своих элементов в непрерывном участке памяти, что делает невозможным безопасное использование арифметики указателей для доступа к элементам контейнера.

Устройство

Устройство: блоки, каждый из которых хранит несколько элементов. Размер n-го блока – logn.

(Из Солтера: в деке не раскрыта схема управления памятью, как в векторе (через методы reserve() или capacity())).

Основныеоперации

begin()	end()	empty()	size()	max_size()	resize (n , value=0);
front()	back()	push_front()	pop_front()	push_back()	pop_back()
insert()	operator[]	erase()	swap()	clear()

Особенности применения

Аналогично вектору сохранность итераторов не гарантирована.

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

Дек рекомендуется использовать вместо вектора, когда нужно вставлять или удалять элементы с любого конца последовательности с сохранением быстрого доступа ко всем элементам. Однако такое требование неприменимо к решению многих задач программирования, поэтому в большинстве случаев используют вектор или очередь.

Stack и Queue

Stack

Устройство

stack<T> - контейнер-адаптер, где добавление и удаление элементов осуществляется с одного конца.

template< class T, class Container = deque<T>> class stack;

Основные операции

empty()

size()

empty()

top() – возвращает последний элемент, вставленный в стек.

push() - добавляет элемент

pop() – удаляет элемент

Особенности применения

Стек, являясь STL-контейнером, обеспечивает быструю вставку и удаление элементов. Структуру стека рекомендуется использовать в случае, когда необходимо реализовать FILO-семантику.

Например, системный администратор хотел иметь такое средство обработки ошибок, которое бы обеспечивало хранение данных об ошибках в стеке, чтобы самая последняя ошибка была доступной для изучения в первую очередь. Процесс обработки ошибок в FILO-порядке полезен потому, что "свежие" ошибки часто помогают устранить более давние.

Queue

Устройство

queue<T> - контейнер-адаптер, в один конец которого можно добавить элемент, а с другого - удалить.
template<classT, classContainer = deque<T>>classstack;

Шаблонный параметр Т задает тип элементов. Второй шаблонный параметр позволяет оговорить базовый контейнер, который эта очередь должна адаптировать. Поскольку очередь требует, чтобы базовый последовательный контейнер поддерживал методы push_back() и pop_back (), то у вас для выбора адаптируемого контейнера есть только два встроенных варианта: list и deque. По умолчанию дек.

Основные операции

empty()

size()

front()

back()

push() - добавляет элемент в конец очереди pop() – удаляет элемент из начала очереди

Особенности применения

Структуру очереди рекомендуется использовать в случае, когда нужно смоделировать реальный механизм "первым прибыл, первым обслужен".

Рассмотрим, например, рабо­ту банка.

Клиенты заходят в банк и становятся в очередь. Один из банковских служащих, отпустив текущего клиента, принимается обслуживать клиента из очереди, реализуя та­ким образом FIFO-поведение. Вы могли бы смоделировать ситуацию в банке, сохраняя объекты класса customer в очереди. По прибытии клиента в банк мы помещаем его в конец очереди. После того как банковский служащий, освободившись, будет готов к об­служиванию, к нему пригласят клиента, стоящего в очереди первым. Таким образом, клиенты обслуживаются в порядке, в котором они пришли в банк.

Map, Set

Map

Устройство

map<K,T> - упорядоченный ассоциативный массив пар ключ-значение.

Ключи должны быть уникальны.

Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.

template< class Key, class T, class Compare = less<Key>, class Allocator =… > class map;

Основные операции

begin()	end()	empty()	size()	max_size()	insert()
operator[]	erase()	swap()	clear()

find – возвращает итератор на элемент. Поиск по ключу

count – считает количество элементов по заданному ключу

lower_bound – возвращает итератор на наименьший из элементов, перед которым будет вставлен элемент с заданным ключом

upper_bound – возвращает итератор за наибольший из элементов, перед которым будет вставлен элемент с заданным ключом

equal_range – тоже что-то делает J
Особенности применения

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

Set

Устройство

set<T> - ассоциативный контейнер, упорядоченное множество уникальных элементов.

При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными.

Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания.

Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор.

Реализован на основе самобалансирующего дерева двоичного поиска.

template< class Key, class Compare = less<Key>, class Allocator = … > class set

Основныеоперации

begin()	end()	empty()	size()	max_size()	insert()
operator[]	erase()	swap()	clear()

find()

lower_bound(), upper_bound()

equal_range()

count(key) – возвращает 1, если элемент найден и 0 в противном случае

Особенности применения

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

Bitset, vector<bool>

Bitset

Устройство

bitset<T> - псевдоконтейнер, служит для хранения битовых масок.

Похож на vector<bool> фиксированного размера.

Размер фиксируется тогда, когда объявляется объект bitset.

Итераторов в bitset нет.

Оптимизирован по размеру памяти.

Битовое множество— не настоящий STL-контейнер: он имеет фиксированный размер, не принимает шаблонный параметр для типа элемента и не поддерживает итеративный доступ к своим элементам.

Основные операции

operator[]

size()

set ( size_t pos, bool val = true ) - устанавливаетбиты

reset(pos) – устанавливает на 0 бит в позиции pos

flip(pos) – меняет значение бита на противоположное в позиции pos

count() – возвращает количество битов в bitset, которые установлены (=1)

test(pos) – возвращает значение бита на позиции pos

any – проверяет, установлены ли хоть какие-нибудь биты

none – проверяет, что никакие биты не установлены

Помимо основных методов манипуляции битами, битовое множество поддерживает реализации всех поразрядных операторов: &, |, ^, ~, «, », &=, |=, ^=, <<= и >>=. Они действуют так, как если бы обрабатывали "настоящую последовательность" битов.

Особенности применения

В качестве примера рассмотрим использование битового множества для отслеживания каналов для кабельных абонентов. Каждому абоненту можно было бы поставить в соответствие bitset-набор каналов, который он оплачивает. Такая система могла бы поддерживать даже "пакеты" каналов, также представляемые в виде битовых множеств, которые бы обозначали обычно подписываемые комбинации каналов.

vector<bool>

Специализацию vector<bool> можно представлять себе не как вектор, а как контейнер для битовых полей. Контейнер bitset обеспечивает реализацию битовых полей с более полным набором функций, чем контейнер vector<bool>. Однако к преимуществам специализации vector<bool> можно отнести его способность динамически изменять размер.

Устройство

В большинстве С++-компиляторов bool-значения имеют такой же размер, как и данные типа int. Специализация vector<Ьоо1> предполагает хранение "массива bool-значений", занимающих именно один бит, т.е. в "режиме экономии памяти".

Основные операции

К основным операциям вектора добавляется метод flip(). Его можно применить как ко всему контейнеру, так и к 1 элементу. Инвертирует биты.

Особенности применения

Позволяет в 8 раз сэкономить память

unordered_map

Устройство

unordered_map<K,T> - контейнер, который содержит пары ключ-значение. Позволяет быстро искать элементы по их ключу.

template< class Key, class T, class Hash = hash<Key>
class Pred = equal_to<Key>, … > class unordered_map

В программировании, неупорядоченный ассоциативные контейнеры относятся к группе шаблонов классов STL, которые реализуют изменения хэш-таблицы.

Будучи шаблонными, их можно использовать для хранения произвольных элементов, таких как int или пользовательских классов.

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

Основныеоперации

empty()	size()	max_size()	size()	begin()	end()
operator[]	find()	count()	insert()	erase()	clear()
swap()

Особенности применения

priority_queue

priority_queue<T> - контейнер-адаптер являющийся очередью с приоритетом, организованной так, что самый большой элемент всегда стоит на первом месте.

template< class T, class Container = vector<T>, class Compare = less<…>> class priority_queue;

Устройство

Представляет собой вектор, который вызывает методы make_heap, push_heap и pop_heap

Основныеоперации

empty()

size()

top()

push()

pop() – удаляет верхний элемент

Особенности применения

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

Этот интерфейс обладает довольно ограниченными возможностями. В частности, адаптер priority_queue не предоставляет никакой итераторной поддержки и не позволяет объединять две очереди по приоритету в одну.