Чем принципиально отличаются итератор по элементам контейнера set и по элементам контейнера vector?

vector – итераторы произвольного доступа

(обеспечивает произвольный доступ к элементам вектора)

set – двунаправленный итератор

(разрешен только последовательный обход контейнера)

 

Какие функции и операторы должны быть определены для итератора по элементам двухсвязного списка?

Контейнеры также поддерживают метод begin(), который возвращает итератор, ссылающийся на первый элемент контейнера.

Метод end() возвращает ссылку на значение, расположенное "за последней чертой" данной последовательности элементов контейнера. Другими словами, метод end() возвращает итератор, который равен результату применения оператора operator++ к итератору, ссылающемуся на последний элемент в данной последовательности.

Вместе методы begin () и end () образуют полуоткрытый диапазон, который включает первый элемент последовательности, но не последний. Причина такого нюанса — в поддержке пустых диапазонов (т.е. контейнеров, не содержащих элементов), для которых результат вызова метода begin() совпадал бы с результатом вызова метода end().

Итак:

· Operator++

· Operator--

· Operator*

· Operator==

· Operator=

 

Итератор с произвольным доступом

Читают и пишут значения с произвольным доступом. Самые мощные итераторы, сочетающие функциональность двунаправленных итераторов и возможность выполнения арифметики указателей и сравнений указателей.

 

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

Vector

vector<T> - последовательный контейнер, предназначен, как и массив, для хранения объектов. К элементам вектора тоже можно обращаться с помощью оператора индексирования [ ]. Но в отличие от массива, который имеет фиксированный размер, размер вектора можно изменять в процессе добавления или удаления элементов.

Вектор всегда расширяется в 2 раза.

Устройство

Все элементы вектора должны принадлежать одному типу. Например, нельзя совместно хранить данные типов char и int в одном экземпляре вектора. Класс vector обладает стандартным набором методов для доступа к элементам, добавления и удаления элементов, а также получения количества хранимых элементов.
Вектор хранится в памяти непрерывным блоком.

 

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

· swap(vector& v) - O(1)

· back() и front() возвращают ссылку на первый и последний элементы - O(1)

· begin() и end() возвращают итератор указывающий на первую и следующую после последнего элемента вектора позицию - O(1)

· empty() проверяет, пустой ли вектор - O(1)

· erase (iterator it) удаляет из вектора элемент на который указывает итератор it и возвращает, итератор указывающий на следующий элемент после удаленного - O(n)

· erase(iterator first, iterator last) удаляет из вектора последовательность определяемую итераторами (first,last) и возвращает итератор, указывающий на следующий элемент после последнего удаленного - O(n)

· clear () то же самое что и erase(begin(), end()) - O(n)

· pop_back () удаляет один элемент с конца вектора - O(1)

· push_back(value) вставляет в конец вектор элемент с значением value - O(1)

· insert(iterator it, value) вставляет элемент со значением value перед элементом, на который указывает итератор it и увеличивает размер вектора на 1 - O(n)

· insert(iterator it, n, value) вставляет n элементов со значением value перед элементом, на который указывает итератор it и увеличивает размер вектора на n
O(n) – вставка в произвольное место; O(1) – в конец без перераспределен памяти.

· insert(iteratorit, const_iteratorfirst, const_iteratorlast) вставляет последовательность определяемую итераторами (first,last) перед элементом на который указывает итератор it - O(n)

· operator[] - O(1)

· size() возвращает число элементов вектора - O(1)

· resize(n, value=0) - если при изменении размера число элементов увеличивается то новым элементам присваивается значение value - O(n)

· capacity() возвращает значение показывающее сколько ещё свободных элементов в векторе - O(1)

· reserve(n) резервирует память необходимую для добавления n элементов - O(n)

· max_size() максимальное число элементов которое можно хранить - O(1)