Последовательный контейнер deque

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

Структура дека, разбитая на блоки (рис. 25.2), обеспечивает произвольный доступ к элементам за постоянное время. Закрашенные области на рисунке соответствуют заполненным элементам дека. Если при вставке элемента в дек блок становится заполненным полностью, выделяется память под очередной блок. При заполнении крайнего из блоков происходит перераспределение памяти под массив указателей таким образом, чтобы использовались только средние его элементы. Нового выделения памяти под заполненные блоки не происходит, а происходит лишь копирование указателей на ранее выделенные участки памяти.

Рис. 25.2. Организация дека

Дек поддерживает те же операции, что и вектор, за исключением capacity() и reserve(). Кроме того, класс deque обеспечивает извлечение и включение элементов как в конец, так и в начало контейнера:

push_back(elem) вставляет элемент elem в конец дека;

pop_back() удаляет последний элемент дека;

push_front(elem) вставляет элемент elem в начало дека;

pop_front() удаляет первый элемент дека.

Если операции выполняются над внутренними элементами дека, все значения итераторов и ссылок на элементы становятся недействительными. После включения элемента в любой из концов (push) все значения итераторов становятся недействительными, а значения ссылок на элементы дека сохраняются. После операций извлечения из любого конца (pop) становятся недействительными только значения итераторов и ссылок, связанных с этими элементами.

Для использования данного контейнера необходимо подключить заголовок <deque>.

Рассмотрим программу с использованием дека.

// Листинг 25.4

#include <iostream>

#include <deque>

using namespace std;

int main()

{

int a[] = {9, 8, 7, 6, 5, 4};

int k = 0;

deque<int> d; // Создание пустого дека

if (!d.empty()) { // Если дек не пуст

// Получение первого элемента дека

k = d.front();

// Удаление элемента из начала дека

d.pop_front();

cout << "pop " << k << endl;

}

cout << " size = " << d.size() << endl;

// Размер дека

// Добавление элементов в конец дека

d.push_back(1);

d.push_back(2);

d.push_back(3);

d.push_front(4);

// Добавление элементов в начало дека

d.push_front(5);

for (int i = 0; i < d.size(); ++i)

cout << "d[" << i << "] = "

<< d[i] << endl;

cout << " size = " << d.size() << endl;

if (!d.empty()) {

k = d.front();

d.pop_front();

cout << "pop " << k << endl;

}

cout << " size = " << d.size() << endl;

if (!d.empty()) {

// Получение последнего элемента дека

k = d.back();

cout << "back = " << k << endl;

}

d[2] = 17; // Изменение значения элемента

for (int i = 0; i < d.size(); ++i)

cout << "d[" << i << "] = "

<< d[i] << endl;

return 0;

}

Результаты выполнения программы:

size = 0

d[0] = 5

d[1] = 4

d[2] = 1

d[3] = 2

d[4] = 3

size = 5

pop 5

size = 4

back = 3

d[0] = 4

d[1] = 1

d[2] = 17

d[3] = 3

Для выполнения операций над контейнерами и другими последовательностями в программе на языке Си++ можно использовать обобщенные алгоритмы STL и функции стандартной библиотеки.

Основные алгоритмы STL обработки данных контейнеров и последовательностей вводятся заголовком <algorithm>.

Рассмотрим следующие алгоритмы:

Алгоритм generate() и спользуется для присвоения сгенерированных значений:

OutputIterator

generate(ForwardIterator beg,

ForwardIterator end, Func op)

Алгоритм присваивает значения, сгенерированные вызовом op() для каждого элемента диапазона [beg,end).

Алгоритм transform() можно использовать для преобразования элементов:

OutputIterator

transform(InputIterator sourceBeg,

InputIterator sourceEnd,

OutputIterator destBeg,

UnaryFunc op)

Алгоритм вызывает унарную операцию op(elem) для каждого элемента в диапазоне-источнике [sourceBeg, sourceEnd) и записывает результат каждого вызова унарной операции op в диапазон получатель, начиная с позиции destBeg.

Возвращает позицию после последнего преобразованного элемента в диапазоне-получателя.

Алгоритм copy():

OutputIterator copy(InputIterator sourceBeg,

InputIterator sourceEnd,

OutputIterator destBeg)

