CS162
Sau đây là bài blog được mình viết ra để tóm tắt lại kiến thức đã học và mở rộng thêm các khía cạnh khác nếu có thể.
Pointers
Đây là phần tương đối trừu tượng cho các bạn mới tiếp cận nhưng mình sẽ cố gắng tóm tắt và viết lại 1 cách dễ hiểu nhất.
Pointers là cái qq gì?
Về cơ bản, pointer chỉ là 1 kiểu dữ liệu. Dữ liệu mà chúng lưu trữ là 1 địa chỉ.
Vd: có 1 address 0x00112233, thì pointer để trỏ vào address thì nó sẽ lưu 0x00112233.
Để khai báo 1 pointer mình có thể khai báo theo cấu trúc <type>* <name> (number of stars depend on your purpose). Ở đây type còn có thể là void* đây là kiểu pointer đặc biệt nó chỉ lưu địa chỉ bất kì và không quan tâm dữ liệu tại đó được sử dụng theo kiểu nào (int, double, float, struct nào đó,…).
Lưu ý: size của 1 pointer chỉ là 4 bytes (x86 bit) hoặc 8 bytes (x64 bit) với mọi kiểu dữ liệu.
Syntax
Khai báo biến với kiểu dữ liệu pointer.
int b = 10;
int *a = &b;
Mình có thể dereference biến a để thay đổi giá trị được lưu trong biến b bằng operator * như sau.
*a = 2; // lúc này b = 2
&a -> /*đây là địa chỉ của a nơi lưu địa chỉ của b.*/
Mình có thể allocate struct theo kiểu dynamic như sau:
struct Node{
int value;
Node *pNext;
};
int main(){
Node *pHead = new Node;
Node *arrayOfNodes = new Node[10]; // declare a array of Nodes
/*
1 style khai báo khác như sau
Node* tmp = new Node;
*/
}
Để tính size của struct thì có thể tham khảo struct padding.
Việc tính size của struct sẽ giúp mình hiểu rõ hơn việc allocate struct trong heap và hiểu được syntax alloc trong C.
ptr = (struct Node*) malloc(sizeof(struct Node)); // malloc trả về void* (đã được nhắc ở trên) nên mình cần reinterpret_cast sang Node*
Để access struct members mình có thể dùng operator -> trong trường hợp dynamic allocating.
int main(){
(...)
pHead->value = 5;
/*
equivalent to
(*pHead).value = 5;
*/
(...)
}
Lỗi syntax kinh điển
int* a, b;
Ở đây a là pointer kiểu int nhưng b là biến int bình thường.
Pointer và array
int b[10];
Khi khai báo 1 mảng thì tên của mảng sẽ tương tự như 1 pointer trỏ vào vị trí đầu tiên của mảng đó. (*b tương tự với b[0])
Việc khai báo như này sẽ tạo ra 10 ô nhớ liên tiếp trong RAM nên mình có thể tuy cập vô phần tử thứ x bằng cách gọi *(nameArr + x). Ở đây, mỗi ô nhớ sẽ chiếm số bytes tùy thuộc vào kiểu dữ liệu here.
b[1];
1[b];
*(b + 1);
Để access vào 1 phần tử trong mảng thì mình có 3 cách như trên. Nhưng mình khuyến khích mọi người dùng cách đầu tiên hơn.
Passing a pointer as a parameter into a function
void func(int *a, int &b, int *&c, int d){
(...)
}
a and d are called by value. That means the dereferenced variable will not be changed if you modify a and d. While b and c are called by reference and the derefrenced variable will be changed if b and c are changed.
Allocating and freeing
Luôn luôn phải delete phân dùng được allocate trong heap sau khi mình sử dụng xong. Điều này sẽ tránh các lỗi memory leak,…
void func(){
Node *a = new Node;
(...)
delete a;
a = nullptr; // important!!!
(...)
}
Dòng cuối cùng trong đoạn code trên là cần thiết để tránh lỗi use after freed. Có thể hiểu đơn giản là lệnh delete chỉ đơn giản là giải phóng phân vùng hiện tại để nó có thể được tiếp tục cấp phát với mục đích khác. Do đó nếu không gán lại nullptr có thể khiến cho mình sơ ý sử dụng hoặc thay đổi giá trị của địa chỉ đã được giải phóng và tệ hơn là nó đã được cấp phát với mục đích khác.
Một lưu ý khác
void func(){
int *a = new int;
int *b = a;
(...)
delete a;
delete b; // error here!
a = nullptr;
}
Lỗi này xảy ra khi delete cả a và b cùng trỏ vào một phân vùng trong heap. Việc này sẽ tương đương với việc delete một phân vùng nhiều hơn 1 lần. Điều này là không hợp lệ vì sau lần delete đầu thì có thể hiểu phân vùng đó đã freed nên mình không thể free 1 phân vùng đã freed được.
An example for deleting an array pointer
int *p = new int[10];
// -> it will create an array with length 10
(...)
delete[] p;
// remember adding square brackets after keyword "delete"
Freeing multi structs
Cho 1 cấu trúc các struct như sau
struct C{
int *z;
};
struct B{
int *y;
C* c;
};
struct A{
int *x;
B* b;
};
void initC(C*& c){
c = new C;
c->z = new int;
}
void initB(B*& b){
b = new B;
b->y = new int;
initC(b->c);
}
void initA(A*& a){
a = new A;
a->x = new int;
initB(a->b);
}
int main(){
A* a;
initA(a);
}
Cách để delete biến a cho chương trình là gì?
void deleteA(A*& a){
delete a->b->c->z;
delete a->b->c;
delete a->b->y;
delete a->b;
delete a->x;
delete a;
a = nullptr;
// delete lan luot cac pointer trong tung struct con
}
Memory layout
In this section, I will introduce the structure of memory. How does a variable be stored in memory?
What is it?
When an executable file is running, it creates many variables and stores these in RAM.
There are 5 parts Text Segment, Initialized Data Segment, Uninitialized Data Segment, Heap, and Stack. They are divided into 2 main layout Dynamic Memory and Static Memory. All segments (Data and Text) should not be changed their size. Otherwise, stack and heap can be changed.
Text/Code Segment
This segment stores your source code and initialized data (strings,…).
char a[] = "etuc mnd";
int main(){
int b = 1212;
}
After we compile the program, a binary file generates, which is used to execute our program by loading it into RAM. This binary file contains instructions, and these instructions get stored in the text segment of the memory.
Text segment has read-only permission that prevents the program from accidental modifications.
The value of these variables ("etuc mnd" or 123) is initially stored in this segment and then will be copied to another segment for initializing variables.
Initialize Data Segment (.data)
Phần Memory layout này tạm thời confused quá nên mình skip nhó từ từ bổ sung sau :<
Nói chung mình chỉ cần nhớ char *p = "abc"(1) và char p[] = "abc"(2) khác nhau ở chỗ cách (1) sẽ lưu "abc" trong read-only data (.rodata, some sources thì bảo .rodata nằm trong Initialize Data Segment còn số còn lại ghi nằm trong Text Segment?) sau đấy biến pointer p sẽ lưu địa chỉ thuộc .rodata. Vì vậy, với cách (1) mình sẽ không modify xâu *p được. Còn với cách (2) thì xâu "abc" sẽ được lưu ở .data và p sẽ là pointer trỏ đến vị trí đầu của xâu này trong .data. Do đó, xâu này có thể thay đổi giá trị được.
Uninitialize Data Segment (.bss)
Heap
Stack
Linked list
Singly Linked list
Initialize
struct Node{
int data;
Node *pNext;
};
Node* createNode(int value){
Node *tmp = new Node;
tmp->pNext = nullptr;
tmp->data = value;
return tmp;
}
Insert
// insert a node at the end
void insertLast(Node *&pHead, Node *&pTail, int value){
Node *tmp = createNode(value);
if (pHead == nullptr) {
pHead = pTail = tmp;
return;
}
pTail->pNext = tmp;
pTail = tmp;
// Do not delete tmp at the end in this function
}
// insert a node at the beginning
void insertBeginning(Node *&pHead, Node *&pTail, int value){
Node *tmp = createNode(value);
if (pHead == nullptr) {
pHead = pTail = tmp;
return;
}
tmp->pNext = pHead;
pHead = tmp;
// Do not delete tmp at the end in this function
}
// insert a node after a specific position
// pos = -1 to initialize the list
void insertAfterPos(Node *&pHead, Node *&pTail, int value, int pos){
int id = 0;
Node *cur = pHead;
while (cur && id != pos) {
cur = cur->pNext;
++id;
}
if (id == pos || pos == -1)
insertBeginning(cur->pNext, pTail, value); // cai nay giong voi ham deleteAtBeginning
}
Delete
// delete the first node
void deleteAtBeginning(Node *&pHead, Node *&pTail){
if (!pHead) return;
Node *tmp = pHead;
pHead = pHead->pNext;
delete tmp;
if (!pHead)
pTail = nullptr;
}
// delete the last node
void deleteAtLast(Node *&pHead, Node *&pTail){
if (!pHead) return;
if(pHead == pTail) {
deleteAtBeginning(pHead, pTail);
return;
}
Node *tmp = pHead;
while(tmp->pNext != pTail)
tmp = tmp->pNext;
deleteAtBeginning(tmp->pNext, pTail);
}
// delete the specific node
void deleteAtPos(Node *&pHead, Node *&pTail, int pos){
if (!pHead)
return; // out of range
if(pos == 0)
deleteAtBeginning(pHead, pTail);
Node *tmp = pHead;
for (int i = 0; i < pos - 1; ++i) {
tmp = tmp->pNext;
if (!tmp)
return; // out of range
}
deleteAtBeginning(tmp->pNext, pTail);
}
Iterate
Printing and freeing
void printList(Node *pHead){
cout << "Here is the list: ";
while(pHead){
cout << pHead->data << ' ';
pHead = pHead->pNext;
}
cout << '\n';
}
void freeList(Node *&pHead, Node *&pTail){
pTail = nullptr;
while(pHead){
Node *tmp = pHead;
pHead = pHead->pNext;
delete tmp;
}
// pHead is assigned nullptr already
}
Sample main
int main(){
int n;
Node *pHead, *pTail;
pHead = pTail = nullptr;
cout << "Input n: ";
cin >> n;
for (int i = 0; i < n; ++i) {
int v;
cin >> v;
insertLast(pHead, pTail, v);
}
printList(pHead);
insertBeginning(pHead, pTail, 5);
insertBeginning(pHead, pTail, 4);
printList(pHead);
insertAfterPos(pHead, pTail, 100, 5);
insertLast(pHead, pTail, 200);
printList(pHead);
deleteAtBeginning(pHead, pTail);
printList(pHead);
deleteAtLast(pHead, pTail);
printList(pHead);
deleteAtPos(pHead, pTail, 2);
printList(pHead);
deleteAtPos(pHead, pTail, 0);
printList(pHead);
// important
freeList(pHead, pTail);
}