Википедија

Vector (C++)

Овој текст ја опишува имплементацијата на векторската предлошка во C++ Стандардната Библиотека.

Векторот е динамичка низа. Тој е еден од неколкуте податочни структури наречени container. Тој се спроведува како предложна класа; тој е генеричка рамка која може да биде забрзана, на пр. како вектор од целобројни вредности, или пак вектор од стрингови (strings).

Дизајн

уреди

Векторската предлошка е дефинирана со <vector>. Како и сите останати компоненти на стандардната библиотека, тој се наоѓа во namespace std.

Посредникот го следи однесувањето на C низата ( способен е за брз и случаен пристап), но со додатна можност да може автоматски да се промени сам кога ќе биде внесен или избришан некој објект.

Векторската предлошка може да биде забрзана со било кој тип којшто ги исполнува CopyConstructible и Assignable побарувањата:

expression return type requirement
t = u T& t е еквивалентно со u
T(t) n/a t е еквивалентно со T(t)
T(u) n/a u е еквивалентно со T(u)
&u (const) T* ја означува адресата на u
t.~T() n/a n/a

Каде T е тип кој се користи да ја го забрза векторот, t е вредност на T и u е вредност на (можна константа) T.

За даден вектор сите елементи мора да припаѓаат на истиот тип. На пример, еден не може да сочува податоци од двете форми int и char внатре во истиот вектор. Векторите пружат стандарден сет на функции за пристапни елементи, додавање елементи на почетокот или крајот, бришење елементи и барање колку елементи се архивирани.

Поединечен пристап на елементите

уреди

До поединечни елементи од векторот може да се пристапи со помош на операциите прикажани во долната табела. Следејќи ги стандардните конвенции за C и C++, првиот елемент има индекс 0, и последниот елемент има индекс size() – 1.

expression return type bounds checking?
v.at(i) T& or const T& to the element at index i yes, throws out_of_range exception
v[i] T& or const T& to the element at index i undefined behaviour if i >= v.size()
v.front() T& or const T& to the first element undefined behaviour if v.empty() is true
v.back() T& or const T& to the last element undefined behaviour if v.empty() is true

Каде v е објект од типот (возможна константа) вектор <T> и го претставува индексот.

Преглед на функции

уреди
  • Информативни
    • vector::front – Го враќа повикот на првиот елемент на векторот.
    • vector::back – Го враќа повикот на последниот елемент на векторот.
    • vector::size – Го враќа бројот на елементи во векторот.
    • vector::empty – Векторт нема елементи.
    • vector::capacity – Го враќа моментниот капацитет на векторот.
  • Стандардни операции
    • vector::insert – Вметнува елементи во векторот, подоцна се преместуваат.
    • vector::push_back – Додава елемент на крајот на некој вектор, доделува меморија ако е потребно.
    • vector::erase – Ги бриши елементите од векторот, подоцна ги преместува долу.
    • vector::pop_back – Ги бриши последните елементи на векторот. Обично не ја намалува меморијата на векторот.
    • vector::clear – Ги бриши сите елементи.
  • Промена на големината
    • vector::reserve – Го променува капацитетот на векторот, ако е потребно.
    • vector::resize – Ја променува големината на векторот.
  • Повторување
    • vector::begin – Го враќа итераторот на почетокот на векторот.
    • vector::end – Го враќа итераторот на крајот на векторот.

Капацитет и доделување

уреди

Типичен вектор се состои од имплементација, внатрешно, на показник на динамички доделено поле, и можни податоци кои го држат капацитетот и големината на векторот. Големината на векторот се однесува на реалните броеви, додека капацитетот се однесува на големината на внатрешниот ред.

Бидејќи адресите на елементите се менуваат во текот на оваа постапка, сите повикувачи или итератори до елементите во векторот се поништуваат. Користејќи ги поништените наводи се предизвикува недефинирано однесување. На пример: 

#include <vector>
int main()
{
  std::vector<int> v(1); // create a vector holding a single int with value 0.

  int& first = *v.begin(); // make a reference to the first element

  v.insert(v.end(), v.capacity(), 0); // append more elements to the vector, forcing a reallocation

  int i = first; // undefined behaviour; the reference has been invalidated 
}

reserve() операцијата може да се користи за да се спречи непотребно делоцирање. После повикувањето на reserve(n), капацитетот на векторот е гарантирано да биде најмалку n. На пример: 

#include <vector>
int main()
{
  std::vector<int> v(1); // create a vector holding a single int with value 0.

  v.reserve(10); // reserve space to prevent reallocation

  int& first = *v.begin(); // make a reference to the first element

  v.insert(v.end(), 5, 0); // append more elements to the vector

  int i = first; // OK, no reallocation has occurred
}

