C, PHP, VB, .NET

Дневникът на Филип Петров


* Вектори (std::vector)

Публикувано на 29 ноември 2008 в раздел С/С++.

Досега се стараехме да не използваме готови библиотеки, класове и обекти. За шаблонният клас vector обаче си заслужава да се отдели специално внимание. Векторите са изключително удобен и ефективен заместител на стандартните масиви, като значително спестява ресурси при редица операции. Чрез него имаме възможност за създаване на т.нар. "динамични масиви".

Първата стъпка е да прибавим класа чрез #include. Вектор се дефинира по следния начин:

#include <vector>
//...
std::vector<тип> v;

Синтаксисът изисква указване на типа елементи във вектора. Често е удобно да използваме typedef при дефиниране на вектори. Например:

typedef std::vector<int> int_vec;
int_vec v1, v2;

Така например създадохме вектор с елементи от тип int. Използването му по-нататък е много сходно с това на масивите. Ето например как създаваме вектор от 10 елемента, и запълваме елементите му с числата от 1 до 10:

std::vector<int> v(10);
for(int i=0; i<10; i++) v[i] = i+1;

Виждате, че в класът вектор е предефиниран операторът []. Аналогично действа член-функцията at(int):

v.at(1000) = 5;

Ако елемент с такъв индекс не съществува, то ще бъде върнат обект от тип std::out_of_range. Ще разгледаме подробно как може да бъде използван в тема за обработка на грешки. Съществена разлика между [int] и .at(int) се явява ако сте насочили указател към вектор. При използване на [] то е възможно векторът да се премести на нов адрес (например при разширение, което ще покажем по-долу) и така указателят ви да сочи на грешна позиция. При функцията at този проблем не съществува, тъй като тя работи с фиксиран размер на вектора. Поради тази причина бъдете особено внимателни при използването на указатели към вектор.

Дефиниран е и операторът =:

std::vector<int> v2(10);
v2 = v;

Две член функции begin и end връщат адреса на началото и края на вектора. Използват се ефективно при употребата на interator. Следният пример демонстрира обхождането на вектор и отпечатването му на екрана:

vector<int>::iterator it;
std::cout << "v contains:";
for (it=v.begin(); it<v.end();it++ ){
	std::cout << " " << *it;
}

Принципно можете да пъстигнете абсолютно същия ефект чрез използването на .at или [] и обхождане на вектора чрез указатели. Въпреки това свикването за използване на iterator се насърчава, тъй като ще е значително по-лесно да го използвате при стандартни алгоритми като сортиране например, тъй като член-функция за тази цел не се предлага, а я има реализирана като шаблонна функция.

Дотук не показахме нищо значително ново в сравнение с обикновените масиви. Нека да разгледаме следния случай - представете си, че имаме масив, в който записваме динамично данни. В един момент може да се окаже, че масива се е запълнил и нямаме достатъчно място. Векторите решават този проблем:

#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;

void main(){
	// Дефинираме празен вектор
	vector<int> v;
	// Функцията size() показва броя елементи на вектора
	cout << "initial: " << v.size() << endl;
	// Чрез push_back можем да добавим елемент
	v.push_back(12);
	cout << "after I add one element: " << v.size() << endl;
	// Добавяме още 10 елемента
	for (int i=0; i<10; i++) v.push_back(i);
	cout << "after I add 10 more: " << v.size() << endl;

	// Отпечатваме съдържанието на вектора
	cout << "the array contents are:";
	for (i=0; i<v.size(); i++) cout << " " << v[i];
	cout << endl;
}

Виждате, че функцията push_back добавя елемент в края на вектора. Тук демонстрирахме и създаването на празен вектор (в предишните примери резервирахме памет за поне десет елемента), както и член-функцията size. Често се използват още две функции - capacity и max_size. Проверете резултатът от следния пример

#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;

void main(){
	vector<int> v;

	for (int i=0; i<100; i++) v.push_back(i);
	cout << "size: " << (int) v.size() << endl;
	cout << "capacity: " << (int) v.capacity() << endl;
	cout << "max_size: " << (int) v.max_size() << endl;
}

