Вектор (C++)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Вектор - це абстрактна модель, яка імітує динамічний масив.

Будова[ред.ред. код]

Шаблон 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 може бути будь-яким типом даних, включаючи тип даних, визначений користувачем.

Заміна масиву[ред.ред. код]

В С і С++, масив - це дані в суміжних блоках пам'яті. Кожному блоку після присвоюється індекс, і дізнатись вміст кожного блока можна знаючи його індекс. Всі елементи масиву мають бути одного типу.

Вектор схожий на динамічний масив, але вектор може змінювати розмір самостійно. Також, немає необхідності ручного звільнення пам'яті.

Оскільки елементи вектора зберігаються неперервно, адресу першого елемента вектора може бути передана функції в якості масива (вказівник на перший елемент). Наступний приклад ілюструє, як вектор може використовуватись з функціями стандартної бібліотеки С 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[0], arr, sizeof arr); 
  // Надрукує "1234567890"
  printf("%s", &vec[0]); 
}

Зверніть увагу, що використання 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[4] = {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() );
 
  cout << "Найбільший елемент " << *largest << endl;
  cout << "Індексцього елемента " << largest - numbers.begin() << endl;
 
  // Сортуємо елементи, складність O(n log n)
  sort(numbers.begin(), numbers.end());
 
  // Заходимо позицію цифри 5 у векторі, складність O(log n)  
  vector<int>::const_iterator five = lower_bound(numbers.begin(), numbers.end(), 5);  
 
  cout << "Цифра 5 розміщена під індексом " << five - numbers.begin() << endl;
 
  // Видаляємо всі елементи більші за 4 
  numbers.erase(remove_if(numbers.begin(), numbers.end(), 
    bind2nd(greater<int>(), 4)), numbers.end() );
 
  // Видруковуємо ті, що залишились
  for (vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) {
    cout << *it << ' ';
  }
 
  return 0;
}

Вивід: Найбільший елемент 8 Індекс цього елемента 6 (залежить від реалізації) Цифра 5 розміщена під індексом 4 1 2 3 4 Приклад двовимірного динамічного вектора, а також приклад доступу до нього і його модифікації

typedef std::vector< std::vector<int> > pxMP;
 
void function() {
    int sizeX, sizeY; // Вказуємо розмір.
    pxMP pxMap(sizeX, std::vector<int>(sizeY)); // масив розміру X/Y пікселів 0,1.
    pxMap[0][5] = 1;  /* доступ */
 
        // Видаляємо ліву і праву колонку
        pxMap.pop_back();
        pxMap.erase(pxMap.begin());
 
        // Видаляємо верхній і нижній рядок з всіх стовпців, для початку створюємо деякі інструменти для цього:
        std::vector< std::vector<int> >::iterator iterlvl2; // ітератор для другого розміру.
        std::vector< int >::iterator iterlvl1; // ітератор для першого розміру
 
        // Йдемо всередину
        for (iterlvl2=pxMap.begin();iterlvl2 != pxMap.end();iterlvl2++) {
            iterlvl1 = (*iterlvl2).begin(); // Тільки для демонстрації
            (*iterlvl2).pop_back();
            (*iterlvl2).erase((*iterlvl2).begin()); // Де ми?
 
            sizeY = (*iterlvl2).size(); // Встановлюємо sizeY поки ми на цьому рівні. Потім ми не зможемо цього зробити
        }
}

Приклад одновимірного динамічного вектора, сортування і видалення дублікатів:

#include <vector>
#include <string>
#include <algorithm> // для використання алгоритмів: sort / unique / erase
 
void main() {
 
    vector<string> v_str;    // пустий вектор v_str
    v_str.push_back("zz");   // {"zz"}
    v_str.push_back("aa");   // {"zz", "aa"}
    v_str.push_back("bb");   // {"zz", "aa", "bb"}
    v_str.push_back("aa");   // {"zz", "aa", "bb", "aa"}
    v_str.push_back("xx");   // {"zz", "aa", "bb", "aa", "xx"}
    v_str.push_back("dd");   // {"zz", "aa", "bb", "aa", "xx", "dd"}
    v_str.push_back("xx");   // {"zz", "aa", "bb", "aa", "xx", "dd", "xx"}
 
    // сортуємо всі елементи вектора
    sort(v_str.begin(), v_str.end());    
    // Результат сортування вектора: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"}
 
    // Видаляємо дублікати
    v_str.erase( unique(v_str.begin(), v_str.end() ), v_str.end() );   
    // Результат сортування і видалення дублікатів: {"aa","bb","dd","xx","zz"}
 
    return void;
}

Доводи за і проти[ред.ред. код]

  • як і всі реалізації динамічного масиву, вектор не використовує додаткових структур даних, дані розміщені в пам'яті поруч, за рахунок чого вони добре кешуються.
  • Вектор може швидко виділяти пам'ять, необхідну для зберігання конкретних даних. Це особливо корисно для зберігання даних у списках, довжина яких може бути невідома до створення списку, а видалення (за винятком, можливо, в кінці) необхідно рідко.
  • Як й інші контейнери STL, може містити примітивні типи даних, складні або ж визначені користувачем.
  • Вектор дозволяє довільний доступ; тобто на елемент вектора можна посилатись так само, як на елемент масиву (по індексу). Зв'язані списки і більшість, навпаки, не підтримують довільний доступ і арифметичні операції над вказівниками.
  • Видалення елемента з вектора або навіть очистка вектора абсолютно не обов'язково звільнить пам'ять, зв'язану з цим елементом. Це тому, щоо максимальний розмір вектора з моменту його створення є гарною оцінкою розміру для нового вектора.
  • Вектори є неефективними для вставки елементів в будь-які місця, крім кінця. Така операциія має складність О(n) в порівнянні з O(1) для Зв'язаних списків. Це компенсується швидкістю доступу і швидкістю видалення. Доступ до довільного елемента вектора має складність O(1) в порівнянні з О(n) для Зв'язаного списку і O(log n) для дерева. Видалення має складність O(2) (перестановка і видалення).

Див. також[ред.ред. код]

Джерела[ред.ред. код]

A Specification to deprecate vector<bool>

vector<bool>: More Problems, Better Solutions

The C++ Standards Committee

96. Vector<bool> is not a container

Посилання[ред.ред. код]

С++ визначення std::vector

Використання std::vector в C++