std:: vector

За исключением std::vector<bool> частичной специализации, элементы хранятся непрерывно, что означает, что к элементам можно обращаться не только через итераторы, но и используя смещения к обычным указателям на элементы. Это означает, что указатель на элемент вектора может быть передан в любую функцию, которая ожидает указатель на элемент массива.

Хранение вектора обрабатывается автоматически, расширяясь по мере необходимости. Векторы обычно занимают больше места, чем статические массивы, потому что выделяется дополнительная память для обработки будущего роста. Таким образом, вектору не требуется перераспределять память каждый раз при вставке элемента, а только когда дополнительная память исчерпана. Общий объем выделенной памяти можно запросить с помощью функции capacity() . Дополнительная память может быть возвращена системе с помощью вызова shrink_to_fit() ^[1] .

Перераспределения обычно являются затратными операциями с точки зрения производительности. Функция reserve() может быть использована для исключения перераспределений, если количество элементов известно заранее.

Сложность (эффективность) стандартных операций с векторами следующая:

• Произвольный доступ - константная сложность 𝓞(1) .
• Вставка или удаление элементов в конце - амортизированная константная сложность 𝓞(1) .
• Вставка или удаление элементов - линейная сложность относительно расстояния до конца вектора 𝓞(n) .

std::vector (для T отличного от bool ) удовлетворяет требованиям Container , AllocatorAwareContainer (начиная с C++11) , SequenceContainer , ContiguousContainer (начиная с C++17) и ReversibleContainer .

1. ↑ В libstdc++, shrink_to_fit() недоступен в режиме C++98.

#include <iostream>
#include <vector>
int main()
{
    // Создаем вектор, содержащий целые числа
    std::vector<int> v = {8, 4, 5, 9};
    // Добавляем еще два целых числа в вектор
    v.push_back(6);
    v.push_back(9);
    // Перезаписываем элемент в позиции 2
    v[2] = -1;
    // Выводим вектор
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

8 4 -1 9 6 9