Работа с std::vector

Мотивация

В программировании часто возникает необходимость где-то сохранять данные, которыми оперирует программа, но количество данных может быть заранее неизвестно. Например, на прошлой лекции мы получали цифры числа в обратном порядке. Если бы мы хоти вывести их в “верном” порядке – справа налево, то нам пришлось бы сохранять цифры по мере их получения, а затем “перевернуть”, восстановив таким образом порядок. В этой ситуации мы не знаем до компиляции, сколько цифр нужно будет сохранить.

Так можно прийти к необходимости контейнера, который может сохранять переменные определенного типа. Наиболее частотный контейнер – вектор std::vector

std::vector

Это динамический массив, который позволяет быстро добавлять элементы в конец и может хранить необходимое число элементов.

{
     std::vector<int> data;         // пустой вектор
     std::vector<int> data(10);     // вектор длины 10, элементы не инициализированы
     std::vector<int> data(10, -1); // вектор длины 10, все элементы равны -1

     std::vector<int> data = {1, 2, 3, 4}; // вектор {1, 2, 3, 4}
     std::vector<int> data{1, 2, 3, 4};    // вектор {1, 2, 3, 4}
     std::vector<int> data{10, -1};        // вектор {10, -1}
 }

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

#include <iostream>
#include <vector>
#include <string>

int main() {
    std::vector<std::string> data = {"Just", "some", "random", "words"};
    for (std::string &word: data) {
        std::cout << word << ' ';
    }
    std::cout << '\n';
}

Код выше выводит через пробел слова, перечисленные в векторе. На что нужно обратить внимание:

для использование вектора, необходимо написать #include <vector> – подключить соответствующую библиотеку
в <> рядом с вектором мы указываем тип элемента вектора. По умолчанию вектор готов работать с любым типом объектов (так написана библиотека вектора), затем компилятор “подставляет” указанный тип всюду, где он используется в библиотеке. Подробнее: шаблонные классы и методы, но это находится за пределами нашего курса
для итерации по вектору используется range-based for. Тип локальной переменно должен совпадать с типом элемента вектора. Действительно, мы же хотим в переменную word уметь положить элементы

#include <iostream>
#include <vector>
#include <string>

int main() {
    std::vector<std::string> data = {"Just", "some", "random", "words"};
    for (size_t i = 0; i < data.size(); ++i) {
        std::cout << data[i] << ' ';
    }
    std::cout << '\n';
}

Код выше по функционалу эквивалентен примеру выше, но использует обращение по индексу.

size_t является специальным называнием для типа, который используется для итерации по индексам. Это наибольшее целое беззнаковое число, которое устройство может хранить процессор устройства. Для 32-битных систем size_t занимает 4 байта, для 64-битных – 8 байт. Важно, что этот тип является беззнаковым – не может принимать отрицательные значения.

Работа с std::vector

Все методы std::vector

Наиболее важные:

{
    std::vector<T> data;
    data.size();         // возвращает size_t -- количество элементов
    data.empty();        // возвращает bool -- true, если вектор пуст
    data.back();         // возвращает последний элемент
    data.front();        // возвращает первый элемент

    data.push_back(obj); // добавляет элемент в конец вектора
    data.erase(it_pos);  // удаляет элемент, на который указывает итератор
}

Например, рассмотрим, как можно вывести все цифры числа в обратном порядке:

#include <iostream>
#include <vector>

int main() {
    int num, d;
    std::cin >> num >> d;

    std::vector<int> digits;
    while (num) {
        digits.push_back(num % d);
        num /= d;
    }

    std::cout << "Your number has " << digits.size() << " digits\n";
    if (num == 0) {
        std::cout << "0\n";
        return 0;
    }

    for (size_t i = digits.size(); i > 0; --i) {
        std::cout << digits[i - 1];
    }
    std::cout << '\n';
}

Мы выводим цифры от конца вектора к его началу, выводя таким образом цифры в верном порядке.

