nhanthanh

[nhanthanh]

Linked list

Là cấu trúc dữ liệu gồm dãy các node kết nối với nhau thông qua các link (liên kết). 

Mỗi node bao gồm data và address của node kế tiếp.

struct node 

{ 

     int data; 

     struct node *next; 

};

Một linked-list (singly-linked list) cơ bản sẽ giống như sau:

class linked_list 

{ 

     private: 

          node *head,*tail; 

     public: 

     linked_list()

     { 

          head = NULL; 

          tail = NULL; 

     } 

};

Một linked-list sẽ bắt đầu từ node head và kết thúc ở node tail.

Ta tạo thêm function để thêm node vào linked-list:

void add_node(int n) 

{ 

     node *tmp = new node; 

     tmp->data = n; 

     tmp->next = NULL; 

     if(head == NULL) 

     { 

          head = tmp; 

          tail = tmp; 

     } 

else 

     { 

          tail->next = tmp; 

          tail = tail->next; 

     } 

}

[nhanthanh]

Pointer và Constant

Pointer to Constant

VD về pointer to constant:

const int *ptr;

Pointer trên:

1. Có thể trỏ đến vùng nhớ của hằng và chỉ pointer to constant mới làm được như vậy.

2. Có thể trỏ đến vùng nhớ của biến thông thường và thông qua con trỏ đó, vùng nhớ trở thành read-only. Cố gắng thay đổi bằng dereference operator sẽ gây ra lỗi compile. Ta có thể dùng để đảm bảo sự toàn vẹn cho dữ liệu của vùng nhớ mà nó trỏ đến.

Constant pointer

Là con trỏ chỉ gán được địa chỉ một lần khi khởi tạo, và không thể trỏ đi nơi khác được. VD về constant pointer:

int value1 = 5;

int value2 = 10; 

int *const ptr = &value1; 

ptr = &value2; //compile error

Lúc này bản thân con trỏ là hằng, còn vùng nhớ nó trỏ đến thì không phải hằng.

Constant pointer to constant

Kết hợp cả hai loại ở trên để tạo ra loại con trỏ chỉ có chức năng read-only và cũng không thể thay đổi vùng nhớ nó trỏ đến.

int value = 5; 

const int *const ptr = &value; 

&ptr = 10; //compile error int otherValue = 10; 

ptr = &otherValue; //compile error

[nhanthanh]

Double pointer

Pointer 1 lưu trữ địa chỉ của biến, pointer thứ 2 lưu trữ địa chỉ của pointer 1 - double pointer.

Cách khai báo double pointer trong C++:

int **ptr;

VD:

int var = 789;    // pointer for var    

int *ptr2;    // double pointer for ptr2    

int **ptr1;    // storing address of var in ptr2    

ptr2 = &var;        // Storing address of ptr2 in ptr1    

ptr1 = &ptr2;

Multidimensional dynamic array

VD mảng 2 chiều:

int **table = new int*[rows];

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

{

       table[i] = new int[cols];

}

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

{

      delete[] table[i];

}

[nhanthanh]

Dãy địa chỉ trên bộ nhớ ảo được chia thành nhiều phân vùng khác nhau.

Code segment (Text segment): Mã nguồn của chương trình sau khi biên dịch trở thành mã máy(0 và 1). Khi chúng ta chạy chương trình thì mã máy được đưa vào code segment chờ CPU gọi khi cần thiết. Vùng code segment chỉ được can thiệp bởi hệ điều hành.

Data segment (initialized data segment) khởi tạo giá trị cho các biến static và global.

BSS segment (uninitialized data segment) cũng để lưu các biến static và global nhưng chưa được khởi tạo giá trị cụ thể.

Heap segment (free srote segment) được sử dụng để cấp phát bộ nhớ thông qua kỹ thuật Dynamic memory allocation. Điều duy nhất phải lưu ý ở đây là dữ liệu trên bộ nhớ heap sẽ không tự động giải phóng mà phát giải phóng thủ công thông qua delete. Việc tự do co giãn vùng nhớ theo nhu cầu trong runtime buộc ta phải kiểm soát thật tốt thông qua công cụ duy nhất là pointer, nếu không sẽ ảnh hưởng đến quá trình cấp phát bộ nhớ động cho chương trình khác.

