Đăng nhập để tham gia lộ trình luyện tập

Some problems in the training are missing or you do not have permission to view them.

251, 252, 253, 254, 255

CON TRỎ TRONG C++

Mục tiêu là hiểu con trỏ lưu gì, * và & tác động thế nào, cách con trỏ liên hệ với mảng, hàm, chuỗi kiểu C và vùng nhớ cấp phát động. Đây không phải chuyên đề Two Pointers, cũng không mở rộng sang linked list, tree, graph, stack, queue hay các cấu trúc dữ liệu phức tạp.

Con trỏ là một biến dùng để lưu địa chỉ của một đối tượng. Nếu p đang trỏ tới x thì:

• p là địa chỉ của x;
• *p là đối tượng nằm tại địa chỉ đó;
• &x là địa chỉ của x;
• &p là địa chỉ của chính biến con trỏ p.

Quan hệ cơ bản:

Hai biểu thức trên mô tả quan hệ địa chỉ và giải tham chiếu, không có nghĩa p và x cùng kiểu dữ liệu.

Giai đoạn 1 - Địa chỉ và giải tham chiếu

1. Địa chỉ của biến

Toán tử lấy địa chỉ & trả về địa chỉ của một đối tượng.

int x = 10;
int* p = &x;

Ở đây p có kiểu int*, nghĩa là con trỏ có thể trỏ tới một đối tượng kiểu int.

Có thể hình dung:

x  = 10
&p = địa chỉ riêng của biến p
p  = địa chỉ của x
*p = 10

Không nên học thuộc địa chỉ thật như 0x... vì địa chỉ cụ thể có thể thay đổi giữa các lần chạy.

2. Giải tham chiếu

Toán tử * dùng để truy cập đối tượng mà con trỏ đang trỏ tới.

int x = 10;
int* p = &x;

*p = 25;

Sau lệnh trên:

x == 25
*p == 25

Sửa *p chính là sửa đối tượng gốc.

3. Phân biệt p, *p, &p

Đây là ba khái niệm khác nhau:

int x = 7;
int* p = &x;

• p: địa chỉ của x;
• *p: giá trị của x;
• &p: địa chỉ của biến con trỏ p.

Mã trace cơ bản:

tạo biến x

cho p trỏ tới x

đọc p:
    nhận địa chỉ của x

đọc *p:
    nhận giá trị của x

đọc &p:
    nhận địa chỉ của chính biến p

4. Hai con trỏ cùng trỏ một đối tượng

Nhiều con trỏ có thể cùng giữ một địa chỉ. Hiện tượng này thường gọi là bí danh địa chỉ (aliasing).

int x = 5;

int* p = &x;
int* q = &x;

*p = 20;

Khi đó:

x == 20
*q == 20

p và q không phải cùng một biến, nhưng chúng cùng trỏ tới một đối tượng.

5. Đổi mục tiêu của con trỏ

Thay đổi p và thay đổi *p là hai việc hoàn toàn khác nhau.

int x = 1;
int y = 2;

int* p = &x;

p = &y;

Lệnh p = &y làm p trỏ sang y.

Trong khi đó:

*p = 100;

sửa giá trị của đối tượng đang được p trỏ tới.

6. Con trỏ rỗng nullptr

Trong C++ hiện đại, khi một con trỏ chưa trỏ tới đối tượng hợp lệ, nên dùng nullptr.

int* p = nullptr;

Không được giải tham chiếu một con trỏ rỗng:

*p = 5; // sai

Mẫu an toàn:

nếu p khác nullptr:
    mới được dùng *p

Trong C++:

if (p != nullptr) {
    cout << *p;
}

nullptr chỉ biểu diễn trạng thái không trỏ tới đối tượng nào. Nó không tự phát hiện con trỏ treo sau khi một vùng nhớ đã hết vòng đời.

7. Kích thước con trỏ và kích thước đối tượng

sizeof(p) là kích thước của biến con trỏ.

sizeof(*p) là kích thước của đối tượng mà p trỏ tới.

int x = 0;
int* p = &x;

cout << sizeof(p);
cout << sizeof(*p);

Không được suy luận rằng mọi hệ thống luôn có cùng kích thước con trỏ.