Зачем необходима проверка на if (num == 0)? Как уже было сказано выше, size_t является беззнаковым типом, значит, вычитание 1 корректно только если переменная не была равна 0. В противном случае \(0 - 1 = 2^{64} - 1\) на 64-битных системах, то есть наибольшему беззнаковому числу.

Задачи на std::vector

Теперь заметим, что все пройденные приемы работы с последовательностями отлично работают с std::vector и циклом for. Например, считаем последовательность длины \(n\) и найдем количество четных элементов, а также наибольший из них.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int length;
    std::cin >> length;

    std::vector<int> data(length);
    for (size_t i = 0; i < length; ++i) {
        std::cin >> data[i];
    }

    int maxm = 0;
    int cnt = 0;
    for (int elem: data) {
        if (elem % 2 == 0) {
            ++cnt;
            // if element is a new max or if it is the first even element
            if (elem > maxm || cnt == 1) {
                maxm = elem;
            }
        }
    }

    std::cout << cnt;
    if (cnt > 0) { // if maximum was updated at least once
        std::cout << " " << maxm;
    }
    std::cout << '\n';
}

Для ясности приведем итерацию по индексам:

for (size_t i = 0; i < data.size(); ++i) {
    if (data[i] % 2 == 0) {
        ++cnt;
        // if element is a new max or if it is the first even element
        if (data[i] > maxm || cnt == 1) {
            maxm = data[i];
        }
    }
}

Нюансы добавления элементов

Строго говоря, есть 2 раздельных понятия: size и capacity:

size – количество элементов в векторе
capacity – на сколько элементов уже выделена память
size≤ capacity Строгое неравенство достигает в том случае, когда память уже была выделена, но не все элементы уже были добавлены в вектор

Иллюстрация `vector::capacity` и `vector::size`

Как происходит добавление элемента в конец динамического массива:

если size< capacity, то есть выделенного места хватает, то элемент записывается по указателю end(), значение size увеличивается на 1. Сложность такой операции составляет \(\cal{O}(1)\)
если size= capacity, то количество выделенной памяти удваивается. Возможен перенос всего массива в памяти в том случае, если ОС не может предоставить память подряд. capacity удваивается, size увеличивается на 1. Сложность такой операции составляет \(\cal{O}(n)\)
на самом деле это амортизированная константная сложность

#include <iostream>
#include <vector>

int main() {
    std::vector<int> data = {1, 2};
    std::cout << data.size() << "\t" << data.capacity() << "\n";

    data.push_back(3);
    std::cout << data.size() << "\t" << data.capacity() << "\n";

    data.push_back(4);
    std::cout << data.size() << "\t" << data.capacity() << "\n";

    data.push_back(5);
    std::cout << data.size() << "\t" << data.capacity() << "\n";
}

С этим новым знанием можно добиться одинакового исполнения уже знакомой нам части кода:

#include <iostream>
#include <vector>

int main() {
    int length;
    std::cin >> length;

    std::vector<int> data(length); // вектор size==length, память выделена сразу
    for (size_t i = 0; i < length; ++i) {
        std::cin >> data[i]; // O(1) на операцию -- "моментально"
    }
}

#include <iostream>
#include <vector>

int main() {
    int length;
    std::cin >> length;

    std::vector<int> data; // вектор size==0
    data.reserve(length); // этот метод выделяет память без изменения размера вектора
    // теперь size==0, capacity==length
    for (size_t i = 0; i < length; ++i) {
        int new_num;
        std::cin >> new_num; // считываем новое число
        data.push_back(new_num); // O(1) на операцию, т.к. память уже была выделена
    }
}

Вложенные `std::vector<T>`

Вложенными векторами мы будем называть векторы из векторов, то есть объекты типа std::vector<std::vector<int>>. Это вектор, элементами которого являются векторы, а их элементами являются числа.

Например:

#include <iostream>
#include <vector>

