§16 Контейнеры. Классы vector и deque. Адаптеры

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

Контейнер — это специализированный класс, предназначенный для хранения массива однотипных объектов и обеспечения доступа к этим объектам. Кроме array, остальные контейнеры (в том числе и string) содержат массивы, являющиеся динамическими. Из этого следует, что контейнеры могут управлять выделяемой памятью. Для различных контейнеров имеются как общие, так и специфичные методы, применимые только для определенного контейнера. Согласно стандарту C++, любой контейнер должен содержать методы begin(), end(), size(), max_size(), empty() и swap(). Общие методы для контейнеров могут иметь разную эффективность. Доступ к элементам в контейнерах предоставляется с помощью функций-членов (vector, deque) или через итераторы (list, set). Контейнеры, в которых элементы располагаются последовательно, один за другим, называются последовательными контейнерами. Последовательные контейнеры реализуют классы:

  • array
  • vector
  • deque
  • list

В каждом таком контейнере (за исключением list) элемент имеет свой индекс; как и в массивах, отсчет начинается с "0".
Выбор того или иного контейнера зависит от решаемой задачи. Для работы со строкой предназначен, уже знакомый нам, контейнер string. На самом деле, string является псевдо-контейнером, который предназначен для работы только с символьными массивами. Он во всем подобен контейнеру vector, но последний работает с различными типами данных, в том числе и абстрактными.

Класс vector

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

#include <vector>;
Описание и инициализация

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

vector<type> name;

Инициализировать вектор можно следующими способами:
Списком инициализации

vector<int> mas {1, 2, 3, 4, 5};

Копированием другого вектора

vector<type> mas2(mas1); // или
vector<type> mas2 = mas1;

Копиями элемента

vector<type> mas(n, el);

Примечание. Инициализация n копиями элемента el
Итераторами в интервале [first, last)

vector<type> mas(first, last);

Потоковым итератором

istream_iterator<int> in_it(cin), eof;
vector<int> mas(in_it, eof);

Примечание. Данные с потока будут записываться до тех пор, пока не встретится символ, который не может быть интерпретирован как целое число или \0.
Опредение вектора (создание экземпляра класса), с инициализацией или без таковой, иначе называется конструктором.

Доступ к элементам

Доступ к элементам можно получить с помощью операций [] или at() с использованием стандартного цикла for. Например, заполнение четными значениями будет выглядеть так:

for (size_t i = 0; i < v.size(); i++)
    v.at(i) = 2 * i;

При использовании диапазонного for запись будет более лаконична и безопасна:

for (auto &i : v)
    i = 2 * k;

Примечание. Диапазонный цикл for можно использовать только тогда, когда размер массива v не изменяется!
Доступ к элементам можно получить и с использованием итераторов. Итератор первого элемента можно получить так:

first = v.begin();
first = v.cbegin();

Если элементы массива не изменяются в процессе обхода, то следует первой форме предпочесть вторую, возвращающую const_iterator. Аналогичным образом получаем итератор элемента, следующего за последним:

last = v.end();
last = v.cend();

Существуют еще одна форма итераторов - реверсивные итераторы. Их назначение - обход массива с обратной стороны. То есть rbegin() (или crbegin()) указывает на последний элемент (так, как если бы он стоял первым), а rend() (или crend()) указывает на элемент, предшествующий первому (так, как если бы он стоял на месте элемента следующим за последним):

first = v.rbegin();
first = v.crbegin();
last = v.rend();
last = v.crend();

Если массив не будет изменять свой размер, то для обхода элементов удобнее, в этом случае, применять цикл while:

while (first != last) {
   cout << *first << " ";
   first++;
}

Примечание. Если размер массива будет изменяться, то в таком случае итератор используется не по имени, а путем вызова функции непосредственно, как, например, реализовано в программе 16.1 (функция end() вызывается каждый раз в заголовке цикла while).
Приведем пример задачи в которой реализуются разные подходы для перебора элементов вектора.
Программа 16.1 Дан целочисленный массив размера N. Удалить из массива все элементы, встречающиеся ровно два раза, и вывести размер полученного массива и его содержимое.

#include <iostream>
#include <vector>
#include <ctime>
#include <random>
#include <algorithm>
using namespace std;

bool twoFind(vector<int>&, int);

int main() {
	vector<int> mas;
	vector<bool> save(0, 20);
	mas.reserve(20);
	default_random_engine rnd(time(0));
	uniform_int_distribution<unsigned> d(10, 99);
	int n;
	cout << "n = "; cin >> n;
	for (int i = 0; i < n; i++) {
		int r = d(rnd);
		mas.push_back(r);
		cout << mas[i] << " ";
	}
	cout << endl;
	// Сохраняем позиции таких элементов
	for (size_t i = 0; i < mas.size(); i++)
		if (twoFind(mas, mas[i])) {
			save[i] = 1;
		}
	auto first = mas.begin();
	int *k = new int(0);
	while (first != mas.end()) {
		if (save[*k])
			// удаляем и передвигаем итератор на
			// следующий элемент
			first = mas.erase(first);
		else
			// иначе переходим к следующему
			first++;
		*k += 1;
	}
	// Освобождаем память
	save.~vector();
	delete k;
	cout << mas.size() << endl;
	for (auto &ar : mas)
		cout << ar << " ";
	cout << endl;
	return 0;
}

