Работа с std::vector

Мотивация

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

Так можно прийти к необходимости контейнера, который может сохранять переменные определенного типа. Наиболее частотный контейнер – вектор [std::vector](https://en.cppreference.com/w/cpp/container/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";
}

Plain Text 2 2 3 4 4 4 5 8

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

#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) на операцию, т.к. память уже была выделена
    }
}