12.  Вектори

 

"Ако се разделят компонентите на контравариантния
вектор (dt, dx, dy, dz) на ds, се получава векторът ..."
Алберт Айнщайн
  Използване на вектори за съхраняване на данни.
* Векторът е множество от данни от един и същи тип и данните са номерирани с последователни неотрицателни цели числа.
    Дефиниция на вектор с 10 елемента тип double:
  vector<double> salaries(10);
На елемента с индекс 4 се задава стойност 355.
  salaries[4] = 355;
Елементите на вектора се номерират, започвайки от 0.
  salaries[0] - първи елемент
  salaries[1] - втори елемент
  salaries[2] - трети елемент
  salaries[3] - четвърти елемент
  ...
  salaries[9] - десети елемент


Индекси на вектори.
* Граници на индексите са от 0 до размерността на вектора минус 1. Грешка  "излизане извън границите на вектора" (или грешка при индексиране) се получава, когато индексираме елемент на вектор с число извън интервала [0, размерност-1]. Тази грешка не се открива нито от компилатора, нито от операционната система по време на изпълнение на програмата. Обикновено тя довежда до повреда на някакъв участък от паметта. Това е една от възможните грешки в една програма, която се открива много трудно.
* Член-функцията за получаване на размерността на вектора е size(). Ето типичен цикъл за обхождане на елементите на вектора (в случая за отпечатването им) с използване на тази член-функция.
  for (i=0; i < salaries.size(); i++) cout << salaries[i];
* Може да се дефинира и вектор с 0 елементи:
  vector<double> salaries;
* Типът vector е реализиран като клас в който са дефинирани член-функциите push_back и pop_back за увеличаване и намаляване на размера на вектора.
  salaries.push_back(елемент)- добавяне на елемент към вектора (след последния);
  salaries.pop_back()- премахване на  последния елемент на вектора.
* Пример. Четат се заплати на служители, стойностите се записват във вектор и се чертае графика на заплатите:
// bargraph.cpp
#include "ccc_win.cpp"

int main()
{ vector<double> salaries;
  bool more = true;
  while (more)
  { double s =
    cwin.get_double("Please enter a salary, 0 to quit: ");
    if (s == 0) more = false;
    else salaries.push_back(s);
  }
  int i;
  double highest = salaries[0];
  for (i = 1; i < salaries.size(); i++)
     if (salaries[i] > highest) highest = salaries[i];
  cwin.coord(0, 0, highest, salaries.size());
  for (i = 0; i < salaries.size(); i++)
  {  Point left(0, i);
     Point right(salaries[i], i);
     Line bar(left, right);
     Message label(left, salaries[i]);
     cwin << bar << label;
  }
  return 0;
}



Векторите като параметри и стойности на функции.
* Намиране на средно аритметично на елементите на вектор.
// average.cpp
#include <iostream>
#include <vector>
using namespace std;
 

/* v е параметър-променлива */
double average(vector<double> v)
{  if (v.size() == 0) return 0;
   int i;
   double sum = 0;
   for (i = 0; i < v.size(); i++)  sum = sum + v[i];
   return sum / v.size();
}
int main()
{  vector<double> salaries(5);
   salaries[0] = 35000.0;
   salaries[1] = 63000.0;
   salaries[2] = 48000.0;
   salaries[3] = 78000.0;
   salaries[4] = 51500.0;

   double avgsal = average(salaries);
   cout << "The average salary is " << avgsal << "\n";
   return 0;
}

The average salary is 55100

*  Промяна на стойностите на елементите на вектор. В примера заплатите се увеличават с 4.5 процента. Използва се параметър-псевдоним.
// upsalary.cpp
#include <iostream>
#include <vector>
using namespace std;