Giai đoạn 2 - const, reference và pointer

1. Con trỏ tới dữ liệu chỉ đọc

Dạng:

const int* p;

hoặc:

int const* p;

Hai cách viết trên có cùng ý nghĩa.

p có thể đổi sang địa chỉ khác, nhưng không được sửa đối tượng thông qua p.

int x = 10;
int y = 20;

const int* p = &x;

p = &y;   // hợp lệ
// *p = 5; // không hợp lệ

Có thể đọc từ phải sang trái theo ý nghĩa:

p là pointer tới const int

2. Con trỏ cố định địa chỉ

Dạng:

int* const p = &x;

p bắt buộc được khởi tạo ngay và không thể trỏ sang địa chỉ khác.

Tuy nhiên dữ liệu đích vẫn sửa được.

int x = 10;
int y = 20;

int* const p = &x;

*p = 30;  // hợp lệ
// p = &y; // không hợp lệ

3. Con trỏ cố định tới dữ liệu chỉ đọc

Dạng:

const int* const p = &x;

Cả hai đều bị khóa:

• không đổi địa chỉ trong p;
• không sửa *p thông qua p.

4. Cách nhớ ba dạng const

const int* p;

Dữ liệu qua p không sửa được, nhưng p có thể đổi mục tiêu.

int* const p = &x;

p không đổi mục tiêu, nhưng *p sửa được.

const int* const p = &x;

Cả địa chỉ lẫn dữ liệu qua pointer đều không đổi được.

5. Pointer và reference

Reference:

int& r = x;

Pointer:

int* p = &x;

Khác biệt thực chiến quan trọng:

• pointer có thể là nullptr;
• pointer có thể đổi sang đối tượng khác;
• pointer truy cập dữ liệu bằng *p;
• reference hoạt động như một bí danh của đối tượng sau khi được gắn.

Ví dụ hai hàm cùng sửa một biến:

void tangBangPointer(int* p) {
    if (p != nullptr) {
        ++(*p);
    }
}

void tangBangReference(int& x) {
    ++x;
}

Khi một tham số có thể không tồn tại, pointer biểu diễn trạng thái đó tự nhiên hơn bằng nullptr.

Giai đoạn 3 - Con trỏ với mảng một chiều

1. Tên mảng và phần tử đầu

int a[4] = {10, 20, 30, 40};

Trong nhiều biểu thức, a được chuyển đổi thành con trỏ tới phần tử đầu:

int* p = a;

tương đương:

int* p = &a[0];

Nhưng cần phân biệt:

a
&a[0]
&a

a và &a[0] thường cho cùng địa chỉ phần tử đầu trong ngữ cảnh giá trị, còn &a có kiểu con trỏ tới cả mảng, không phải int*.

2. Công thức chỉ số và con trỏ

Với mảng a:

Ví dụ:

int a[4] = {10, 20, 30, 40};

cout << *(a + 2);

kết quả là 30.

3. Số học con trỏ

Nếu p là int* thì:

p + 1

không có nghĩa tăng địa chỉ thêm đúng 1 byte.

Nó có nghĩa: chuyển sang phần tử int kế tiếp.

Tổng quát:

là vị trí cách p đúng k phần tử cùng kiểu trong cùng một mảng hợp lệ.

Mã giả:

p trỏ tới phần tử đầu

trong khi p chưa tới cuối:
    xử lý *p
    tăng p sang phần tử kế tiếp

4. Duyệt mảng bằng con trỏ chạy

int a[5] = {2, 4, 6, 8, 10};

int* p = a;
int* end = a + 5;

while (p != end) {
    cout << *p << ' ';
    ++p;
}

Ở đây end = a + 5 là con trỏ one-past, tức vị trí ngay sau phần tử cuối.

Có thể tạo và so sánh end, nhưng không được giải tham chiếu:

*end // sai

5. Khoảng [begin, end)

Đây là cách biểu diễn rất quan trọng trong C++.

Khoảng:

bao gồm mọi phần tử từ begin đến trước end.

Độ dài:

Điều kiện quan trọng: phép trừ hai con trỏ chỉ có ý nghĩa khi chúng cùng nằm trong một mảng hợp lệ, hoặc ở vị trí one-past của chính mảng đó.