bool twoFind(vector<int> &ar, int t) {
	// count - функция из библиотеки algorithm
	// возвращает количество элементов равных
	// переданному значению t
	int d = count(ar.cbegin(), ar.cend(), t);
	return d == 2 ? true : false;
}

Примечание. В стр. 39 используется специальная функция ~vector(), называемая деструктором. Деструктор (класса) уничтожает вектор и его элементы (освобождая память тогда, когда это нужно).
Доступ к первому и последнему элементу можно получить с помощью методов front() и back(). Эти методы возвращают ссылки на первый и последний элемент в контейнере. Пример использования этих методов показан на примере дека в программе 16.2.

Размер и объем вектора

Мы ранее обсуждали понятия размера и объема для динамического массива string. Абсолютно аналогичные понятия существуют и для любого другого контейнера, в том числе и для вектора. Размер вектора — это фактическое число элементов, а объём — количество используемой им памяти. Если при вставке в вектор новых элементов, его размер становится больше его объёма, происходит перераспределение памяти. Как правило, это приводит к тому, что вектор выделяет новую область хранения, перемещая элементы и свободные старые области в новый участок памяти. Поскольку адреса элементов в течение этого процесса меняются, итераторы элементов в векторе могут стать недействительными. Использование недействительных итераторов приведёт к неопределенному поведению.
vecДля работы с размером и объемом вектора определены следующие методы:

  • empty() Возвращает true, если вектор пуст
  • size() Возвращает количество элементов в векторе
  • max_size() Возвращает максимально возможное количество элементов в векторе
  • reserve() Устанавливает минимально возможное количество элементов в векторе
  • capacity() Возвращает количество элементов, которое может содержать вектор до того, как ему потребуется выделить больше места.
  • shrink_to_fit() Уменьшает количество используемой памяти за счет освобождения неиспользованной

Модификаторы и функция-член assign()

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

  • clear() Очищает контейнер
  • insert() Вставляет элементы
  • emplace() Создает элементы на месте (в позиции итератора). Не используется копирование или перемещение. В определенных задачах может использоваться вместо insert()
  • emplace_back() Создает элементы на месте в конце массива
  • erase() Удаляет элементы
  • push_back() Добавляет элемент в конец
  • pop_back() Удаляет последний элемент
  • resize() Изменяет количество хранимых элементов
  • swap() Обменивает содержимое
  • assign() Заменяет содержимое вектора на новое

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

Операции сравнения

Для контейнера vector определены операции сравнения ==,!=,<,<=,>,>=. Сравнение двух массивов осуществляется точно также, как и для контейнера string, т. е. поэлементно. Следует заметить, что если для фундаментальных типов будут разрешены все операции сравнения, то для сравнения массивов абстрактных типов соответствующие операции сравнения должны быть разрешены (определены в классе).

Контейнер deque

Контейнер deque (двухсторонняя очередь) имеет много общего с контейнером vector. deque также является последовательным контейнером произвольного доступа, как и vector. В отличие от vector, расширение deque происходит более эффективно, но нет гарантии, что данные будут находится в одной области памяти. Главное отличие этих контейнеров в том, что deque открыт не с одного конца (как vector), а с обоих.
deqДеки более сложные структуры данных, чем вектора. Если вектор представляет собой один блок памяти, то дек можно представить себе как пакет таких блоков.
Вставка элементов в начало и в конец deque осуществляется очень быстро. Обход дека с помощью итераторов, в виду его устройства, будет осуществляться медленнее, чем обход вектора. При каждой вставке и удалении не в начало или не в конец дека приведет к недействительности итераторов как начала, так и конца.
Примечание. Если имеется необходимость поддержки быстрой вставки в любую позицию, то необходимо использовать контейнер list (двусвязный список). В отличие от предыдущих, list не предоставляет произвольный доступ (т. е. отсутствуют операции [] и at()), поэтому обход этого контейнера можно осуществлять только с помощью итераторов.
Для контейнера deque не определены методы работы с объемом capacity() и reserve(), но метод shrink_to_fit() использовать можно. Связано это с тем, что деки самостоятельно освобождают блоки памяти, однако, не уменьшают при этом объем.

Методы push_front(), pop_front() и emplace_front()

Для вставки и удаления элементов в начале массива deque имеет специальные методы:

  • push_front() - добавляет элемент в начало контейнера
  • pop_front() - удаляет элемент в начале контейнера
  • emplace_front() – создает элементы в начале списка

