§23 Класс vector

Общие сведения

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

Определение и инициализация

Для начала работы с контейнером необходимо включить заголовок следующей директивой:

#include <vector>
Конструктор

Конструктор класса (от англ. constructor) — специальный метод, вызываемый при создании объекта. Основная задача конструктора — произвести инициализацию. Чтобы создать объект типа vector необходимо объявить или определить вектор. Для определения вектора (V) используется специальное описание типа шаблонного класса включающее имя класса и (в угловых скобках) тип элементов. В качестве типа элементов (T) может выступать как один из базовых типов, так и абстрактные типы (например, string):

vector<T> V;

Данный вид определения называется конструктором по умолчанию. Он создает пустой контейнер.
Другие виды конструкторов принимают инициализирующие аргументы. Все конструкторы принимают ещё один необязательный параметр — объект-распределитель памяти (allocator). В STD определен распределитель памяти по умолчанию, который использует для выделения и освобождения памяти стандартные операции new и delete. Ниже везде этот параметр опущен. (Подробнее см. здесь [2]).
Следующий конструктор создает вектор в котором будет count элементов, равных value

vector<T> V(size_t count, const T& value) 

Конструктор копирования. Создает контейнер с копией содержимого other_V.

vector<T> V(other_V); // или
vector<T> V = other_V;

Конструктор использует итераторы. Инициализация значениями из промежутка в интервале [first, last)

vector<T> V(first, last);

Конструктор использует список инициализации.

vector<T> V(std::initializer_list init); // или непосредственно
vector<T> V = {val1, val2, val3...}; // или
vector<T> V {val1, val2, val3...};
Деструктор

Деструктор — это специальный метод, который разрушает объект, созданный конструктором. После вызова деструктора используемая память освобождается. Если элементы являются указателями, то объекты, на которые они указывают, не уничтожаются.

V.~vector();

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

Доступ к элементам вектора можно получить различными способами.

Операция обращения по индексу []

Эта операция используется для вектора аналогично, как и для для C-массивов. Будет возвращена ссылка на элемент по индексу. Контроль выхода за границы массива также не осуществляется. Поэтому данная операция не рекомендуется к использованию.

Метод at

Чтобы обход массива был более безопасен при использовании индексов, необходимо применять метод at(). Метод возвращает ссылку на элемент по индексу. В случае выхода индекса за границы вектора генерируется исключение std::out_of_range.
Программа 23.1 Демонстрация вывода одного и того же вектора с помощью operator[] и метода at().

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
	vector<int> mas {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	for (int i = 0; i < 10; i++)
		cout << mas[i] << setw(3);
	cout << endl;
	for (size_t i = 0; i < mass.size(); i++)
		cout << mass.at(i) << setw(3);

	return 0;
}

Если в процессе работы цикла изменение размера массива не предвидится, то наилучшим решением для обхода элементов вектора будет использование диапазонного цикла for:
Программа 23.2

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
	int ar[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	// Инициализация элементами C-массива
	vector<int> mas(ar + 5, ar + 10);
	for (auto &r : mas)
		cout << 2 * r << setw(3);
	return 0;
}

Примечание. Переменная r не обязательно должна быть ссылкой. Если r не является ссылкой, то значения будут копироваться.

Доступ с помощью итераторов

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

  • begin(), cbegin() - Возвращает итератор на первый элемент контейнера.
  • end(), cend() - Возвращает итератор на элемент, следующий за последним.
  • rbegin(), crbegin() — Возвращает обратный итератор на первый элемент.
  • rend(), crend() — Возвращает обратный итератор на элемент, следующий за последним.

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

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

int main() {
	vector<int> mas {1, 5, 4, 0, 6, 7, 5, 3, 4, 5,
					 3, 7, 8, 7, 5, 6, 2, 2, 6, 8};
	auto first = mas.begin();
	auto last = mas.end();
	double s = 0;
	while (first != last) {
		s += *first;
		first++;
	}
	s /= mas.size();
	int k = count_if(mas.cbegin(), mas.cend(), [&s](int &r){
		return r > s;
	});
	cout << double(k) / mas.size() * 100 << "%" << endl;
	return 0;
}
}
Методы front и back

