[STL] So sánh giữa Vector và List trong C++

Khi làm việc với dữ liệu, mình thường cần sử dụng các cấu trúc dữ liệu để lưu trữ và quản lý dữ liệu. Trong STL (Standard Template Library) của C++, std::vector và std::list là hai cấu trúc dữ liệu phổ biến. Mặc dù cả hai đều cung cấp khả năng lưu trữ dữ liệu, nhưng chúng có những đặc điểm khác nhau về cách thức lưu trữ và hiệu suất. Bài viết này sẽ so sánh giữa std::vector và std::list trong STL của C++, cung cấp giải thích cho mỗi điểm khác biệt và cung cấp ví dụ minh họa.

Vector trong C++

Ưu điểm:

• Truy cập ngẫu nhiên nhanh chóng: std::vector được triển khai như một mảng liên tục các phần tử, cho phép truy cập ngẫu nhiên vào bất kỳ phần tử nào với thời gian hằng số O(1).
• Thêm và xóa phần tử ở cuối vector hiệu quả: Thao tác thêm và xóa phần tử ở cuối vector chỉ mất thời gian hằng số O(1).

Nhược điểm:

• Thêm và xóa phần tử ở vị trí khác không phải cuối vector có thể chậm: Khi thêm hoặc xóa phần tử ở đầu hoặc ở giữa vector, toàn bộ vector phải được sao chép lại, có thể tốn nhiều thời gian O(n).

Ví dụ:

Bài viết này được đăng tại [free tuts .net]

#include <iostream>
#include <vector>

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

    // Truy cập ngẫu nhiên
    std::cout << "Element at index 2: " << vec[2] << std::endl;
    //freetuts.net

    // Thêm phần tử vào cuối vector
    vec.push_back(6);

    // Xóa phần tử cuối cùng của vector
    vec.pop_back();

    return 0;
}

List trong C++

Ưu điểm:

• Thêm và xóa phần tử ở bất kỳ vị trí nào hiệu quả: std::list được triển khai dưới dạng danh sách liên kết, cho phép thêm và xóa phần tử ở bất kỳ vị trí nào với thời gian hằng số O(1).
• Không cần phải di chuyển dữ liệu khi thêm hoặc xóa: Do danh sách liên kết không cần phải di chuyển các phần tử khác khi thêm hoặc xóa, giúp tăng hiệu suất.

Nhược điểm:

• Truy cập ngẫu nhiên chậm: Việc truy cập phần tử trong std::list yêu cầu phải đi qua từng nút, do đó có độ phức tạp thời gian tuyến tính O(n).

Ví dụ:

#include <iostream>
#include <list>
//freetuts.net

int main() {
    std::list<int> mylist = {1, 2, 3, 4, 5};

    // Thêm phần tử vào đầu danh sách
    mylist.push_front(0);

    // Xóa phần tử ở vị trí thứ 3
    auto it = std::next(mylist.begin(), 2);
    mylist.erase(it);

    return 0;
}

So sánh giữa Vector và List trong C++

Độ phức tạp thời gian và không gian

• Vector: Thời gian truy cập ngẫu nhiên là O(1), nhưng thêm và xóa phần tử ở vị trí bất kỳ có độ phức tạp là O(n) do cần di chuyển các phần tử. Chiếm không gian liên tục trong bộ nhớ.
• List: Thời gian truy cập ngẫu nhiên là O(n) do phải đi qua từ đầu đến vị trí cần truy cập. Thêm và xóa phần tử ở bất kỳ vị trí nào có độ phức tạp là O(1) vì không cần di chuyển các phần tử. Chiếm không gian không liên tục trong bộ nhớ vì cần lưu trữ con trỏ.

Tốc độ truy cập và tìm kiếm:

• Vector có tốc độ truy cập ngẫu nhiên nhanh hơn so với List do dữ liệu được lưu trữ liên tục trong bộ nhớ.
• Trong trường hợp tìm kiếm, cả Vector và List đều có độ phức tạp O(n) vì phải đi qua từ đầu đến cuối dữ liệu.

Thêm và xóa phần tử:

• Vector không linh hoạt trong việc thêm và xóa phần tử ở vị trí bất kỳ do độ phức tạp thời gian là O(n).
• List linh hoạt trong việc thêm và xóa phần tử ở bất kỳ vị trí nào với độ phức tạp thời gian là O(1).

