vector - це шаблон з стандартної бібліотеки C + +, що реалізує динамічний масив довільного доступу. Це одна з структур даних, іменованих контейнерами (наприклад, list, deque і т. д.)


1. Пристрій

Шаблон vector розташований в заголовному файлі . Як і всі стандартні компоненти, він розташований в просторі імен std. Даний інтерфейс емулює роботу стандартного масиву C (наприклад, швидкий довільний доступ до елементів), а також деякі додаткові можливості, начебто автоматичної зміни розміру вектора при вставці або видаленні елементів.

Всі елементи вектора повинні належати одному типу. Наприклад, не можна спільно зберігати дані типів char і int в одному примірнику вектора. Клас vector володіє стандартним набором методів для доступу до елементів, додавання і видалення елементів, а також отримання кількості збережених елементів.


1.1. Ініціалізація

Вектор може бути ініціалізований будь-яким типом, мають конструктор копії і певний operator= і задовольняючим наступним умовам [1] :

Вираз Повертаний тип Умова
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 

1.2. Доступ до елементів

Доступ до окремого елементу вектора можна отримати, використовуючи операції, описані в таблиці нижче. За угодою C і C + +, перший елемент має індекс 0, останній - size() - 1 [2].

Вираз Повертаний тип Перевірка кордону?
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, а i - індекс необхідного елемента вектора.


1.3. Деякі методи

Клас vector - це контейнер. Відповідно до стандарту C + +, будь контейнер повинен містити методи 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)

1.4. Ітератори

На додаток до функцій прямого доступу до елементів, описаними вище, елементи вектора можна отримати за допомогою ітераторів.

Ітератори зазвичай використовуються парами, один з яких використовується для вказівки поточної ітерації, а другий служить для позначення кінця контейнера. Ітератори створюються за допомогою таких стандартних методів як begin() і end(). Функція begin() повертає покажчик на перший елемент, а end() - на уявний неіснуючий елемент, наступний за останнім.

Вектор використовує найбільш функціонально багатий тип ітераторів - RandomAccessIterator (ітератор довільного доступу), який дозволяє обходити контейнер в якому порядку, а також змінювати вміст вектора в процесі обходу. Однак, при зміні вектора ітератор може стати недійсним.

Приклад підрахунку суми елементів вектора за допомогою ітераторів:

 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


1.5. Обсяг вектора і зміна розміру

Типова реалізація вектора - це покажчик на динамічний масив. Розмір вектора - це фактичне число елементів, а обсяг - кількість використовуваної ним пам'яті.

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

Оскільки адреси елементів протягом цього процесу міняються, будь-які посилання або ітератори елементів у векторі можуть стати недійсними. Використання недійсних посилань приводить до невизначеного поведінки. Приклад:

 # Include   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   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   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  } 

[ ""> правити ] 1.6. Спеціалізація vector

Стандартна бібліотека C + + визначає спеціалізацію шаблону вектора для типу bool. Згідно спеціалізації, вектор повинен упакувати елементи так, щоб кожен елемент типу bооl використовував тільки один біт пам'яті [3]. Це багато хто називає помилкою [4] [5], так як vector не відповідає вимогам контейнера стандартної бібліотеки C + +. Наприклад, контейнер ::reference повинен бути вірним lvalue типу T. Це не виконується у випадку з vector::reference, яка є об'єктом-заступником, конвертованим у bool [6]. Крім того, vector::iterator не дає bool& при разименованія. Існує угода між комітетом по стандартизації C + + і групою розробників бібліотеки, що vector повинен бути виключений, а потім видалений з стандартної бібліотеки, а функціональність буде відновлено, але під іншим ім'ям. [7]


2. Використання

Програми на C + +, які використовують вектор, повинні містити в собі заголовний файл :

 # Include   / / Після цього, можна проініціалізувати змінну  std  ::  vector  <  T  >  myVector  ; 

або можна підключити заголовний файл vector.h, де простір імен std вже підключено

 # Include   / / Після цього, можна проініціалізувати змінну  vector  <  T  >  myVector  ; 

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


2.1. Заміна масиву

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

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

Оскільки елементи вектора зберігаються безперервно, адреса першого елемента вектора може бути переданий функції в якості масиву (вказівник на перший елемент). Наступний приклад ілюструє, як вектор може використовуватися з функціями стандартної бібліотеки С memcpy memcpy і printf printf :

 # Include  / / memcpy  # Include   # Include  / / 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 memcpy і printf printf не вітається, на користь більш безпечних альтернатив з стандартної бібліотеки C + +


2.2. Приклад використання

Наступний приклад демонструє різні техніки за участю вектора і алгоритмів стандартної бібліотеки C + +, зокрема, перемішування, сортування, знаходження найбільшого елементу, а також видалення з вектора з використанням ідіоми erase-remove.

 # Include   # Include   # Include  / / sort, max_element, random_shuffle, remove_if, lower_bound  # Include  / / 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

Приклад 2-мірного динамічного вектора, а також приклад доступу до нього і його модифікації

 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   # Include   # Include  / / для використання алгоритмів: 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  ;  } 

3. Доводи за і проти

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

Джерела

  1. ISO / IEC (2003). ISO / IEC 14882:2003 (E): Programming Languages ​​- C + + 23.1 Container requirements [lib.container.requirements] para. 4
  2. Josuttis Nicolai C + + Standard Library - A Tutorial and Reference. - Addison-Wesley, 1999.
  3. ISO / IEC (2003). ISO / IEC 14882:2003 (E): Programming Languages ​​- C + + 23.2.5 Class vector [lib.vector.bool] para. 1
  4. vector : More Problems, Better Solutions (PDF) (August 1999). Статичний з першоджерела 31 серпня 2012.
  5. A Specification to deprecate vector (March 2007). Статичний з першоджерела 31 серпня 2012.
  6. ISO / IEC (2003). ISO / IEC 14882:2003 (E): Programming Languages ​​- C + + 23.2.5 Class vector [lib.vector.bool] para. 2
  7. 96. Vector is not a container. Статичний з першоджерела 31 серпня 2012.