C++. Динамические массивы: vector

Векторы в С++ (vector)

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

Создание вектора

#include <vector>
...
int main()
{
    // объявление целочисленного вектора v для 10 элементов
    vector <int> v(10); 
 
    // тоже самое с нулевыми начальными значениями (вектор v1)
    vector <int> v1(10, 0);
...

 

Заполнение вектора

Способ 1
Выделяем память для n-го количества элементов и заполняем их, считывая их с клавиатуры.
 

int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; i++) 
    cin >> a[i];

Способ 2
Второй способ бывает нужен когда количество элементов неизвестно. Сначала создается пустой вектор, а потом с помощью метода push_back() новый элемент добавляется в конец вектора.
 

int n;
cin >> n;
vector <int> a;

for (int i = 0; i < n; i++) {
      int b;
      cin >> b;
      a.push_back(b);   
}

Размер вектора

int b = a.size();

Итераторы

Одним из способов перебора элементов в контейнерах (структурах данных) является итератор (iterator), которые бывают нескольких типов.
 
Для вектора используется самый мощный - итератор с произвольным доступом (random-access Iterator).  Итератор с произвольным доступом помимо последовательного перемещения может обратиться к произвольному элементу вектора.

Преимущества итераторов
1)  При удалении элементов и переборе элементов с помощью индексов ([]) нам надо все время следить за количеством оставшихся элементов, чтобы не выйти за пределы вектора, а с помощью итератора можно использовать end(), указывающий на конец вектора.
2) С помощью итератора можно легко динамически удалять и вставлять элементы в векторе. 
 

Объявление итератора

1) Объявление итератора для целочисленного вектора и указание его на первый элемент в векторе.

vector <int> myvector = { 1, 2, 3, 4, 5 };       
vector <int>::iterator it = myvector.begin(); 

2) Объявление итератора для целочисленного вектора и указание его на элемент после последнего в векторе.

vector <int> myvector = { 1, 2, 3, 4, 5 };       
vector <int>::iterator it = myvector.end();   // указывает на элемент после последнего, 
vector <int>::iterator it1 = myvector.end() - 1 ;  // указание на последний элемент.

 

Получение и вывод значения

Получение и вывод элемента на который указывает итератор.

cout << *it;

 

Перемещение позиции итератора

Перемещение позиции итератора на 3 позиции вперед.

advance(it, 3); 

 

Создание нового итератора на основе существующего

Создание нового итератора на основе существующего с продвижением на 3 позиции.

auto it1 = next(it, 3);

 

Вывод значений вектора с помощью итератора

vector<int>::iterator it;
for (it = myvector.begin(); it != myvector.end(); ++it) {
     cout<<*it<<" ";
 }

Обход вектора

Для обхода вектора от последнего элемента к первому используется обратный итератор reverse_iterator, его получение обеспечивают:
1) rbegin() -  возвращает обратный итератор, указывающий на последний элемент вектора, применение операции ++ приводит к переходу на предыдущий элемент;
2) rend() -  возвращает обратный итератор, указывающий на предшествующий первому элемент вектора, применение операции ++ приводит к переходу  на следующий.

vector<int>::reverse_iterator it = myvector.rbegin();  // указывает на последний элемент
vector<int>::reverse_iterator it = myvector.rend();    // указывает на элемент, 
                                                       // который стоит до первого, 

Вставка элемента в вектор с использованием итератора

• arr.insert(it, a) вставляет значение a перед позицией итератора it
• Метод insert() возвращает итератор на вставленный элемент

Пример использования

it = arr.insert(it, a)  // в переменную it сохраняет итератор на вставленный элемент

---

После arr.insert(it, a) итератор it становится невалидным, так как:

• либо происходит реаллокация (вектор перемещается в новый участок памяти, и it указывает на старый)

• либо элементы сдвигаются вправо (и it начинает указывать на другой элемент)

Метод insert() возвращает валидный итератор на вставленный элемент, который нужно присвоить итератору, чтобы продолжить корректную работу с вектором

Удаление элемента массива

arr.erase(it) - удаление элемента. Метод erase() удаляет элемент, на который указывает итератор it.

После arr.erase(it) it становится НЕВАЛИДНЫМ (указывает на удаленный участок памяти)!

После удаления элемента, итератор it "висит" в воздухе и указывает на удаленную память. Использование такого итератора приводит к неопределенному поведению (программа может упасть или работать неправильно).

it = arr.erase(it) - метод erase() возвращает новый валидный итератор на элемент, следующий за удаленным, и этот итератор необходимо присвоить it.

Изменение размера вектора

Метод resize() изменяет размер контейнера a (строки, вектора) до указанного размера y: a.resize(y, value)

Особенности

1. Увеличение размера - добавляет элементы по умолчанию (для строк - '\0', для чисел - 0)

2. Уменьшение размера - удаляет лишние элементы (безвозвратно!)

3. С заполнением - можно указать значение для новых элементов (value)

4. Сохраняет существующие данные (если не уменьшаем)

Многомерные вектора

Многомерные векторы - это векторы, содержащие другие векторы в качестве элементов. 

Двумерные вектора

// Способ 1: Объявление без инициализации
    vector<vector<int>> matrix1;
    
// Способ 2: С указанием размеров
    vector<vector<int>> matrix2(3, vector<int>(4)); // 3x4
    vector<vector<int>> matrix3(3, vector<int>(4, 0)); // 3x4, заполнен нулями
    
// Способ 3: Прямая инициализация
    vector<vector<int>> matrix4 = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

Трехмерные вектора

int x = 2, y = 3, z = 4;
    
// Создаем 3D вектор 2x3x4
vector<vector<vector<int>>> cube(x, 
      vector<vector<int>>(y, 
      vector<int>(z, 0)));

Вектора большей размерности создаются подобным образом.

Сортировка вектора

Стандартная сортировка (по возрастанию)

vector<int> v = {5, 2, 8, 1, 9};
sort(v.begin(), v.end());  // 1, 2, 5, 8, 9

Сортировка по убыванию

// Способ 1 - greater<>
sort(v.begin(), v.end(), greater<int>());

// Способ 2 - лямбда-функция
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});

Сортировка части вектора

vector<int> v = {9, 3, 7, 1, 5, 2};
sort(v.begin() + 1, v.begin() + 4);  // сортирует элементы 1-3
// Результат: 9, 1, 3, 7, 5, 2