Việc cấp phát và truy xuất đến vùng nhớ là chậm hơn các phân vùng khác.

Heap có dung lượng lớn nhất.

Vùng nhớ được cấp phát mãi mãi thuộc về quyền kiểm soát của 1 chương trình cho đến khi nó được delete hoặc chương trình đó kết thúc.

Stack segment được dùng để cấp phát bộ nhớ cho parameter của hàm và local variable. Dữ liệu trên stack segment được cấp phát và giải phóng theo cấu trúc dữ liệu stack - "last in-first out" - nghĩa là các dữ liệu thuộc khối lệnh nhỏ hơn sẽ nằm cao hơn, nên việc giải phóng cũng nhanh hơn.

Cấp phát bộ nhớ khá nhanh.

Truy xuất trực tiếp qua định danh.

Kích thước vùng nhớ cần cấp phát phải được khai báo rõ ràng khi biên dịch.

Kích thước khá hạn chế (1MB).

[nhanthanh]

Cấp phát bộ nhớ động

C++ buộc chúng ta phải cấp phát vùng nhớ ngay khi chạy chương trình (Compile-time allocation/Static memory allocation) khiến chương trình kém linh hoạt và sử dụng nhiều tài nguyên bộ nhớ. Automatic memory allocation (cấp phát bộ nhớ tự động) thì cấp phát bộ nhớ trong runtime khi đi vào các hàm (dành cho local variable và parameter) và bị thu hồi sau khi ra khỏi hàm. Kích thước vùng nhớ cấp phát cho static memory allocation và automatic memory allocation là rất giới hạn (phân vùng Stack trên bộ nhớ ảo) dễ gây nên stackoverflow.

Kỹ thuật Dynamic memory allocation là giải pháp cấp phát bộ nhớ tại runtime sử dụng phân vùng Heap trải qua 2 bước: yêu cầu cấp phát vùng nhớ trên Heap (bằng new operator) và lưu trữ địa chỉ của vùng nhớ vừa được cấp phát vào pointer, vùng nhớ được cấp phát sau khi sử dụng xong phải được hoàn lại bằng toán tử delete.

Kiểu trả về của toán tử new là con trỏ kiểu void (con trỏ chỉ lưu trữ địa chỉ chứ không quan trọng dữ liệu lưu trữ ở địa chỉ đó thuộc data type nào).

new int; //allocate 4 bytes on Heap partition to an int variable

new double; //allocate 8 bytes on Heap partition to a double variable

Sau đó đưa cho 2 pointer quản lý, thông qua 2 con trỏ để thay đổi giá trị bên trong vùng nhớ này

int *p_int = new int;

double *p_double = new double;

Để trả vùng nhớ về cho Heap, ta cung cấp cho toán tử delete một địa chỉ.

delete p;

Lúc này vùng nhớ được trả về nhưng giá trị lưu trong vùng nhớ còn nguyên cho đến khi hệ thống can thiệp và con trỏ p vẫn lưu trữ địa chỉ của vùng nhớ đó. Nếu ta sử dụng dereference hay delete lần nữa cho p thì sẽ trả về undefined behavior.

Trường hợp xin cấp phát trên bộ nhớ Heap thất bại, chương trình sẽ kết thúc với lỗi unhandled exception error.

int *p = new (std::nothrow) int;

Sử dụng cách xin cấp phát trên, new sẽ trả về NULL nếu thất bại.

[nhanthanh]

Pointer-Array

Pointer và Array

Trong hầu hết trường hợp ta có thể xét Array cũng giống như một pointer trỏ đến ô nhớ của phần tử đầu tiên của mảng.

int *ptr;

int arr[]

ptr = arr;

Hay có thể hiểu là ptr = &arr[0];

Vậy

ptr + 1 = &arr[1];

ptr + 2 = &arr[2];

Nhưng về cơ bản thì pointer và array không giống nhau.

Xem thêm: https://www.learncpp.com/cpp-tutorial/pointers-and-arrays/

Truyền array vào function