/* s е параметър-псевдоним */
void raise_salaries(vector<double>& s, double p)
{  int i;
   for (i=0; i<s.size(); i++) s[i] = s[i]*(1 + p/100);
}
int main()
{  vector<double> salaries(5);
   salaries[0] = 35000.0;
   salaries[1] = 63000.0;
   salaries[2] = 48000.0;
   salaries[3] = 78000.0;
   salaries[4] = 51500.0;
   raise_salaries(salaries, 4.5);
   int i;
   for (i = 0; i < salaries.size(); i++)
            cout << salaries[i] << "\n";
   return 0;
}

36575
65835
50160
81510
53817.5

* Вектор като връщана стойност на функция. Намиране на всички стойности, които попадат в определен интервал. Функцията връща стойност от тип vector<double>.
// between.cpp
#include <iostream>
#include <vector>
using namespace std;

/* връщаната стойност на функцията е от тип vector */
vector<double>
        between(vector<double> v, double low, double high)
{ vector<double> result;
  int i;
  for (i = 0; i < v.size(); i++)
  if (low <= v[i] and v[i] <= high) result.push_back(v[i]);
  return result;
}
int main()
{  vector<double> salaries(5);
   salaries[0] = 35000.0;
   salaries[1] = 63000.0;
   salaries[2] = 48000.0;
   salaries[3] = 78000.0;
   salaries[4] = 51500.0;
   vector<double> midrange_salaries
                  = between(salaries, 45000.0, 65000.0);
   int i;
   for (i = 0; i < midrange_salaries.size(); i++)
                   cout << midrange_salaries[i] << "\n";
   return 0;
}
 

63000
48000
51500

Прости алгоритми за вектори.
* Намиране на стойност. Функцията намира първата срещната стойност на елемент на вектора, която е по-голяма от зададено число.
// find.cpp
#include <iostream>
#include <vector>
using namespace std;

int find_first_greater(vector<double> a, double t)
/* ЦЕЛ: намира първия елемент на вектора a,
        чиято стойност е по-голяма от t
   ПОЛУЧАВА: вектор a и число t
   ВРЪЩА: индекса на намерения елемент или
          -1, ако няма елемент, по-голям от t
*/
{ int i = 0;
  while (i < a.size())
  { if (a[i] > t) return i;
    else i++;
  }
  return -1;
}
int main()
{  vector<double> salaries(5);
   salaries[0] = 35000.0;
   salaries[1] = 63000.0;
   salaries[2] = 48000.0;
   salaries[3] = 78000.0;
   salaries[4] = 51500.0;
   int i = find_first_greater(salaries, 50000);
   if (i > 0)
   {  cout << "The first salary above 50000 is at index " << i
         << " and is " << salaries[i] << "\n";
   }
   return 0;
}

The first salary above 50000 is at index 1 and is 63000

* Броене. Намиране на броя на елементите на вектор, които удовлетворяват зададено условие.
// count.cpp
#include <iostream>
#include <vector>
using namespace std;

int count_greater(vector<double> a, double t)
/* ЦЕЛ: намира броя на елементите на вектора a
        със стойност по-голяма от t
   ПОЛУЧАВА: вектор a и число t
   ВРЪЩА: броя на намерените елементи, по-големи от t
*/
{  int count = 0;
   int i;
   for (i = 0; i < a.size(); i++)
       if (a[i] > t)   count++;
   return count;
}
int main()
{  vector<double> salaries(5);
   salaries[0] = 35000.0;
   salaries[1] = 63000.0;
   salaries[2] = 48000.0;
   salaries[3] = 78000.0;
   salaries[4] = 51500.0;
   int count = count_greater(salaries, 50000);
   cout << count << " salaries are above 50000\n";
   return 0;
}
 

3 salaries are above 50000

