Вектори и итератори

Всеки контейнер от стандартната библиотека дефинира спомагателен тип iterator.

Обектите от типа iterator се използват за последователно обхождане на елементите на контейнера.

Итераторите могат да се разглеждат като “указатели” към елементите на контейнера.За всички итератори е дефиниран операторът ++, който премества итератора към следващия елемент от контейнера. Итераторите на някои контейнери поддържат и операцията --.

1. Деклариране

vector <Т>::iterator име;

Итератор към вектор от тип Т
обхождане от началото към края

Пример:

vector<int> v;

vector<int>::iterator it; //итератор към вектор от тип int

vector<Т>:: reverse_iterator

Итератор към вектор от тип Т
обхождане от края към началото

vector<int> v;

vector<double>:: reverse_iterator it; //итератор към вектор от тип double

2. Итератор към елемент на вектора

v.begin()

Връща итератор към първия елемент на вектора

v.begin()+i

Връща итератор, насочен към (i+1)-я елемент на вектора.

v. end()

Връща итератор, насочен след последния елемент на вектора

vector<int>::iterator it;

it = v.begin()+4;// насочваме итератора към 5ти елемент

3. Стойност на елемент сочен от итератор

*it

Връща стойността на елемента сочен от итератора it

Пример:

Обхождане на вектор и отпечатване съдържанието му на екрана:

vector<int> v1( 3, 5 );

- vector<int>::iterator it;

for( it = v1.begin(); it != v1.end(); it++ ) cout << *it<<" ";

cout << endl;

}

Реализация чрез функция:

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;

}

Обхождане в обратен ред:

vector<int>::reverse_iterator it;

for(it=a.rbegin(); it!=a.rend();it++) cout<<*it<<" " ;

4. Добавяне на елемент на произволно място във вектор

v.insert( it ,value );

Вмъква елемент със стойност value преди елемента, сочен от итератора it.

v.insert(it_pos, count_n,value);

Вмъква count_n на брой елемента със стойност value преди елемента сочен от итератора it_pos.

Пример:

// създава вектор от три елемента

// всеки от които със стойност 5

vector<int> v(3,5);

// добавяме още три елемента

v.push_back(10);v.push_back(11);v.push_back(12);

showvector(v); // показва елементите на вектора

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

v.insert(it, 33); // добавяме числото 33 като пети елемент

showvector(v); it = v.begin()+2; // насочваме итератора към 3ти елемент

v.insert(it,5,10); //добавяме 5 елемента със стойност 10 след 2 елементshowvector(v);

Изход:

5 5 5 10 11 12

5 5 5 10 33 11 12

5 5 20 20 20 20 20 5 10 33 11 12

v.insert(it_pos, begin_it,end_it);

Преди елемента сочен от итератора it_pos, се вмъкват всички елементи от begin_it до end_it.

Връща итератор сочещ първият вмъкнат елемент

Пример:

vector<int> v1;

v1.push_back( 0 ); v1.push_back( 1 ); v1.push_back( 2 );

v1.push_back( 3 );

vector<int> v2;

v2.push_back( 5 ); v2.push_back( 6 );

v2.push_back( 7 ); v2.push_back( 8 );

cout << "Before, v2 is: ";

for( int i = 0; i < v2.size(); i++ ) cout << v2[i] << " ";

cout <<endl;

v2.insert( v2.end(), v1.begin(), v1.end() );

cout << "After, v2 is: ";

for( int i = 0; i < v2.size(); i++ ) cout << v2[i] << " ";

cout <<endl;

Програмата ще изведе:

Before, v2 is: 5 6 7 8 After, v2 is: 5 6 7 8 0 1 2 3

5. Изтриване на елемент сочен от итератор

v.erase(it);

Премахва елемента указван от it. Връща итератор към елемента след премахнатия

v.erase(it1 , it2);

Изтрива елементите от [ it1 , it2 ). Връща итератор към следващ елемент.

Връща итератор сочещ след последния изтрит елемент

Примери:

// изтриваме 6ти елемент

it = v.begin() + 5;

v.erase(it);

// изтриваме елементите от 3ти до 7ми включително

it = v.begin();

v.erase(it+2, it + 7);

Примерна програма за използването на итератори за обобщени алгоритми:

Алгоритъм за сортиране:

sort(<начален_итератор>,<итератор_след_края>);

Програмиране на приложение с използване на алгоритъма за сортиране:

#include <algorithm>

// създаване на вектора v

// запълване на вектора v

// прилагане на алгоритъм

sort (v.begin(), v.end() );

Пример2:

Програма, която намира броя на нечетните елементи

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

bool IsOdd (int i)

{

return ((i%2)==1);

}

int main () {

vector<int> v;

for(int i=1;i<10;i++) v.push_back(i); //v: 1 2 3 4 5 6 7 8 9

int mycount = count_if (v.begin(), v.end(), IsOdd);

cout << "myvector contains " << mycount << " odd values.\n";

return 0;

}

Изход: myvector contains 5 odd values.

Пример3.

Програма, която създава вектор от n произволни числа и

- сортира елементите му

- извежда максималния и минималния му елемент

-намира броя на простите числа във вектора

- изтрива всички прости числа от вектора

#include <iostream>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

using namespace std;

bool prosto (int n)

{

if(n==1) return 0;

for(int i=2; i<=sqrt(n); i++) if(n%i==0) return 0;

return 1;

}

void write(vector <int> v)

{

cout << "v contains:";

for (int i=0; i<v.size(); i++) cout << " " << v[i];

cout << "\n\n";

}

void read(vector <int> &v,int n)

{

srand(time(0));

for(int i=1; i<=n; i++)

{

int p=rand()%100+1;

v.push_back(p);

}

int main ()

{

cout<<"n=";

int n;

cin>>n;

vector<int> v;

//запълване на вектора със случайни числа

read(v,n);

write(v);

vector <int>::iterator it,it1=v.end();

// сортиране

sort(v.begin(),v.end());

write(v);

//max елемент

cout<<"max= "<<*max_element(v.begin(),v.end())<<endl;

//min елемент

cout<<"min= "<<*min_element(v.begin(),v.end())<<endl;

//намиране на броя на простите числа

cout<<"Broi prosti chisla: "<<count_if(v.begin(),v.end(),prosto)<<endl;

//изтриване на простите числа от вектора

it=remove_if(v.begin(), v.end(), prosto);

v.erase(it,v.end());

write(v);

return 0;

}

Решение на задачата с низове:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

void read(vector <string> &v,int n)
{
for(int i=1; i<=n; i++)
{
string s;
getline(cin, s);
v.push_back(s);
}
}

bool palindrom(string s) {
string p = s;
reverse(s.begin(), s.end());
string snew = s;
if (p == s) return true;
else return false;
}

int brPalindromi(vector <string> v) {
int br = 0;
for (int i = 0; i < v.size(); i++) {
if (palindrom(v[i])) br++;cout<<v[i]<<endl;
}
return br;
}

int main ()
{
cout<<"n=";
int n;
cin>>n;
cin.ignore();//Игнорира знака Enter натиснат след въвеждане на n
vector <string> v;
read(v,n);
cout << count_if(v.begin(),v.end(),palindrom) << endl;

return 0;
}