Generatori

Sa propun azi o abordare ce ajuta la rezolvarea multor feluri de probleme: generators.

Cum putem itera un vector?

Daca avem un vector de intregi, una din cele mai intalnite modalitati de a itera prin el (pentru a afisa, de exemplu, valorile pe ecran) arata cam asa:

int valori[] = { 1, 2, 3, 4, 5 };
for (int i = 0; i < 5; ++i)
{
   int valoare = valori[i];
   std::cout << valoare << " ";
}

E insa singura modalitate? Nu

Cei ce au inteles pointerii se vor gandi probabil la o solutie de genul asta:

int valori[] = { 1, 2, 3, 4, 5 };

int* pointer_valoare_curenta = valori;
int* sfarsit_valori = valori + 5; //pointer spre primul element de dupa sfarsitul vectorului

while (pointer_valoare_curenta != sfarsit_valori)
{
   int valoare = *pointer_valoare_curenta;
   ++pointer_valoare_curenta; //avanseaza la urmatoarea valoare
   std::cout << valoare << " ";
}

Aceasta abordare ajuta mult deoarece:

• Putem foarte usor sa iteram doar printr-o parte a vectorului, schimband doar pointerii initiali.
  
• Putem adapta usor solutia pentru alte structuri de date (gen liste inlantuite)
  
• Putem generaliza solutia in mod transparent pentru orice structura de date

Abordarea este atat de populara incat biblioteca standard a C++ ofera o gramada de algoritmi care folosesc aceasta abordare de a parcurge o structura de date. De exemplu, suma tuturor elementelor din vector se poate calcula foarte usor asa:

int valori[] = { 1, 2, 3, 4, 5 };
int suma = std::accumulate(valori, valori + 5, 0);
std::cout << "Suma(valori) = " << suma;

Vrem doar suma a doua elemente incepand cu al doilea? Nici o problema:

int valori[] = { 1, 2, 3, 4, 5 };
int suma = std::accumulate(valori + 1, valori + 3, 0);
std::cout << "Suma(valori) = " << suma;

Ce-i un iterator?

Ce-i un iterator in C++? Un obiect care se comparta ca un pointer de mai sus. Ne ofera valoarea curenta, stie avansa la urmatoarea (sau precedenta), suporta comparatie cu alt iterator.

Asadar, daca schimbam vectorul clasic de mai sus cu unul din STL, putem repeta operatiile de mai sus intr-un mod aproape identic, doarece vectorul ne ofera iteratori.

std::vector<int> valori = { 1, 2, 3, 4, 5 };
std::vector<int>::iterator iterator = valori.begin();
std::vector<int>::iterator iterator_sfarsit = valori.end();

while (iterator != iterator_sfarsit)
{
   int valoare = *iterator;
   ++iterator;
   std::cout << valoare << " ";
}

std::vector<int> valori = { 1, 2, 3, 4, 5 };
int suma = std::accumulate(valori.begin() + 1, valori.begin() + 3, 0);
std::cout << "Suma(valori) = " << suma;

std::vector<int> valori = { 1, 2, 3, 4, 5 };
int suma = std::accumulate(valori.begin(), valori.end(), 0);
std::cout << "Suma(valori) = " << suma;

Ziceam mai sus ca solutia se poate generaliza. Daca am folosi o lista inlantuita s-ar schimba ceva? Aproape nimic.

std::list<int> valori = { 1, 2, 3, 4, 5 };
std::list<int>::iterator iterator = valori.begin();
std::list<int>::iterator iterator_sfarsit = valori.end();

while (iterator != iterator_sfarsit)
{
   int valoare = *iterator;
   ++iterator;
   std::cout << valoare << " ";
}

std::list<int> valori = { 1, 2, 3, 4, 5 };
int suma = std::accumulate(valori.begin() + 1, valori.begin() + 3, 0);
std::cout << "Suma(valori) = " << suma;

std::list<int> valori = { 1, 2, 3, 4, 5 };
int suma = std::accumulate(valori.begin(), valori.end(), 0);
std::cout << "Suma(valori) = " << suma;

Ce-i un generator?

Daca am avea un vector cu toate elementele de la 1 la 1000, am putea foarte usor folosi iteratori pentru a-l parcurge. Dar a numara de la 1 la 1000 e ceva trivial, de ce ar trebui sa umplu memoria cu toate valorile pentru asa ceva?

Aici intervine un generator: un iterator mai special ce iti genereaza pe loc valoarea curenta, n-o citeste pur si simplu dintr-o colectie.

La ce ar putea ajuta un astfel de generator? De exemplu la obtinerea sirului lui Fibonacci. Daca am dori sa iteram pe rand valorile sirului, beneficiam de avantaje din ambele directii:

• Parcurgem generatorul ca si cum am fi avut un vector cu toate valorile deja calculate
  
• Calculam insa valoarea pe loc, cand e nevoie; nu calculez in avans primele 100 valori ca apoi sa n-am nevoie decat de 10

class FibonacciGenerator
{
public:
   //instiintam algoritmii ca e un iterator ce stie merge doar inainte, cate un pas odata
   typedef std::input_iterator_tag iterator_category;
   typedef uint64_t value_type;
   typedef uint64_t* pointer;
   typedef uint64_t* reference;

   FibonacciGenerator()
   {
	  currentIndex = 0;
	  //primele doua valori sunt fixate
	  lastValues[0] = 0;
	  lastValues[1] = 1;
   }

   static FibonacciGenerator FibonacciGenerator::end()
   {
	  //returnam un iterator de dupa finalul sirului; 
	  //sirul e infinit, insa folosind uint64_t incap doar vreo 93 elemente
	  FibonacciGenerator result;
	  result.currentIndex = 100;
	  return result;
   }

   uint64_t operator*() const
   {
	  //daca suntem la primul sau al doilea element, returnam valorile fixate
	  //atfel returnam suma ultimelor doua valori
	  if (currentIndex == 0)
	  {
		 return lastValues[0];
	  }
	  if (currentIndex == 1)
	  {
		 return lastValues[1];
	  }
	  return lastValues[0] + lastValues[1];
   }

   bool operator==(const FibonacciGenerator& other) const
   {
	  return currentIndex == other.currentIndex;
   }

   bool operator!=(const FibonacciGenerator& other) const
   {
	  return ! (*this == other);
   }

   FibonacciGenerator& operator++()
   {
	  currentIndex += 1;
	  if (currentIndex > 2)
	  {
		 uint64_t currentValue = **this;
		 lastValues[0] = lastValues[1];
		 lastValues[1] = currentValue;
	  }

	  return *this;
   }

   FibonacciGenerator operator++(int)
   {
	  FibonacciGenerator temp = *this;
	  ++*this;
	  return temp;
   }

private:
   //tinem minte precedentele doua valori
   uint64_t lastValues[2];
   //la al catelea element din sir am ajuns
   uint64_t currentIndex;
};

Vrem sa afisam primele 50 elemente? Nimic mai simplu

FibonacciGenerator fibonacci;

for (size_t i = 0; i < 50; i++)
{
   std::cout << "Fibonacci(" << i + 1 << ") = " << *fibonacci++ << "\n";
}

Quote

Edited by dani.user, 26 October 2016 - 11:18.