锐客网

  1. 首页 > it技术 > >

动态数组(一维驾驭高维数组)

好的 coder 總是有辦法以 1D array 來駕馭高維陣列操作，
但有時使用高維陣列，可讓 code 中的邏輯概念更加清晰。
早期的 C 或目前的 C++ 中，無動態陣列配置的語法，
(在 C99 中才有，例如 gcc 可編譯動態陣列)
因此需要自己實現，底下是我的簡單作法:

設計陣列配置時有 3 點需考量:

1. 配置效率: 最好只呼叫一次 malloc 或 new。
2. 存取效率: 存取速度必須逼近 primary array。
3. 語意: array 的記憶體必須連續分佈。
(所以 vector< vector > 不能算是真正的陣列，
只是個 array container... )

N維動態陣列配置較複雜，先從二維的寫起：

(1) 使用 C 語言:

void** new_arr (int size, int x, int y)//size = 元素大小 { intsz = sizeof (void*); void** a= (void **) malloc (sz*x + size*x*y); if (!a) return 0; char* p = (char*)a + sz * x; while (x--) a[x] = p + size*x*y; return a; }void del_arr (void** a) { if (a) free (a); }void set_arr (void** a, int size, int n...) { va_list p; va_start (p, n); memcpy (a[0], p, size*n); }int main () { typedef struct {float f; char c; } CC; CC cc[4] = {0.2,'a', 0.4,'b', 0.6,'c', 0.8, 'd'}; intsz; int**a; char* **b; CC**c; a = (int**) new_arr (sz = sizeof(int), 2,4); set_arr ((void**)a, sz, 2*4, 1,2,3,4,//依序輸入資料 7,8,9,0 ); printf ("%d", a[1][2]); b = (char***) new_arr (sz = sizeof(char*), 2,2); set_arr ((void**)b, sz, 2*2, "陣列","2D",//依序輸入資料 "輸入","範例" ); printf ("/n%s", b[0][1]); c = (CC**) new_arr (sz = sizeof(CC), 2,2); set_arr ((void**)c, sz, 2*2, cc[0], cc[1],//依序輸入資料 cc[2], cc[3] ); printf ("/n%f %c", c[1][0].f, c[0][0].c); del_arr ((void**)a); del_arr ((void**)b); del_arr ((void**)c); }


(2) 使用 C++:
template struct Array { Array (int x, int y=1): y(y), x(x), p(new T[x*y]) {} ~Array () { for (x*=y; x--; p[x].~T()); delete[] p; } T* operator[] (int i) { return p+i*y; } Array& operator< (T o) { p[n=0] = o; return*this; } Array& operator, (T o) { p[++n] = o; return*this; } private: int x, y, n; T*p; }; int main () { struct CC {float f; char c; } cc[4] = {0.2,'a', 0.4,'b', 0.6,'c', 0.8, 'd'}; Array a (2,4); a < 1,2,3,4,//依序輸入資料 7,8,9,0; cout << a[1][2]; Array b (2,2); b < "陣列","模版",//依序輸入資料 "輸入","範例"; cout < c (2,2); c < cc[0], cc[1],//依序輸入資料 cc[2], cc[3]; cout <

依照相同概念，繼續擴展到 N 維:

C 語言寫法: (此 code 由曾侃的程式修改而來)
#include void* new_arr (int size, int nDim, int n...) { static int d[32] = {0}; //限制最多到 32 維 int i,j, nPtr, nElem, sz = sizeof (void*); //指位器與元素數目 void *a, **b, **c, **t; char *p; //a = 動態陣列起始位址va_list v; va_start (v, nDim); for (i=nDim-1; i>=0; i--)//讀取各個維數 d[i] = va_arg (v, int); if (0 == nDim) return 0; //禁止配置 0 維陣列 d[nDim-1] = n; //糾正Release版別移掉nnPtr= d[1]; //計算指位器表大小 nElem = d[0]*d[1]; //與元素所佔之總空間 for (i=2; i

C++ 寫法:

C++ 動態多維陣列目前最有效率的實作是... 暴力法....
也就是用 template 由 1 維一直特製化到 N 維，
此法速度等同 build-in array，亦是 boost::multi_array 的 4~5 倍..
底下另取它徑，實作一個動態陣列的變形，
改以 array (D1, D2, ...) 的形式來存取陣列元素:
template struct Array { Array (int d...)//傳入各維的維度 { dim[1] = dim[N] = 1; //確保()能正確存取 memcpy (dim, &d, N*sizeof(int)); //紀錄各維的維度 for (n=dim[N-1], i=N-2; i>=0; i--) n *= dim[i], dim[i] = n; //預先計算累加維度 if (0 == n) cout <<"arr size=0"; //配置錯誤 else p = new T[dim[0]]; //配置實體空間 } T& operator()(int j...) { va_start (v,j); for (n=j*dim[1], i=2; i<=N; ++i) n += dim[i] * va_arg (v,int); //算出索引偏移量 return p[n]; } ~Array () { for (i=dim[0]; i--; p[i].~T()); //解構陣列內元素 delete[] p; } private: int i,n, dim[N+1]; //dim[.] = 各維的維度 va_list v; T* p; //陣列實體 }; int main (/* daviddr 080705 */) { Array a(2,3,4,5); for (int i=0; i<2*3*4*5; i++) a(0,0,0,i) = i; cout <


為了模擬陣列語法，只好再加些又長又醜陋的碼，
於是現在可以用 arr (D1,D2,..Dn) 與 arr [D1][D2]..[Dn]
兩種方法來存取陣列了~
template struct Array { Array (int d...)//傳入各維的維度 { dim[1] = dim[N] = 1; //確保()能正確存取 memcpy (dim, &d, N*sizeof(int)); //紀錄各維的維度 for (n=dim[N-1], i=N-2; i>=0; i--) n *= dim[i], dim[i] = n; //預先計算累加維度 if (0 == n) cout <<"arr size=0"; //配置錯誤 else p = new T[dim[0]]; //配置實體空間 } T& operator()(int j...) { va_start (v,j); for (n=j*dim[1], i=2; i<=N; ++i) n += dim[i] * va_arg (v,int); //算出索引偏移量 return p[n]; } ~Array () { for (i=dim[0]; i--; p[i].~T()); //解構陣列內元素 delete[] p; } template struct Ptr//遞迴定義中繼物件 { Ptr (T* t, int* d): p(t), d(d) {} Ptr operator[] (int n) { return Ptr (p + n*(*d), d+1); } operator T*() {return p; } private: T* p; int* d; //用來傳遞暫時參數 }; template struct Ptr//邊界定義 { Ptr (T* t, int*): p(t) {} T& operator[](int n) {return p[n]; } operator T*() {return p; } private: T* p; }; Ptr operator[] (int n) { return Ptr (p + n*dim[1], dim+2); } operator T*() {return p; } private: int i,n, dim[N+1]; //dim[.] = 各維的維度 va_list v; T* p; //陣列實體 }; template struct Array { Array (int d): d(d), p(new T[d]) {} ~Array () { while (d--) p[d].~T(); delete[] p; } T& operator[] (int n) {return p[n]; } T& operator() (int n) {return p[n]; } private: T* p; int d; } ; int main (/* daviddr 080705 */) { int i; Array a(2,3,4,5); for (i=0; i<2*3*4*5; i++) a(0,0,0,i) = i; cout < b(3); for (i=0; i<3; i++) b(i) = java[i]; cout <

【动态数组(一维驾驭高维数组)】

    推荐阅读


    上一篇：Grpc在Python下的小小小操作

    下一篇：多线程交替打印ABC的多种实现方法