Оценка числа элементов и размеров контейнера

 

метод	пояснение
size()	возвращает фактическое количество элементов в контейнере
max_size()	возвращает максимальный размер контейнера (порядка миллиарда элементов)
empty()	возвращает значение true, если контейнер пуст

 

Сравнение контейнеров

Для однотипных контейнеров сравнение может быть выполнено с помощью стандартных операций отношений ==,!=, <, <=, >, >=.

Отношения <, <=, >, >= проверяются по лексикографическому критерию. В этом случае два контейнера сравниваются с учетом интервалов размещения элементов [beg1, end1) и [beg2, end2). Элементы из интервалов сравниваются попарно до тех пор, пока не будет выполнено одно из условий:

· если очередные два элемента не равны, то результат этих элементов сравнения определяет результат сравнения контейнеров;

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

Присваивание контейнеров и обмен содержимым

Все типы контейнеров имеют общие операции вставки и удаления:

метод	содержание
swap(T& left, T& right)	обмен содержимым элементов контейнера
insert (iterator position, const T& value)	вставка элемента со значением value в позицию, заданную итератором position
insert (iterator position, size_type n, const T& value)	вставка n элементов со значением value, начиная с позиции position
insert (iterator position, const_iterator first, const_iterator last)	вставка диапазона элементов, заданного итераторами first и last, начиная с позиции position
erase(iterator position)	удаление элемента, на который указывает итератор position
erase(iterator first, iterator last)	удаление диапазона элементов, заданного позициями first и last
clear()	удаление всех элементов контейнера, но не его самого

 

Методы частного применения

 

push_back() – вставка элемента в конец контейнера; применим к деку, вектору, списку.

push_front() – вставка элемента в начало контейнера; применим к деку, списку.

 

pop_back() – удаление последнего элемента контейнера; применим к деку, вектору, списку.

pop_front() – удаление элемента из начала контейнера; применим к деку, списку

Методы pop_back() и pop_front() не возвращают удаленное значение.

Для считывания первого элемента используется метод front(), а для считывания последнего элемента – метод back().

 

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

 

Действия методов вставки и удаления:

 

push_back() push_front()

элементы последовательности

 

pop_back() pop_front()

 

Применение представленных в таблице методов дает разную эффективность для разных контейнеров:

Название операции	метод	vector	deque	list
добавление в начало	push_front()	-	O(1)	O(1)
удаление из начала	pop_front()	-	O(1)	O(1)
добавление в конец	push_back()	O(1)+	O(1)	O(1)
удаление из конца	pop_back()	O(1)+	O(1)	O(1)
вставка в произвольное место	insert()	O(n)+	O(n)	O(1)
удаление из произвольного места	erase()	O(n)+	O(n)	O(1)
обращение по индексу с проверкой допустимости	at()	O(1)	O(1)	-
обращение по индексу без проверки допустимости	[ ]	O(1)	O(1)	-
доступ к первому элементу	front()	O(1)	O(1)	O(1)
доступ к последнему элементу	back()	O(1)	O(1)	O(1)

 

Обозначения в таблице:

O(1) – длительность операции не зависит от числа элементов в контейнере;

O(n) – длительность операции пропорциональна числу элементов в контейнере;

+ – суффикс, обозначающий, что длительность исполнения операции может возрастать;

- – неприменимость операции к контейнеру.

Итераторы

Каждый контейнер включает тип с названием итератор.В шаблоне контейнера с параметром Т этому типу соответствуют Т* или const Т*, т.е. итератор ведет себя как указатель на элемент, помещенный в контейнер. Итератор – объект, по своим функциям напоминающий указатель при работе с массивом, аналог указателя на элемент. Он используется для обеспечения доступа к элементам контейнера, для просмотра контейнера в прямом или обратном направлении. От него требуется умение ссылаться на элемент контейнера и реализовывать операции перехода к следующему элементу. При помощи итераторов можно просматривать контейнеры, не заботясь о фактических типах данных, используемых для доступа к элементам. Константные итераторы используются тогда, когда значений соответствующих элементов контейнера не изменяются.

Существуют итераторы:

· однонаправленные (прямые); если нужно продвигаться вперед, но при этом совершать как запись, так и чтение, используется «прямой» итератор;

· двунаправленные;