Метод front возвращает ссылку на первый элемент в контейнере. Выражение V.front() эквивалентно *V.begin().
back() возвращает ссылку на последний элемент в контейнере. Выражение V.back() эквивалентно *(--V.end()).

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

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

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

Примечание. Уменьшить объем массива можно следующей инструкцией:

vector<int> (V).swap(V);

Программа 23.4

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

int main() {
    int k = 200;
    vector<int> V;
    cout << "size = " << V.size()
         << "\ncapacity = " << V.capacity()
         << "\n------------------------------------"
         << endl;
    while (k--) V.push_back(10);
    cout << "size = " << V.size()
         << "\ncapacity = " << V.capacity()
         << "\n------------------------------------"
         << endl;
    vector<int> (V).swap(V);
    cout << "size = " << V.size()
         << "\ncapacity = " << V.capacity()
         << "\n------------------------------------"
         << endl;
    return 0;
}
size = 0
capacity = 0
------------------------------------
size = 200
capacity = 256
------------------------------------
size = 200
capacity = 200
------------------------------------

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

Над векторами применимы все виды операций сравнения (отношения): ==, !=, <, <=,>, >= и прямого присваивания одному вектору, значения другого. Сравнение двух массивов осуществляется точно также, как и для контейнера string, т. е. поэлементно. Следует заметить, что для вектора, имеющего элементы фундаментальных типов, будут разрешены все операции сравнения, а для сравнения массивов абстрактных типов соответствующие операции сравнения должны быть разрешены (определены в классе этого типа). Присваивание заменяет значение одного вектора значением другого. Это фактически, равносильно применению метода assign() (см. ниже).
Программа 23.5 Заполнить вектор значениями элементов другого вектора, если он меньше сравниваемого. Если два вектора равны, то исходный вектор заполнить этими же элементами, но в обратном порядке.

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

int main() {
    vector<int> mas1 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<int> mas2 (10);
    if (mas1 > mas2)
        mas2 = mas1;
    if (mas2 == mas1) {
        auto i = mas1.size() - 1;
        for (auto &ar: mas1) {
            ar = mas2[i];
            --i;
        }
    }
    for (auto &ar: mas1) cout << ar << " "; cout << endl;
    for (auto &ar: mas2) cout << ar << " "; cout << endl;
    return 0;
}
10 9 8 7 6 5 4 3 2 1 
1 2 3 4 5 6 7 8 9 10

Методы-модификаторы

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

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

Рассмотрим их подробнее.

clear и empty

Метод V.clear(void) очищает контейнер (удаляет все элементы). При этом, V.capacity() оставляет без изменений. Возвращаемый тип void.
Проверить пуст ли контейнер можно методом empty() (проверяет begin() == end()).

V.clear();
if (V.empty()) cout << true << endl;
insert и erase

Методы insert() и erase() вставляют и удаляют элементы в произвольной позиции.

//Вставить элемент, имеющий значение value, в позицию it:
it_in = V.insert(it, value); //или
it_in = V.insert(it, count, value); //или
it_in = V.insert(it, first, last); //из интервала [first, last)
//Удалить элемент в позиции it:
it_er = V.erase(it); //или
it_er = V.erase(first, last); //из интервала [first, last)

Примечание. Поскольку методы insert() и erase() делают итератор end() недействительным, в заголовке цикла следует использовать вызов метода end() непосредственно.
Методы insert() и erase() возвращают соответствующий итератор, что может быть использовано для обновления итератора first. Как это сделать, показано в следующей программе.
Программа 23.6 Перед каждым четным элементом вектора вставить 0.

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