Алгоритм копирует все элементы исходного интервала [sourceBeg, sourceEnd) в приемный интервал, начиная с destBeg, и возвращают позицию, следующую за последним скопированным элементом. Причем контейнеры источника и приемника могут быть различными, в качестве источника может выступать итератор входного потока, а приемником может служить итератор выходного потока.

Рассмотрим задачу:

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

В программе реализовать следующие функции:

- функцию f1(), которой передаются три параметра: контейнер вектор и два целочисленных параметра a и b. Функция заполняет вектор целыми случайными значениями из диапазона [a,b], используя генератор случайных чисел rand() и алгоритм STL generate();

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

- функцию f3(), которой в качестве параметра передается контейнер вектор, функция прибавляет к каждому элементу вектора максимальное значение с использованием алгоритма transform();

- функцию f4(), которой в качестве аргументов функции предаётся контейнер вектор. Функция выводит элементы контейнера на экран с помощью алгоритма STL copy().

С помощью функции f1() заполнить вектор, с помощью функций f2() и f3() модифицировать вектор.

Решение задачи:

По условию задачи в программе должны быть определены четыре функции f1(), f2(), f3() и f4().

В функциях f1() и f3() требуется использовать алгоритмы STL generate() и transform() соответственно. Для настройки данных алгоритмов на выполнение необходимых действий применим функциональные объекты. Функциональным объектом в самом общем виде называют любой объект, к которому можно обратиться, используя синтаксис вызова функции.

В данной программе создадим два функциональных класса func1 и func2, в которых определим операцию вызова функции, т.е. операцию "круглые скобки". Напомним, что операцию () можно определять только как метод класса. Объект функционального класса, называемый функтором, используется так, как если бы он был функцией.

Функциональный класс func1 имеет два элемента-данных типа int, для задания границ диапазона случайных чисел. В этом классе определены конструктор, в котором происходит инициализация полей-данных, и перегруженная операция (), где с помощью библиотечной функции rand() генерируется случайное число из заданного диапазона.

В функции f1(), создается объект класса func1 и он передается в качестве третьего параметра алгоритму generate().

Функциональный класс func2 имеет одно поле-данных типа int, для задания прибавляемого значения. В классе определены конструктор, инициализирующий прибавляемое значение, и метод operation(), в котором к элементу прибавляется значение.

В функции f3() вычислим максимальное значение вектора с помощью алгоритма max_element(), создадим объект класса func2, у которого поле равно найденному максимуму, и передадим его в качестве последнего параметра алгоритму transform().

Необходимо обратить внимание, что для корректной работы функций f1(), f2() и f3() параметр контейнер-вектор должен передаваться по ссылке.

В программе используются алгоритмы max_element() и min_element(), которым передаются итератор начала диапазона и итератор конца диапазона, они возвращают итератор, указывающий на элемент с максимальным (минимальным) значением. Для получения максимального (минимального) значения следует применить операцию разыменования.

В функции f4(), предназначенной для вывода содержимого контейнера-вектор на экран, используется алгоритм copy(). В качестве третьего параметра следует использовать итератор, связанный с выходным потоком cout, в котором выводимые значения разделяются пробелом: osream_iterator<int>(cout," ").

В функции main() создается вектор и тестируются все функции.

Листинг программы с подробными комментариями приведен ниже.

//Листинг 25.5

#include<iostream>

#include<vector>

#include<algorithm>

#include<iterator>

#include<time.h>

using namespace std;

//функциональный класс, объекты которого

//используются в алгоритме generate

//в качестве третьего параметра

class func1{

int a, b; //границы диапазона

public:

//конструктор инициализирует границы

func1(int c, int d):a(c), b(d) { }

//"вызов функции" для генерации

//случайного числа из [a,b]

int operator()()

{

return rand()*(b - a) / RAND_MAX + a;

}

};

//функциональный класс, объекты которого

//используются в алгоритме transform

//в качестве четвертого параметра

class func2{

int m; //добавляемое значение

public:

//конструктор инициализирует

//добавляемое значение

func2(int c): m(c){ }

//"вызов функции" для элемента,

//к которому добавляется значение

int operator()(int x)

{

return m + x;

}

};

void f1(vector<int> &vec,int a,int b)

{ //создаем функтор

func1 f(a, b);

//заполняем случайными числами из [a,b]

//вектор с помощью алгоритма generate

generate(vec.begin(), vec.end(), f);

}