int main() {
    const std::vector<std::vector<int>> data = {{1, 2, 3},
                                                {4, 5, 6},
                                                {7, 8, 9}};
    std::cout << data[0][0] << ' ' << data[1][1] << ' ' << data[2][2] << '\n';
    // 1 5 9
}

Так работает индексация в двумерном векторе:

Индексация в двумерном векторе: сначала получаем ряд, потом элемент в этом ряду

Двумерный вектор из примера выше

Создадим двумерный вектора и выведем его элементы. Затем выведем только его диагональ.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    size_t m, n;
    std::cin >> m >> n;  // число строк и столбцов

    // создаём матрицу matrix из m строк
    std::vector<std::vector<int>> matrix(m);
    // std::vector<std::vector<int>> matrix(m, std::vector<int>(n));

    for (size_t i = 0; i < m; ++i) {
        matrix[i].resize(n); // эта строка не нужна, если вложенные векторы изначально были созданы непустыми
        for (size_t j = 0; j < n; ++j) {
            std::cin >> matrix[i][j];
        }
    }
    // тип matrix[i] -- это std::vector<int> -- как и раньше,
    //переходим к элементу вектора по индексу

    // напечатаем матрицу, выводя элементы через табуляцию
    for (size_t i = 0; i < m; ++i) {
        for (size_t j = 0; j < n; ++j) {
            std::cout << matrix[i][j] << '\t'; // сначала индекс строки, затем индекс элемента в этой строке
        }
        std::cout << '\n';
    }
    std::cout << '\n';

    // элементы на диагонале обладают равными индексами (см. иллюстрации выше)
    for (size_t i = 0; i < std::min(n, m); ++i) {
        std::cout << matrix[i][i] << ' ';
    }
    std::cout << '\n';
}

Вывод программы выше, если будет введена квадратная матрица из примера выше:

Напишем функцию, которая будет получать по константной ссылке двумерный вектор чисел и возвращать наибольшее значение. Главное, что здесь нужно отметить – перебор всех элементов почти не изменился от того, что было рассмотрено в прошлых главах.

#include <iostream>
#include <vector>

int findMaxValue(const std::vector<std::vector<int>>& matrix) {
    int maxValue = matrix[0][0];
    // во время изучения рекомендуется явно писать даже сложные типы и не использовать тип auto
    for (const std::vector<int>& row : matrix) {
        for (const int& num : row) {
            if (num > maxValue) {
                maxValue = num;
            }
        }
    }
    return maxValue;
}

int main() {
    std::vector<std::vector<int>> matrix = {{1, 5, 3}, {8, 2, 6}, {4, 9, 7}};

    int maxVal = findMaxValue(matrix);
    std::cout << maxVal << '\n';  // 9
}

Можно аналогично реализовать функцию поиск наибольшего значения в двумерном векторе с использование обращения по индексу:

int findMaxValue(const std::vector<std::vector<int>>& matrix) {
    int maxValue = matrix[0][0];
    for (size_t i = 0; i < matrix.size(); ++i) {
        for (size_t j = 0; j < matrix[i].size(); j++) {
            if (matrix[i][j] > maxValue) {
                maxValue = matrix[i][j];
            }
        }
    }

    return maxValue;
}

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

Сортировка std::vector

Если мы добавили все простые делители в std::vector, то затем нам может потребоваться отсортировать этот массив в порядке возрастания. Сделать это можно с помощью функции sort из стандартной библиотеке

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> data = {1, 5, 2, 4, 3};

    std::sort(data.begin(), data.end()); // теперь вектор отсортирован
    // data равняется {1, 2, 3, 4, 5}

    for (int elem: data) {
        std::cout << elem << ' ';
    }
    // будет выведено: 1 2 3 4 5
    std::cout << '\n';
}

Мотивация

std::vector

Работа с std::vector

Задачи на std::vector

Нюансы добавления элементов

Вложенные std::vector<T>

Сортировка std::vector

Вложенные `std::vector<T>`