Trong C++ nên dùng kiểu:

std::ptrdiff_t

cho kết quả hiệu hai con trỏ.

6. Template duyệt pointer range

long long tong(const int* begin, const int* end) {
    long long s = 0;

    while (begin != end) {
        s += *begin;
        ++begin;
    }

    return s;
}

Cách gọi:

int a[] = {3, 5, 7, 9};

cout << tong(a, a + 4);

7. Tìm phần tử và trả địa chỉ

Khi cần xác định chính phần tử nằm trong mảng, pointer có thể đóng vai trò như vị trí.

const int* timMin(const int* begin, const int* end) {
    if (begin == end) {
        return nullptr;
    }

    const int* best = begin;

    for (const int* p = begin + 1; p != end; ++p) {
        if (*p < *best) {
            best = p;
        }
    }

    return best;
}

Kết quả không chỉ cho giá trị nhỏ nhất mà còn cho địa chỉ của phần tử đó trong vùng nhớ của mảng.

Giai đoạn 4 - Con trỏ với hàm

1. Truyền địa chỉ để hàm sửa biến gốc

void gan0(int* p) {
    if (p != nullptr) {
        *p = 0;
    }
}

Gọi:

int x = 15;
gan0(&x);

Hàm nhận bản sao của địa chỉ &x, nhưng *p vẫn truy cập đúng đối tượng x.

2. Hoán đổi hai biến bằng pointer