· обеспечивающие произвольное перемещение (произвольный доступ); итератор «произвольного доступа» обеспечивает доступ к элементу контейнера без всяких продвижений.

 

Имеются два специализированных типа итераторов:

· потоковые итераторы, благодаря которым входные и выходные потоки могут вести себя как итераторы:

§ ostream_iterator – итератор выходного потока; используется, если требуется только лишь продвинуться на один шаг по контейнеру для осуществления последовательной записи, например, при записи в файл или выводе на экран;

§ istream_iterator – итератор входного потока; используется, если требуется только лишь продвинуться на один шаг по контейнеру. для осуществления последовательного чтения, например, при чтении из файлов или с клавиатуры.

 

· адаптеры итераторов – варианты модификации обычного итератора, которые могут необычным способом изменять поведение обычных итераторов:

o обратный итератор (reverse_iterator) для реверсного прохода контейнера (в обратном направлении);

o итератор вставки:

§ back_inserter вставляет новые элементы в конец контейнера

§ front_inserter вставляет новые элементы в начало контейнера (кроме вектора)

§ inserter вставляет новые элементы в указанное место

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

 

Тип итератора	Шаг вперед ++	Шаг назад --	Чтение value=*i	Запись *i= value	Произвольный доступ
Произвольного доступа	х	х	х	х	х
Двунаправленный	х	х	х	х
Однонаправленный	х		х	х
Входной	х		х
Выходной	х			х

 

 

Для просмотра контейнеров с помощью итераторов в каждом контейнере определены методы:

 

метод	пояснение
iterator begin() const_iterator begin() const	указывают на первый элемент
iterator end() const_iterator end() const	указывают на элемент, следующий за последним
reverse_iterator rbegin() const_reverse_iterator rbegin() const	указывают на первый элемент в обратной последовательности, который инкрементируется (при использовании обратного итератора)
reverse_iterator rend() const_reverse_iterator rend() const	указывают на элемент, следующий за последним, в обратной последовательности (при использовании обратного итератора)

 

Алгоритмы

Алгоритм – независимая шаблонная функция, производящая действия над элементами контейнера (для ее использования к программе подключается заголовочный файл <algorithm>). Алгоритмы можно использовать и при работе с обычными массивами С++.

Наиболее популярные алгоритмы STL:

название	назначение	аргументы
adjacent_find	поиск смежных пар одинаковых значений в последовательности; возвращает итератор первой пары поиск смежных пар одинаковых значений в последовательности, удовлетворяющих заданному предикатом условию в виде функции; возвращает итератор первой пары	first, last     first, last, predicate
accumulate	вычисление суммы элементов в заданном диапазоне; последовательное применение к каждому объекту диапазона формулы: init= init+*iter	first, last, init
binary_search	бинарный поиск в упорядоченной последовательности	first, last, val first, last, val, predicate
сopy	копирование объектов из первого диапазона во второй	first1, last1, first2
copy_backward	копирование объектов из первого диапазона во второй, располагая их в обратном порядке от last2 к first2	first1, last1, first2
count	возвращает количество вхождений n элемента value в последовательность	first, last, value, n
count_if	подсчет количества n выполнений в последовательности условия, удовлетворяющего значению predicate	first, last, predicate, n
еqual	определяет идентичность двух диапазонов; определяет идентичность двух диапазонов в соответствии с условием	first1, last1, first2 first1, last1, first2, predicate
fill	заменяет все элементы заданным значением	value
fill_n	заполняет диапазон от first до first+n заданным значением value	first, n, value
find	возвращает итератор, указывающий на первый объект, равный значению value	first, last, value
find_if	возвращает итератор, указывающий на первый объект, для которого условие принимает значение true	first, last, predicate
find_end	поиск конца последовательности [first2, last2] внутри диапазона [first1, last1] поиск конца последовательности [first2, last2] для некоторого условия внутри диапазона [first1, last1]	first1, last1, first2, last2   first1, last1, first2, last2, predicate
find_first_of	нахождение первого значения из одной последовательности в другой нахождение первого значения из одной последовательности в другой в соответствии с условием	first1, last1, first2, last2   first1, last1, first2, last2, predicate
for_each	вызов function для каждого элемента последовательности	first, last, function
generate	присваивает всем элементам значения, получаемые с помощью последовательных вызовов функции gen	first, last, gen
generate_ n	присваивает всем элементам диапазона от first до first+n значения, получаемые с помощью последовательных вызовов функции gen	first, n, gen
includes	определяет, включает ли одна последовательность все элементы другой последовательности определяет, включает ли одна последовательность все элементы другой последовательности в соответствии с условием	first1, last1, first2, last2     first1, last1, first2, last2, predicate
inplace_merge	слияние диапазонов, отсортированных в порядке возрастания элементов; слияние диапазонов, отсортированных в соответствии с условием	first, middle, last   first, middle, last, predicate
iter_swap	меняет местами значения	left, right
lexicographical_compare	лексикографическое сравнение последовательностей лексикографическое сравнение последовательностей в соответствии с условием	first1, last1, first2, last2   first1, last1, first2, last2, predicate
lower_bound	нахождение первого значения в последовательности, которое не меньше заданного value	value
max	возвращает максимальный из двух элементов	value1, value2
max_element	возвращает итератор максимального элемента внутри диапазона возвращает итератор максимального элемента внутри диапазона в соответствии с условием	first, last   first, last, predicate
merge	соединяет отсортированные диапазоны 1 и 2 в диапазон 3 соединяет отсортированные диапазоны 1 и 2 в диапазон 3; порядок сортировки определяется функцией comp	first1, last1, first2, last2, first3   first1, last1, first2, last2, first3, comp
min	возвращает минимальный из двух элементов	value1, value2
min_element	возвращает итератор минимального элемента внутри диапазона возвращает итератор минимального элемента внутри диапазона в соответствии с условием	first, last   first, last, predicate
mismatch	поиск первого несовпадения между элементами двух последовательностей; возвращаются итераторы несовпадающих элементов поиск первого несовпадения между элементами двух последовательностей в соответствии с условием; возвращаются итераторы несовпадающих элементов	first1, last1, first2   first1, last1, first2, predicate
remove	удаляет из диапазона все объекты, равные value	first, last, value
remove_copy	копирует все объекты, не равные значению value, из диапазона 1 в диапазон 2	first1, last1, first2, value
remove_copy_if	копирует все объекты, не удовлетворяющие predicate, из диапазона 1 в диапазон 2	first1, last1, first2, predicate
replace	заменяет все объекты, равные old, объектами, равными new	first, last, old, new
replace_if	заменяет все объекты, удовлетворяющие predicate, объектами, равными new	first, last, predicate, new
replace_copy	производит копирование из диапазона 1 в диапазон 2, заменяя все объекты, равные old, объектами, равными new	first1, last1, first2, old, new
replace_copy_if	производит копирование из диапазона 1 в диапазон 2, заменяя все объекты, удовлетворяющие predicate, объектами, равными new	first1, last1, first2, predicate, new
reverse	обращает последовательность элементов из диапазона	first, last
reverse_copy	копирует объекты из диапазона 1 в диапазон 2 в обратном порядке	first1, last1, first2
search	проверяет, содержится ли второй диапазон внутри первого; возвращает начало совпадения или last1, если нет совпадения	first1, last1, first2, last2
search	проверяет, содержится ли второй диапазон внутри первого, равенство определяется по predicate; возвращает начало совпадения или last1, если нет совпадения	first1, last1, first2, last2, predicate
sort	сортирует объекты в диапазоне	first, last
sort	сортирует объекты в диапазоне, используя comp в качестве функции сравнения	first, last, comp
swap	заменяет один объект другим	a, b
iter_swap	обменивает объекты, на которые указывают два итератора	iter1, iter2
swap_ranges	обменивает соответствующие объекты в двух диапазонах	first1, last1, first2

 

В списках параметров всех алгоритмов первые два параметра задают диапазон обрабатываемых элементов в виде полуинтервала [first, last), где first – итератор, указывающий на начало диапазона, а last – итератор, указывающий на выход за границы диапазона, т.е. на элемент, располагающийся за последним.

Например, массив int arr[7] = {15, 2, 19, -3, 28, 6, 8};

можно отсортировать с помощью алгоритма sort: sort (arr, arr +7);

Здесь имя массива arr (имеющее тип указателя int*) используется как итератор.

Примеры