[C++] Jak zaimplementować tablicę dynamiczną wielowymiarową?


(Sebastianp88) #1

Witam wszystkich

Mam problem z pewnym zadankiem. Stosując programowanie obiektowe mam zaprogramować programik który umożliwi utworzenie tablicy wielowymiarowej. Problem ten jest o tyle łatwy do wykonania pod warunkiem, że z góry znamy znamy ilość wymiarów tablicy którą chcemy utworzyć, tym samym można użyć odpowiedniej ilości operatorów wyłuskania ( *, **, *** odpowiednio dla 1, 2 i 3 wymiarowej tablicy). Tutaj pojawia się mój problem. Jak stworzyć program, który utworzy tablicę dynamiczną o n-wymiarach? Wymiar tablicy jest podawany przez użytkownika. Z góry pragnę podkreślić, że nie oczekuję otrzymania gotowego rozwiązania, bo nie w tym rzecz. Będę wdzięczny za "nakreślenie" odpowiedniego sposobu w jaki mógłbym zabrać się do wykonania tego zadanka. Z góry dziękuję za pomoc.


(Sawyer47) #2

Można to różnie zaimplementować, niekoniecznie jako tablice wskaźników, kod byłby raczej zagmatwany. Można zarezerwować odpowiednio dużą tablicę i całą logikę wielowymiarowości obsługiwać przez dodatkowe funkcje. Np. masz tablicę 2x2 więc rezerwujesz tablicę czteroelementową i tłumaczysz współrzędne do jednej liczby, więc (0, 0) = 0, (0, 1) = 1, (1, 0) = 2, (1, 1) = 3; Oczywiście to tylko propozycja na szybko, takie podejście też pewnie tworzy dodatkowe problemy do rozwiązania. Zobacz jak zrobili to twórcy Boost.Multi-Array.


(Sebastianp88) #3

Pomysł z zarezerwowaniem odpowiednio dużej tablicy nie złym pomysłem. Tylko tak jak zauważyłeś, wymaga on zadeklarowania odpowiednio dużej tablicy. Sam ten pomysł moim zdaniem jest możliwy do wykonania tylko przy ograniczeniu do 3 wymiarów. Trzeba tylko jeszcze wiedzieć jak poruszać się w 4 i większych wymiar - a z tym już gorzej. Link który umieściłeś na pierwszy rzut oka wygląda ciekawie. Poświęcę stronce pół albo i całą nockę i się zobaczy co się da z tego stworzyć. W każdym razie dzięki za pomysł :slight_smile:


(Sawyer47) #4

Tak sobie jeszcze pomyślałem, że pod spodem może być posortowana lista lub hash, ważne byle się zachowywało jak tablica wielowymiarowa. Kluczami byłby specjalne obiekty-indeksy, a gdyby chcieć mieć dostęp do poszczególnego wymiaru można by zwracać coś jak iteratory (widoki? nie wiem jak to nazwać :wink:), które przechowuje informacje o źródłowej "tablicy" oraz wymiarze który reprezentują. Jeśli danego indeksu nie ma w hashu, to zwracało by wartość domyślną, a przypisanie do niedodanego wcześniej indeksu dodawałoby go razem z wartością do hasha. A odwołania do nieistniejących wymiarów łatwo rozpoznać. Plusem byłaby oszczędność pamięci, nieporównywalna do alokacji od razu, ale na pewno ucierpiała by szybkość. Na tym to polega, żeby znaleźć kompromis między pamięciożernością a cyklożernością.


([alex]) #5

O jakich komplikacjach wy gadacie? Proszę - proste przeliczanie z wymiarów tablicy na ilość potrzebnej pamięci, oraz przeliczanie ze współrzędnych w N-wymiarowej tablice na Index w pamięci ciągłej i z powrotem.

const unsigned IleWymiarow=7;typedef unsigned Wymiary[IleWymiarow];

(Sebastianp88) #6

Alex, jeśli dobrze Ciebie zrozumiałem, to podsunąłeś mi dobry pomysł. W praktyce mam już wykonane 80% zadania.

Dziękuję za pomoc.


([alex]) #7

To nie mój pomysł, dokładnie tak się oblicza (jak w WspolrzedneNaIndex) gdzie wpisać liczbę w przypadku:

double T[5][6][7][8];T[3][4][5][6]=5.5; [/code]Da się to nawet sprawdzić wywołując debuger'a i analizując kod w assemblerze.
Rozmiar obszaru pamięci który zajmuje tablica T jest obliczany jak w Rozmiar, tego akurat nie sprawdzisz ponieważ dzieje się to podczas kompilacji, ale jest to jedyny poprawny sposób, więc łatwo uwierzyć.

(pebal) #8

Pytanie jest co tak naprawdę chcesz uzyskać - dynamiczne tablice o zdefiniowanym wymiarze, czy dynamiczne wymiary tablic.

To pierwsze ma większy sens, bo trudno mi sobie wyobrazić, jakie zastosowanie mogłaby mieć np. 16-sto wymiarowa tablica.

Pomijając jednak sensowność rozwiązań, proponuję jak poniżej.

Dla tablic dynamicznych, gdzie wymiary tablic ustalane są statycznie (domyślnie 1 wymiar)

#include 