* Намиране на всички съответствия. Функцията връща вектор, съдържащ индексите на всички елементи, които удовлетворяват дадено условие.
// matches.cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> find_all_greater(vector<double> a, double t)
/* ЦЕЛ:      намира елементите на вектора a
             със стойност по-голяма от t
   ПОЛУЧАВА: вектор a и число t
   ВРЪЩА:    вектор с индексите на намерените елементи,
             по-големи от t
*/
{  vector<int> pos;
   int i;
   for (i = 0; i < a.size(); i++)
     if (a[i] > t) pos.push_back(i);
   return pos;
}
int main()
{  vector<double> salaries(5);
   salaries[0] = 35000.0;
   salaries[1] = 63000.0;
   salaries[2] = 48000.0;
   salaries[3] = 78000.0;
   salaries[4] = 51500.0;
   vector<int> matches = find_all_greater(salaries, 50000);
   int j;
   cout << "These are the salaries above 50000:\n";
   for (j = 0; j < matches.size(); j++)
      cout << salaries[matches[j]] << "\n";
   return 0;
}
 

These are the salaries above 50000:
63000
78000
51500

 

* Отстраняване на елемент от вектор. Целта е да се изтрие един елемент на вектора и всички елементи след него да се преместят с една позиция назад - т.е. индексите на елементите след изтрития да се намалят с 1.
// remove2.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void erase(vector<string>& a, int pos)
/* ЦЕЛ: отстранява елемент с индекс pos от вектор a
   ПОЛУЧАВА: вектор a и индекс pos
   ЗАБЕЛЕЖКА: редът на оставащите елементи се запазва
*/
{  int i;
   for (i = pos; i < a.size()-1; i++) a[i] = a[i+1];
   a.pop_back();
}
void print(vector<string> a)
{  int i;
   for (i = 0; i < a.size(); i++)
      cout << "[" << i << "] " << a[i] << "\n";
}
int main()
{  vector<string> staff(5);
   staff[0] = "Cracker, Carl";
   staff[1] = "Hacker, Harry";
   staff[2] = "Lam, Larry";
   staff[3] = "Reindeer, Rudolf";
   staff[4] = "Sandman, Susan";
   print(staff);
   int pos;
   cout << "Remove which element? ";
   cin >> pos;
   erase(staff, pos);
   print(staff);
   return 0;
}

[0] Cracker, Carl
[1] Hacker, Harry
[2] Lam, Larry
[3] Reindeer, Rudolf
[4] Sandman, Susan
Remove which element? 2
[0] Cracker, Carl
[1] Hacker, Harry
[2] Reindeer, Rudolf
[3] Sandman, Susan

* Вмъкване на елемент на вектор. Целта е да се вмъкне нов елемент на вектора на зададена позиция и всички елементи след него да се преместят с една позиция напред - т.е. индексите на елементите след новия елемент да се увеличат с 1.
// insert.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void insert(vector<string>& a, int pos, string s)
/* ЦЕЛ: вмъква елемент s с индекс pos във вектора a
   ПОЛУЧАВА: вектор a, индекс pos и елемент s
   ЗАБЕЛЕЖКА: редът на останалите елементи се запазва
*/
{  int last = a.size() - 1;
   a.push_back(a[last]);
   int i;
   for (i = last; i > pos; i--) a[i] = a[i - 1];
   a[pos] = s;
}
void print(vector<string> a)
{  int i;
   for (i = 0; i < a.size(); i++)
      cout << "[" << i << "] " << a[i] << "\n";
}
int main()
{  vector<string> staff(5);
   staff[0] = "Cracker, Carl";
   staff[1] = "Hacker, Harry";
   staff[2] = "Lam, Larry";
   staff[3] = "Reindeer, Rudolf";
   staff[4] = "Sandman, Susan";
   print(staff);
   int pos;
   cout << "Insert before which element? ";
   cin >> pos;
   insert(staff, pos, "New, Nina");
   print(staff);
   return 0;
}
 

[0] Cracker, Carl
[1] Hacker, Harry
[2] Lam, Larry
[3] Reindeer, Rudolf
[4] Sandman, Susan
Insert before which element? 1
[0] Cracker, Carl
[1] New, Nina
[2] Hacker, Harry
[3] Lam, Larry
[4] Reindeer, Rudolf
[5] Sandman, Susan