С помощью контейнера deque решим классическую задачу проверки баланса скобок. Дана строка, содержащая открывающие и закрывающие скобки (, ), [ и ]. Проверить, что скобки расставлены правильно. Например, строка "((()[()]))" имеет правильный набор скобок, но баланс нарушен. В строке ")()[[])))" - скобки расставлены неверно. А в этой строке скобки расставлены правильно: "((([(([[[]]]))])))".
Программа 16.2

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main() {
	cout << "Введите строку из скобок\n";
	deque<char> d;
	string s;
	getline(cin, s);
	for (auto &r : s) d.push_back(r);
	bool f = true;
	while (f)
		if ((d.back() == ')' && d.front() == '(') ||
			(d.back() == ']' && d.front() == '[')) {
				d.pop_back();
				d.pop_front();
		} else {
			f = false;
		}
	d.shrink_to_fit();
	if (d.empty())
		cout << "Скобки расставлены верно!";
	else
		cout << "Скобки расставлены неправильно!";
	cout << endl;
	return 0;
}

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

Адаптеры контейнеров

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

stack

Стек - это структура данных в которой элементы добавляются и удаляются в вершине стека. Массив элементов, организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Обычно такую структуру представляют как стопка тарелок: доступ ко второй (сверху) тарелке можно получить только после того, как будет взята первая тарелка. В основу адаптера stack положен (по умолчанию) контейнер deque.
stack
Для stack определены следующие функции:

  • top() Доступ к верхнему элементу
  • empty() Возвращает true, если stack пуст
  • size() Количество элементов в стеке
  • push() Добавляет элемент в вершину
  • emplace() Создание элемента на месте с добавлением в вершину
  • pop() Удаляет элемент с вершины
  • swap() Обменивает содержимое

Помимо этого, поддерживаются все операции сравнения и операция присваивания.
Рассмотрим одну из задач, которую легко можно решить с помощью стека. В постфиксной записи арифметического выражения операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения. Дано выражение в постфиксой записи, содержащее однозначные числа, операции +, , *. Вычислите значение выражения, записанного в постфиксной форме (называемой также обратной польской записью).
Программа 16.3

#include <iostream>
#include <string>
#include <stack>
using namespace std;

void myStk(int&, int&, stack<int>&);

int main() {
	string S;
	cout << "Введите строку, изображающую арифметическое выражение:"
		 << endl;
	getline(cin, S);
	stack<int> stc;
	for (auto &r : S) {
		if (r == '*') {
			int a, b;
			myStk(a, b, stc);
			stc.push(a * b);
		}
		else if (r == '+') {
			int a, b;
			myStk(a, b, stc);
			stc.push(a + b);
		}
		else if (r == '-') {
			int a, b;
			myStk(a, b, stc);
			stc.push(a - b);
		}
		else
			stc.push(r - '0');
	}
	cout << stc.top() << endl;
	return 0;
}

void myStk(int &m, int &n, stack<int> &st) {
	m = st.top();
	st.pop();
	n = st.top();
	st.pop();
}
queue

Очередь — структура данных в которой добавление элемента возможно лишь в конец очереди, а выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется. Массив элементов, организован по принципу FIFO (англ. First In — First Out, «первый пришёл — первый вышел»).
В основу адаптера queue положен (по умолчанию) контейнер deque.
queue
Для queue определены следующие функции:

  • front() Доступ к первому элементу
  • back() Доступ к последнему элементу
  • empty() Возвращает true, если queue пуста
  • size() Количество элементов в очереди
  • push() Вставляет элемент в конец очереди
  • emplace() Создаёт элемент на месте с добавлением в конец очереди
  • pop() Удаляет первый элемент
  • swap() Обменивает содержимое

Помимо этого, поддерживаются все операции сравнения и операция присваивания.
Очередь нашла свое применение в алгоритмах так называемого обхода дерева (или графа) в ширину (англ. breadth-first search, BFS). Не вдаваясь глубоко в теорию графов, рассмотрим пример такой задачи на основе задачи ЕГЭ.
Вася, решая задачи формата ЕГЭ, дошел до задачи об исполнителе:
«У исполнителя Калькулятор две команды:

  1. прибавь 3
  2. умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4».
graf
Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел a и b построить программу наименьшей длины получения числа b из числа a. Напишите программу, которая по заданным числам a и b вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из a число b (при условии, что команды используются теже).

#include <iostream>
#include <queue>
using namespace std;

int main() {
	int a, b, i = 0;
	cout << "Корень => "; cin >> a;
	cout << "Искомая вершина => "; cin >> b;
	queue<int> rob;
	bool f = false;
	// Помещаем исходную вершину в очередь
	rob.push(a);
	// Пока очередь не пуста
	while (!rob.empty()) {
		// Берем элемент из очереди (посещаем вершину)
		int p = rob.front();
		rob.pop();
		// Определяем потомков и добавляем их в очередь
		rob.push(p * 4);
		rob.push(p + 3);
		i += 2;
		// Если найдена вершина с необходимым значением - выходим
		if (p * 4 == b || p + 3 == b) {
			f = true;
			break;
		}
		// Также выходим, если достигли лимита
		if (rob.size() > 1000)
			break;
	}
	int j = 0;
	// Определяем количество команд
	if (f) {
		while (i > 1) {
			++j;
			i /= 2;
		}
		cout << "Наименьшее число команд = "
			 << j << endl;
	} else
		cout << "Алгоритм не найден" << endl;
	return 0;
}

Ссылки


Print Friendly, PDF & Email

Comments are closed.