void swapPtr(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

Điểm quan trọng không nằm ở bài hoán đổi, mà ở cơ chế:

&a và &b của hàm gọi
        ↓
được truyền vào pointer
        ↓
dereference để sửa đối tượng gốc

3. Pointer được truyền theo giá trị

Xét:

void doiPointer(int* p, int* q) {
    p = q;
}

Nếu gọi:

int x = 1;
int y = 2;

int* p = &x;
int* q = &y;

doiPointer(p, q);

thì pointer p ở hàm gọi không đổi.

Lý do: biến p bên trong hàm chỉ là một bản sao địa chỉ.

Mã giả:

caller có pointer p

gọi hàm(p)

hàm nhận một bản sao của p

đổi bản sao:
    không đổi pointer p ở caller

4. Khi cần thay pointer của bên gọi

Nếu thật sự muốn hàm thay địa chỉ mà pointer ở caller đang giữ, có thể dùng con trỏ cấp hai T**.

void troSang(int** pp, int* dich) {
    *pp = dich;
}

Gọi:

int x = 1;
int y = 2;

int* p = &x;

troSang(&p, &y);

Sau đó p trỏ tới y.

Cơ chế:

pp   = địa chỉ của biến p
*pp  = chính biến p
**pp = đối tượng mà p đang trỏ tới

5. Hàm nhận mảng chỉ đọc

long long tong(const int* a, int n) {
    long long s = 0;

    for (int i = 0; i < n; ++i) {
        s += *(a + i);
    }

    return s;
}

const int* thể hiện rõ rằng hàm chỉ đọc dữ liệu.

6. Hàm trả pointer vào vùng nhớ của bên gọi

Đây là trường hợp hợp lệ:

const int* tim(const int* a, int n, int x) {
    for (int i = 0; i < n; ++i) {
        if (*(a + i) == x) {
            return a + i;
        }
    }

    return nullptr;
}

Pointer trả về vẫn hợp lệ miễn là mảng gốc còn sống.

7. Không trả địa chỉ biến local

Sai:

int* tao() {
    int x = 10;
    return &x;
}

x là biến cục bộ có thời hạn lưu trữ tự động. Khi hàm kết thúc, vòng đời của x kết thúc.

Pointer trả về trở thành con trỏ treo (dangling pointer).

Không được dựa vào việc chương trình "chạy được trên máy mình" để kết luận đoạn code này hợp lệ.

Giai đoạn 5 - Con trỏ với mảng ký tự

1. Chuỗi kiểu C và ký tự kết thúc

Mảng ký tự kiểu C kết thúc bằng ký tự:

'\0'

Ví dụ:

char s[] = "ABC";

Trong bộ nhớ có bốn ký tự:

'A' 'B' 'C' '\0'

2. Duyệt chuỗi bằng pointer

const char* p = s;

while (*p != '\0') {
    cout << *p;
    ++p;
}

Điều kiện kết thúc không dựa vào kích thước pointer mà dựa vào ký tự '\0'.

3. Tính độ dài chuỗi

int doDai(const char* s) {
    const char* p = s;

    while (*p != '\0') {
        ++p;
    }

    return int(p - s);
}

Nếu p dừng đúng tại ký tự '\0' thì:

4. Chuỗi chỉ đọc và chuỗi có thể sửa

Chuỗi nằm trong mảng:

char s[] = "abc";

có thể sửa:

s[0] = 'A';

Nhưng không nên dùng pointer không const để sửa string literal.

Dùng:

const char* p = "abc";

và chỉ đọc dữ liệu.

5. Sao chép chuỗi

Khi sao chép C-string phải sao chép cả ký tự kết thúc '\0'.

void copyChuoi(char* dst, const char* src) {
    while (*src != '\0') {
        *dst = *src;
        ++dst;
        ++src;
    }

    *dst = '\0';
}

Điều kiện tiên quyết: vùng đích phải đủ chỗ cho toàn bộ ký tự và thêm một vị trí cho '\0'.

Giai đoạn 6 - Cấp phát động và vòng đời

1. Cấp phát một đối tượng

int* p = new int(10);

new tạo một đối tượng có thời hạn lưu trữ động và trả về địa chỉ của đối tượng đó.

Sử dụng:

cout << *p;

Giải phóng:

delete p;
p = nullptr;

2. Cấp phát mảng động

Khi số phần tử chỉ biết lúc chạy:

int n;
cin >> n;

int* a = new int[n];

Giải phóng đúng cặp:

delete[] a;
a = nullptr;

Quy tắc ghép cặp:

new      -> delete
new[]    -> delete[]

Không được trộn hai cặp này.

3. Duyệt mảng động

Sau:

int* a = new int[n];

ta có thể dùng số học con trỏ giống mảng liên tiếp:

for (int* p = a; p != a + n; ++p) {
    cin >> *p;
}

4. new[] không tự thay đổi kích thước

Raw dynamic array không có thao tác resize tự động.

Muốn tăng kích thước, cách cơ bản là:

cấp phát vùng mới lớn hơn

sao chép dữ liệu cần giữ

delete[] vùng cũ

cho pointer chính trỏ sang vùng mới

Mẫu C++:

int* b = new int[moi];

for (int i = 0; i < min(cu, moi); ++i) {
    b[i] = a[i];
}

delete[] a;
a = b;

Sau delete[] a cũ, mọi pointer phụ đang trỏ vào vùng nhớ cũ đều không còn hợp lệ.

5. Rò rỉ bộ nhớ

Rò rỉ bộ nhớ (memory leak) xảy ra khi vùng nhớ động vẫn tồn tại nhưng chương trình không còn giữ được pointer cần thiết để giải phóng nó.

Ví dụ sai:

int* p = new int(5);

p = new int(10);

Địa chỉ vùng đầu tiên đã bị mất trước khi delete.

Mẫu suy nghĩ:

trước khi gán đè một pointer đang sở hữu vùng nhớ:
    hỏi vùng cũ đã được delete chưa?

6. Con trỏ treo sau delete

int* p = new int(7);
int* q = p;

delete p;
p = nullptr;

Sau đó:

• đối tượng đã hết vòng đời;
• p là nullptr;
• q vẫn giữ địa chỉ cũ nhưng địa chỉ đó không còn chỉ tới một đối tượng int đang sống;
• q là dangling pointer.

Không được:

cout << *q;

Đặt p = nullptr chỉ thay đổi biến p, không tự động cập nhật mọi alias.

7. Thời hạn lưu trữ và "stack/heap"

Trong học con trỏ thường nghe:

• biến local nằm trên "stack";
• new lấy vùng nhớ từ "heap".

Đây là mô hình triển khai phổ biến và hữu ích để hình dung, nhưng chuẩn C++ quan trọng hơn ở khái niệm thời hạn lưu trữ (storage duration) và vòng đời đối tượng (object lifetime).

Điều cần nhớ:

biến local:
    thường tự kết thúc vòng đời khi rời scope

đối tượng tạo bởi new:
    tồn tại tới khi được delete phù hợp

Giai đoạn 7 - Con trỏ cấp hai và an toàn bộ nhớ

1. Con trỏ cấp hai T**

int x = 10;
int* p = &x;
int** pp = &p;

Quan hệ:

p    = địa chỉ của x
*p   = x

pp   = địa chỉ của p
*pp  = p
**pp = x

Có thể viết:

khi pp trỏ đúng tới p và p trỏ đúng tới x.

2. Sửa dữ liệu qua hai tầng dereference

**pp = 50;

khi đó x trở thành 50.

Trace:

pp
↓
p
↓
x

Mỗi dấu * đi xuống một tầng gián tiếp.

3. Cấp phát mảng trong hàm bằng int**

void taoMang(int** out, int n) {
    *out = new int[n];
}

Gọi:

int* a = nullptr;

taoMang(&a, n);

Sau lời gọi, a giữ địa chỉ vùng nhớ mới.

Bên gọi chịu trách nhiệm:

delete[] a;
a = nullptr;

4. Các lỗi con trỏ thường gặp

Con trỏ chưa khởi tạo

Sai:

int* p;
*p = 5;

p đang chứa giá trị không xác định.

Nên khởi tạo:

int* p = nullptr;

hoặc gán ngay một địa chỉ hợp lệ.

Giải tham chiếu nullptr

Sai:

int* p = nullptr;
cout << *p;

Vượt biên mảng

Sai:

int a[3];
int* p = a + 3;

cout << *p;

a + 3 là one-past nên có thể dùng làm mốc kết thúc, nhưng không được dereference.

Use-after-free

Sai:

int* p = new int(10);

delete p;

cout << *p;

delete sai loại

Sai:

int* a = new int[10];

delete a;

Đúng:

delete[] a;

Double delete

Sai:

int* p = new int(5);

delete p;
delete p;

Sau delete, không được giải phóng lại cùng đối tượng qua một pointer cũ.

5. AddressSanitizer trong GNU C++14

Trong lúc học pointer, AddressSanitizer rất hữu ích để phát hiện các lỗi như:

• truy cập vượt biên;
• use-after-free;
• một số lỗi cấp phát/giải phóng;
• truy cập bộ nhớ không hợp lệ.

Có thể biên dịch khi luyện tập:

g++ -std=c++14 -fsanitize=address,undefined -g main.cpp -o main

Sanitizer là công cụ hỗ trợ phát hiện lỗi, không thay thế việc hiểu vòng đời và tính hợp lệ của pointer.

6. Template tổng hợp mảng động bằng raw pointer

đọc n

cấp phát:
    a = new int[n]

nhập dữ liệu bằng pointer chạy

xử lý dữ liệu:
    dùng begin = a
    dùng end = a + n

nếu cần đổi kích thước:
    cấp phát vùng mới
    sao chép phần cần giữ
    delete[] vùng cũ
    cập nhật a sang vùng mới

khi không còn dùng:
    delete[] a
    a = nullptr

Đây là điểm kết thúc phù hợp của chuyên đề raw pointer cơ bản. Không cần đưa thêm linked list, cây, đồ thị hay các cấu trúc dữ liệu phức tạp để hiểu chắc con trỏ.

Ghi nhớ theo bản chất

&x lấy địa chỉ của x.

p = &x cho p trỏ tới x.

*p truy cập đối tượng mà p đang trỏ tới.

p + i di chuyển theo đơn vị phần tử cùng kiểu trong cùng một mảng hợp lệ.

a[i] tương đương *(a + i).

Khoảng [begin, end) dùng end làm mốc kết thúc và không dereference end.

Pointer truyền vào hàm vẫn được truyền theo giá trị; muốn thay pointer ở caller có thể dùng T**.

new ghép với delete.

new[] ghép với delete[].

nullptr là trạng thái không trỏ tới đối tượng nào; nó không tự phát hiện dangling pointer.

Sau khi object hết vòng đời, mọi pointer còn giữ địa chỉ cũ của object đó đều không được dereference.