Успоредни вектори и вектор от обекти.
*  Два вектора са успоредни, ако съществува логическа (смислова) връзка между елементите им с еднакви индекси.
*  Задачата за най-добро отношение цена-качество на компютри (от 11. Класове).
// plotdat1.cpp
#include "ccc_win.cpp"
int main()
/* трите вектора са успоредни */
{  vector<string> names;
   vector<double> prices;
   vector<int> scores;
   string more;
   do
   {  string n = cwin.get_string("Product name:");
      names.push_back(n);
      double p = cwin.get_double("Price:");
      prices.push_back(p);
      int s = cwin.get_int("Score:");
      scores.push_back(s);
      more = cwin.get_string("More data? (y/n)");
   } while (more == "y");
   const double MAX_PRICE = 10000;
   const double MAX_SCORE = 100;
   cwin.coord(0, 0, MAX_PRICE, MAX_SCORE);
   int i;
   for (i = 0; i < names.size(); i++)
   {  Message label(Point(prices[i], scores[i]), names[i]);
      cwin << label.get_start() << label;
   }
   return 0;
}
* Успоредните вектори обикновено създават проблеми и трябва да се избягват. По-добро решение на задачата е с използване на вектор от обекти.
// plotdat2.cpp
#include "ccc_win.cpp"

class Product   {
public:
   Product();
   void read();
   void get_price() const;
   void plot() const;
private:
   double price;
   int score;
   string name;
};
Product::Product()
{ price = 1000; score = 0;
}
void Product::read()
{  name = cwin.get_string("Product name:");
   price = cwin.get_double("Price:");
   score = cwin.get_int("Score:");
}
void Product::plot() const
{  Message label(Point(price, score), name);
   cwin << label.get_start() << label;
}
int main()
{  vector<Product> data;
   string more;
   do
   {  Product c;
      c.read();
      data.push_back(c);
      more = cwin.get_string("More data? (y/n)");
   } while (more == "y");
   const double MAX_PRICE = 10000;
   const double MAX_SCORE = 100;
   cwin.coord(0, 0, MAX_PRICE, MAX_SCORE);
   int i;
   for (i = 0; i < data.size(); i++)
      data[i].plot();
   return 0;
}



Векторите като данни на обект.
* Програма за чертаене на многоъгълници. Програмата чертае триъгълник със зададени координати на върховете му, правилен петоъгълник и накрая правилен n-ъгълник, като числото n се задава като вход.
// polygon.cpp
#include "ccc_win.cpp"

class Polygon {
public:
   Polygon();
   void add_point(Point p);
   void plot() const;
private:
   vector<Point> corners;
};
Polygon::Polygon()
{}
void Polygon::add_point(Point p)
{  corners.push_back(p);
}
void Polygon::plot() const
{  int i;
   int n = corners.size();
   for (i = 0; i < n; i++)
      cwin << Line(corners[i], corners[(i + 1)%n]);
}
int main()
{  Polygon triangle;
   triangle.add_point(Point(1, 1));
   triangle.add_point(Point(3, 4));
   triangle.add_point(Point(2, 6));
   triangle.plot();

   const double PI = 3.141592653589793;
   Polygon pentagon;
   for (int i = 0; i < 5; i++)
      pentagon.add_point(Point(cos(2*PI*i/5),sin(2*PI*i/5)));
   pentagon.plot();

   Polygon n_gon;
   int n = cwin.get_int("Enter n for a new n-gon: ");
   for (int i = 0; i < n; i++)
      n_gon.add_point(Point(cos(2*PI*i/n),sin(2*PI*i/n)));
   n_gon.plot();
   return 0;
}
    Многоъгълникът е представен като клас с данни вектор от точки и функции за обработка на тези данни.