Bài 24.1: Kỹ thuật xử lý mảng 1 chiều nâng cao trong C++

Mảng một chiều là một trong những cấu trúc dữ liệu cơ bản và được sử dụng rộng rãi nhất trong lập trình. Chúng ta đã quá quen thuộc với việc khai báo mảng kích thước cố định và truy xuất các phần tử bằng chỉ số. Tuy nhiên, để thực sự làm chủ mảng trong C++ và giải quyết các bài toán phức tạp hơn, chúng ta cần đi sâu vào các kỹ thuật nâng cao vượt ra ngoài những kiến thức cơ bản.

Bài viết này sẽ đưa bạn khám phá những khía cạnh mạnh mẽ hơn trong việc xử lý mảng một chiều trong C++, từ việc quản lý bộ nhớ linh hoạt cho đến việc tận dụng sức mạnh của Thư viện Chuẩn (Standard Library) để thực hiện các thao tác hiệu quả.

Vượt qua giới hạn kích thước cố định: Mảng động và `vector`

Mảng kích thước cố định (ví dụ: int arr[10];) rất đơn giản để sử dụng, nhưng chúng có một nhược điểm lớn: kích thước phải được xác định tại thời điểm biên dịch. Điều gì xảy ra nếu kích thước mảng phụ thuộc vào dữ liệu người dùng nhập vào hoặc thay đổi trong quá trình chạy chương trình? Đó là lúc chúng ta cần đến mảng động.

Cấp phát mảng động với `new[]` và `delete[]`

C++ cho phép chúng ta cấp phát bộ nhớ cho mảng trên vùng nhớ heap (vùng nhớ động) bằng toán tử new[]. Kích thước mảng có thể là một biến được xác định lúc chương trình chạy.

Ví dụ:

#include <iostream>

int main() {
    int kich_thuoc;
    cout << "Nhap kich thuoc mang: ";
    cin >> kich_thuoc;

    // Cap phat mang dong
    int* mang_dong = new int[kich_thuoc];

    // Su dung mang dong (chi mang tinh minh hoa)
    for (int i = 0; i < kich_thuoc; ++i) {
        mang_dong[i] = i * 10;
    }

    cout << "Cac phan tu mang: ";
    for (int i = 0; i < kich_thuoc; ++i) {
        cout << mang_dong[i] << " ";
    }
    cout << endl;

    // *** Quan trong: Giai phong bo nho ***
    delete[] mang_dong;
    mang_dong = nullptr; // Tranh loi con tro treo (dangling pointer)

    return 0;
}

Giải thích:

int* mang_dong = new int[kich_thuoc]; yêu cầu hệ thống cấp phát một khối bộ nhớ trên heap đủ lớn để chứa kich_thuoc số nguyên. new[] trả về địa chỉ của phần tử đầu tiên trong khối bộ nhớ đó, và chúng ta lưu địa chỉ này vào con trỏ mang_dong.
Chúng ta có thể truy cập các phần tử của mảng động bằng cách sử dụng cú pháp chỉ số (mang_dong[i]) hoặc phép toán con trỏ (*(mang_dong + i)).
Cực kỳ quan trọng: Khi không còn sử dụng mảng động nữa, bạn phải giải phóng bộ nhớ đã cấp phát bằng toán tử delete[]. Nếu không, bộ nhớ sẽ bị chiếm dụng cho đến khi chương trình kết thúc, dẫn đến tình trạng rò rỉ bộ nhớ (memory leak). Sau khi giải phóng, gán con trỏ về nullptr là một thực hành tốt để tránh sử dụng nhầm con trỏ đã bị giải phóng.

`vector` - Công cụ hiện đại và an toàn hơn

Trong C++ hiện đại, việc quản lý bộ nhớ thủ công với new[] và delete[] thường được thay thế bằng các container của Thư viện Chuẩn, mà phổ biến nhất cho mảng động là vector. vector cung cấp chức năng tương tự như mảng động nhưng tự động quản lý bộ nhớ cho bạn. Nó có thể tự động thay đổi kích thước khi cần thêm hoặc bớt phần tử.

Ví dụ:

#include <iostream>
#include <vector> // Bao gom header <vector>

