Использование последовательных контейнеров

Последовательности

Transform Выполнение заданной операции над каждым элементом

Swap Обмен двух элементов

Sort Сортировка

Последовательность второй последовательности

Search Нахождение первого вхождения в первую

Replace Замена элементов с заданным значением

Remove Перемещение элементов с заданным значением

Merge Слияние отсортированных последовательностей

For_each Вызов функции для каждого элемента последовательности

Последовательности

Find_if Нахождение первого соответствия условию в

Последовательности в другой

Find_first_of Нахождение первого значения из одной

 

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

Полуинтервал [а, b) — это промежуток, включающий а, но не включающий b — последний элемент полуинтервала предшествует элементу b.

 

Например, если имеется массив:

int arr[7] = {15, 2, 19, -3, 28, 6, 8};

то его можно отсортировать с помощью алгоритма sort:

sort(arr, arr + 7);

 

Здесь имя массива arr имеет тип указателя int* и используется как итератор. Примеры использования некоторых алгоритмов будут даны ниже.

 

К основным последовательным контейнерам относятся вектор (vector), список ( list) и двусторонняя очередь (deque).

 

Чтобы использовать последовательный контейнер, нужно включить в программу соответствующий заголовочный файл:

#inclucie <vector>

#include <list>

#include <deque>

using namespace std;

 

1) Контейнер векторявляется аналогом обычного массива, за исключением того, что он автоматически выделяет и освобождает память по мере необходимости.

Контейнер эффективно обрабатывает произвольную выборку элементов с помощью операции индексации [] или метода at.

 

/* Метод at() аналогичен операции индексации, но в отличие от последней, проверяет выход индекса за границу вектора. Если такое нарушение обнаруживается, то метод генерирует исключение out_of_range.*/

 

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

 

2) Контейнер списокорганизует хранение объектов в виде двусвязного списка.

Каждый элемент списка содержит три поля: значение элемента, указатель на предшествующий и указатель на последующий элементы списка.

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

 

3) Контейнер двусторонняя очередь (дек)во многом аналогичен вектору, элементы хранятся в непрерывной области памяти. Но в отличие от вектора двусторонняя очередь эффективно поддерживает вставку и удаление первого элемента (так же, как и последнего).

 

Существует пять способов определить объект для последовательного контейнера:

 

1. Создать пустой контейнер:

 

vector<int> vecl;

list<string> list1;

2. Создать контейнер заданного размера и инициализировать его элементы значениями по умолчанию:

vector<string> vecl(100);

list<double> listl(20);

3. Создать контейнер заданного размера и инициализировать его элементы указанным значением:

vector<string> vec1(1OO, "Hello!");

deque<int> dec1(300, -1);

4. Создать контейнер и инициализировать его элементы значениями диапазона [first, last) элементов другого контейнера:

 

int arr[7] = {15, 2, 19, -3, 28, 6, 8}:

vector<int> v1 (arr, arr + 7);

list<int> lst (v1.beg() + 2, v1.end());

5. Создать контейнер и инициализировать его элементы значениями элементов другого однотипногоконтейнера:

 

vector<int> v1;

// создает копию v1

vector<int> v2(vl);

 

6. Для вставки и удаления последнего элемента контейнера любого из трех рассматриваемых классов предназначены методы push_back() и рор_back().

Кроме того, список и очередь (но не вектор) поддерживают операции вставки и удаления первого элемента контейнера push_front() и pop_front().

Учтите, что методы рор_back() и pop_front() не возвращают удаленное значение.

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

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

 

Таблица 4. Методы insert() и erase()

 

Метод Пояснение

insert(iterator position,const Т& value) Вставка элемента со значением value в