Вектор — це абстрактна модель, яка імітує динамічний масив.
Будова Шаблон vector розміщений у заголовковому файлі <vector>. Як і всі стандартні компоненти, він розміщений у просторі імен std. Даний інтерфейс емулює роботу стандартного масиву мови C (наприклад швидкий довільний доступ до елементів), а також деякі додаткові можливості, такі, як автоматична зміни розміру вектора при вставці або видаленні елемента.
Всі елементи класу мають належати одному типові. Наприклад, не можна одночасно зберігати дані типів char і int у одному векторі. Клас vector володіє стандартним набором методів для доступу до елементів, додавання та видалення елементів, а також отримання кількості збережених елементів.
Ініціалізація Вектор може бути ініціалізований будь-яким типом, що володіє конструктором копіювання і визначеним operator=, що задовольняє наступним умовам: Вираз Тип результату Умова t = u T& t еквівалентне u T(t) t еквівалентне T(t) T(u) u еквівалентне T(u) &u const T* показує адресу u t.~T()
Тут T — тип, яким ініціалізований vector, t — змінна типу T, u — змінна типу (можливо const) T.
Наприклад: vector<int> myVector; // Пустий вектор з елементів типу int vector<float> myVector(10) // Вектор з 10-и елементів типу float vector<char> myVector(5, ' ') // Вектор, що складається з 5-и пробілів
class T { ... }; n = 10; vector<T> myVector(n); // Вектор з 10-и елементів користувацького типу T
Доступ до елементів Доступ до окремого елемента вектора можна отримати, використовуючи операції, описані нижче у таблиці. Згідно з домовленістю C і C++, перший елемент має індекс 0, останній size() - 1.
Вираз Тип повернення Перевірка межі v.at(i) T& або const T& для елемента i Можливий викид винятку out_of_range v[i] T& або const T& для елемента i Невизначена поведінка для i >= v.size() v.front() T& або const T& для першого елемента Невизначена поведінка для v.empty() == true v.back() T& або const T& для останнього елемента Невизначена поведінка для v.empty() == true
Де v елемент (можливо const) типу vector<T>, а i — індекс потрібного елемента вектора.
Деякі методи Клас vector — це контейнер. Згідно з стандартом С++, будь-який контейнер повинен мати такі методи begin(), end(), size(), max_size(), empty() і swap(). Нижче наведені короткий опис доступних методів і їх складність Метод Опис Складність Конструктори vector::vector Конструктор за замовчуванням. Не приймає аргументів, створює новий екземпляр вектора O(1) (виконується за константний час) vector::vector(const vector& c) Конструктор копіювання. Створює копію вектора c O(n) (виконується за лінійний час, пропорційний розміру вектора c) vector::vector(size_type n, const T& val = T()) Створює вектор з n об'єктами. Якщо val оголошено, то кожному з цих об'єктів буде присвоєно це значення; в протилежному випадку об'єкти отримають значення конструктора за замовчуванням типу T. O(n) vector::vector(input_iterator start, input_iterator end) Створює вектор з елементів, що лежать між start і end O(n) Деструктор vector::~vector Знищує вектор і його елементи Оператори vector::operator= Копіює значення одного вектора в інший. O(n) vector::operator== Порівняння двох векторів O(n) Доступдо елементів vector::at Доступ до елемента з перевіркою виходу за межі O(1) vector::operator[] Доступ до певного елемента O(1) vector::front Доступ до першого елемента O(1) vector::back Доступ до останнього елемента O(1) Ітератори vector::begin Повертає ітератор на перший елемент вектора O(1) vector::end Повертає ітератор на місце після останнього елемента вектора O(1) vector::rbegin Повертає reverse_iterator на кінець поточного вектора. O(1) vector::rend Повертає reverse_iterator на початок вектора. O(1) Робота зрозміром вектора vector::empty Повертає true, якщо вектор пустий O(1) vector::size Повертає кількість елементів у векторі O(1) vector::max_size Повертає максимально можливу кількість елементів у векторі O(1) vector::reserve Встановлює мінімально можливу кількість елементів у векторі O(n) vector::capacity Повертає кількість елементів, яку може утримувати вектор до того, як йому буде потрібно виділити більше місця. O(1) vector::shrink_to_fit Зменшує кількість використовуваної пам'яті за рахунок звільнення невикористаної (C++11) O(1) Модифікатори vector::clear Видаляє всі елементи вектора O(n) vector::insert Вставка елементів у вектор Вставка в кінець, при умові, що пам'ять не буде перерозподілятись — O(1), в довільне місце — O(n) vector::erase Видалення вказаних елементів вектора (один або декілька) O(n) vector::push_back Вставка елемента в кінець вектора O(1) vector::pop_back Видалити останній елемент вектора O(1) vector::resize Змінює розмір вектора на задану величину O(n) vector::swap Обміняти вміст двох векторів O(1) Інші методи vector::assign Асоціює з вектором подані значення O(n), якщо встановлений потрібний розмір вектора, O(n*log(n)) при перерозподілі пам'яті vector::get_allocator O(1)
Ітератори В додаток до функцій прямого доступу до елементів, описаних вище, елементи вектора можна отримати за допомогою ітераторів.
Ітератори зазвичай використовуються парами, один з яких використовується для вказівки поточної ітерації, а другий слугує для позначення кінця контейнера. Ітератори створюються за допомогою таких стандартних методів, як begin() і end(). Функція begin() повертає вказівник на перший елемент, а end() — на уявний неіснуючий елемент, що є наступним після останнього.
Вектор використовує найбільш функціонально багатий тип ітераторів — RandomAcessIterator (ітератор довільного доступу), який дозволяє обходити контейнер в довільному порядку, а також змінювати його вміст в процесі обходу. Однак, при зміні вектора, ітератор може стати недійсним.
Приклад підрахунку суми за допомогою ітераторів: vector<int> the_vector; vector<int>::iterator the_iterator;
for (int i=0; i < 10; i++) { the_vector.push_back(i);
int total = 0; the_iterator = the_vector.begin(); while (the_iterator != the_vector.end()) { total += *the_iterator; /* Зверніть увагу, що доступ до елемента можна отримати за допомогою розіменування ітератора */ ++the_iterator;
cout << "Сума=" << total << endl; Результат: Сума=45
Об'єм вектора і зміна розміру Типова реалізація вектора — це вказівник на динамічний масив. Розмір вектора — це кількість елементів, а об'єм — кількість використаної ним пам'яті.
Якщо при вставці в вектор нових елементів, його розмір стає більшим від його об'єму, відбувається перерозподіл пам'яті. Як правило, це призводить до того, що вектор виділяє нову область збереження, переміщуючи елементи і вільні старі області в нову ділянку пам'яті.
Оскільки адреси елементів при цьому змінюються, будь-які посилання, або ітератори елементів у векторі можуть стати недійсними. Використання недійсних посилань призводить до невизначеної поведінки. Приклад: #include <vector> int main() { std::vector<int> v(1); // Створюємо вектор, що складається з одного елемента типу int, значення якого рівне 0
int& first = *v.begin(); // Створюємо посилання на перший елемент
v.insert(v.end(), v.capacity(), 0); // Додаємо нові елементи
int i = first; // Невизначена поведінка. Посилання може бути недійсним. } Метод reserve() використовується для запобігання непотрібному перерозподілу пам'яті. Після виклику reserve(n), об'єм вектора гарантовано буде не менше ніж n. Приклад: #include <vector> int main() { std::vector<int> v(1); // Створюємо вектор, що складається з одного елемента типу int, значення якого рівне 0
v.reserve(10); // Резервуємо місце
int& first = *v.begin(); // Створюємо посилання на перший елемент
v.insert(v.end(), 5, 0); // додаємо елементи до вектора
int i = first; // OK, так як не було перерозподілу пам'яті } Вектор зберігає певний порядок його елементів, так, що при вставці нового елемента на початок або в середину вектора, наступні елементи переміщуються в протилежному напрямі з точки зору їх оператора присвоєння і конструктора копіювання. Отже, посилання і ітератори елементів після місця вставки стають недійсними. Приклад: #include <vector> int main() { std::vector<int> v(2); // створюємо вектор, що складається з двох елементів типу int
// Створюємо посилання на обидва елемента int& first = v.front(); int& last = v.back();
v.insert(v.begin() + 1, 1, 1); // Додаємо нові елементи в середину вектора
int i = first; // Невизначена поведінка, якщо вставка викликала перерозподіл пам'яті int j = last; // Невизначена поведінка, згідно з стандартом C++, §23.2.4.3/1 }
Спеціалізація vector<bool> Стандартна бібліотека С++ визначає спеціалізацію шаблону вектора для типу bool. Згідно з спеціалізацією, вектор має упаковувати елементи так, щоб кожен елемент типу bool використовував лише один біт пам'яті. Це більшість називає помилкою, так як vector<bool> не відповідає вимогам контейнера стандартної бібліотеки С++. Наприклад, контейнер <T>::reference має бути вірним lvalue типу Т. Це не виконується у випадку з vector<bool>::reference, що є об'єктом-заступником, конвертованим у bool. Крім того, vector<bool>::iterator не дає bool& при розіменуванні. Існує домовленість між комітетом по стандартизації С++ і групою розробників бібліотеки, що vector<bool> має бути виключеним, а згодом і видаленим з стандартної бібліотеки, а функціональність буде повернена, але під іншою назвою.
Використання Програми на С++, що використовують вектор, повинні мати в собі заголовковий файл <vector>: #include <vector> // Після цього можна проініціалізувати змінну std::vector<T> myVector; або можна підключити заголовковий файл vector.h, де простір імен std вже підключено #include "vector.h" // Після цього можна проініціалізувати змінну vector<T> myVector; Тут T — тип даних, які будуть зберігатись у контейнері, а myVector — змінна, яка буде використовуватись. T може бути будь-яким типом даних, включаючи тип даних, визначений користувачем.
Заміна масиву В C і С++, масив — це дані в суміжних блоках пам'яті. Кожному блоку після присвоюється індекс, і дізнатись вміст кожного блока можна знаючи його індекс. Всі елементи масиву є даними одного типу.
Вектор схожий на динамічний масив, але вектор може змінювати розмір самостійно. Також, немає необхідності ручного звільнення пам'яті.
Оскільки елементи вектора зберігаються неперервно, адреса першого елемента вектора може бути передана функції як масив (вказівник на перший елемент). Наступний приклад ілюструє, як вектор може використовуватись з функціями стандартної бібліотеки С memcpy і printf: #include <cstring> // memcpy #include <vector> #include <cstdio> // printf int main() { using namespace std; const char arr[] = "1234567890"; // Створимо вектор з 11-и '\0' vector<char> vec(sizeof arr); // Скопіюємо 11 елементів типу 'char' в вектор memcpy(&vec, arr, sizeof arr); // Надрукує "1234567890" printf("%s", &vec); } Зверніть увагу, що використання memcpy і printf небажане, на користь більш безпечних альтернатив з стандартної бібліотеки С++.
Приклад використання Наступний приклад демонструє різні техніки за участю вектора і алгоритмів стандартної бібліотеки C + +, зокрема, перемішування, сортування, знаходження найбільшого елемента, а також видалення з вектора з використанням ідіоми erase-remove. #include <iostream> #include <vector> #include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound #include <functional> // greater, bind2nd
// Використовується для зручності. В реальних програмах використовуйте з обережністю using namespace std;
int main() { int arr = {1, 2, 3, 4}; // Ініціалізація вектора з використанням масиву vector<int> numbers(arr, arr+4); // Додаємо числа до вектора numbers.push_back(5); numbers.push_back(6); numbers.push_back(7); numbers.push_back(8); // Тепер вектор виглядає так: {1, 2, 3, 4, 5, 6, 7, 8}
// Довільно перемішуємо елементи random_shuffle(numbers.begin(), numbers.end());
// Отримуємо максимальний елемент, складність O(n) vector<int>::const_iterator largest = max_element( numbers.begin(), numbers.end() );