int main() {
    int kich_thuoc;
    cout << "Nhap kich thuoc vector: ";
    cin >> kich_thuoc;

    // Khai bao va khoi tao vector voi kich thuoc ban dau
    vector<int> vector_dong(kich_thuoc);

    // Su dung vector
    for (int i = 0; i < kich_thuoc; ++i) {
        vector_dong[i] = i * 100;
    }

    cout << "Cac phan tu vector: ";
    for (int i = 0; i < vector_dong.size(); ++i) { // Su dung .size() de lay kich thuoc hien tai
        cout << vector_dong[i] << " ";
    }
    cout << endl;

    // Them phan tu moi (vector tu dong thay doi kich thuoc)
    vector_dong.push_back(999);
    cout << "Vector sau khi them phan tu cuoi: ";
    for (int phan_tu : vector_dong) { // Vong lap for-each tien loi
        cout << phan_tu << " ";
    }
    cout << endl;

    // Khong can delete[]! vector tu dong quan ly bo nho.

    return 0;
}

Giải thích:

vector<int> vector_dong(kich_thuoc); khai báo một vector chứa các số nguyên với kích thước ban đầu là kich_thuoc.
Bạn truy cập các phần tử tương tự như mảng truyền thống (vector_dong[i]) hoặc an toàn hơn với vector_dong.at(i) (sẽ kiểm tra lỗi ngoài phạm vi).
vector_dong.size() trả về số lượng phần tử hiện tại trong vector.
vector_dong.push_back(999); thêm một phần tử vào cuối vector. Nếu không còn đủ chỗ trong bộ nhớ đã cấp phát, vector sẽ tự động cấp phát một khối nhớ lớn hơn, sao chép dữ liệu cũ sang và giải phóng khối nhớ cũ. Đây chính là sức mạnh của nó – bạn không cần lo lắng về việc cấp phát/giải phóng thủ công.
Khi vector_dong ra khỏi phạm vi (ví dụ: khi hàm main kết thúc), bộ nhớ mà nó đang quản lý sẽ tự động được giải phóng. Điều này ngăn ngừa rò rỉ bộ nhớ và làm code của bạn an toàn hơn rất nhiều.
Việc sử dụng vòng lặp for-each (for (int phan_tu : vector_dong)) cũng là một kỹ thuật hiện đại và tiện lợi để duyệt qua tất cả các phần tử.

Trong hầu hết các trường hợp trong C++ hiện đại, bạn nên ưu tiên sử dụng vector thay vì mảng động cấp phát thủ công trừ khi có lý do rất cụ thể (ví dụ: làm việc với các API C cũ hoặc tối ưu hiệu năng cực cao trong các trường hợp đặc biệt).

Sức mạnh của Thuật toán Thư viện Chuẩn (`<algorithm>`)

Thư viện Chuẩn C++ cung cấp một tập hợp các thuật toán mạnh mẽ trong header <algorithm> có thể thực hiện các thao tác phổ biến trên các dãy phần tử (bao gồm cả mảng và vector) một cách hiệu quả và dễ đọc. Thay vì viết lại các vòng lặp phức tạp cho tìm kiếm, sắp xếp, v.v., bạn có thể sử dụng các hàm có sẵn này.

Các thuật toán này thường làm việc với iterator (bộ lặp), đại diện cho vị trí của các phần tử trong dãy. Mảng C++ thô và vector đều cung cấp iterator. Đối với mảng thô arr, arr hoặc &arr[0] là iterator tới phần tử đầu tiên, và arr + kich_thuoc là iterator tới vị trí sau phần tử cuối cùng. Đối với vector<T> vec, vec.begin() là iterator tới phần tử đầu tiên và vec.end() là iterator tới vị trí sau phần tử cuối cùng.

Dưới đây là một vài ví dụ điển hình:

Sắp xếp (Sorting)

Thuật toán sort là một trong những thuật toán được sử dụng nhiều nhất. Nó sắp xếp các phần tử trong một phạm vi theo thứ tự tăng dần mặc định.

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm> // Bao gom header <algorithm>
#include <functional> // Can cho greater

int main() {
    vector<int> so = {5, 2, 8, 1, 9, 4};

    // Sap xep tang dan
    sort(so.begin(), so.end());
    cout << "Sap xep tang dan: ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << endl; // Output: 1 2 4 5 8 9

    // Sap xep giam dan (su dung comparator)
    sort(so.begin(), so.end(), greater<int>());
    cout << "Sap xep giam dan: ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << endl; // Output: 9 8 5 4 2 1

    // Sap xep mot mang thong thuong
    int mang_thuong[] = {7, 3, 6, 2, 8};
    int n = sizeof(mang_thuong) / sizeof(mang_thuong[0]); // Tinh kich thuoc mang

    sort(mang_thuong, mang_thuong + n); // Su dung con tro lam iterator
    cout << "Sap xep mang thong thuong: ";
    for (int i = 0; i < n; ++i) {
        cout << mang_thuong[i] << " ";
    }
    cout << endl; // Output: 2 3 6 7 8

    return 0;
}

Giải thích:

sort nhận hai iterator: iterator bắt đầu và iterator kết thúc (vị trí sau phần tử cuối cùng của phạm vi muốn sắp xếp).
Với vector, chúng ta dùng vec.begin() và vec.end().
Với mảng thô arr kích thước n, phạm vi là từ arr (hoặc &arr[0]) đến arr + n.
Tham số thứ ba của sort là một hàm so sánh (comparator). Nếu không cung cấp, nó dùng toán tử < để sắp xếp tăng dần. Bạn có thể cung cấp greater<T>() (từ <functional>) hoặc một lambda function/hàm tự định nghĩa để sắp xếp theo tiêu chí khác (ví dụ: giảm dần).

Tìm kiếm (Searching)

Các thuật toán tìm kiếm giúp tìm kiếm sự xuất hiện của một giá trị hoặc một điều kiện trong dãy.

find: Tìm kiếm sự xuất hiện đầu tiên của một giá trị cụ thể.
find_if: Tìm kiếm phần tử đầu tiên thỏa mãn một điều kiện nhất định (được định nghĩa bởi một hàm hoặc lambda).

Ví dụ find:

#include <iostream>
#include <vector>
#include <algorithm> // Can cho find

int main() {
    vector<int> so = {10, 20, 30, 40, 50};
    int gia_tri_tim = 30;

    auto it = find(so.begin(), so.end(), gia_tri_tim);

    if (it != so.end()) {
        cout << "Tim thay " << gia_tri_tim << " tai vi tri (chi muc): "
                  << distance(so.begin(), it) << endl; // distance tinh khoang cach iterator
    } else {
        cout << "Khong tim thay " << gia_tri_tim << " trong vector." << endl;
    }

    gia_tri_tim = 60;
    it = find(so.begin(), so.end(), gia_tri_tim);
    if (it != so.end()) {
         cout << "Tim thay " << gia_tri_tim << " tai vi tri (chi muc): "
                  << distance(so.begin(), it) << endl;
    } else {
        cout << "Khong tim thay " << gia_tri_tim << " trong vector." << endl;
    }

    return 0;
}

Giải thích:

find nhận iterator bắt đầu, iterator kết thúc và giá trị cần tìm.
Nó trả về một iterator trỏ đến vị trí đầu tiên tìm thấy giá trị.
Nếu không tìm thấy, nó trả về iterator kết thúc (so.end()). Do đó, để kiểm tra xem có tìm thấy hay không, chúng ta so sánh giá trị trả về với iterator kết thúc.
distance(so.begin(), it) (từ <iterator>) có thể được dùng để tính chỉ mục của phần tử được tìm thấy so với phần tử đầu tiên.

Ví dụ find_if (kết hợp Lambda):

#include <iostream>
#include <vector>
#include <algorithm> // Can cho find_if
#include <string>

int main() {
    vector<string> ten = {"Alice", "Bob", "Charlie", "David", "Eve"};

    // Tim ten bat dau bang chu 'C'
    auto it = find_if(ten.begin(), ten.end(),
                           [](const string& s) { // Lambda function
                               return s.size() > 0 && s[0] == 'C';
                           });

    if (it != ten.end()) {
        cout << "Tim thay ten bat dau bang 'C': " << *it << endl; // *it lay gia tri ma iterator tro toi
    } else {
        cout << "Khong tim thay ten nao bat dau bang 'C'." << endl;
    }

    return 0;
}

Giải thích:

find_if nhận iterator bắt đầu, iterator kết thúc và một predicate (một hàm hoặc lambda trả về bool).
Nó tìm kiếm phần tử đầu tiên mà khi áp dụng predicate lên nó, kết quả là true.
Trong ví dụ này, chúng ta dùng một lambda function ([](...) { ... }) để định nghĩa điều kiện tìm kiếm: chuỗi không rỗng và ký tự đầu tiên là 'C'.

Tìm min/max

min_element và max_element tìm iterator tới phần tử nhỏ nhất và lớn nhất trong một phạm vi.

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm> // Can cho min_element, max_element

int main() {
    vector<int> diem = {85, 92, 78, 95, 88};

    // Tim diem nho nhat
    auto min_it = min_element(diem.begin(), diem.end());
    if (min_it != diem.end()) { // Luon kiem tra xem vector co rong khong
        cout << "Diem thap nhat la: " << *min_it << endl;
    }

    // Tim diem lon nhat
    auto max_it = max_element(diem.begin(), diem.end());
    if (max_it != diem.end()) {
        cout << "Diem cao nhat la: " << *max_it << endl;
    }

    return 0;
}

Giải thích:

Cả hai hàm đều trả về iterator tới phần tử min/max.
Bạn cần dùng toán tử * để lấy giá trị thực sự từ iterator.
Luôn kiểm tra iterator trả về có bằng .end() hay không (đặc biệt khi làm việc với vector rỗng) để tránh lỗi.

Loại bỏ phần tử trùng lặp (Removing Duplicates)

Một kỹ thuật phổ biến để loại bỏ các phần tử trùng lặp khỏi một vector (và giữ lại thứ tự tương đối hoặc không quan tâm thứ tự) là kết hợp sort và unique. unique di chuyển các phần tử duy nhất lên đầu phạm vi và trả về iterator tới vị trí bắt đầu của các phần tử trùng lặp. Nó không thực sự thay đổi kích thước container. Sau đó, chúng ta dùng phương thức erase của vector để xóa phần tử từ iterator đó đến cuối.

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm> // Can cho sort, unique

int main() {
    vector<int> so = {1, 3, 2, 3, 1, 4, 2, 5, 4};

    // 1. Sap xep vector (can thiet cho unique)
    sort(so.begin(), so.end());
    // so bay gio la: {1, 1, 2, 2, 3, 3, 4, 4, 5}

    // 2. Dich chuyen cac phan tu duy nhat len dau
    auto it = unique(so.begin(), so.end());
    // so bay gio la: {1, 2, 3, 4, 5, ?, ?, ?, ?}
    // it tro den vi tri cua so 3 dau tien sau so 5

    // 3. Xoa cac phan tu thua o cuoi
    so.erase(it, so.end());

    cout << "Vector sau khi loai bo trung lap: ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << endl; // Output: 1 2 3 4 5

    return 0;
}

Giải thích:

sort nhóm các phần tử giống nhau lại gần nhau.
unique duyệt qua phạm vi đã sắp xếp, giữ lại bản sao đầu tiên của mỗi giá trị duy nhất và di chuyển nó về phía đầu mảng. Nó trả về iterator tới vị trí đầu tiên của các phần tử bị "trùng lặp" (những phần tử không được giữ lại ở phía trước). Lưu ý rằng các phần tử ở cuối phạm vi sau it vẫn còn đó nhưng giá trị của chúng không còn quan trọng và có thể không phải là bản sao của các phần tử duy nhất.
so.erase(it, so.end()); là phương thức của vector thực sự xóa các phần tử trong phạm vi từ iterator it đến iterator so.end(), làm giảm kích thước của vector.

Đảo ngược thứ tự (Reversing)

reverse đảo ngược thứ tự của các phần tử trong một phạm vi.

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm> // Can cho reverse

int main() {
    vector<int> day_so = {1, 2, 3, 4, 5};

    reverse(day_so.begin(), day_so.end());

    cout << "Day so sau khi dao nguoc: ";
    for (int x : day_so) {
        cout << x << " ";
    }
    cout << endl; // Output: 5 4 3 2 1

    return 0;
}

Giải thích:

reverse chỉ đơn giản là đảo ngược thứ tự các phần tử giữa iterator bắt đầu và iterator kết thúc.

