Класс vector: динамический массив

Класс vector реализует динамический массив, все элементы которого размещаются в памяти последовательно. Добавить элементы можно в любое место массива, при этом размер массива будет автоматически увеличиваться по мере необходимости (в отличие от обычных массивов и объектов класса array). Получить доступ к элементу массива можно по индексу или с помощью итератора. Благодаря последовательному размещению доступ к элементам выполняется быстро, но вставка новых элементов приводит к выделению объема памяти, достаточного для размещения всей последовательности элементов, и переносу всех элементов в новую область. При удалении элемента производится сдвиг всех последующих элементов на одну позицию влево. Прежде чем использовать класс, необходимо в начало программы добавить инструкцию:

#include <vector>

Создание объекта

Объявление класса vector:

template<typename _Tp, typename _Alloc = allocator<_Tp> >
   class vector : protected _Vector_base<_Tp, _Alloc>;

Создать объект можно следующими способами (полный список конструкторов смотрите в документации):

  • объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок задается тип данных. В этом случае массив не содержит элементов. Пример объявления без инициализации:
std::vector<int> arr;
  • указать внутри круглых скобок количество элементов. Пример:
std::vector<int> arr(5);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0 0 0 

Все элементы будут иметь значения по умолчанию для типа. Например, для типа int все элементы будут содержать значение 0. Указать другое значение можно во втором параметре. Пример создания объекта из 5 элементов со значением 1:

std::vector<int> arr(5, 1);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 1 1 1 1
  • перечислить значения через запятую внутри фигурных скобок:
std::vector<int> arr1{1, 2, 3};
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
std::vector<int> arr2 = {4, 5, 6};
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
  • указать объект класса vector внутри круглых скобок или после оператора = (доступны конструкторы копирования и перемещения):
std::vector<int> arr1 = {1, 2, 3};
// Создание копии
std::vector<int> arr2(arr1);
arr2[0] = 55;
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 55 2 3
// Перемещение элементов
std::vector<int> arr3(std::move(arr1));
for (int &el : arr3) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
std::cout << arr1.size() << std::endl; // 0
  • указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона. Пример:
std::vector<int> arr1 = {1, 2, 3};
std::vector<int> arr2(arr1.begin(), arr1.end());
arr2[0] = 55;
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 55 2 3

Вместо итератора можно передать указатель. Создадим объект на основе обычного массива:

const int ARR_SIZE = 3;
int arr[ARR_SIZE] = {1, 2, 3};
std::vector<int> arr2(arr, arr + ARR_SIZE);
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Над двумя объектами класса vector определены операции ==, !=, <, <=, > и >=. Пример сравнения двух объектов:

std::vector<int> arr1 = {1, 2, 3};
std::vector<int> arr2(arr1.begin(), arr1.end());
if (arr1 == arr2) {
   std::cout << "arr1 == arr2" << std::endl;
}

Кроме того, один объект можно присвоить другому объекту. В этом случае выполняется поэлементное копирование (оператор копирования) или перемещение элементов (оператор перемещения). Пример:

std::vector<int> arr1 = {1, 2, 3}, arr2, arr3;
// Создание копии
arr2 = arr1;
arr2[0] = 55;
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 55 2 3
// Перемещение элементов
arr3 = std::move(arr1);
for (int &el : arr3) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
std::cout << arr1.size() << std::endl; // 0

Доступно также присваивание элементов из списка инициализации:

std::vector<int> arr;
arr = {1, 2, 3};
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вместо оператора = для присваивания значения можно воспользоваться методом assign(). Прототипы метода:

void assign(size_type count, const value_type &val);
template<typename _InputIterator>
   void assign(_InputIterator first, _InputIterator last);
void assign(initializer_list<value_type> list);

Первый прототип удаляет существующие элементы, а затем вставляет count элементов val. Второй прототип удаляет существующие элементы, а затем вставляет элементы из диапазона, ограниченного итераторами first и last. Третий прототип удаляет существующие элементы, а затем вставляет элементы из списка инициализации. Пример:

std::vector<int> arr1 = {1, 2, 3}, arr2 = {4, 5};
arr1.assign(3, 0);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0
arr1.assign(arr2.begin(), arr2.end());
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5
arr1.assign({6, 7, 8});
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 6 7 8

Пример присваивания элементов из обычного массива:

const int ARR_SIZE = 3;
int arr[ARR_SIZE] = {1, 2, 3};
std::vector<int> arr2;
arr2.assign(arr, arr + ARR_SIZE);
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вставка элементов

Вставить элементы позволяют следующие методы:

  • push_back() — добавляет элемент в конец массива (доступно копирование и перемещение значения):
std::vector<int> arr;
arr.push_back(10);
arr.push_back(20);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 10 20
  • emplace_back() — создает объект, передавая конструктору указанные через запятую значения, а затем добавляет объект в конец массива. Начиная со стандарта C++17, метод возвращает ссылку на созданный объект:
class C {
public:
   int x, y;
   C(int a, int b) : x(a), y(b) { }
};
// ... Фрагмент опущен ...
std::vector<C> arr;
arr.push_back(C(10, 20));
arr.emplace_back(30, 40);
arr.emplace_back(50, 60);
for (C &el : arr) std::cout << el.x << ' ';
std::cout << std::endl; // 10 30 50
  • insert() — вставляет один или несколько элементов в позицию pos, заданную с помощью итератора. Прототипы метода:
iterator insert(const_iterator pos, const value_type &val);
iterator insert(const_iterator pos, value_type &&val);
iterator insert(const_iterator pos, size_type count,
                const value_type &val);
template<typename _InputIterator>
   iterator insert(const_iterator pos, _InputIterator first,
                   _InputIterator last);
iterator insert(const_iterator pos,
                initializer_list<value_type> list);

Первые два прототипа вставляют элемент в позицию pos, на которую указывает итератор и возвращают итератор, ссылающийся на вставленный элемент. Остальные элементы сдвигаются в конец массива:

std::vector<int> arr = {10};
arr.insert(arr.begin(), 0);     // В начало массива
arr.insert(arr.end(), 20);      // В конец массива
arr.insert(arr.begin() + 1, 5); // В позицию 1
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 5 10 20

Третий прототип вставляет count копий элемента val в позицию pos, на которую указывает итератор. Остальные элементы сдвигаются в конец массива:

std::vector<int> arr = {1, 2, 3};
arr.insert(arr.begin(), 3, 0);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 0 0 0 1 2 3

Четвертый прототип вставляет элементы из диапазона, ограниченного итераторами first и last, в позицию pos, на которую указывает итератор. Остальные элементы сдвигаются в конец массива:

std::vector<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr1.insert(arr1.end(), arr2.begin(), arr2.end());
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6

Пример вставки элементов из обычного массива:

std::vector<int> arr1 = {1, 2, 3};
int arr2[] = {4, 5, 6};
arr1.insert(arr1.end(), arr2, arr2 + 3);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6

Пятый прототип вставляет элементы из списка инициализации в позицию pos, на которую указывает итератор. Остальные элементы сдвигаются в конец массива:

std::vector<int> arr = {1, 2, 3};
arr.insert(arr.end(), {4, 5, 6});
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5 6
  • emplace() — создает объект, передавая конструктору указанные через запятую значения во втором и последующих параметрах, а затем добавляет объект в позицию, заданную в первом параметре. Метод возвращает итератор, ссылающийся на вставленный элемент. Добавим два объекта в конец массива и один в начало:
std::vector<C> arr;
arr.emplace(arr.end(), 30, 40);
arr.emplace(arr.end(), 50, 60);
arr.emplace(arr.begin(), 10, 20);
for (C &el : arr) std::cout << el.x << ' ';
std::cout << std::endl; // 10 30 50
  • swap() — меняет элементы двух массивов местами:
std::vector<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
arr1.swap(arr2);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вместо метода swap() можно воспользоваться одноименной функцией:

std::vector<int> arr1 = {1, 2, 3}, arr2 = {4, 5, 6};
std::swap(arr1, arr2);
for (int &el : arr1) std::cout << el << ' ';
std::cout << std::endl; // 4 5 6
for (int &el : arr2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Определение и изменение количества элементов

Как вы уже знаете, класс vector реализует динамический массив, который может автоматически увеличивать объем зарезервированной памяти. Вставка новых элементов приводит к выделению объема памяти, достаточного для размещения всей последовательности элементов, и переносу всех элементов в новую область. Если зарезервированной памяти достаточно, то перераспределение памяти не производится. Получить количество элементов, для которых зарезервирована память, позволяет метод capacity(), а текущее количество элементов возвращает метод size(). Прототипы методов:

size_type capacity() const noexcept;
size_type size() const noexcept;

Пример:

std::vector<int> arr = {1, 2, 3};
std::cout << arr.size() << std::endl;              // 3
std::cout << arr.capacity() << std::endl;          // 3
arr.pop_back();                                    // Удаляем элемент
std::cout << arr.size() << std::endl;              // 2
std::cout << arr.capacity() << std::endl;          // 3

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

void reserve(size_type n);

Пример резервирования пространства под 10 элементов:

std::vector<int> arr;
arr.reserve(10);
std::cout << arr.size() << std::endl;              // 0
std::cout << arr.capacity() << std::endl;          // 10
arr.push_back(1); arr.push_back(2); arr.push_back(3);
std::cout << arr.size() << std::endl;              // 3
std::cout << arr.capacity() << std::endl;          // 10

Уменьшить размер массива до минимального значения позволяет метод shrink_to_fit(). Прототип метода:

void shrink_to_fit();

Пример:

std::vector<int> arr;
arr.reserve(10);
std::cout << arr.size() << std::endl;              // 0
std::cout << arr.capacity() << std::endl;          // 10
arr.push_back(1); arr.push_back(2); arr.push_back(3);
arr.shrink_to_fit();
std::cout << arr.size() << std::endl;              // 3
std::cout << arr.capacity() << std::endl;          // 3

Метод resize() задает количество элементов, равное числу new_size. Если указанное количество элементов меньше текущего количества, то лишние элементы будут удалены. Если количество элементов необходимо увеличить, то в параметре val можно указать значение, которое заполнит новое пространство. Прототипы метода:

void resize(size_type new_size);
void resize(size_type new_size, const value_type &val);

Пример:

std::vector<int> arr = {1, 2, 3};
arr.resize(2);
std::cout << arr.size() << std::endl;          // 2
arr.resize(5, 0);
std::cout << arr.size() << std::endl;          // 5
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl;                        // 1 2 0 0 0

Метод empty() возвращает значение true, если массив не содержит элементов, и false — в противном случае. Прототип метода:

bool empty() const noexcept;

Пример:

std::vector<int> arr;
std::cout << std::boolalpha
          << arr.empty() << std::endl;          // true
arr = {1, 2, 3};
std::cout << arr.empty() << std::endl;          // false

Узнать максимальное количество элементов, которое теоретически может содержаться в контейнере, позволяет метод max_size(). Прототип метода:

size_type max_size() const noexcept;

Пример:

std::vector<int> arr;
std::cout << arr.max_size() << std::endl; // 4611686018427387903

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

Для удаления элементов предназначены следующие методы:

  • pop_back() — удаляет последний элемент. Прототип метода:
void pop_back();

Пример:

std::vector<int> arr = {1, 2, 3};
arr.pop_back();
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2
  • erase() — удаляет один элемент или элементы из диапазона. Прототипы метода:
iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);

Первый прототип удаляет элемент на который указывает итератор. Второй прототип удаляет элементы из диапазона, ограниченного итераторами first и last:

std::vector<int> arr = {1, 2, 3, 4, 5};
arr.erase(arr.begin());
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 2 3 4 5
arr.erase(arr.begin() + 1, arr.begin() + 3);
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 2 5
  • clear() — удаляет все элементы. Прототип метода:
void clear() noexcept;

Пример:

std::vector<int> arr = {1, 2, 3, 4, 5};
arr.clear();
std::cout << arr.size() << std::endl;     // 0
std::cout << arr.capacity() << std::endl; // 5

Доступ к элементам

К любому элементу контейнера можно обратиться как к элементу массива. Достаточно указать его индекс в квадратных скобках. Нумерация начинается с нуля. Можно как получить значение, так и изменить его. Если индекс выходит за границы диапазона, то возвращаемое значение не определено. Пример доступа к элементу по индексу:

std::vector<int> arr = {1, 2, 3};
std::cout << arr[0] << std::endl; // 1
arr[0] = 55;
std::cout << arr[0] << std::endl; // 55

Для доступа к элементам предназначены следующие методы:

  • at() — возвращает ссылку на элемент, расположенный по индексу n. Метод позволяет как получить значение, так и изменить его. Если индекс выходит за границы диапазона, то генерируется исключение. Прототипы метода:
reference at(size_type n);
const_reference at(size_type n) const;

Пример:

std::vector<int> arr = {1, 2, 3};
std::cout << arr.at(0) << std::endl; // 1
arr.at(0) = 55;
std::cout << arr.at(0) << std::endl; // 55
  • front() — возвращает ссылку на первый элемент. Метод позволяет как получить значение, так и изменить его. Прототипы метода:
reference front();
const_reference front() const;
  • back() — возвращает ссылку на последний элемент. Метод позволяет как получить значение, так и изменить его. Прототипы метода:
reference back();
const_reference back() const;

Пример:

std::vector<int> arr = {1, 2, 3};
arr.front() = 55;
arr.back() = 88;
std::cout << arr.front() << std::endl; // 55
std::cout << arr.back() << std::endl;  // 88
  • begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin() и crend() — возвращают итераторы (см. разд. 16.1.1). Изменим и выведем значение первого элемента:
std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it = arr.begin();
std::cout << *it << std::endl; // 1
*it = 0;
std::cout << *it << std::endl; // 0

Вместо методов begin() и end() можно воспользоваться одноименными функциями. Выведем значение последнего элемента:

std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it = std::end(arr);
std::cout << *(--it) << std::endl; // 3

Все элементы динамического массива размещаются в памяти последовательно. Поэтому массив поддерживает возможность доступа к элементам с помощью указателей. Присвоить указателю адрес первого элемента массива позволяет метод data(). Прототипы метода:

_Tp *data() noexcept;
const _Tp *data() const noexcept;

Пример:

std::vector<int> arr = {1, 2, 3};
int *p = arr.data();
std::cout << *p << std::endl;     // 1
*p = 0;
std::cout << arr[0] << std::endl; // 0

Перебор элементов

Перебрать все элементы можно с помощью цикла for each, итераторов и алгоритма for_each(). Пример использования цикла for each:

std::vector<int> arr(3);
// Заполняем массив значениями
int n = 1;
for (int &el : arr) {
   el = n++;
}
// Выводим значения
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Если нужен доступ по индексу, то можно воспользоваться циклом for:

std::vector<int> arr = {1, 2, 3};
for (size_t i = 0, j = arr.size(); i < j; ++i)
   std::cout << arr.at(i) << ' ';
std::cout << std::endl; // 1 2 3

Пример перебора элементов с помощью итераторов и цикла for в прямом и обратном порядке:

std::vector<int> arr = {1, 2, 3};
std::vector<int>::iterator it1, it2;
// Перебор в прямом порядке
for (it1 = arr.begin(), it2 = arr.end(); it1 != it2; ++it1) {
   std::cout << *it1 << ' ';
}
std::cout << std::endl; // 1 2 3
// Перебор в обратном порядке
std::vector<int>::reverse_iterator it3, it4;
for (it3 = arr.rbegin(), it4 = arr.rend(); it3 != it4; ++it3) {
   std::cout << *it3 << ' ';
}
std::cout << std::endl; // 3 2 1

Пример перебора элементов с помощью итераторов и цикла while:

std::vector<int> arr = {1, 2, 3};
auto it1 = arr.begin(), it2 = arr.end();
while (it1 != it2) {
   std::cout << *it1++ << ' ';
}
std::cout << std::endl; // 1 2 3

С помощью алгоритма for_each() умножим значение каждого элемента массива на 2, а затем выведем все значения в окно консоли:

// #include <algorithm>
std::vector<int> arr = {1, 2, 3};
// Умножаем все элементы на 2
std::for_each( arr.begin(), arr.end(),
               [](int &a) { a *= 2; } );
// Выводим значения всех элементов
std::for_each( arr.begin(), arr.end(),
               [](int &a){ std::cout << a << ' '; } );
std::cout << std::endl; // 2 4 6

Специализация vector<bool>

Для специализации vector<bool> определены дополнительные методы:

  • flip() — инвертирует значения всех элементов. Прототип метода:
void flip() noexcept;

Пример:

std::vector<bool> arr = {true, false};
arr.flip();
std::cout << std::boolalpha << arr[0] << ' '
          << arr[1] << std::endl; // false true
  • swap() — меняет два элемента местами. Прототип метода:
static void swap(reference left, reference right) noexcept;

Пример:

std::vector<bool> arr = {true, false};
arr.swap(arr[0], arr[1]);
std::cout << std::boolalpha << arr[0] << ' '
          << arr[1] << std::endl; // false true

Учебник C++ (Qt Creator и MinGW)
Учебник C++ (Qt Creator и MinGW) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов