مصفوفات ثلاثية الأبعاد للأعداد الصحيحة في لغة C++

Question

أرغب في اكتشاف طرق آمنة لتنفيذ مصفوفات ثلاثية الأبعاد من الأعداد الصحيحة في لغة C++، باستخدام المؤشر الحسابي/تخصيص الذاكرة الديناميكية، أو بدلاً من ذلك باستخدام STL تقنيات مثل المتجهات.

أريد بشكل أساسي أن تبدو أبعاد صفيف الأعداد الصحيحة كما يلي:

[ x ][ y ][ z ]

X و Y في النطاق 20-6000 Z معروف ويساوي 4.

Answer 1

ألق نظرة على التعزيز مصفوفة متعددة الأبعاد مكتبة.إليك مثال (مقتبس من وثائق Boost):

#include "boost/multi_array.hpp"

int main() {
  // Create a 3D array that is 20 x 30 x 4
  int x = 20;
  int y = 30;
  int z = 4;

  typedef boost::multi_array<int, 3> array_type;
  typedef array_type::index index;
  array_type my_array(boost::extents[x][y][z]);

  // Assign values to the elements
  int values = 0;
  for (index i = 0; i != x; ++i) {
    for (index j = 0; j != y; ++j) {
      for (index k = 0; k != z; ++k) {
        my_array[i][j][k] = values++;
      }
    }
  }
}

Answer 2

كل زوج من الأقواس المربعة هو عملية إلغاء مرجعية (عند تطبيقها على المؤشر).على سبيل المثال، أزواج الأسطر التالية من التعليمات البرمجية متكافئة:

x = myArray[4];
x = *(myArray+4);

 

x = myArray[2][7];
x = *((*(myArray+2))+7);

لاستخدام بناء الجملة المقترح، فإنك ببساطة تقوم بإلغاء مرجعية القيمة التي تم إرجاعها من إلغاء المرجع الأول.

int*** myArray = (some allocation method, keep reading);
//
// All in one line:
int   value = myArray[x][y][z];
//
// Separated to multiple steps:
int** deref1 = myArray[x];
int*  deref2 = deref1[y];
int   value = deref2[z];

للبدء في تخصيص هذه المصفوفة، تحتاج ببساطة إلى إدراك أنه ليس لديك في الواقع مصفوفة ثلاثية الأبعاد من الأعداد الصحيحة.لديك مجموعة من صفائف صفائف الأعداد الصحيحة.

// Start by allocating an array for array of arrays
int*** myArray = new int**[X_MAXIMUM];

// Allocate an array for each element of the first array
for(int x = 0; x < X_MAXIMUM; ++x)
{
    myArray[x] = new int*[Y_MAXIMUM];

    // Allocate an array of integers for each element of this array
    for(int y = 0; y < Y_MAXIMUM; ++y)
    {
        myArray[x][y] = new int[Z_MAXIMUM];

        // Specify an initial value (if desired)
        for(int z = 0; z < Z_MAXIMUM; ++z)
        {
            myArray[x][y][z] = -1;
        }
    }
}

يتبع إلغاء تخصيص هذه المصفوفة عملية مشابهة لتخصيصها:

for(int x = 0; x < X_MAXIMUM; ++x)
{
    for(int y = 0; y < Y_MAXIMUM; ++y)
    {
        delete[] myArray[x][y];
    }

    delete[] myArray[x];
}

delete[] myArray;

Answer 3

يوجد أدناه طريقة مباشرة لإنشاء مصفوفات ثلاثية الأبعاد باستخدام C أو C++ في جزء واحد من الذاكرة لكل مصفوفة.ليست هناك حاجة لاستخدام BOOST (حتى لو كان ذلك جيدًا)، أو لتقسيم التخصيص بين الأسطر ذات الاتجاه غير المباشر المتعدد (وهذا أمر سيء للغاية لأنه عادةً ما يؤدي إلى فرض عقوبات كبيرة على الأداء عند الوصول إلى البيانات ويؤدي إلى تجزئة الذاكرة).

الشيء الوحيد الذي يجب أن نفهمه هو أنه لا يوجد شيء اسمه مصفوفات متعددة الأبعاد، بل مجرد مصفوفات من المصفوفات (من المصفوفات).الفهرس الأعمق هو الأبعد في الذاكرة.

#include <stdio.h>
#include <stdlib.h>

int main(){

    {
        // C Style Static 3D Arrays
        int a[10][20][30];
        a[9][19][29] = 10;
        printf("a[9][19][29]=%d\n", a[9][19][29]);
    }

    {
        // C Style dynamic 3D Arrays
        int (*a)[20][30];
        a = (int (*)[20][30])malloc(10*20*30*sizeof(int));
        a[9][19][29] = 10;
        printf("a[9][19][29]=%d\n", a[9][19][29]);
        free(a);
    }

    {
        // C++ Style dynamic 3D Arrays
        int (*a)[20][30];
        a = new int[10][20][30];
        a[9][19][29] = 10;
        printf("a[9][19][29]=%d\n", a[9][19][29]);
        delete [] a;
    }

}

بالنسبة لمشكلتك الفعلية، نظرًا لاحتمال وجود بعدين غير معروفين، هناك مشكلة في اقتراحي وهو السماح ببُعد واحد غير معروف فقط.هناك عدة طرق لإدارة ذلك.

والخبر السار هو أن استخدام المتغيرات يعمل الآن مع لغة C، ويسمى بالمصفوفات ذات الطول المتغير.أنت تبدو هنا للتفاصيل.

    int x = 100;
    int y = 200;
    int z = 30;

    {
        // C Style Static 3D Arrays 
        int a[x][y][z];
        a[99][199][29] = 10;
        printf("a[99][199][29]=%d\n", a[99][199][29]);
    }

    {
        // C Style dynamic 3D Arrays
        int (*a)[y][z];
        a = (int (*)[y][z])malloc(x*y*z*sizeof(int));
        a[99][199][29] = 10;
        printf("a[99][199][29]=%d\n", a[99][199][29]);
        free(a);
    }

إذا كنت تستخدم C++، فإن أبسط طريقة هي على الأرجح استخدام التحميل الزائد للمشغل للالتزام ببناء جملة المصفوفة:

    {
        class ThreeDArray {
            class InnerTwoDArray {
                int * data;
                size_t y;
                size_t z;
                public:
                InnerTwoDArray(int * data, size_t y, size_t z)
                    : data(data), y(y), z(z) {}

                public:
                int * operator [](size_t y){ return data + y*z; }
            };

            int * data;
            size_t x;
            size_t y;
            size_t z;
            public:
            ThreeDArray(size_t x, size_t y, size_t z) : x(x), y(y), z(z) {
                data = (int*)malloc(x*y*z*sizeof data);
            }

            ~ThreeDArray(){ free(data); }

            InnerTwoDArray operator [](size_t x){
                return InnerTwoDArray(data + x*y*z, y, z);
            }
        };

        ThreeDArray a(x, y, z);
        a[99][199][29] = 10;
        printf("a[99][199][29]=%d\n", a[99][199][29]);
    }

يحتوي الكود أعلاه على بعض التكلفة غير المباشرة للوصول إلى InnerTwoDArray (ولكن من المحتمل أن يتمكن المترجم الجيد من تحسينه بعيدًا) ولكنه يستخدم قطعة ذاكرة واحدة فقط للصفيف المخصص في الكومة.والذي عادة ما يكون الخيار الأكثر كفاءة.

من الواضح أنه حتى لو كان الكود أعلاه لا يزال بسيطًا ومباشرًا، فإن STL أو BOOST يقومان بذلك بشكل جيد، وبالتالي لا داعي لإعادة اختراع العجلة.ما زلت أعتقد أنه من المثير للاهتمام معرفة أنه يمكن القيام بذلك بسهولة.

Answer 4

مع المتجهات:

std::vector< std::vector< std::vector< int > > > array3d;

يمكن الوصول إلى كل عنصر باستخدام array3d[x][y][z] إذا تمت إضافة العنصر بالفعل.(على سبيل المثالعبر Push_back)

Answer 5

تجدر الإشارة إلى أنك، لجميع المقاصد والأغراض، تتعامل مع مصفوفة ثنائية الأبعاد فقط، لأن البعد الثالث (والأقل أهمية) معروف.

يعد استخدام STL أو Boost من الأساليب الجيدة جدًا إذا كنت لا تعرف مسبقًا عدد الإدخالات التي ستحصل عليها في كل بُعد من أبعاد المصفوفة، لأنها ستمنحك تخصيصًا ديناميكيًا للذاكرة، وأوصي بأي من هذه الأساليب إذا كانت مجموعة البيانات الخاصة بك ليظل ثابتًا إلى حد كبير، أو إذا كان يتلقى في الغالب إدخالات جديدة فقط وليس الكثير من عمليات الحذف.

ومع ذلك، إذا كنت تعرف شيئًا ما عن مجموعة البيانات الخاصة بك مسبقًا، مثل العدد الإجمالي للعناصر التي سيتم تخزينها تقريبًا، أو إذا كانت المصفوفات ذات كثافة سكانية منخفضة، فقد يكون من الأفضل استخدام نوع ما من وظائف التجزئة/الدلو، واستخدام مؤشرات XYZ كمفتاحك.في هذه الحالة، بافتراض عدم وجود أكثر من 8192 إدخالًا (13 بت) لكل بُعد، يمكنك التعامل مع مفتاح 40 بت (5 بايت).أو، بافتراض أن هناك دائمًا 4 إدخالات Z، يمكنك ببساطة استخدام مفتاح XY بطول 26 بت.يعد هذا أحد المفاضلات الأكثر كفاءة بين السرعة واستخدام الذاكرة والتخصيص الديناميكي.

Answer 6

هناك العديد من المزايا لاستخدام STL لإدارة ذاكرتك عبر استخدام الجديد/الحذف.يعتمد اختيار كيفية تمثيل بياناتك على الطريقة التي تخطط لاستخدامها بها.قد يكون أحد الاقتراحات عبارة عن فئة تخفي قرار التنفيذ وتوفر طرق الحصول/المجموعة ثلاثية الأبعاد لمتجه STL أحادي البعد.

إذا كنت تعتقد حقًا أنك بحاجة إلى إنشاء نوع متجه ثلاثي الأبعاد مخصص، فتحقق من Boost أولاً.

// a class that does something in 3 dimensions

class MySimpleClass
{
public:

  MySimpleClass(const size_t inWidth, const size_t inHeight, const size_t inDepth) :
   mWidth(inWidth), mHeight(inHeight), mDepth(inDepth)
   {
       mArray.resize(mWidth * mHeight * mDepth);
   }


  // inline for speed
  int Get(const size_t inX, const size_t inY, const size_t inZ) {
     return mArray[(inZ * mWidth * mHeight) + (mY * mWidth) + mX];
  }

  void Set(const size_t inX, const size_t inY, const size_t inZ, const int inVal) {
     return mArray[(inZ * mWidth * mHeight) + (mY * mWidth) + mX];
  }

  // doing something uniform with the data is easier if it's not a vector of vectors
  void DoSomething()
  {
     std::transform(mArray.begin(), mArray.end(), mArray.begin(), MyUnaryFunc);
  }

private:

  // dimensions of data
  size_t mWidth;
  size_t mHeight;
  size_t mDepth;

  // data buffer
  std::vector< int > mArray;
};

Answer 7

اقتراح بيتر جيد بالطبع، ولكن هناك شيء واحد عليك أن تضعه في الاعتبار وهو أنه في حالة بناء المصفوفات الكبيرة، قد يكون الأمر بطيئًا للغاية.في كل مرة تتغير سعة المتجه، يجب نسخ جميع البيانات حول (متجهات المتجهات).