CodeCT | Cấp phát động

Vượt qua những giới hạn của ngôn ngữ lập trình và làm cái gì đó thật lớn với kĩ thuật cấp phát động sử dụng Heap – vùng nhớ động và bộ thư viện STL.

Chuẩn hoá chuỗi

Bài tập về nhà của bài tập trước: sử dụng string, viết chương trình chuẩn hoá chuỗi được nhập từ bàn phím.

Định nghĩa chuỗi đã chuẩn hoá: không dư dấu cách, các chữ cái đầu câu phải viết hoa. Bạn có thể tham khảo bên dưới. Để hiểu rõ hơn một số hàm tôi đã sử dụng, truy cậphttp://www.cplusplus.com/reference/string/string/.

#include <iostream>

#include <string> // thư viện string của C++

using namespace std;

char* g_spec = "!?.,:";

#define CHAR_UPPERCASE 3 // kí tự < 3 cần in hoa

/* Hàm kiểm tra xem kí tự a có phải kí tự đặc biệt không

Trả về thứ tự trong g_spec

int isSpecial(char a){

for (unsigned int i = 0; i < strlen(g_spec); i++)

if (g_spec[i] == a) return i;

return -1;

}

int main(){

string s;

cout << "Nhap chuoi ban dau: "; getline(cin, s);

int i = s.length() - 2;

int j;

while (i > 0){ // duyệt từ cuối chuỗi

/* GHI CHÚ: để đảm bảo an toàn, chúng ta sẽ duyệt từ cuối chuỗi

và chỉ xoá các kí tự có chỉ số lớn hơn phần tử hiện tại.

Tức là chỉ xoá những phần tử >= i + 1

Bạn có thể thử bằng vòng lặp for và dự đoán vấn đề sẽ xảy ra khi

duyệt và xoá theo chiều xuôi.

j = isSpecial(s[i]);

if (j >= 0){ // nếu là kí tự đặc biệt

// thêm khoảng trắng nếu không có

if (s[i + 1] != ' ') s.insert(s.begin() + i + 1, ' ');

// kiểm tra xem có cần in hoa hay không?

if (j < CHAR_UPPERCASE){

// đảm bảo không phải cuối chuỗi

if (i < (int)s.length() - 3)

// biến kí tự đằng sau thành in hoa

s[i + 2] = toupper(s[i + 2]);

}

if (s[i] == ' '){

if (s[i + 1] == ' '){ // xoá các khoảng trắng thừa

s.erase(s.begin() + i);

}

i--;

}

// Chúng ta còn khoảng trắng ở đầu và cuối câu.

while (s[0] == ' '){ // đầu

s.erase(s.begin());

}

i = s.length() - 1;

while (s[i] == ' '){ // cuối

s.erase(s.begin() + i);

i--;

}

s[0] = toupper(s[0]); // biến kí tự đầu tiên thành hoa

cout << s;

system("pause");

return 0;

}

Thế thôi, không giải thích gì thêm nhé (tôi chú thích khá đầy đủ rồi. Nếu vẫn chưa hiểu, cứ comment bên dưới, tôi sẽ giải đáp). Giờ vào vấn đề chính, khi khai báo biến, chúng ta khai báo chúng trong stack, đúng không? Chuyện gì xảy ra nếu stack đầy, Overflow. Điều đó có nghĩa số lượng biến bạn khai báo có giới hạn, không vui tí nào! Để tận dụng hết thanh RAM của bạn, chúng ta phải nghiên cứu tới Heap, bài hôm nay đây.

Heap

RAM máy bạn bao nhiêu? Của tôi là 6GB, khá là bự! Thế mà một chương trình, khai báo 9MB biến thôi mà lại bị lỗi overflow. Bộ nhớ của tôi rất nhiều mà. Đúng, tài nguyên của tôi rất phong phú, nhưng chưa biết cách sử dụng nó.

Tôi từng nói rằng, chương trình khi nạp lên bộ nhớ thường sẽ có 4 phần. Phần cuối cùng, chưa bao giờ bạn đụng tới, đó là Heap, vùng nhớ được quản lý bởi hệ điều hành. Nó lớn rất nhiều so với stack. Nó có thể to đến mức chiếm hết toàn bộ RAM của máy bạn (không bao giờ!). Vậy làm thế nào để sử dụng vùng nhớ đó, chúng ta hãy cùng tìm hiểu.

Sử dụng vùng nhớ Heap

Do hệ điều hành quản lý vùng nhớ heap, nên bạn sẽ gặp khó khăn nếu không biết cách ‘bảo’ hệ điều hành đưa (cấp phát) vùng nhớ đó cho bạn.

Chú ý: bạn cần có kiến thức tốt về con trỏ trước khi tiếp tục.

Để yêu cầu hệ điều hành cung cấp bộ nhớ cho bạn, hãy sử dụng:

C: malloc (hàm, yêu cầu có thư viện stdlib.h)

C++: new (toán tử)

Chúng ta hãy nghiên cứu dạng cơ bản nhất trước, đó là hàm malloc của C. Cấu trúc tham số của hàm như sau:

1	void * malloc(size_t _Size);

Trong đó, size_t là một kiểu dữ liệu do bộ thư viện C định nghĩa, bạn không cần phải quan tâm tới nó. Chỉ cần hiểu nó tương tự như biến int là được (nhưng rất lơn so với int). Hàm malloc sẽ yêu cầu hệ điều hành cung cấp bộ nhớ cho chương trình của chúng ta. Số lượng dựa vào giá trị của tham số _size, tính theo đơn vị byte. Kết quả trả về là một con trỏ, trỏ tới vùng nhớ đó. Kiểu trả về là void*, cũng đúng vì hàm này đâu biết bạn sẽ sử dụng chúng để làm gì. Nếu kết quả trả về là con trỏ NULL ( = 0), nghĩa là hệ thống không thể tiếp tục cung cấp bộ nhớ cho bạn nữa, có thể là RAM đã hết rồi! Nhưng nó rất ít khi xảy ra. Sau khi vùng nhớ được cấp phát, bạn muốn làm gì nó thì làm. Hệ điều hành đã giao quyền cho bạn rồi.

Tôi sẽ sử dụng nó như là một mảng số nguyên:

#include <stdio.h>

#include <stdlib.h>

int main(){

int *pi, i;

void *pointer;

// chúng ta yêu cầu hệ thống cung cấp 10 phần tử liên tiếp nhau

// mỗi phần tử có kích thước 4 byte (int)

// thực tế, tôi yêu cầu hệ thống cấp 40 byte liên tiếp

// do đó, nó có thể trở thành mảng

pointer = malloc(sizeof(int) * 10);

// do kiểu trả về là void*

// nên chúng ta cần ép kiểu sang int* cho dễ sử dụng

pi = (int*)pointer;

// bắt đầu gán dữ liệu cho vùng nhớ nào

for (i = 0; i < 10; i++)

pi[i] = i; // có thể thao tác với con trỏ y như mảng

// tránh sử dụng lại cách mà tôi đã gán

// thay vào đó, tôi cho con trỏ pi tịnh tiến 10 lần

// sau đó in kết quả ra

for (i = 0; i < 10; i++){

printf("%d ", *pi);

pi++;

}

// huỷ vùng nhớ

free(pointer);

return 0;

}

Quan sát đoạn mã trên và đọc các chú thích, chắc hẳn bạn cũng hiểu ra nhiều điều. Chúng ta cần một con trỏ để lưu vị trí vùng nhớ (nơi bắt đầu) mà hệ thống đã cấp phát. Sau đó, vùng nhớ hoàn toàn thuộc quản lý của bạn, bạn ép kiểu, gán giá trị gì thì tuỳ bạn, miễn là không sử dụng vượt quá bộ nhớ đã được cấp phát (nếu may mắn nó sẽ báo lỗi run-time, mà nhiều lúc thì không đâu). Như trên, tôi sử dụng 40 byte bộ nhớ liên tiếp để làm mảng số nguyên có 10 phần tử.

Lỗi truy cập vùng nhớ sai (thao tác đọc và ghi) thường có thông báo lỗi: Access violation reading/writing location 0xxxxxxx (con số này khác 0) hoặc Cann’t write to protected memory,…

Chú ý trong hàm malloc, tôi sử dụng sizeof(int) thay vì số 4 để bạn có thể dễ hiểu, đồng thời giúp cho những bạn có cấu hình máy khác tôi có thể chạy đúng (kích thước của int có thể khác nhau nhưng rất hiếm gặp). Đó cũng là một quy tắc chung khi cấp phát, cấp phát cho chính xác.

Thêm một ví dụ nữa, tôi sẽ sử dụng bộ nhớ như một mảng struct:

#include <stdio.h>

#include <stdlib.h>

struct Mark{

int tb; // trung bình

float math; // toán

float biology; // sinh

};

int main(){

int i;

void *pointer;

Mark *ps;

pointer = malloc(sizeof(Mark) * 10);

ps = (Mark*)pointer;

// bắt đầu gán dữ liệu cho vùng nhớ

for (i = 0; i < 10; i++){

ps[i].tb = i;

ps[i].biology = (float)i;

ps[i].math = 10 - (float)i;

}

for (i = 0; i < 10; i++){

printf("%d %f %f\n", ps->tb, ps->math, ps->biology);

ps++;

}

free(pointer);

return 0;

}

Với hai ví dụ này, tôi hi vọng bạn đã hiểu cách cấp phát bộ nhớ trong vùng nhớ Heap bằng ngôn ngữ C. Bạn đã thoả mãn chưa? Chúng ta có 1 vấn đề, liệu rằng đây có đúng là vùng nhớ vô hạn như quảng cáo? Chúng ta cùng kiểm tra, với bộ test 1triệu biến double ngày hôm qua:

#include <stdio.h>

#include <stdlib.h>

int main(){

double *pd;

// để tiết kiệm thao tác, bạn có thể rút ngắn quá trình lại như thế này

pd = (double*)malloc(sizeof(double) * 1000000);

free(pd);

return 0;

}

Hãy ấn F5 và kiểm tra lại. Không hề gặp lỗi stack overflow, nghĩa là bạn đã biết cách sử dụng vùng nhớ Heap rồi. Cheer!

Chưa xong đâu, bây giờ mới tới chuyện nghiêm túc. Bạn yêu cầu hệ thống cấp phát bộ nhớ cho bạn, sau đó nó hoàn toàn thuộc quản lý của bạn, trình biên dịch không bao giờ đụng tới. Có nghĩa là, vòng đời của vùng nhớ này sẽ do bạn quyết định. Khi nào bạn yêu cầu tạo thì nó tạo, khi nào bạn yêu cầu huỷ thì nó huỷ. Nó không bao giờ bị huỷ khi kết thúc khối lệnh, hoặc kết thúc chương trình. Bạn cần nhớ rõ. Do đó, một mặt lợi thấy rõ là giá trị không bị mất đi khi kết thúc hàm. Hãy xem qua ví dụ:

#include <stdio.h>

#include <stdlib.h>

int* Create(){

int* pi;

// tôi sẽ tạo một vùng nhớ ở đây

pi = (int*)malloc(sizeof(int)); // 1 biến thôi

*pi = 10; // gán giá trị 10 cho nó

return pi; // rồi trả về hàm main

}

int main(){

int *i = Create();

printf("%d", *i);

// kết thúc vòng đời

free(i);

return 0;

}

Tôi có một hàm mang tên Create, nó sẽ yêu cầu hệ thống cấp phát 4 byte bộ nhớ để lưu trữ biến số nguyên. Sau khi tạo xong, chúng ta gán giá trị 10 cho nó và trả về địa chỉ chúng trong bộ nhớ. Về hàm main, biến đó trong Heap vẫn còn, bạn có thể thực hiện truy xuất mà biến đó không bị mất đi. Nhưng trường hợp này là không được:

#include <stdio.h>

#include <stdlib.h>

void Dummy(){

int i = 5;

}

int* Create(){

int i; // khởi tạo i trong stack

i = 10; // gán giá trị 10 cho nó

return &i; // rồi trả về hàm main

}

int main(){

int *i = Create();

Dummy();

printf("%d", *i);

return 0;

}

Bạn có đoán ra được giá trị khi in ra của i là gì không? Ở đây chúng ta có 2 vấn đề cần bàn: nếu bỏ hàm Dummy đi thì giá trị của i là bao nhiêu, Tác dụng của hàm Dummy là gì, tại sao khi in ra, giá trị của i lại là số đó.

Khi chương trình chạy, bắt đầu hàm main, bạn có thể liên tưởng stack như bên dưới:

Trong stack chỉ có hàm main với biến con trỏ i. Sau đó, main gọi hàm Create. Hàm create sẽ được đặt bên trên main, biểu thị rằng tới lượt nó chạy, nơi gọi nó là hàm main, sau khi kết thúc, hàm main sẽ tiếp tục chạy.

Khu vực nhớ dành cho hàm Create bao gồm cả biến số nguyên int của nó, khai báo tại vị trí như trên hình. Tôi gán giá trị 10 cho nó, nên ô nhớ đó lưu trữ giá trị 10. Hàm Create kết thúc, stack hạ đỉnh của nó xuống, chỉ tới hàm main. Chú ý rằng, hệ thống chỉ đẩy stack xuống, đánh dấu main là đỉnh của nó chứ không đụng tới dữ liệu trong bộ nhớ. Giá trị trả về là địa chỉ của ô nhớ mà Create đã sử dụng hiện tại đang có giá trị 10. Địa chỉ đó được gán cho con trỏ i.

Tiếp theo, main gọi hàm dummy, tương tự như Create, hàm dummy sẽ được đặt trên main, trùng với vị trí mà Create đã để lại trước đó. Đồng thời nó cũng có 1 biến cục bộ là i. Nên biến i của hàm Dummy sẽ ở vị trí biến i cũ mà hàm Create đã sử dụng.

Hàm dummy gán giá trị 5 cho i rồi kết thúc, nó gán cho ô nhớ mà Create đã sử dụng trước đó giá trị 5. Có nghĩa là giá trị mà con trỏ i của hàm main đang trỏ tới bị gán giá trị 5. Stack hạ xuống, đánh dấu main là đỉnh và tiếp tục thực hiện. Lúc này, main truy cập vào ô nhớ i trỏ tới, hiển nhiên vị trí đó đang lưu giá trị 5. Thế là chúng in ra con số 5 trên màn hình. Kết thúc main, stack rỗng, kết thúc chương trình.

Như vậy, hàm dummy đã thay đổi giá trị mà con trỏ i trỏ tới, khiến cho việc in giá trị của i ra bị thay đổi. Đây là một trường hợp rất đơn giản cho bạn dễ hiểu, khi chỉ gọi hàm Dummy có 1 lần. Nhưng khi viết dự án, bạn sẽ phải gọi rất nhiều hàm, nên tôi đảm bảo bạn sẽ không thể đoán trước được kết quả như ví dụ này đâu.

Các biến cục bộ, vòng đời của nó kết thúc khi hàm kết thúc, ô nhớ của nó sẽ được dành cho biến khác. Nên, bạn không bao giờ được phép trả về địa chỉ của biến cục bộ như trên (ah mà thích thí cứ làm cũng không sao), nó sẽ làm chương trình bạn gặp vấn đề.

Chuyện tiếp theo thì đơn giản rồi, bạn bỏ lời gọi hàm dummy trong hàm main đi, kết quả in ra sẽ là giá trị 10.

Vòng đời của một vùng nhớ Heap bắt đầu khi bạn yêu cầu hệ thống cấp phát. Nó kết thúc khi bị thu hồi, đúng không. Đương nhiên là hệ thống sẽ không bao giờ thu hồi trừ khi chương trình của bạn kết thúc. Nhưng đừng bao giờ tin tưởng nó, đa số là nó biết, chỉ là đa số thôi. Tốt nhất, sau khi thực hiện xong tất cả công việc đối với vùng nhớ heap, bạn cần tự tay huỷ nó. Đó là trách nhiệm của bạn. Nếu yêu thích con trỏ, bạn cần nhớ điều này. Thử tưởng tượng rằng bạn viết một chương trình, chạy ngày đêm, mà không hề huỷ vùng nhớ sau khi sử dụng, bạn đoán điều gì sẽ xảy ra! Chỉ cần 1 hàm liên tục yêu cầu hệ thống cấp phát, dần dần cho dù RAM của bạn có lớn đến bao nhiêu, nó cũng sẽ không đủ. Vùng nhớ hệ thống đã cấp phát rồi, thì không thể cấp phát tiếp trừ khi bạn giải phóng nó.

Để huỷ vùng nhớ, sử dụng hàm free như tôi đã làm. Tham số truyền vào là địa chỉ bắt đầu của vùng nhớ đã cấp phát.

free(i);

Nhớ free nó nhé.

C++

Tất cả những gì tôi vừa nói ở trên, đều áp dụng được trong C++. Tuy nhiên, C++ đã tối ưu hoá quá trình này, giúp bạn dễ dàng thực hiện hơn bằng từ khoá new và delete.

#include <iostream>

using namespace std;

int main(){

int *i = new int; // cấp phát 1 biến int

delete i; // huỷ biến i đó

i = new int[10]; // cấp phát 10 biến i liên tiếp

delete[] i; // huỷ 10 biến i đó

return 0;

}

Khi sử dụng cú pháp của C++, bạn gặp một số điểm lợi sau

Độ dài đoạn mã ngắn hơn do không dùng hàm, chúng ta dùng toán tử.
Kiểu trả về đã được tự động ép kiểu, không phải tốn công như malloc.
Muốn cấp vùng nhớ cho biến nào cũng được, không phải chỉ định kích thước kiểu dữ liệu.
Nếu muốn cấp một dãy biến liên tiếp, sử dụng cặp dấu [] như mảng vậy

Cú pháp C++ chỉ có 1 điểm yếu. Khi bạn cấp phát bằng từ khoá new, thì bạn cần huỷ với từ khoá delete. Khi bạn cấp phát mảng (bằng từ khoá new int[5] chẳng hạn), thì phải huỷ bằng từ khoá delete[].

Nhắc lại, tất cả những nguyên lý tôi đã trình bày đều giống hệt bên ngôn ngữ C.

Cấp phát động

Giả sử chưa có khái niệm cấp phát động, tôi yêu cầu bạn viết chương trình nhập một mảng từ bàn phím, sau đó in nó ra màn hình. Cần lưu ý, kích thước mảng là bất kì, bạn sẽ làm như thế nào?

Quay lại mảng, trước giờ chúng ta vẫn khai báo chúng trong stack. Tôi có một cách để làm kích thước mảng linh động được, bạn hãy xem:

1	int a[] = { 1, 2, 3, 4, 5, 6 };

Khi muốn tăng kích thước của mảng lên, tôi chỉ cần thêm vào vế phải, trình biên dịch sẽ giúp tính toán số lượng phần tử. OK, đó là suy nghĩ tốt, nhưng, số lượng phần tử là cố định, theo như yêu cầu, số lượng phần tử sẽ do người dùng nhập vào qua hàm cin. Nên cách này phá sản.

Lại có một phương án khác khả thi hơn: tôi sẽ khai báo một mảng có kích thước thật lớn, sau đó dùng một biến int làm biến đếm, lưu trữ số lượng phần tử.

int count;

int a[1000]; // khai báo thật lớn

// sau đó yêu cầu người dùng nhập số lượng

cout << "Hay nhap so phan tu: "; cin >> count;

Cách này rất phổ biến, thường được sử dụng khi bạn muốn thiết kế chương trình cách nhanh-gọn-lẹ. Tôi cũng đã từng sử dụng phương pháp này rất nhiều. Bây giờ, bạn cũng cần phải thử. Bên trên là một đoạn chương trình, bạn hãy viết tiếp để thực hiện yêu cầu tôi nêu ở trên: nhập count phần tử, sau đó in ra ngoài.

Làm đi nhé! Không khó mà.

Với sự trợ giúp của vòng lặp for, mọi chuyện đã êm đẹp.

#include <iostream>

using namespace std;

int main(){

int count;

int a[1000]; // khai báo thật lớn

// sau đó yêu cầu người dùng nhập số lượng

cout << "Hay nhap so phan tu: "; cin >> count;

for (int i = 0; i < count; i++){

cout << "Nhap phan tu thu " << i + 1 << ": ";

cin >> a[i];

}

cout << "Mang da nhap: ";

for (int i = 0; i < count; i++)

cout << a[i] << " ";

}

return 0;

}

Bây giờ tôi sẽ phân tích một số vấn đề với chương trình này. Thật sự viết nó rất nhanh, dễ hiểu, thuận lợi. Mặt khác, nếu người dùng nhập giá trị trên 1000 (chẳng ai rảnh đâu) bạn sẽ làm gì? Một là để đó cho chương trình crash (gặp lỗi), hai là thông báo tới người dùng rằng: chúng tôi không thể phục vụ vì con số đó quá lớn !!! Cả hai cách đều khiến chúng ta bất lợi. Điểm bất lợi thứ hai cần bàn tới, đó là sự lãng phí bộ nhớ (đừng bảo rằng bạn có nhiều RAM). Khi người dùng nhập số lượng 5, có nghĩa 1000 – 5 ô nhớ còn lại hoàn toàn không sử dụng tới. Quá lãng phí.

Với khả năng của cấp phát động, bạn sẽ hoàn toàn thoát khỏi các vấn đề đó. Bạn hãy làm như tôi hướng dẫn:

Khai báo biến a dạng con trỏ int, khai báo biến count.
Yêu cầu người dùng nhập giá trị vào biến count.
Sử dụng giá trị biến count, yêu cầu hệ thống cung cấp đủ lượng bộ nhớ đó.
Coi biến a như là một mảng, thao tác bình thường.
Kết thúc chương trình, thông báo hệ thống rằng chúng ta muốn huỷ vùng nhớ vừa được cấp phát.

OK, viết theo hướng dẫn của tôi đi, sau đó tham khảo bên dưới.

#include <iostream>

using namespace std;

int main(){

int count;

int *a;

// yêu cầu người dùng nhập số lượng

cout << "Hay nhap so phan tu: "; cin >> count;

// sau đó, chúng ta yêu cầu hệ thống cấp phát bộ nhớ

a = new int[count]; // cấp mảng số nguyên có count phần tử

// bây giờ chúng ta khai thác nó

for (int i = 0; i < count; i++){

cout << "Nhap phan tu thu " << i + 1 << ": ";

cin >> a[i];

}

cout << "Mang da nhap: ";

for (int i = 0; i < count; i++)

cout << a[i] << " ";

// sau khi sử dụng, huỷ nó

delete[] a; // chúng ta cấp phát mảng cho a, nên cần dùng delete[]

return 0;

}

Với struct, bạn cũng có thể làm thao tác tương tự. Chỉ cần thay kiểu dữ liệu của biến con trỏ a, thay đổi các thao tác một chút, là bạn đã hoàn thành.

Ngoài lề: trong C, để huỷ vùng nhớ, chúng a chỉ cần dùng 1 hàm free là xong. Thế nhưng C++ lại có tới hai hàm huỷ là delete và delete[], một cho biến thường, một cho mảng. C++ phát triển hơn C, tại sao lại làm việc huỷ vùng nhớ trở nên rắc rối như thế? Chúng ta cùng phân tích. Trước tiên, tôi sẽ phá luật, khai báo biến a không phải mảng, sau đó dùng hàm huỷ delete[]:

#include <iostream>

using namespace std;

int main(){

int *a = new int; // chỉ một

delete[] a;

return 0;

}

Run! Không có chuyện gì xảy ra. Oh, hãy đổi lại:

#include <iostream>

using namespace std;

int main(){

int *a = new int[1000]; // 1 ngàn

delete a;

return 0;

}

Cũng chẳng có chuyện gì xảy ra hết. Vậy là muốn dùng cái nào cũng được hết. Đúng, nó không có lỗi, nhưng chỉ vì chưa tới lúc của nó. Khi lập trình cao hơn, ví dụ đầu tiên sẽ báo lỗi, còn ví dụ thứ hai sẽ không bao giờ. Chúng ta cùng đi vào hai hàm huỷ (đúng ra phải nói đó là từ khoá). Hàm huỷ thứ nhất, delete chỉ huỷ một vùng nhớ (một biến), không bao giờ huỷ mảng. Do đó, nếu bạn truyền cho nó địa chỉ một mảng, nó chỉ xoá phần tử đầu tiên và giữ lại toàn bộ những phần tử phía sau. Oh, nhưng bạn lại tưởng nó đã huỷ hết, bạn huỷ luôn con trỏ trỏ tới địa chỉ đó, khiến vùng nhớ không còn nằm trong kiểm soát của bạn nữa (có còn biết nó ở đâu nữa đâu). Đó gọi là lãng phí bộ nhớ. Trong khi ấy, hàm delete[] không chỉ xoá phần tử đầu tiên, nó còn xoá hết các phần tử đằng sau cho đến khi hết thì thôi (làm sao nó biết đã hết? Tôi cũng chịu). Lúc này bộ nhớ mới được giải phóng hoàn hảo. Nếu bạn sử dụng hàm delete[] để xoá 1 ô nhớ, ‘có thể’ bạn sẽ gặp lỗi run-time thông báo rằng ‘bộ phận kiểm tra tính toàn vẹn’ không thành công (chẳng hạn).

Một lỗi nữa bạn cũng cần chú ý, bạn chỉ được huỷ vùng nhớ 1 lần, không được huỷ 2 lần. Vì lần huỷ thứ hai, hệ thống kiểm tra vùng nhớ đó -> nó không thuộc quản lý của bạn -> lỗi:

#include <iostream>

using namespace std;

int main(){

int *a = new int; // 1 ngàn

delete a;

delete a; // delete lần 2

return 0;

}

Chắc chắn sẽ báo lỗi.

Nãy giờ tôi chỉ nói về mảng một chiều, thật thiếu công bằng khi bỏ lơ mảng hai chiều. Chúng ta cùng làm quen với chúng.

Ở các bài trước, tôi có nói về sự khác nhau giữa mảng hai chiều và con trỏ hai chiều. Mảng hai chiều cấu tạo từ mảng một chiều. Nhưng con trỏ hai chiều nó sẽ tạo nên mảng hai chiều từ các vùng nhớ rời rạc.

Cùng một vấn đề với mảng một chiều, tôi yêu cầu bạn tạo ra mảng hai chiều với kích thước không giới hạn. Chúng ta cùng quay lại sơ đồ:

Tôi mong muốn có kết quả như trên. Bạn cần khai báo một biến con trỏ cấp 2 có tên a. Con trỏ này là một mảng của con trỏ cấp 1. Mỗi phần tử lưu địa chỉ của mảng số nguyên như bên hình. Các giá trị 90, 210,150, 10 là giá trị địa chỉ của 4 mảng một chiều bên phải. 50 là địa chỉ của a, nơi chứa mảng các con trỏ cấp 1. Bạn có thể hình dung ra cách thức thực hiện: khai báo mảng a với số phần tử là số hàng. Sau đó duyệt hết các con trỏ cấp 1 bên trong, khởi tạo bộ nhớ cho chúng. Chi tiết hơn bạn có thể xem bên dưới:

#include <iostream>

using namespace std;

int main(){

int h, c, i, j;

int **a;

cout << "Nhap so hang, so cot: "; cin >> h >> c;

// bắt đầu khởi tạo từ a

a = new int*[h]; // tạo mảng của con trỏ cấp 1

for (i = 0; i < h; i++) // duyệt hết các con trỏ con

a[i] = new int; // cấp vùng nhớ cho nó

// tới đây, chúng ta đã hoàn tất tạo mảng

// các thao tác trên mảng

for (i = 0; i < h; i++)

for (j = 0; j < c; j++){

cout << "Nhap phan tu (" << i + 1 << "," << j + 1 << "): ";

cin >> a[i][j]; // thao tác như mảng hai chiều vậy

}

// giờ in nó ra

cout << "Ket qua" << endl;

for (i = 0; i < h; i++){

for (j = 0; j < c; j++){

cout << a[i][j] << " "; // thao tác như mảng hai chiều vậy

}

cout << endl;

}

// huỷ vùng nhớ lần lượt theo chiều ngược lại so với cấp phát

for (i = 0; i < h; i++)

delete[] a[i];

delete[] a;

return 0;

}

Chương trình này mô tả lại chính xác biểu đồ ở trên (ngoại trừ các giá trị địa chỉ). Hãy quan sát kĩ các thao tác tôi đã làm. Chú ý tới đoạn cout << a[i][j], tại sao tôi có thể làm như thế? Rõ ràng cấu trúc mảng hai chiều và con trỏ hai chiều khác biệt nhau.

Để giải thích, chúng ta bắt đầu từ **a, bạn cần hiểu các thao tác như [] tương tự với việc đặt dấu * ở đằng trước, như thế a[i][j] có thể viết lại thành *(*(a + i) + j). Nhìn biểu thức này bạn có thể hiểu chuyện gì xảy ra rồi.

Dành một chút thời gian để phân tích nó nhen.

Về phần mảng hai chiều thuần tuý, khi bạn viết a[i][j], nó sẽ làm như thế này *(a + i*h +j), rất khác biệt. Cấu trúc của mảng hai chiều và con trỏ hai chiều khác nhau, do đó bạn không thể gán a[4][6] cho biến con trỏ cấp 2 được. Mảng hai chiều thuần tuý có kiểu *int[4] khác với **int, nên bạn cần chú ý.

Tôi không quen dùng, và cũng không thích dùng mảng hai chiều kiểu như *int[], nó hơi rắc rối, nhiều chuyện và cũng chẳng giải quyết được vấn đề gì to tát. Trừ khi bạn ghét con trỏ, hãy tìm hiểu và dùng nó cách **int của tôi.

Phần chính của bài học đã hoàn tất, YEAH! Bài tập hả, đọc và ngẫm nghĩ lại những gì tôi đã trình bày ở trên.

Giới thiệu thêm: thư viện STL

STL viết tắt của Standard Template Library.

STL là bộ thư viện dành riêng cho C++, nó cung cấp khá nhiều kiểu dữ liệu mới với tính năng đa dạng, thú vị. Tìm hiểu thêm tại http://en.wikipedia.org/wiki/Standard_Template_Library. Sau đây sẽ là 3 kiểu dữ liệu chính:

Stack

Oh, có stack nữa kìa. Kiểu stack và vùng nhớ stack trong memory có giống nhau không? Gần giống, stack là một mảng một chiều động, kích thước có thể tăng giảm tuỳ thuộc vào số lượng phần tử trong khi stack trong memory có giới hạn. Điểm quan trọng cần chú ý đó là tính năng đẩy vào và lấy dữ liệu ra. Cuối cùng, stack hỗ trợ rất nhiều kiểu dữ liệu. Bạn hãy xem thử.

#include <stack> // sử dụng stack thì include nó vô

#include <iostream>

using namespace std;

int main(){

stack<int> st; // tạo 1 stack theo kiểu số nguyên

stack<float> sf; // tạo 1 stack theo kiểu float

int i;

for (i = 0; i < 10; i++)

st.push(i); // đẩy dữ liệu vào trong stack và đặt nó lên trên đỉnh

for (i = 0; i < 10; i++){

cout << st.top(); // lấy phần tử ở trên đỉnh

st.pop(); // xoá phần tử ở trên đỉnh

}

if (st.empty()) // kiểm tra trong stack còn phần tử nào không

cout << "Stack empty";

return 0;

}

Tôi mô tả cách thức hoạt động của stack qua mô hình sau:

Hàm push đẩy giá trị 5 vào trong stack, đưa giá trị 5 thành đỉnh của stack (trước đó là 10).

Hàm pop sẽ loại bỏ phần tử đang ở đỉnh stack, trong trường hợp này là 5, sau đó đỉnh stack ở vị trí 10.

Hàm top lấy giá trị của phần tử đang ở đỉnh stack.

Tưởng tượng stack giống như ly nước uống. Khi rót vào, những giọt nước đầu tiên sẽ xuống đáy ly. Đương nhiên chúng sẽ được uống sau cùng. Còn nhưng giọt nước nào vào sau cùng, lại được đi ra trước hết.

Queue

Cũng là mảng như stack, nhưng theo dạng ‘First In First Out’, phần tử đầu tiên vào sẽ được lấy ra trước. Cùng là ví dụ ở trên, nhưng tôi sử dụng queue, kết quả có sự khác biệt:

#include <queue> // khi sử dụng queue thì include nó vô

#include <iostream>

using namespace std;

int main(){

queue<int> q; // tạo 1 queue theo kiểu số nguyên

queue<float> qf; // tạo 1 queue theo kiểu float

int i;

for (i = 0; i < 10; i++)

q.push(i); // đẩy dữ liệu vào trong queue

for (i = 0; i < 10; i++){

cout << q.front(); // lấy phần tử vào đầu tiên rồi in ra

q.pop(); // xoá phần tử được vào đầu tiên

}

if (q.empty()) // kiểm tra trong queue còn phần tử nào không

cout << "Stack empty";

return 0;

}

Bạn hãy chạy và đánh giá kết quả hiển thị so với stack.

Vector

Kiểu cuối cùng tôi muốn giới thiệu có thể bao hàm luôn cả stack lẫn queue. Đồng thời nó cung cấp cho bạn nhiều tính năng hơn hẳn, nó có tên vector. Có thể hiểu nó là một danh sách, bạn có thể thêm vào, xoá đi cách tuỳ ý mà không gặp vấn đề gì về bộ nhớ (vector quản lý hết cho bạn rồi).

#include <vector> // khi sử dụng vector thì include thằng này vô

#include <iostream>

using namespace std;

int main(){

vector<int> v; // mảng số nguyên

vector<float> vf; // sử dụng kiểu float

return 0;

}

Giống như stack, queue, vector có thể lưu trữ kiểu dữ liệu tuỳ theo ý thích của bạn. Ví dụ trên, tôi tạo hai vector kiểu int và kiểu float.

Dành chung cho cả stack, queue, vector:

Khi khai báo, bạn đã lựa chọn kiểu dữ liệu mà chúng lưu trữ. Thì sau này, các thao tác bạn cũng phải sử dụng kiểu dữ liệu đó, không chấp nhận kiểu khác.

Một stack<int> chỉ có thể push kiểu int như số 5,… Một queue<MyStruct> cũng chỉ có thể push MyStruct. Tương tự, một vector<int*> chỉ có thể push_back kiểu int* (push_back sẽ đưa giá trị vào cuối danh sách). Viết như bên dưới sẽ gặp lỗi cú pháp:

struct MyStruct{

int i, j;

};

int main(){

vector<int> v; // mảng số nguyên

MyStruct s;

v.push_back(s); // push MyStruct vào

return 0;

}

Bên trong cặp dấu <> là kiểu dữ liệu bạn muốn nó sẽ sử dụng, tôi hay dùng int để ví dụ đó. Chúng ta còn một vấn đề, bạn cần phải nhớ rõ: tất cả các thao tác đẩy vào (thêm phần tử vào) danh sách đều có chung nguyên lý, đó là sao chép dữ liệu chúng ta truyền vào. Giả sử hàm push_back ở trên chạy được, tôi truyền biến struct s, thì vector v sẽ lưu bản copy của struct (nó tạo thêm biến struct sau đó gán bằng s). Điều này giúp bạn có thể tiếp tục sử dụng struct đó mà không lo lắng về chuyện giá trị đang lưu trong vector bị thay đổi. Ví dụ:

#include <vector> // khi sử dụng vector thì include thằng này vô

#include <iostream>

using namespace std;

struct MyStruct{

int i, j;

};

int main(){

vector<MyStruct> v; // mảng số nguyên

MyStruct s;

for (int i = 0; i < 10; i++){

s.i = i;

s.j = i;

v.push_back(s); // push MyStruct vào

}

// OK, in ra để kiểm tra

for (int i = 0; i < 10; i++){

cout << v[i].i << " " << v[i].j << endl;

}

return 0;

}

Bạn thấy đó, tôi chỉ sử dụng 1 struct, nhưng khi in ra, kết quả vẫn giống như lúc nó được push vào vector. Đồng thời, bạn cũng thấy cách truy cập vào phần tử bên trong vector giống hệt mảng một chiều không. Thú vị chứ ha.

Tiếp theo là danh sách một số hàm mà vector hỗ trợ, bạn hãy xem thử:

clear(): xoá tất cả các phần tử đang có trong vector.
front(): trả về phần tử đầu tiên trong danh sách.
insert(vị trí, giá trị): chèn một giá trị vào vị trí cho trước.
pop_back(): xoá phần tử cuối cùng.
size(): trả về số lượng phần tử trong vector
erase(vị trí bắt đầu, vị trí kết thúc): xoá một dãy từ bắt đầu đến kết thúc

Ví dụ sử dụng hàm erase và size:

int main(){

vector<MyStruct> v; // mảng số nguyên

MyStruct s;

for (int i = 0; i < 10; i++){

s.i = i;

s.j = i;

v.push_back(s); // push MyStruct vào

}

v.erase(v.begin() + 3, v.begin() + 6);

// OK, in ra để kiểm tra

for (int i = 0; i < v.size(); i++){

cout << v[i].i << " " << v[i].j << endl;

}

return 0;

}

Chú ý về giá trị vị trí được sử dụng trong vector: nó không phải là chỉ số như mảng. Bạn cần sử dụng theo cấu trúc:

<điểm bắt đầu> + số lượng

Điểm bắt đầu ở đây thường có hai giá trị: v.begin() như ở trên hoặc v.end() tương ứng vị trí của phần tử đầu tiên và phần tử cuối cùng trong vector. Nếu bạn sử dụng begin() + 3 nghĩa là bạn đang chỉ định phần tử thứ 4 (có chỉ số là 3) trong vector. Quay lại ví dụ ở trên, tôi sử dụng hàm erase, xoá từ begin() + 3 tới begin() + 6 nghĩa là tôi sẽ xoá từ phần tử có chỉ số 3 tới phần tử có chỉ số 6 (không xoá chỉ số 6).

I think i’m lacking something.

Nếu muốn xoá từ vị trí có chỉ số 6 cho tới cuối, bạn có thể viết:

1	v.erase(v.begin() + 6, v.end());