int main() {
    vector<int> mas(10);
    auto first = mas.begin();
    int i = 0;
    while (first != mas.end()) {
        *first = ++i;
		cout << *first << " ";
		++first;
	}
	//Возвращаем итератор на место
    first = mas.begin();
    //Для end не используем сохранение
	while (first != mas.end()){ 
        if (*first % 2 == 0){
            first = mas.insert(first, 0);
            // Перешагиваем через один
            first += 2;
		} else {
		    // Иначе идем к следующему
            ++first;
		}
	}
	cout << endl;
    first = mas.begin();
    while (first != mas.end()) {
		cout << *first << " ";
		++first;
	}
	return 0;
}
1 2 3 4 5 6 7 8 9 10 
1 0 2 3 0 4 5 0 6 7 0 8 9 0 10 
push_back и pop_back

Метод push_back() вставляет элемент в конец, а pop_back() удаляет последний элемент.
Использование:

V.push_back(value);
V.pop_back();
emplace и emplace_back

Методы emplace() и emplace_back() создают элементы на месте (в позиции итератора), без использования операций копирования или перемещения. Передается инициализированный список аргументов.

V.emplace(const_iterator pos, Args&&... args);
V.emplace_back(Args&&... args);

Эти методы призваны создать более удобный интерфейс для работы с абстрактными типами, но вполне могут быть использованы и для векторов с элементами фундаментальных типов, заменяя, тем самым, метод insert. Рассмотрим на примере.
Программа 23.7 Создайте структуру в которой будут храниться (в виде массива) параметры треугольников. Используйте метод emplace_back для инициализации полей структуры переменными, хранящими величины сторон. Выведите площади сохраненных треугольников.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct tri {
	double a, b, c;
	tri (double ta, double tb, double tc) :
		a(ta), b(tb), c(tc) {}
	double P = a + b + c;
	double p = P / 2;
	double S = sqrt(p * (p - a) * (p - b) * (p - c));
	double R = a * b * c / 4 / S;
	double r = 2 * S / P;
};

int main() {
	int n;
	vector<tri> V;
	cout << "Количество треугольников: ";
	cin >> n;
	while (n--) {
		double l, p, z;
		cout << "Сторона А => "; cin >> l;
		cout << "Сторона В => "; cin >> p;
		cout << "Сторона С => "; cin >> z;
		V.emplace_back(l, p, z);
	}
	for (auto &r : V)
		cout << r.S << " ";
	return 0;
}
resize

Метод resize() изменяет размер контейнера. Использование:

V.resize(count);
V.resize(count,  value);

resize() увеличивает размер массива до величины size_t count, если текущий размер меньше, чем count, добавляются дополнительные элементы, которые инициализируются const value_type& value. Если текущий размер больше count, контейнер сводится к размеру первых count элементов.

swap

Метод производит обмен элементов между двумя массивами vector. Типы векторов должны совпадать:

V.swap(V2); // или
swap(V, V2);
assign

Метод assign() заменяет содержимое контейнера.

V.assign(count, value);
V.assign(first, last);

В первом случае заменяется size_t count копиями значений const T& value. Во втором копиями элементов из диапазона [first, last).

Презентация к уроку
Домашняя работа
  1. Дан целочисленный массив размера N. Увеличить все четные числа, содержащиеся в массиве, на исходное значение первого четного числа. Если четные числа в массиве отсутствуют, то оставить массив без изменений.
  2. Дан массив A размера N и целые числа K и L (1 ≤ K < L ≤ N). Переставить в обратном порядке элементы массива, расположенные между элементами A[K] и A[L] , не включая эти элементы.
  3. Дан целочисленный массив размера N. Удалить из массива все элементы, встречающиеся более двух раз, и вывести размер полученного массива и его содержимое.
Литература
  1. vector (C++)
  2. Джосаттис Н.М. Стандартная библиотека C++. Справочное руководство. 2-е изд. — М.: Вильямс, 2014
  3. Прата, Стивен. Язык программирования C++. Лекции и упражнения, 6-е изд.: Пер. с англ. — М.: ООО «И.Д. Вильямс», 2012
  4. Липпман Б. Стенли, Жози Лажойе, Барбара Э. Му. Язык программирования С++. Базовый курс. Изд. 5-е. М: ООО "И. Д. Вильямс", 2014


Comments are closed