Jak zrobić tablicę wielowymiarową bez tablicy wielowymiarowej

Załóżmy, że trzeba zrobić tablicę wielowymiarową. W C wielowymiarowość jest nieprzyjemna, szczególnie gdy chcemy uniwersalne funkcje operujące na tablicy o dowolnej wymiarowości. W C++ sprawa jest prostsza, bo są wektory, które można wzajemnie zagnieżdżać. Inne, że wygoda takiego rozwiązania jest podobna jak w C, z tym że odpada problem de-re-alokacji.

W Python jest NumPy, czyli jest cudownie ^^

Czy w zasadzie potrzebujemy tablic wielowymiarowych? Programowanie przypomina tworzenie filmu. Ważne jest co zobaczy użytkownik, a nie jak to powstało ( zastanawiam się czy aluzja do parówek nie była by bardziej stosowna ).

Załóżmy, że potrzebujemy napisać w C++ mechanizm wygodnej tablicy 1D, 2D i 3D. Nie chcemy robić wektora wektorów wektorów, bo to nieeleganckie, nieefektywne i siermiężne.

Tablicę dowolnej wymiarowości można trzymać w wektorze. Istnieje mapowanie tablicy dowolnej wymiarowości N na wymiarowość niższą, włączając jednowymiarową. Niech nasza tablica wygląda tak:

, a chcemy ją zapisać za pomocą wektora 1D, czyli szukamy mapowania

 Każde równanie mapujące tablicę ND na MD jest równaniem liniowym. My będziemy chcieli tablicę 2D sprowadzić do 1D. Sprowadzając cokolwiek do 1D nasze równanie będzie zawsze postaci wielowymiarowego równania linowego, np:

To, co stoi po lewej stronie to indeks liniowy, czyli pod którym indeksie w wektorze znajdzie się element, gdy tablicę ND sprowadzimy do wektora. W tym przypadku aby z wektora wydobyć element znajdujący się na w-tym wierszu i w k-tej kolumnie należy posłużyć się dwoma zmiennymi (w,k), czyli równaniem z dwoma zmiennymi:

Ściślej, nasze równanie będzie wyglądało i ( w, k ) = a*w+b*k+c. Niewiadomych ( a, b, c ) pozbędziemy się dzięki układowi równań. Typuję 3 indeksy z mojej tablicy, które posłużą mi do
wyznaczenia stałych ( a, b, c ). Zakładam dla siebie, że wiersze i kolumny indeksujemy od 0. Wektor w którym będziemy trzymać dane też jest indeksowany od 0. Wybrałem te elementy:

czyli dla elementów (w=1, k=2) wyliczam indeks liniowy (2), analogicznie dla elementów (w=1, k=0) oraz (w=1, k=1).

Gdyby wybrać indeks (w=0, k=0), od razu by było widać, że c=0.

Wracając, wśród współczynników widać wartość a=3. Ta trójka to nic innego, jak ilość kolumn w tabeli. Ostatecznie równanie funkcji mapującej 2D -> 1D to:

Widać, że  ilość wierszy nie ma żadnego przełożenia na to, pod jakim indeksem będzie trzymana wartość.

Poniżej kod prezentujący na szybko jak stosować taką tablicę:

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef struct Tab2D
{
 private:
  vector<int> v; //jednowymiarowy
  size_t iw, ik;

 public: 
  typedef pair<size_t, size_t> wymiar;
  
  Tab2D(int w, int k, int wypelnienie=0)
  {
   v.resize( w * k, wypelnienie );
   iw=w;
   ik=k;
  }
  
  int& operator()(size_t indeksLiniowy)
  {
   return v.at ( indeksLiniowy );
  }
  
  int& operator()(size_t w, size_t k)
  {
   return v.at( w*ik + k ); //to wynika z rownania liniowego mapujacego 2D -> 1D
  }
  
  wymiar wezWymiar()
  {
   return make_pair(iw, ik);
  }
  
  void wypisz()     //TYLKO DO CELOW TESTOWYCH
  {
   cout << "-------" << endl;
   for (int w=0; w<iw; w++)
    for (int k=0; k<ik; k++)
     cout << w << ' ' << k  << ' ' << (*this)(w,k) << endl;
  }
 
} Tab2D;

int main()
{
 Tab2D t(3,2);
 
 cout << t.wezWymiar().first << ' ' << t.wezWymiar().second << endl;
 
 t.wypisz();
 
 for (int w=0; w<t.wezWymiar().first; w++)
  for (int k=0; k<t.wezWymiar().second; k++)
   t(w, k) = w+k;

 t.wypisz();

 return 0;
}