template

class array

{

	std::vector > _arr;


public:

	array& operator [](unsigned int i)

	{

		if (_arr.size() <= i)

		{

			_arr.insert(_arr.end(), i - _arr.size() + 1, array());

		}


		return _arr[i];

	}

};


template

class array

{

	std::vector _arr;


public:

	T& operator [](unsigned int i)

	{

		if (_arr.size() <= i)

		{

			_arr.insert(_arr.end(), i - _arr.size() + 1, T());

		}


		return _arr[i];

	}

};

gdzie tablice tworzone są i używane jak poniżej

array t1;

t1[1] = 10;

t1[4] = 13;


array t2;

t2[1][2][2] = 5;

t2[3][7][1] = 2;

A dla tablic o dynamicznym wymiarze, gdzie ustalana jest jedynie maksymalna ilość dopuszczalnych wymiarów (domyślnie 16)

#include 


template

class array

{

	std::vector > _arr;

	T _val;


public:

	array& operator [](unsigned int i)

	{

		if (_arr.size() <= i)

		{

			_arr.insert(_arr.end(), i - _arr.size() + 1, array());

		}


		return _arr[i];

	}


	operator T& () { return _val; }

	T& operator = (const T& v) { _val = v; return _val; }

};


template

class array

{

	std::vector _arr;

	T _val;


public:

	T& operator [](unsigned int i)

	{

		if (_arr.size() <= i)

		{

			_arr.insert(_arr.end(), i - _arr.size() + 1, T());

		}


		return _arr[i];

	}


	operator T& () { return _val; }

	T& operator = (const T& v) { _val = v; return _val; }

};

gdzie tablice tworzone są i używane jak poniżej

array t1;

t1[1] = 5;

t1[4][8][3] = 13;


array t2;

t2[3][4] = 2;

t2[1][3][5][2][3] = 4;

Dla poprawności, szablony klasy array dla drugiego przypadku, należałoby uzupełnić o wszystkie operatory arytmetyczne i logiczne - obecnie zdefiniowano jedynie operator przypisania.

Pozdrawiam.


([alex]) #9

pebal , ten drugi wariant jest bardzo ciekawym tworem, tylko nie wiem czy komukolwiek dla czegokolwiek się przyda. Autor tematu na początku zaznaczył że ilość wymiarów jest znana no i wypadało by przeczytać całe pytanie zanim zaczynasz odpowiadać. :smiley:

Więc wypowiem się tylko na temat pierwszego wariantu. Wyobraź sobie że na podstawie twojego pierwszego wariantu zrobimy:

templateT,unsigned int N> array<T,N> array<T,N>::operator+(const array<T,N> &A)const {...}

Który tworzy nową tablicę każda komórka której jest sumą komórek z tablicy *this i tablicy A. Załóżmy że stworzymy dwie tablicy trójwymiarowe po 10 elementów w każdym z wymiarów generalnie A[10][10][10] i B[10][10][10], wypełnimy je i użyjemy operatora array C=A+B;

Uwaga pytanie , ile konstruktorów i ile destruktorów zostanie uruchomione pod czas tej operacji?

Odpowiedź: 223 konstruktorów, 222 destruktorów. Straszne nieprawdaż?

Ale zawsze jest coś za coś, właściwie w 15 linijek kodu (nie licząc klamerek) mamy z głowy kontener dla tablicy.


(pebal) #10

Ja czytam pytania na które odpowiadam, bo inaczej nie byłbym w stanie na nie odpowiedzieć.

Autor wątku napisał: "Wymiar tablicy jest podawany przez użytkownika".

Ja z tego rozumiem, że ilość wymiarów znana z góry nie jest, ale Ty oczywiście możesz to rozumieć inaczej.


([alex]) #11

Jednak jak widać nie do końca czytasz.

Ja z tego rozumiem że użytkownik podaje rozmiary tablicy w określonych z góry ilościach wymiarów.

Znowu jak widać, nie czytasz.

W ostatnim wymiarze jest liczba int dla której nie wywołuje się żaden konstruktor. Może znowu nie doczytałeś?

To poczytaj mój poprzedni post w tym temacie, jak widać nie raczyłeś sprawdzić co już inni odpowiedzieli.

Tu się zgadzam, i właśnie to napisałem tylko że innymi słowami:


(pebal) #12

"Problem ten jest o tyle łatwy do wykonania pod warunkiem , że z góry znamy znamy ilość wymiarów tablicy którą chcemy utworzyć"

Gdzie masz napisane, że ten warunek jest spełniony?

"Jak stworzyć program, który utworzy tablicę dynamiczną o n-wymiarach?"

Wiesz ile wynosi n?

Ustosunkowałem się do Twojego "wypełnienia" w następnym punkcie, w czymś Ci to przeszkadza?.

Typ int posiada trywialny konstruktor, podobnie zresztą jak wiele innych typów. Podczas kopiowania danych, wywoływany jest domyślny konstruktor kopiujący.

Proponuje się dokształcić.

Wiesz co to jest dynamiczna tablica?

Pokaż mi który przykład pokazuje jak utworzyć wielowymiarową, dynamiczną tablicę, czyli taka której rozmiar w trakcie jej życia może się zmienić (np. w drugim wymiarze).