По возможности используйте std :: vector :: reserve

Опубликовано: 31 Декабря, 2021

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

Класс std :: vector предоставляет полезный резерв функции, который помогает пользователю указать минимальный размер вектора. Он указывает, что вектор создан таким образом, что он может хранить по крайней мере количество указанных элементов без необходимости перераспределять память.

std :: vector :: резерв

недействительный резерв (size_type n)
Тип возврата: нет
Аргументы: n, обозначающее количество элементов, которые должны быть сохранены в векторе.

Запрашивает, чтобы вектор был достаточно большим, чтобы хранить как минимум n элементов. 
Если текущая емкость вектора меньше n, то перераспределение будет 
происходить. В остальных случаях перераспределения не произойдет. Функция делает
не изменять существующие элементы в векторе

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

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

 // CPP program to demonstrate use of
 // std::vector::reserve
 #include <chrono>
 #include <iostream>
 #include <vector>
 
using std::vector;
 using std::cout;
 using namespace std::chrono;
 
int main()
 {
    // No of charactes
    int N = ( int )1e6;
 
    vector< int > v1, v2;
 
    // Reserve space in v2
    v2.reserve(N);
 
    // Start filling up elements in v1
    // To measure execution time in C++, refer below
    // https://www.geeksforgeeks.org/measure-execution-time-function-cpp/
 
    auto start = high_resolution_clock::now();
    for ( int i = 0; i < N; ++i)
        v1.push_back(i);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
 
    cout << "Method I took " << duration.count() << " microseconds
" ;
 
    // Start filling up elements in v2
    start = high_resolution_clock::now();
    for ( int i = 0; i < N; ++i)
        v2.push_back(i);
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);
 
    cout << "Method II took " << duration.count()
         << " microseconds 
" ;
 
    return 0;
 }

Выход: (Зависит от машины)

Метод I занял 18699 микросекунд
Метод II занял 16276 микросекунд.

Примечание:
Гарантируется, что предварительное резервирование места займет меньше времени, чем попытка вставить элементы без указания размера вектора. Кроме того, он добавляет семантическую полезность коду, и мы, по крайней мере, узнаем, насколько большим будет вектор.

Хотите узнать о лучших видео и практических задачах, ознакомьтесь с базовым курсом C ++ для базового и продвинутого уровня C ++ и курсом C ++ STL для базового уровня плюс STL. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

C++

По возможности используйте std :: vector :: reserve

РЕКОМЕНДУЕМЫЕ СТАТЬИ