تخصیص دینامیک آرایه های دو بعدی در 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 ];
}
};
مجموعه ای از
typedef
s در ابتدا صفحه جوش هستند تا کلاس به خوبی با 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، اجرای کارآمدتر حافظه ماتریس دوبعدی تخصیص یافته پویا را امکانپذیر میسازد – اما با توجه به نیاز به ضرب برای دسترسی تصادفی عنصر.