C/C++

C++ containers

[NỘI DUNG BÀI VIẾT ĐƯỢC CẬP NHẬT LIÊN TỤC]

Xin chào, bài viết này sẽ giới thiệu về các Standard Containers của C++ như: vector, list, array, deque, stack, queue, map, set, …


VECTOR

Có thể coi vector như một mảng động với các phần tử được lưu trữ ở một vùng nhớ liên tục. Với đặc điểm đó, vector rất phù hợp cho các ứng dụng cần truy xuất ngẫu nhiên (Random Access) và các thao tác như sort, search, find, count. Tuy nhiên, khi có số lượng phần tử lớn, các thao tác insert/erase trong vector rất chậm.

  • Khởi tạo vector

+ Khởi tạo một vector rỗng (mặc định):

std::vector<data-type> name;

+ Khởi tạo một vector với số lượng phần tử cho trước:

std::vector<data-type> name(n, value);

+ Khởi tạo một vector từ một số phần tử của một container C khác:

std::vector<data-type> name(C.begin(), C.end());

+ Khởi tạo một vector bằng cách copy một vector V khác:

std::vector<data-type> name(V);

Trong đó:
data-type – kiểu dữ liệu chuẩn hoặc kiểu dữ liệu tự tạo (struct, class);
C.begin(), C.end() – iterator trỏ đến phần tử đầu tiên và phần tử đứng sau phần tử cuối cùng của container C.

  • Truy cập vào vector

+ Truy cập bằng chỉ số: sử dụng kiểu dữ liệu std::vector<data-type>::size_type và function size();
+ Truy cập bằng iterator: sử dụng kiểu dữ liệu std::vector<data-type>::iterator hoặc std::vector<data-type>::const_iterator; được dùng để truy xuất ngẫu nhiên và truy xuất tuần tự;
+ Truy cập bởi vòng lặp range-for: được dùng để truy xuất tuần tự.

  • Các function cơ bản

+ iterator begin() – trả về iterator trỏ đến phần tử đầu tiên của vector;
+ iterator end() – trả về iterator trỏ đến phần tử đứng sau phần tử cuối cùng của vector;
+ void push_back() – thêm một phần tử vào cuối vector;
+ size_type size() – trả về số lượng phần tử của vector;
+ bool empty() – trả về true nếu vector rỗng;
+ iterator insert(d, b, e) – copy các phần tử được trỏ bởi các iterators b và e vào phía trước iterator d; trả về iterator trỏ đến phần tử đầu tiên được chèn vào;
+ iterator erase(it), iterator erase(b, e) – xóa phần tử it hoặc các phần tử được trỏ bởi các iterators b và e; trả về iterator trỏ đến phần tử nằm ngay sau phần tử đã bị xóa;
+ void resize(n) – resize kích thước của vector về n phần tử.

Example:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> data;
    for (int i = 0; i < 10; i++)
    	data.push_back(i);

    cout << "Access via index: ";
    for (vector<int>::size_type i = 0; i < 5; i++)
    	cout << data[i] << ' ';
    cout << endl;

    cout << "Access via iterator: ";
    for (vector<int>::iterator it = data.begin()+5; it < data.end(); it++)
    	cout << *it << ' ';
    cout << endl;

    cout << "Access via range-for loop: ";
    for (const auto& e : data)
    	cout << e << ' ';
    cout << endl;

    return 0;
}

Output:
Access via index: 0 1 2 3 4
Access via iterator: 5 6 7 8 9
Access via range-for loop: 0 1 2 3 4 5 6 7 8 9

Tham khảo: std::vector


LIST

List là một danh sách liên kết đôi, rất phù hợp cho các ứng dụng cần truy xuất tuần tự (Sequential Access) và đặc biệt nhanh khi cần thực hiện các thao tác insert/erase khi số lượng phần tử lớn.

  • Khởi tạo list

+ Khởi tạo một list rỗng (mặc định):

std::list<data-type> name;

+ Khởi tạo một list với số lượng phần tử cho trước:

std::list<data-type> name(n, value);

+ Khởi tạo một list từ một số phần tử của một container C khác:

std::list<data-type> name(C.begin(), C.end());

+ Khởi tạo một list từ bằng cách copy một list L khác:

std::list<data-type> name(L);

Trong đó:
data-type – kiểu dữ liệu chuẩn hoặc kiểu dữ liệu tự tạo (struct, class);
C.begin(), C.end() – iterator trỏ đến phần tử đầu tiên và phần tử đứng sau phần tử cuối cùng của container C.

  • Truy cập vào list

+ Truy cập bằng iterator: sử dụng kiểu dữ liệu std::list<data-type>::iterator hoặc std::list<data-type>::const_iterator; được dùng để truy xuất ngẫu nhiên và truy xuất tuần tự;
+ Truy cập bởi vòng lặp range-for: được dùng để truy xuất tuần tự.

  • Các functions cơ bản

Ngoài các function cơ bản như của vector, list có thêm:
+ void push_front() – thêm một phần tử vào đầu list;
+ void sort(), void sort(compFunc) – sắp xếp các phần tử của list theo quy định ở compFunc.

Tham khảo: std::list

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s