void f2(vector<int> &vec)

{ //вычисляем минимум

int min = *min_element(vec.begin(),

vec.end());

//умножаем все элементы на 5

for (int i = 0; i<vec.size(); ++i)

vec[i] *= 5;

//добавляем в конец новый элемент

vec.push_back(min);

}

void f3(vector<int> &vec)

{ //вычисляем максимум

int max = *max_element(vec.begin(),

vec.end());

//создаем функтор

func2 f(max);

//с помощью алгоритма transform

//складываем каждый элемент с максимумом

transform(vec.begin(), vec.end(),

vec.begin(), f);

}

void f4(vector<int> &vec)

{ //вывод вектора на экран

// с помощью алгоритма copy()

copy(vec.begin(), vec.end(),

ostream_iterator<int>(cout,

" "));

cout << endl;

}

int main()

{

srand(time(NULL));

setlocale(LC_ALL, "Russian");

//создаем вектор из n элементов

int n;

cout << "Количество элементов в векторе: ";

cin >> n;

vector<int> vec(n);

//заполняем вектор случайными числами

// из диапазона [a,b]

int a, b;

cout <<

"Введите границы диапазона случайных чисел: ";

cin >> a >> b;

f1(vec,a,b);

//вывод вектора на экран

cout << "Начальные значения вектора"

<< endl;

f4(vec);

//модифицируем содержимое вектора фунцией f2()

f2(vec);

//вывод вектора на экран

cout <<

"Вектор после выполнения функции f2()"

<< endl;

f4(vec);

//модифицируем содержимое вектора фунцией f3()

f3(vec);

//вывод вектора на экран

cout <<

"Вектор после выполнения функции f3()"

<< endl;

f4(vec);

return 0;

}

Результаты выполнения программы:

Количество элементов в векторе: 10

Введите границы диапазона случайных чисел: 5 20

Начальные значения вектора

9 14 6 19 16 17 7 19 9 11

Вектор после выполнения функции f2()

45 70 30 95 80 85 35 95 45 55 6

Вектор после выполнения функции f3()

140 165 125 190 175 180 130 190 140 150 101

Задание:

Введем понятие дискретного белого шума. Дискретный белый шум — это последовательность независимых (то есть статистически не связанных друг с другом) чисел. С использованием генератора случайных чисел языка С\C++ функции rand(), дискретный белый шум можно получить следующим образом:

x[i] = 2 * ((rand()/((double)RAND_MAX)) — 0.5), (1)

где x[i] - элемент массива дискретного белого шума (без нулевой частотной составляющей), имеющего равномерное распределение от −1 до 1.

Написать программу на языке С++, в которой используются последовательные контейнеры STL вектор и дек.

В программе должны быть следующие шаблоны функций:

- white_noise() -в качестве аргумента функции передается контейнер. Функция заполняет данный контейнер по формуле (1) с помощью алгоритма STL generate();

- modify1() - в качестве аргумента функции передается контейнер. Функция модифицирует содержимое контейнера согласно варианту задания и добавляет в конец контейнера два значения: сумму всех элементов и среднее арифметическое всех элементов по абсолютной величине;

- modify2() - в качестве аргумента функции передается контейнер. Функция модифицирует содержимое контейнера согласно варианту задания с помощью алгоритма STL transform();

- outfile() – в качестве аргументов функции предаются контейнер и имя файла. Функция записывает элементы контейнера в текстовый файл с помощью алгоритма STL copy().

В программе создаются вектор дискретного белого шума из n элементов и дек дискретного белого шума из m элементов (значения m и n вводятся с клавиатуры). Содержимое контейнера - вектор модифицируется с помощью функции modify1() и записывается в один файл. Содержимое контейнера-дек модифицируется с помощью функции modify2() и записывается в другой файл.

Вариант 1

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

Вариант 2

Разделить каждый элемент на полусумму первого отрицательного и 30-го элемента.

Вариант 3

Вычесть из каждого элемента значение наибольшего элемента.

Вариант 4

Умножить каждый элемент на значение минимального элемента.

Вариант 5

Вычесть из каждого элемента значение суммы всех элементов.

Вариант 6

Умножить каждый элемент на удвоенную сумму первого и последнего отрицательных элементов.