Ще забележите, че size връща текущия брой елементи записани във вектора, capacity показва памет за колко елемента е резервирана (т.е. векторът може по подразбиране да задели повече памет отколкото използваме!), а max_size определя максималният в момента свободен блок памет, който може да бъде заделен за нашият вектор. Ако искаме да резервираме допълнително памет (да увеличим capacity), то можем да използваме функцията reserve:

v.reserve(200);
cout << "now capacity is: " << (int) v.capacity() << endl;

Ако подадем по-малка стойност на reserve отколкото е текущия capacity, то функцията няма да направи нищо. С resize обаче можем да "изрязваме" елементи от вектор:

v.resize(12);
cout << "size: " << (int) v.size() << endl;
cout << "capacity: " << (int) v.capacity() << endl;
cout << "max_size: " << (int) v.max_size() << endl;

Изпълнете примера и отпечатайте съдържанието на вектора. Ще видите, че capacity се е запазило, но size е станал 12 и всички елементи след този с индекс 11 са изтрити. Нека сега да извикаме resize чрез втория му конструктор:

v.resize(20, 5);

По този начин добавихме 8 елемента със стойност числото 5 в края на вектора. Това е просто по-лесен начин за добавяне на множество еднакви елементи. Като бързина в сравнение с push_back няма почти никаква разлика.

Вече споменахме функцията at(int). Други две функции, които можем да използваме са front() и back(), чрез които достъпваме съответно първия и последния елемент на вектор. Друга полезна функция е empty(). Тя връща 0 ако в масива има елементи и true ако векторът е празен. Използва се като еквивалент на size()==0.

Много ценна възможност на векторите е да ги използваме за реализацията на структурата стек. Вече се запознахте с функцията push_back, която практически добавя елемент в края на стек. В класа vector са се погрижили и за функция за премахване на елемент от стек:

	v.pop_back();

Така просто изтриваме последния елемент на вектора. Имайте предвид, че тя ще намали size(), но не и capacity().

Накрая една изключително силна възможност на векторите, е тяхната функционалност на структура от тип списък, а именно: вмъкване и изтриване на елементи във вектора. За целта е нужно използването на iterator:

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

void showvector(vector<int> &v){
	if (v.empty()) cout << "empty vector" << endl;
	else{
		vector<int>::iterator it;
		for (it=v.begin(); it<v.end();it++ ){
			cout << " " << *it;
		}
	}
	cout << endl;
}

int main (){
	// създава вектор от три елемента
	// всеки от които със стойност 5
	vector<int> v(3,5);
	// добавяме още три елемента
	v.push_back(10);
	v.push_back(11);
	v.push_back(12);
	// показва елементите на вектора
	showvector(v);

	vector<int>::iterator it;
	// накочваме инетатора към 5ти елемент
	it = v.begin()+4;
	// добавяме числото 33 като пети елемент
	v.insert(it, 33);
	showvector(v);

	// създаваме втори вектор
	vector<int> v2(0);
	v2.push_back(999);
	v2.push_back(999);

	// насочваме итератора към трети елемент
	it = v.begin()+2;
	// вмъкваме вектор v2 преди трети елемент на v
	v.insert(it, v2.begin(), v2.end());
	showvector(v);

	// изтриваме 6ти елемент
	it = v.begin() + 5;
	v.erase(it);
	showvector(v);

	// изтриваме елементите от 3ти до 7ми включително
	it = v.begin();
	v.erase(it+2, it + 7);
	showvector(v);

	// разменяме съдържанието на двата вектора
	cout << "the vectors are:" << endl;
	showvector(v);
	showvector(v2);
	cout << "swapped" << endl;
	v.swap(v2);
	showvector(v);
	showvector(v2);

	// изтриваме съдържанието на вектор
	v.clear();
	showvector(v);
	return 0;
}

 



Добави коментар

Адресът на електронната поща няма да се публикува


*