برنامه نویسی

تخصیص دینامیک آرایه های دو بعدی در C++

معرفی

با فرض اینکه «تخصیص دینامیک آرایه‌های دوبعدی به‌طور مؤثر (و درست!)» را در زبان C خوانده‌اید، آخرین پاراگراف به این موضوع اشاره کرد:

در C++، می توانید نشانگرهای ردیف را حذف کنید و همچنان از آن استفاده کنید [][] نحو با استفاده از قالب ها و بارگذاری بیش از حد operator[]()، اما این یک داستان برای زمان دیگری است.

آن زمان فرا رسیده است.

یک کلاس ماتریس دو بعدی کوچک

در C++ می توان یک کلاس ماتریس دو بعدی کوچک نوشت. یک پیاده سازی بدون استخوان عبارت است از:

template<typename T>
class matrix2d {
public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef value_type const* const_pointer;
    typedef value_type& reference;
    typedef value_type const& const_reference;

    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    matrix2d( size_type idim, size_type jdim ) :
        _dim{ idim, jdim },
        _elem{ alloc( _dim ) }
    {
    }

    ~matrix2d() noexcept {
        delete[] _elem;
    }

    pointer operator[]( size_type row ) noexcept {
        return &_elem[ row * _dim.first ];
    }

    const_pointer operator[]( size_type row ) const noexcept {
        return &_elem[ row * _dim.first ];
    }

private:
    std::pair<size_type,size_type> _dim;
    pointer _elem;

    static pointer alloc( std::pair<size_type,size_type> const &dim ) {
        return new value_type[ dim.first * dim.second ];
    }
};
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

مجموعه ای از typedefs در ابتدا صفحه جوش هستند تا کلاس به خوبی با STL بازی کند.

برخلاف پیاده سازی C، کلاس ماتریس 2 بعدی اندازه ردیف خود را به خاطر می آورد – به این معنی که یک بار بیش از حد operator[]() می توانید از آن برای محاسبه افست استفاده کنید ith ردیف:

    pointer operator[]( size_type row ) noexcept {
        return &_elem[ row * _dim.first ];
    }
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

از این رو در کدهایی مانند:

matrix2d<int> m2d{ 3, 3 };
m2d[i][j] = 0;
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

را [i] اضافه بار را فرا می خواند operator[]() که یک اشاره گر را به شروع باز می گرداند ith ردیف در عناصر به هم پیوسته به ترتیب ردیف اصلی که بیش از حد بارگذاری نشده است [j] به jth عنصر (از ith ردیف “زیر آرایه”). بر خلاف پیاده سازی C، هیچ اشاره گر ردیف اضافی مورد نیاز نیست، زیرا آنها در زمان اجرا محاسبه می شوند.

دسترسی به عنصر

اخطار این است که هر عنصر ماتریس از طریق دسترسی دارد [i][j] اکنون به ضربی نیاز دارد که در اجرای C مورد نیاز نبود. مانند بسیاری از چیزهای دیگر در علوم کامپیوتر، این یک معامله است. با این حال، این را می توان از چند طریق کاهش داد. به جای نوشتن:

for ( size_t i = 0; i < 3; ++i ) {
    for ( size_t j = 0; j < 3; ++i ) {
        // ... m2d[i][j] ...
    }
}
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

این را می توان نوشت:

for ( size_t i = 0; i < 3; ++i ) {
    auto row = m2d[i];
    for ( size_t j = 0; j < 3; ++i ) {
        // ... row[j] ...
    }
}
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

به طوری که تنها یک ضرب در هر ردیف به جای هر عنصر انجام می شود.

راه دیگر برای کاهش این مشکل، افزودن iterator boilerplate به کلاس است:

class matrix2d {
public:
    // ...
    typedef pointer iterator;
    typedef const_pointer const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> reverse_const_iterator;
    // ...

    size_type size() const noexcept {
        return _dim.first * _dim.second;
    }

    iterator begin() noexcept {
        return _elem;
    }

    const_iterator cbegin() const noexcept {
        return _elem;
    }

    const_iterator begin() const noexcept {
        return cbegin();
    }

    reverse_iterator rbegin() noexcept {
        return reverse_iterator{ end() };
    }

    const_reverse_iterator crbegin() const noexcept {
        return const_reverse_iterator{ cend() };
    }

    const_reverse_iterator rbegin() const noexcept {
        return crbegin();
    }

    iterator end() noexcept {
        return _elem + size();
    }

    const_iterator cend() const noexcept {
        return _elem + size();
    }

    const_iterator end() const noexcept {
        return cend();
    }

    reverse_iterator rend() noexcept {
        return reverse_iterator{ begin() };
    }

    const_reverse_iterator crend() const noexcept {
        return const_reverse_iterator{ cbegin() };
    }

    const_reverse_iterator rend() const noexcept {
        return crend();
    }

    // ...
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اکنون می توانید انجام دهید:

for ( auto elem : m2d ) {
    // ... elem ...
}
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

برای تکرار بر روی همه عناصر بدون ضرب انجام شود.

کپی، انتقال و تعیین تکلیف

ساختن matrix2d درست است، به اضافه کردن یک سازنده کپی نیاز دارد:

    matrix2d( matrix2d const &from ) :
        _dim{ from._dim },
        _elem{ alloc( _dim ) }
    {
        copy_elem( from );
    }

    // ...
private:
    // ...

    static pointer alloc( std::pair<size_type,size_type> const &dim ) {
        return new value_type[ dim.first * dim.second ];
    }

    void copy_elem( matrix2d const &from ) noexcept {
        for ( size_type i = 0; i < from.size(); ++i )
            _elem[i] = from._elem[i];
    }
};
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

یک سازنده حرکت کارایی حرکت را بهبود می بخشد:

    matrix2d( matrix2d &&from ) noexcept :
        _dim{ from._dim },
        _elem{ std::exchange( from._elem, nullptr ) }
    {
    }
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

توجه داشته باشید که from._dim لازم نیست صفر شود

و تکلیف را کپی و جابجا کنید:

    matrix2d& operator=( matrix2d const &from ) {
        if ( &from != this ) {
            delete[] _elem;
            _dim = from._dim;
            alloc( _dim );
            copy_elem( from );
        }
        return *this;
    }

    matrix2d& operator=( matrix2d &&from ) noexcept {
        delete[] _elem;
        _dim = from._dim;
        _elem = std::exchange( from._elem, nullptr );
        return *this;
    }
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

پایان لمس

بعلاوه size() که تعداد کل عناصر را برمی گرداند، dim() ممکن است برای بدست آوردن هر بعد مفید باشد:

    std::pair<size_type,size_type> dim() const noexcept {
        return _dim;
    }
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

و بالاخره، swap()، هر دو به عنوان یک تابع عضو:

    void swap( matrix2d &other ) {
        _dim = std::exchange( other._dim, _dim );
        _elem = std::exchange( other._elem, _elem );
    }
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

و یک تابع جهانی بنابراین std::swap() آثار:

namespace std {
    template<typename T>
    inline void swap( matrix2d<T> &a, matrix2d<T> &b ) {
        a.swap( b );
    }
}
وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

نتیجه

قدرت کلاس‌ها در C++ با حذف نشانگرهای ردیف مورد نیاز در C، اجرای کارآمدتر حافظه ماتریس دوبعدی تخصیص یافته پویا را امکان‌پذیر می‌سازد – اما با توجه به نیاز به ضرب برای دسترسی تصادفی عنصر.

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا