Matrix

tech • 306 słów • 2 minuty czytania

Kiedyś, prawie rok temu kombinowałem coś z dwuwymiarowymi tablicami dynamicznymi.

W projekcie xime, lista kontaktów wykorzystuje prostą implementację takowej tablicy opartą na małym rozszerzeniu standardowego wektora. Tablica ta odzwierciedla widoczne w danej chwili w kontrolce elementy, zawiera wskaźniki, bądź proste elementy z wskaźnikami do elementów kontaktów umieszczonych w powiązanym drzewie, coś w stylu B-tree.

Idea działania tablicy jest dokładnie taka, jaką opisano w wspomnianej notce, jako ostatnie rozwiązanie.

Miałem ostatnio chwilkę, to poprawiłem i doprowadziłem do porządku kod tablicy dwuwymiarowej używany w xime, aby można było go wykorzystać w dowolnym innym miejscu.

Podobnie jak poprzednio opisywany vector_ptr, klasa matrix dostępna jest na projects.malcom.pl, na licencji MIT. Mam nadzieje, ze komuś również się przyda w prostym projekcie.

Do bardziej zaawansowanych operacji warto zaznajomić się z podobnymi kontenerami z biblioteki boost.

Wracając do tematu mojego matrixa.

Poniżej przykład jak można byłoby zaimplementować w niestandardowym wykonaniu algorytm for_each, do operowania na wszystkich elementach kolejki. Ważne jest, aby umożliwić wykonanie jakiś obliczeń lub operacji pomiędzy przetwarzaniem poszczególnych wierszy, dlatego funktor przyjmuje następującą postać:

template<typename T>
class MatrixFunctor {
public:
	PreRowProcess() {}
	void operator()(const T& item) {}
	PostRowProcess() {}
};

Wtedy sam algorytm wyglądałby tak:

template<typename Matrix, class Fn>
Fn for_each(Matrix& m, Fn func) {

	Matrix::iterator first = m.begin();
	Matrix::iterator row   = m.begin();
	Matrix::iterator last  = m.end();

	while (first != last) {
		row += m.size_cols();
		func.PreRowProcess();

		while (first != row) {
			func(*first);
			++first;
		}

		func.PostRowProcess();
	}

	return func;
}

W implementacji listy kontaktów xime nie wykorzystuje podobnych algorytmów, tam każda operacja na jakimś zakresie elementów kontenera ma własną ręcznie pisaną pętle, głownie dostosowana do danej sytuacji. W niektórych sytuacjach zmiana na ogólniejszy algorytm pogorszyłaby wydajność. Może nie zauważalnie, ale na pewno dodatkowe klasy z funktorami zaciemniłyby kod i ideę jego działania.

Może następnym razem, jak wrócę z Warszawy, uda mi się uporządkować kod tej struktury powiązanych drzewem list w stylu B-tree.

Komentarze (0)

Dodaj komentarz

/dozwolony markdown/

/nie zostanie opublikowany/