Dzień dobry.
Mój problem dotyczy wskaźników.
Np:
wchar_t* zm1;
wchar_t** zm2;
wchar_t*** zm3;
//...
wchar_t/*n[*]*/ zm_n;
Przepraszam za ten zapis ale myślę, że wiecie o co mi chodzi (ostatnia linia). Jak stworzyć wskaźnik o dowolnej ilości "zagnieżdżeń" wiedząc jednak ile tych "zagnieżdżeń" ma być (parametr podany w konstruktorze np. jakiejś klasy).
Gdyby makra miały jakiś mechanizm pętli byłoby możliwe sklejenie takiego wyrażenia. Szukałem w sieci jakiegoś rozw. ale bezskutecznie.
Chciałem już napisać, że się nie da, ale na szczęście (niestety dla ludzi, którzy pracują nad utrzymaniem kodu) w C++ można zastosować lepsze makra, czyli szablony.
C++
template <class T,int n>
struct MultiStarPointer
{
typedef typename MultiStarPointer<T,n-1>::pointer * pointer;
};
template <class T>
struct MultiStarPointer<T,0>
{
typedef T pointer;
};
int main(){
MultiStarPointer<char,1>::pointer p;
char * v;
p=v;
MultiStarPointer<int,3>::pointer pi3;
int*** pi3test;
pi3=pi3test;
}
Ogólnie to po co tobie takie rozwiązanie. Jeżeli potrzebujesz tworzyć dużo różnych wskaźników ("wielo gwiaździstych"), to bym się zastanowił nad strukturą kodu oraz czy nie można tego problemu rozwiązać w inny sposób.
Dziękuję za odp. Nie wiedziałem, że tak się nawet da.
Natomiast czy przyjąłem dobre założenia, tego nie wiem. Chciałem zrobić najpospolitszą rzecz czyli tablicę n-wymiarową i zamknąć to w jakiejś klasie.
Ktoś zapyta o sens robienia takiego czegoś, przecież są gotowe rozw. jak np. boost multi arrays. To wszystko prawda, jednak chciałem stworzyć sobie coś takiego sam, dostosować do konkretnych potrzeb i przy okazji czegoś się nauczyć. Jeśli ktoś ma jakieś sugestie co do sposobu alokacji pamięci (lepszy sposób), niech pisze śmiało.
Można to rozwiązać na wiele sposób. Na ogół rozwiązania uniwersalne są gorsze.
A najlepiej napisz do czego to ma być stosowane ;)
Rozwiązanie zaproponowane przez Zjarka ma sporą wadę - dostanie się do elementu w tablicy n-wymiarowej wymaga zdereferencjowania n wskaźników.
Tablice wielowymiarowe o każdym wymiarze stałym (tzn np bez sytuacji, w której rzędy tablicy mają różną długość) można łatwo emulować za pomocą tablicy jednowymiarowej i schematu Hornera. Np:
int a[A][B][C];
a[x][y][z] = v;
// ten kod jest równoważny z poprzednim
int b[A * B * C];
b[(x * B + y) * C + z] = v;
Dziękuję za pomoc.
Liczba wymiarów tablicy jest stała, ich długość raczej też (nad tym jeszcze pomyślę ale raczej stała) i mogą to być wartości określone zarówno w czasie działania programu jak i kompilacji. Tablice nie będą puste (hm zdawało mi się, że w rzeczywistości tablica nigdy nie jest pusta). Mogą służyć do tymczasowego przechowania jakiś danych np inf. o modelu 3d, po spełnieniu swojej funkcji ulegną zniszczeniu lub do trzymania jakiś informacji dłuższy czas. Złożoność ... nie wiem czy dobrze rozumiem ale ważniejsza będzie tu raczej lepsza wydajność niż użycie pamięci. Wybaczcie mi braki w wiedzy.
Sprawdzę też pomysł Wibowita, ale czy tutaj można, po przeciążeniu operatora [], zastosować potem wyłuskanie jakiejś wartości np. przez zapis: tab3d[x][y][z]?
Emulowanie tablicy fajny pomysł, jest tylko mały problem związany z narzutem w postaci dodatkowych obliczeń podczas pobierania jakiegoś elementu. Nic mądrego nie wymyślę i zastanawiałem się czy po prostu nie zrobić tego w podobny sposób jak np. w przypadku std::vector, czyli do już istniejącego obiektu dodać kolejny itd., czyli wystarczyłaby tylko tablica 1-wymiarowa i druga n-wymiarowa, która używałaby tej pierwszej:
//zgodnie z tym założeniem np. tablica
int arr[x][y][z];
//tablica o wymiarze x ze wskaźnikami do x tablic
//x tablic o wymiarach y ze wskaźnikami do już właściwych tablic
//x * y tych właściwych tablic o wymiarach z
//np.
template <typename TYPE> class Simple_array
{
//...
};
typedef Simple_array <Simple_array*> _Simple_array_;
template <typename TYPE> class Array
{
//...
Array( unsigned dimensions_count, unsigned dimensions[] )
{
//przydział pamięci
}
//...
};
Narzut związany z obliczeniami jest dość mały, stawiałbym na to, że mniejszy niż wynikający z dereferencji wskaźników (na pewno tak było jak robiłem trójwymiarową tablicę bitów, ale o narzuconym rozmiarze (128), więc mnożenie było zredukowane do przesunięcia bitowego). Dodatkowo przy tablicy wskaźników masz gorsze cache'owanie, co też może się przełożyć na wydajność.
//Edit
Dodatkowo iterowanie po jednym wymiarze (jakimkolwiek) ogranicza się do dodawania stałej do indeksu, dzięki czemu narzut arytmetyczny praktycznie nie ma znaczenia.
Schemat Hornera podałem w sumie jako ciekawostkę. Skoro A, B i C to stałe, to ich iloczyny też są stałymi, a więc można je raz przeliczyć na wstępie i nie używać schematu Hornera. Dlatego:
int b[A * B * C];
// zamiast
b[(x * B + y) * C + z] = v;
// można użyć
b[x * B * C + y * C + z] = v;
Kompilator powinien sobie obliczyć te iloczyny w czasie kompilacji, ewentualnie jeżeli wymiary są obliczane przed tworzeniem instancji klasy, to można to wymnożyć w konstruktorze. Zostaje więc kod:
b[x * BC + y * C + z] = v;
Ilość mnożeń i dodawań pozostała taka sama jak w schemacie Hornera, ale tutaj można wykonywać mnożenia równolegle. Obecnie (tzn od czasów Pentiumów) procesory są wielopotokowe i mogą robić kilka niezależnych operacji naraz, a więc na przykład w tym przypadku.
Różnice w szybkości iteracji pomiędzy implementacją z emulacją za pomocą mnożenia, a implementacją z wielokrotną dereferencją zależy od wielkości najniższych wymiarów. Jeśli są one niskie to narzut w implementacji z wielokrotną dereferencją jest duży.
Ok, jeszcze raz dziękuję wam za wszystkie uwagi.