Một biến thông thường khi truyền vào như parameter của function sẽ pass-by-value. Có nghĩa là C++ copy giá trị của biến đó rồi đưa vào một biến cục bộ mới. Tuy nhiên array thì khác, việc copy cả array vào sẽ khiến tài nguyên bộ nhớ bị hao hụt nên sẽ được pass-by-pointer vào function - thay đổi diễn ra trong function lên array sẽ thay đổi chính array truyền vào.

Hai function dưới đây là giống nhau:

void printSize(int array[]);

void printSize(int *array);

[nhanthanh]

Pointer (con trỏ)

Thông thường, biến là tên tượng trưng cho một giá trị.

Giá trị trong biến được lưu trữ trong RAM của máy tính. Tùy vào kiểu dữ liệu mà một giá trị có thể cần đến 1, 2, 4 hay 8 ô nhớ (mỗi ô nhớ tương ứng 1 byte) để lưu trữ giá trị của nó. Để truy cập dữ liệu trên RAM thì người ta cần gọi đúng địa chỉ ô nhớ đầu tiên của chuỗi n ô nhớ đang lưu trữ giá trị mà ta cần.

Pointer là tên tượng trưng cho địa chỉ của một giá trị đang lưu trữ trên RAM. Size của pointer không phụ thuộc vào kiểu dữ liệu. Thường với hệ máy 32bit thì 1 pointer chiếm 4 byte còn 64bit thì chiếm 8 byte.

int var = 10;

int *ptr = &var;

* trong khai báo chỉ để biểu thị nó là pointer.

& (address-of operator): lấy địa chỉ của biến.

* (dereference operator): lấy giá trị của ô nhớ mà pointer trỏ đến.

[nhanthanh]

Generics function là một function có thể làm việc với tất cả các data type để trách việc lặp cùng các dòng code cho những data type khác nhau khi bản thân thuật toán không phụ thuộc vào data type (tránh overloading function cho từng data type).

Vậy ở đây khi ta truyền tham số vào cho generics function, không chỉ có giá trị của biến là parameter mà ngay cả kiểu của biến cũng là parameter (type parameterization). Kiểu của biến sẽ được truyền vào template - một kiểu dữ liệu trừu tượng tổng quát hóa cho các kiểu dữ liệu khác và được xác định khi generics function được gọi.

VD:

template <</code>typename T>

T myMax(T x, T y)

{

     return (x > y) ? x : y;

}

Ngoài generics function thì ta còn có generics class. Generics class định nghĩa một class mà không phụ thuộc vào data type như LinkedList, Binary Tree, Stack, Queue, Array,...

[nhanthanh]

Một video dài 7 phút khá xúc tích và dễ hiểu về OOP, có đầy đủ ví dụ thực tế để ta hiểu về từng đặc tính của OOP.

Trước khi OOP xuất hiện, ta có Procedural Programming - xây dựng chương trình xoay quanh các function. Chương trình càng ngày càng giãn ra, copy&paste các function rải rác ở khắp nơi khiến cho chúng phụ thuộc nhưng không có sự liên kết khiến cho việc sửa chữa các function cực kỳ khó khăn.

Qua OOP, ta gom các functions và variables có liên quan vào một unit - Object. Từ đó, variable trở thành property, function trở thành method. Property và method của một object sẽ có sự liên kết chặt chẽ với nhau. Đó chính là tính đóng gói - Encapsulation.

Tiếp là Abstraction - tính trừu tượng thể hiện qua việc ẩn đi những function và variable không cần thiết có sự tương tác với bên ngoài để:

Giảm thiểu sự thay đổi không đáng có.

Thay đổi những thành phần đã ẩn đi không làm ảnh hưởng đến chương trình

Đơn giản hóa interface

Tính kế thừa - Inheritance cho phép ta tái sử dụng code để tránh các đoạn code lặp lại thừa thải. Ta định nghĩa các property và method trong một generic object và sau đó cho các object có chung những điểm chung với generic object đó kế thừa nó.

Mặc dù các object cùng kế thừa tới một generic object nhưng cách chúng hoạt động lại có phần khác nhau. VD một method chung là Speak() nhưng People, Cat, Dog sẽ không thể kêu tiếng giống nhau được. Từ đó ta có tính đa hình - Polymorphism, cùng chung tên gọi nhưng cách hành động khác nhau tùy vào loại object.

Tóm gọn lại: