|
Реализация динамического массива на С++ с помощью std::vectorКурс по структурам данных: https://stepik.org/a/134212 Мы продолжаем рассматривать динамический массив и на этом занятии посмотрим, как реализуется эта структура данных в языке С++. Использование динамических массивов на С++Непосредственно в С++ есть только статические массивы. Для динамических, чаще всего, используют класс vector из стандартной библиотеки шаблонов (STL). Поэтому вначале нам нужно импортировать модуль vector: #include <vector>А, затем, можно объявить динамический массив, например, так: std::vector<float> digits; Здесь в угловых скобках указывается тип элементов динамического массива. Имя массива digits мы придумываем сами, как и все имена переменных. Все, теперь у нас в программе имеется динамический массив digits и мы можем его использовать. Давайте посмотрим на основные операции, которые можно выполнять с этим объектом. Во-первых, в каждом векторе (динамическом массиве) имеется метод size(), который возвращает число хранимых элементов. Если мы сейчас выведем это значение: std::cout << digits.size(); то увидим ноль. Действительно, на данный момент мы не добавили в вектор ни одного значения. Чтобы добавить новый элемент в конец вектора используется метод: digits.push_back(5.0); И теперь метод size() возвращает один, то есть, массив хранит один элемент. Давайте добавим еще несколько элементов в динамический массив: digits.push_back(4.0); digits.push_back(3.0); digits.push_back(2.0); Соответственно, метод size() возвращает значение 4. Отлично, мы научились объявлять вектор, добавлять в конец новые значения. Но как нам теперь получить (прочитать) отдельные значения этого вектора? Все делается по общему синтаксису, который используется во многих языках программирования, в том числе и в Python. Достаточно записать имя динамического массива и в квадратных скобках указать индекс нужного элемента. Например: std::cout << digits[0] << std::endl; увидим первое значение 5. Или: std::cout << digits[2] << std::endl; увидим значение 3. И так далее. Мы можем указывать любой индекс, принадлежащий диапазону этого массива, начиная с нуля. Если нужно изменить какое-либо значение, то делается все по аналогии следующим образом: digits[1] = -5.43f; сохраняем новое значение -5.43 во 2-м элементе массива. Как видите, все достаточно просто. Используя эту информацию, можно легко догадаться, как вывести все значения вектора в консоль. Для этого воспользуемся циклом for следующим образом: for (int i = 0; i < digits.size(); ++i) std::cout << digits[i] << " "; В ряде случаев бывает полезна операция начальной инициализации вектора определенными значениями. Делается это так: std::vector<float> digits = { 1.0, 2.0, 3.0 }; в момент объявления вектора в фигурных скобках через запятую указываются значения первых элементов (в данном случае первых трех). Если теперь запустить программу, то увидим, что вектор содержит семь элементов (вместе с четырьмя добавляемыми методом push_back()). Давайте дополнительно еще выведем значение capacity – физической емкости динамического массива: std::cout << digits.capacity() << std::endl; Смотрите, эта величина равна 9. Тогда как метод size() возвратил 7 – число хранимых значений. Вспоминаем, что я вам говорил про динамические массивы на предыдущем занятии. У них есть физический размер и логический размер. Как раз capacity показывает физическое пространство, а size() – логическое, то есть, число хранимых значений. Мало того, если нам нужно явно указать размер физического пространства (число элементов), то это можно сделать с помощью метода reserve: digits.reserve(20); Теперь, начальный физический размер нашего динамического массива составляет 20 элементов. В ряде случаев это бывает полезно, чтобы подсказать программе, какой начальный размер целесообразно выбрать, чтобы лишний раз не формировать новый массив с большим размером. Еще один распространенный способ инициализации вектора, когда в момент его объявления мы указываем начальный размер следующим образом: std::vector<float> digits(10); В результате получим 10 элементов и все 10 будут заполнены нулями. Если нужно записать другое начальное значение элементов, то оно указывается следующим аргументом: std::vector<float> digits(10, -5.2f); Далее, для удаления последних элементов используется метод pop_back(): digits.pop_back(); В результате мы видим 9 значений, а capacity при это возвращает прежнее число 10. То есть, при удалении элементов, физический размер массива остается прежним. Если нужно удалить все элементы из вектора, это делается методом: digits.clear(); А метод digits.empty(); возвращает булево значение True для пустого массива (когда size() дает 0) и False в противном случае. Это основные операции с вектором (динамическим массивом) в С++. Конечно, дополнительно можно выполнять вставку новых элементов в произвольную позицию с помощью метода: insert() и удаление промежуточных элементов методом: erase() Но всегда следует помнить, что вычислительная сложность этих операций составляет O(n), а потому в динамическом массиве их лучше избегать. ЗаключениеВот примеры того, как используются динамические массивы в С++. Конечно, они есть практически во всех других современных языках, и принцип их использования подобен тому, что мы с вами рассмотрели на этом занятии. Главное здесь понимать структуру динамического массива и знать скорость выполнения основных его операций: доступа к произвольному элементу, добавление/удаление последних элементов и вставка/удаление промежуточных значений. Все это мы подробно рассмотрели на последних занятиях, и вы теперь это должны хорошо знать. Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