Векторот одржува редослед помеѓу неговите елементи. Со тоа се овозможува, кога нов елемент ќе се внеси на почетокот или на средината на векторот, сите елементи да се поместат наназад од деделениот елемент. Значи, повикувачите и итераторите до елементите зад точката на внесување стануваат невалидни. На пример: 

#include <vector>
int main()
{
  std::vector<int> v(2); // constructs a vector holding two ints

  // make references to the two ints
  int& first = v.front(); 
  int& last = v.back();
 
  v.insert(v.begin() + 1, 1, 1); // insert a new int in the middle of the vector.

  int i = first; // undefined behaviour iff the previous insert caused reallocation
  int j = last; // undefined behaviour per the C++ standard, §23.2.4.3/1
}

Употреба

уреди

C++ програма која содржи вектор мора да има: #include <vector> Употребата на векторот е делкарирана со: 

std::vector<T> instance;

каде „T“ е врста на податок во вектор, а „instance” е името на променливата во вектор. „T” може да биде било која врста Assignable, вклучувајќи ги и корисничките дефинирани типови.

Алтернатива за чување објекти од типот Т е да се складираат објекти од типот T*. Тоа е корисно ако Т не е пренослив или е „прескапо” за копирање.

Замена на низа

уреди

Во C++, низите се допирни делови со меморијата. Тие се нешто како блокови меѓусебно сврзани. На секој блок тогаш му се доделува број. Сите елементи мора да бидат од ист тип.

Векторот е сличен на динамички доделено поле , али со можност за самостојна големина и без потреба за рачна делокација на меморијата.

Бидејќи векторските елементи се складирани , адресата од првиот елемент е вектор и може да се пренеси на функции очекувајќи низа (покажувач на првиот елемент). Следниот пример покажува како еден вектор може да се користи со стандардната библиотека на C. 

#include <cstring> // memcpy
#include <vector> 
#include <cstdio> // printf
int main()
{
  using namespace std;
  const char arr[] = "1234567890";
  // construct a vector with 11 zero-initialized chars.
  vector<char> vec(sizeof arr);  
  // copy 11 chars from arr into the vector
  memcpy(&vec[0], arr, sizeof arr); 
  // prints "1234567890"
  printf("%s", &vec[0]); 
}

Имајте на ум дека таквата употреба на memcpy и printf е општо обесхрабрен во корист на сигурносната алтернатива од типот од C++ Стандардната Библиотека.

Пример

уреди

Следниот пример покажува разни техники кои вклучуваат вектори и стандардната библиотека на C++. 

#include <iostream>
#include <vector>
#include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound 
#include <functional> // greater, bind2nd
// used here for convenience, use judiciously in real programs. 
using namespace std;

int main()
{
  int arr[4] = {1, 2, 3, 4};
  // initialize a vector from an array
  vector<int> numbers(arr, arr+4);
  // insert more numbers into the vector
  numbers.push_back(5);
  numbers.push_back(6);
  numbers.push_back(7);
  numbers.push_back(8);
  // the vector currently holds {1, 2, 3, 4, 5, 6, 7, 8}

  // randomly shuffle the elements
  random_shuffle( numbers.begin(), numbers.end() );
  
  // locate the largest element, O(n)
  vector<int>::const_iterator largest = 
    max_element( numbers.begin(), numbers.end() );
  
  cout << "The largest number is " << *largest << "\n";
  cout << "It is located at index " << largest - numbers.begin() << "\n";
  
  // sort the elements
  sort( numbers.begin(), numbers.end() );

  // find the position of the number 5 in the vector, O(log n)  
  vector<int>::const_iterator five = 
    lower_bound( numbers.begin(), numbers.end(), 5 );  
  
  cout << "The number 5 is located at index " << five - numbers.begin() << "\n";
  
  // erase all the elements greater than 4   
  numbers.erase( remove_if(numbers.begin(), numbers.end(), 
    bind2nd(greater<int>(), 4) ), numbers.end() );
  
  // print all the remaining numbers
  for(vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it)
  {
    cout << *it << " ";
  }
  
  return 0;
}

При извршување на програмата добиваме:

Најголемиот број е 8

Сместен е на индекс 6

Бројот 5 е сместен на индекс 4

1234

Одлики

уреди
  • Векторите искористуваат мал дел од меморијата.
  • Како и другите STL контејнери, векторите можат да содржат двата вида на податоци (првобитни и сложени) , кориснички дефинирани класи или структури.

Надворешни Врски

уреди
Преземено од „https://mk.wikipedia.org/w/index.php?title=Vector_(C%2B%2B)&oldid=4848031“