[C++] Parcurgerea elegantă a matricilor, în orice ordine

Probleme ce implica matrici sunt printre cele mai frecvente din liceu, si nu numai.

Sa luam un exemplu: https://forum.softpe...onacci-matrice/ . Cerinta, pe scurt: popularea unei matrici cu un sir Fibonacci, insa matricea trebuie parcursa intr-o ordine mai aparte.

Si unde-i problema?

Elevul incepe, probabil, sa scrie diverse for'uri, pentru a parcurge matricea in ordinea dorita, amesteca apoi logica cu generarea sirului lui Fibonacci rezultand:

• Fie un amalgam care-l zapaceste de elev, acesta nereusind sa rezolve problema pana la capat (cum se intampla in topicul indicat)
  
• Fie un amalgam functional, dar aproape ilizibil de oricine altcineva, astfel incat urmatorul elev ce are aceeasi problema nu intelege rezolvarea si-o ia de la capat.

De ce se intampla asta?

Fiindca elevii pun totul la gramada si nu stiu/vor/constientizeaza ca probleme diferite ar trebui rezolvate separat.

• O matrice o parcurgi intr-un anume fel indiferent de ce citesti din/scrii in ea
  
• Sirul lui Fibonacci il generezi intr-un anume fel indiferent ce faci apoi cu el

Se poate rezolva mai elegant?

Evident

Cum?

C++ abstractizeaza iterarea prin structuri de date cu ajutorul iteratorilor. Drept urmare, de ce sa nu folosim iteratori si pentru a parcurge matrici?

Ne aducem aminte ca o matrice gen int[3][3] e asezata secvential in memorie, ca un sir de 3*3 = 9 elemente. Asa cum putem folosi un pointer pentru a ne plimba prin sir, la fel putem folosi un pointer pentru a ne plimba prin matrice.

Iteratorul practic va avea un comportament asemenea unui astfel de pointer. Va retine:

• Pointerul spre datele din matrice
  
• Dimensiunile matricii
  
• Pozitia curenta
  
• O strategie de parcurgere a matricii

template<typename T, typename Strategy>
class MatrixIterator
{
public:
	typedef std::random_access_iterator_tag iterator_category;
	typedef T value_type;
	typedef ptrdiff_t difference_type;
	typedef T* pointer;
	typedef T& reference;
	MatrixIterator(T* matrix, size_t width, size_t height, Strategy strategy)
		: matrix_(matrix), width_(width), height_(height), current_index_(0), strategy_(strategy)
	{}
	template<size_t Width, size_t Height>
	explicit MatrixIterator(T (&matrix)[Width][Height], Strategy strategy)
		: MatrixIterator(matrix, Width, Height, strategy)
	{}
	MatrixIterator(const MatrixIterator& other) = default;
	MatrixIterator(MatrixIterator&& other) = default;
	MatrixIterator& operator=(const MatrixIterator& other) = default;
	MatrixIterator& operator=(MatrixIterator&& other) = default;
	T& operator*() const
	{
		return this->operator[](0);
	}
	T& operator[](int offset) const
	{
		return matrix_[strategy_(width_, height_, current_index_ + offset)];
	}
	MatrixIterator& operator++()
	{
		current_index_ += 1;
		return *this;
	}
	MatrixIterator operator++(int)
	{
		MatrixIterator temp = *this;
		++*this;
		return temp;
	}
	MatrixIterator& operator--()
	{
		current_index_ -= 1;		   
		return *this;
	}
	MatrixIterator operator--(int)
	{
		MatrixIterator temp = *this;
		--*this;
		return temp;
	}
	MatrixIterator& operator+=(int n)
	{
		current_index_ += n;
		return *this;
	}
	MatrixIterator& operator-=(int n)
	{
		return *this += -n;
	}
	MatrixIterator operator+(int n) const
	{
		MatrixIterator copy(*this);
		return copy += n;
	}
	MatrixIterator operator-(int n) const
	{
		MatrixIterator copy(*this);
		return copy -= n;
	}
	difference_type operator-(const MatrixIterator& other) const
	{
		return current_index_ - other.current_index_;
	}
	bool operator==(const MatrixIterator& other) const
	{
		return std::tie(width_, height_, current_index_, strategy_)
			== std::tie(other.width_, other.height_, other.current_index_, strategy_);
	}
	bool operator!=(const MatrixIterator& other) const
	{
		return !(*this == other);
	}

	bool operator<(const MatrixIterator& other) const
	{
		return std::tie(width_, height_, current_index_, strategy_)
			 < std::tie(other.width_, other.height_, other.current_index_, strategy_);
	}
	bool operator>(const MatrixIterator& other) const
	{
		return std::tie(width_, height_, current_index_, strategy_)
			 > std::tie(other.width_, other.height_, other.current_index_, strategy_);
	}
	bool operator<=(const MatrixIterator& other) const
	{
		return !(*this > other);
	}
	bool operator>=(const MatrixIterator& other) const
	{
		return !(*this < other);
	}
private:
	T* matrix_;
	size_t width_;
	size_t height_;
	size_t current_index_;
	Strategy strategy_;
};

Pare complicat la prima vedere, dar nu prea face altceva decat sa reproduca operatii primitive.
Atentie, iteratorul trebuie folosit cu grija. Nu se verifica accesul la zone de memorie nedorite daca sunt depasite limitele.

Constructorul are cam multi parametrii?

Hai sa scriem niste functii ajutatoare:

template<typename T, typename Strategy>
MatrixIterator<T, Strategy> make_matrix_iterator(T* matrix, size_t width, size_t height, Strategy strategy)
{
	return MatrixIterator<T, Strategy>(matrix, width, height, strategy);
}

template<typename T, typename Strategy, size_t Width, size_t Height>
MatrixIterator<T, Strategy> make_matrix_iterator(T(&matrix)[Width][Height], Strategy strategy)
{
	return make_matrix_iterator<T, Strategy>(matrix[0], Width, Height, strategy);
}

template<typename T, typename Strategy>
MatrixIterator<T, Strategy> make_matrix_iterator_end(T* matrix, size_t width, size_t height, Strategy strategy)
{
	auto result = make_matrix_iterator(matrix, width, height, strategy);
	result += width * height;
	return result;
}

template<typename T, typename Strategy, size_t Width, size_t Height>
MatrixIterator<T, Strategy> make_matrix_iterator_end(T(&matrix)[Width][Height], Strategy strategy)
{
	return make_matrix_iterator_end<T, Strategy>(matrix[0], Width, Height, strategy);
}

Si cum ma ajuta asta sa parcug matricea intr-o ordine diferita?

Iteratorul tine evidenta pozitiei curente intr-o matrice de dimensiuni date. Cand ii este cerut in element, el nu va folosi direct pozitia curenta ci va cere unei strategii de iterare ce pozitie sa foloseasca defapt.

Daca se doreste iterarea in ordine normala sus/jos, stanga/dreapta, strategia nu face altceva decat sa returneze pozitia curenta:

size_t normal_matrix_order(size_t width, size_t height, size_t current_index)
{
	return current_index;
}

Daca insa se vrea, de exemplu, iterarea in ordine inversa, jos/sus, dreapta/stanga, strategia calculeaza o alta pozitie:

size_t reverse_matrix_order(size_t width, size_t height, size_t current_index)
{
	return width * height - current_index - 1;
}

Cum folosesc asta?

int matrix[3][3] =
{
	{1, 2, 3},
	{4, 5, 6},
	{7, 8, 9}
};

auto start = make_matrix_iterator(matrix, &normal_matrix_order);
auto end = make_matrix_iterator_end(matrix, &normal_matrix_order);

for (auto it = start; it != end; ++it)
{
	std::cout << *it << ' ';
}

Quote

Ordine inversa:

int matrix[3][3] =
{
	{1, 2, 3},
	{4, 5, 6},
	{7, 8, 9}
};

auto start = make_matrix_iterator(matrix, &reverse_matrix_order);
auto end = make_matrix_iterator_end(matrix, &reverse_matrix_order);

for (auto it = start; it != end; ++it)
{
	std::cout << *it << ' ';
}

Quote

S-a schimbat ceva? Doar am zis ca vreau sa iterez in alta ordine, indicand strategia folosita

Pot itera si in ordinea de mai sus?

Definesc o strategie noua:

size_t alternate_matrix_order(size_t width, size_t height, size_t current_index)
{
	auto x = current_index % width;
	auto y = current_index / height;

	if (y % 2 == 0)
	{
		//normal order
		return current_index;
	}
	else
	{
		//alternate order
		auto firstInRow = y * height;
		auto offsetInRow = width - x - 1;
		return firstInRow + offsetInRow;
	}
}

int matrix[3][3] =
{
	{1, 2, 3},
	{4, 5, 6},
	{7, 8, 9}
};

auto start = make_matrix_iterator(matrix, &alternate_matrix_order);
auto end = make_matrix_iterator_end(matrix, &alternate_matrix_order);

for (auto it = start; it != end; ++it)
{
	std::cout << *it << ' ';
}

Quote

Am vazut cum citesc elemente din matrice, dar cum le modific?

Iteratorul permite si modificarea elementului curent.

Exemplul de mai jos populeaza, in ordine inversa, o matrice cu puteri de-a lui 2, iar apoi le afiseaza in ordinea obisnuita a matricii

int powers_of_two[3][3];
auto powers_of_two_start = make_matrix_iterator(powers_of_two, &reverse_matrix_order);
auto powers_of_two_end = make_matrix_iterator_end(powers_of_two, &reverse_matrix_order);

int current_value = 1;

for (auto it = powers_of_two_start; it != powers_of_two_end; ++it)
{
	*it = current_value;
	current_value *= 2;
}

powers_of_two_start = make_matrix_iterator(powers_of_two, &normal_matrix_order);
powers_of_two_end = make_matrix_iterator_end(powers_of_two, &normal_matrix_order);

for (auto it = powers_of_two_start; it != powers_of_two_end; ++it)
{
	std::cout << *it << ' ';
}

Quote

Combinatiile sunt atat de flexibile incat se pot copia elementele dintr-o matrice, parcursa intr-un anumit mod, in alta matrice, parcursa in alt mod:

int matrix[3][3] =
{
	{1, 2, 3},
	{4, 5, 6},
	{7, 8, 9}
};

auto start = make_matrix_iterator(matrix, &alternate_matrix_order);
auto end = make_matrix_iterator_end(matrix, &alternate_matrix_order);


int destination_matrix[3][3];

auto destination_start = make_matrix_iterator(destination_matrix, &reverse_matrix_order);

std::copy(start, end, destination_start);

 Untitled.png   7.23K   22 downloads

Ce fac daca am o matrice de siruri de caractere?

Acelasi lucru, codului de mai sus nu-i pasa ce stochezi in matrice.

Cool