Kết hợp Lambda Functions với Thuật toán

Sức mạnh thực sự của các thuật toán trong <algorithm> lộ rõ khi bạn kết hợp chúng với lambda functions. Lambda cho phép bạn định nghĩa các hàm nhỏ, ẩn danh ngay tại chỗ để sử dụng làm predicate (kiểm tra điều kiện) hoặc comparator (định nghĩa thứ tự) cho các thuật toán. Điều này làm cho code linh hoạt và dễ đọc hơn rất nhiều so với việc viết các hàm riêng lẻ.

Chúng ta đã thấy một ví dụ với find_if. Dưới đây là một ví dụ khác với sort để sắp xếp theo tiêu chí tùy chỉnh:

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm>

struct SinhVien {
    string ten;
    double diem;
};

int main() {
    vector<SinhVien> danh_sach = {
        {"Alice", 8.5},
        {"Bob", 7.0},
        {"Charlie", 9.2},
        {"David", 8.5}
    };

    // Sap xep danh sach theo diem giam dan. Neu diem bang nhau thi sap xep theo ten tang dan.
    sort(danh_sach.begin(), danh_sach.end(),
              [](const SinhVien& a, const SinhVien& b) { // Lambda comparator
                  if (a.diem != b.diem) {
                      return a.diem > b.diem; // Sap xep theo diem giam dan
                  }
                  return a.ten < b.ten; // Neu diem bang nhau, sap xep theo ten tang dan
              });

    cout << "Danh sach sinh vien sau khi sap xep:" << endl;
    for (const auto& sv : danh_sach) {
        cout << sv.ten << " - " << sv.diem << endl;
    }

    return 0;
}

Giải thích:

Lambda function [](const SinhVien& a, const SinhVien& b) { ... } được dùng làm comparator cho sort.
Nó nhận hai đối tượng SinhVien và trả về true nếu a nên đứng trước b trong thứ tự sắp xếp.
Logic bên trong lambda định nghĩa quy tắc sắp xếp phức tạp: ưu tiên điểm cao hơn, nếu điểm bằng nhau thì xét tên theo thứ tự bảng chữ cái.

Việc sử dụng lambda function với các thuật toán chuẩn giúp code của bạn trở nên ngắn gọn, biểu cảm và mạnh mẽ hơn rất nhiều khi xử lý các tác vụ trên mảng hoặc vector.

Tổng kết

Bài viết này đã đưa bạn đi qua các kỹ thuật xử lý mảng một chiều nâng cao hơn trong C++:

Sử dụng mảng động với new[] và delete[] để có kích thước linh hoạt, nhưng nhấn mạnh tầm quan trọng của việc quản lý bộ nhớ thủ công.
Chuyển sang sử dụng vector như là giải pháp an toàn hơn và hiện đại hơn cho mảng động, nhờ khả năng tự động quản lý bộ nhớ và thay đổi kích thước.
Khai thác sức mạnh của các thuật toán trong <algorithm> để thực hiện các thao tác phổ biến (sắp xếp, tìm kiếm, loại bỏ trùng lặp, đảo ngược, v.v.) một cách hiệu quả.
Kết hợp lambda functions với các thuật toán để định nghĩa các tiêu chí tùy chỉnh cho việc tìm kiếm hoặc sắp xếp, làm cho code của bạn mạnh mẽ và linh hoạt hơn.

Làm chủ những kỹ thuật này sẽ giúp bạn giải quyết các bài toán liên quan đến mảng một chiều một cách hiệu quả và chuyên nghiệp hơn trong C++. Hãy luyện tập sử dụng vector và các thuật toán chuẩn thật nhiều, vì chúng là những công cụ không thể thiếu trong bộ công cụ của một lập trình viên C++ hiện đại.

Hướng dẫn sử dụng:

Lưu toàn bộ nội dung trên vào một file văn bản và đặt tên file có đuôi .md (ví dụ: bai_24_1_xu_ly_mang_nang_cao.md).
File này đã sẵn sàng để bạn sử dụng làm nội dung bài blog của mình, tuân thủ các yêu cầu về cấu trúc và nội dung bạn đã đưa ra.

Comments

There are no comments at the moment.