Sử dụng phù hợp của Vector và List

Sử dụng Vector khi:

• Cần truy cập ngẫu nhiên đến các phần tử.
• Dữ liệu có kích thước không thay đổi và ít thao tác thêm/xóa.
• Yêu cầu không gian liên tục trong bộ nhớ.

Sử dụng List khi:

• Cần thực hiện các thao tác thêm/xóa phần tử thường xuyên ở bất kỳ vị trí nào.
• Cần tiết kiệm thời gian cho các thao tác thêm/xóa phần tử.
• Dữ liệu có thể mở rộng và thay đổi kích thước linh hoạt.

Ví dụ:

#include <iostream>
#include <vector>
#include <list>

int main() {
    // Sử dụng Vector
    std::vector<int> vec = {1, 2, 3};
    vec.push_back(4); // Thêm phần tử vào cuối Vector
    vec.erase(vec.begin() + 1); // Xóa phần tử ở vị trí thứ 2 trong Vector
     // bài viết được đăng tại freetuts.net

    // Sử dụng List
    std::list<int> li = {1, 2, 3};
    li.push_back(4); // Thêm phần tử vào cuối List
    li.erase(++li.begin()); // Xóa phần tử ở vị trí thứ 2 trong List

    return 0;
}

Trong ví dụ trên, ta có thể thấy cách sử dụng Vector và List để thêm và xóa phần tử, và sự khác biệt về độ phức tạp thời gian của từng cấu trúc dữ liệu.

Ví dụ thực hành Vector trong C++

Ví dụ về sử dụng Vector trong C++:

#include <iostream>
#include <vector>

int main() {
    // Khai báo và khởi tạo Vector
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Thêm một phần tử vào cuối Vector
    vec.push_back(6);

    // Truy cập và hiển thị các phần tử trong Vector
    std::cout << "Vector: ";
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
     //Bài viết được đăng tại freetuts.net

    // Xóa phần tử ở vị trí thứ 3 trong Vector
    vec.erase(vec.begin() + 2);

    // Hiển thị Vector sau khi xóa phần tử
    std::cout << "Vector sau khi xoa: ";
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

Kết quả:

Ví dụ về sử dụng List trong C++:

#include <iostream>
#include <list>

int main() {
    // Khai báo và khởi tạo List
    std::list<int> li = {1, 2, 3, 4, 5};

    // Thêm một phần tử vào cuối List
    li.push_back(6);

    // Truy cập và hiển thị các phần tử trong List
    std::cout << "List: ";
    for (int i : li) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    //Bài viết được đăng tại freetuts.net

    // Xóa phần tử ở vị trí thứ 3 trong List
    auto it = std::next(li.begin(), 2);
    li.erase(it);

    // Hiển thị List sau khi xóa phần tử
    std::cout << "List sau khi xoa: ";
    for (int i : li) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

Kết quả:

Trong các ví dụ trên, ta đã sử dụng Vector và List để thực hiện các thao tác thêm và xóa phần tử. Vector được sử dụng cho các trường hợp cần truy cập ngẫu nhiên và không cần thêm/xóa phần tử nhiều, trong khi List được sử dụng khi cần thêm/xóa phần tử thường xuyên ở bất kỳ vị trí nào.

Kết bài

Trong bài viết này, mình đã tìm hiểu về hai cấu trúc dữ liệu phổ biến trong STL của C++, đó là Vector và List. Chúng ta đã đi vào chi tiết về định nghĩa, tính chất, ưu điểm và nhược điểm của mỗi loại cấu trúc dữ liệu, cũng như so sánh giữa chúng dựa trên các yếu tố như độ phức tạp thời gian, tốc độ truy cập, thêm và xóa phần tử.

Thông qua các ví dụ minh họa, mình đã thấy cách sử dụng Vector và List trong các tình huống khác nhau, từ đó đưa ra quyết định về việc lựa chọn cấu trúc dữ liệu phù hợp cho mỗi bài toán cụ thể.

Tùy thuộc vào yêu cầu và đặc điểm của từng vấn đề, mình có thể lựa chọn sử dụng Vector hoặc List để tối ưu hiệu suất và tiện ích của chương trình. Hi vọng bài viết này đã cung cấp cho bạn cái nhìn tổng quan và chi tiết về sự khác biệt giữa hai cấu trúc dữ liệu quan trọng này trong STL của C++.