Nội dung bài viết
Đăng ký học lập trình C++
Tại STDIO bạn được dạy nền tảng lập trình tốt nhất.
Đăng ký học
Trong khuôn khổ bài viết này tôi xin trình bày về một vấn đề cơ bản đó là cấp phát mảng động 2 chiều (hay nhiều chiều). Thật ra là cấp phát vùng nhớ để sử dụng như mảng 2 chiều, tạm gọi là mảng động 2 chiều.

Giới thiệu

Nội dung chính của bài viết gồm 3 phần. Phần thứ nhất đề cập tới vấn đề cấp phát 1 vùng nhớ để dùng như một mảng 2 chiều. Phần thứ hai đề cập tới vấn đề dùng con trỏ 2 cấp để dùng như một mảng 2 chiều. Phần thứ 3 tôi dành cho việc so sánh và đánh giá 2 phương pháp này.

Tiền đề bài viết

Qua thảo luận với anh Kevin La về vấn đề này tại group STDIO Training, tôi được anh Kevin La khuyến khích viết một bài chia sẻ kiến thức, kinh nghiệm mà tôi có được. Tuy tôi học văn không tốt, viết lách cũng không giỏi, nhưng cũng xin đóng góp chút ít cho STDIO, chia sẻ những hiểu biết của mình.

Đối tượng hướng đến

  • Bài viết hướng đến đối tượng lập trình viên đang gặp vấn đề về phân mảnh bộ nhớ trong lập trình C++, muốn tìm giải pháp để tối ưu hoá hệ thống.
  • Các đối tượng bạn đọc của bài viết này cần biết về con trỏ và cấp phát động.
  • Các đối tượng khác có thể xem bài viết ở mức độ tham khảo.

Biến đổi mảng một chiều thành mảng nhiều chiều

Khi bạn cấp phát động mảng 2 chiều có m dòng và n cột, bạn hình dung giống như bạn cấp phát một mảng động có m*n phần tử và mảng này được chia làm m nhóm bằng nhau. Khi biết được vị trí của một phần tử, ta dễ dàng tính được phần tử đó thuộc nhóm nào với vị trí của nó trong nhóm, điều ngược lại cũng đúng.

Với phần tử ở vị trí i, thì nó thuộc nhóm thứ i / n, và vị trí tương đối của nó trong nhóm là i % n (với n là kích thước của mỗi nhóm). Với phần tử thuộc nhóm thứ g và vị trí tương đối của nó trong nhóm thứ g là h thì vị trí của nó ở trong mảng là g*n + h.

Ví dụ: Ta có khai báo mảng 2 chiều với kích thước 2*3 như sau:

a[0][0] a[0][1] a[0][2]
a[1][0] a[1][1] a[1][2]

Mảng trên hoàn toàn có thể đưa về dạng một chiều và ta dễ dàng xác định các phần tử trong mảng như sau:

a[0] a[1] a[2] a[0/3][0%3] a[1/3][1%3] a[2/3][2%3]
a[3] a[4] a[5] a[3/3][3%3] a[4/3][4%3] a[4/3][4%3]

Hoặc chúng ta cũng có thể xác định vị trí của nó dựa vào chỉ số nhóm và vị trí tương đối của nó trong nhóm.

a[0*3+0] a[0*3+1] a[0*3+2]
a[1*3+0] a[1*3+1] a[1*3+2]

Phương pháp này cũng có thể được áp dụng cho mảng tĩnh.

Mảng nhiều chiều

Dùng con trỏ 2 cấp hay còn hiểu là con trỏ của con trỏ. Khi đó, bạn sẽ có một con trỏ trỏ đến một vùng nhớ, vùng nhớ này chỉ lưu các con trỏ, các con trỏ trong vùng nhớ này trỏ tới các vùng nhớ khác (những vùng nhớ chứa dữ liệu).

Ví dụ: Với hình mô tả bên dưới ta có mảng động với kích thước 3*4:

con_tro_toi_con_tro

So sánh

PHƯƠNG PHÁP 1 PHƯƠNG PHÁP 2
Tiết kiệm bộ nhớ hơn, chỉ dùng một con trỏ. Dùng nhiều con trỏ hơn. Với mảng động 2 chiều - n hàng thì phải tốn n + 1 con trỏ.
Quản lí bộ nhớ đơn giản hơn. Chỉ một vùng nhớ, đăng kí cấp phát 1 lần, giải phóng một lần. Nhiều vùng nhớ. Đăng kí cấp phát nhiều lần, giải phóng nhiều lần.
Nếu bộ nhớ phân mảnh quá nhiều thì sẽ dễ bị không tìm được vùng nhớ có kích thước thích hợp. Dữ liệu được chia nhỏ và lưu trữ ở nhiều nơi. Tuy nhiên, đây cũng là một nguyên nhân dẫn đến phân mảnh bộ nhớ. Nếu có nhu cầu sử dụng bộ nhớ trong khoảng thời gian dài thì cũng nên tránh dùng cách này.
Không linh động trong việc các nhóm phần tử có kích thước khác nhau. Linh động hơn trong việc cấp phát bộ nhớ và quản lí các nhóm phần tử có độ dài khác nhau.

Về vấn đề các nhóm phần tử có kích thước khác nhau, tôi không trình bày ở 2 mục đầu. Tuy nhiên việc cấp phát mảng động với các nhóm phần tử có kích thước khác nhau có thể tổ chức bằng cách dùng một mảng khác để lưu kích thước của các nhóm hoặc có thể tổ chức lưu các kích thước này cùng với dữ liệu.

Các bài liên quan

THẢO LUẬN