Làm Thế Nào Để Tạo Vector Trong C++

Đã bao giờ bạn thắc mắc vector được tạo như thế nào, hoạt động ra sao chưa? Nếu chưa thì cùng tìm hiểu với mình nhé! Trong bài viết này mình sẽ trình bày cho các bạn biết cách tạo một vector mà chúng ta vẫn hay sử dụng trong thư viện có sẵn #include <vector> và ở đây mình sẽ cài đặt chúng bằng một template class.

#include <bits/stdc++.h>
using namespace std;

template <typename T>
class Vector{
private:
	int size;   // bien luu do dai cua vector
	int capacity;   // bien luu dung luong cua vector
	T *array;  // tao con tro chua mang
	void expand(int newCapacity); // ham tang dung luong vector 
public:
	Vector(int initCapacity = 100) {}  // ham tao vector
	~Vector() {} // ham huy vector
	Vector & operator=(Vector & rhs); //  ham nap chong toan tu gan 
	int Size(); // ham tra ve kich thuoc
	bool empty(); // ham kiem tra vector giong
	T & operator[](int index);  // ham nap chong toan tu truy cap chi so vector
	void push_back(T newElement); // ham day phan tu vao cuoi vector
	void pop_back();  //ham xoa phan tu cuoi vector
	void insert(int pos, T newElement); // ham them phan tu vao vi tri pos
	void erase(int pos); //ham xoa phan tu tai vi tri pos
        void clearn(); // ham xoa tat ca cac phan tu vector	
};

int main()
{
	
	return 0;
 }

Các thuộc tính của vector

Đầu tiên về phần thuộc tính ở đây mình có dùng các thuộc tính là:

size - độ dài hiện có của vector hay còn gọi là kích thước, ví dụ vector có 5 phần tử 1 2 3 4 5 thì size = 5;

T *array - con trỏ tới mảng (T ở đây sẽ phụ thuộc vào kiểu dữ liệu chúng ta truyền vào)

capacity - chứ dung lượng tối đa của mảng, ví dụ tạo 1 mảng có 100 phần tử thì capacity = 100 

Lưu ý: ở đây chúng ta cần phải phân biệt được độ dài của vector hiện có, và dung lượng tối đa mà vector có thể dùng.

Sau đây mình xin được giải thích và định nghĩa đầy đủ lần lượt các phương thức như sau:

0. Ta có hàm: void expand(int newCapacity); hàm này được đặt trong phạm vi private nhằm mục đích không cho các đối tượng bên ngoài truy xuất bừa bãi cấp phát bộ nhớ cho mảng, cụ thể hàm được định nghĩa như sau: 

void expand(int newCapacity)
	{ 
	    if (newCapacity <= size)
	        return;
	
	    T * old = array;            // old tro toi mang cu
	    array = new T[newCapacity]; // array tro toi mang moi
	    
	    for (int i = 0; i < size; i++)
	        array[i] = old[i];      // sao chep phan tu tu mang cu sang mang moi
	    
		delete[] old;               // xoa mang cu
	    capacity = newCapacity;     // dat dung luong moi
	}

Hàm expand có tác dụng là tăng dung lượng của vector.

Khi ta truyền một tham số là newCapacity ( newCapatcity là biến chứa dung lượng mới của vector) thì đầu tiên ta sẽ so sánh độ dài mới cần thêm vào với độ dài hiện của của vecotr nếu độ dài cần cấp phát thêm nhỏ hơn độ dài hiện có của vector thì ta không thực hiện tăng dung lượng của vector nữa.

Trong trường hợp mà độ dài cần thêm lớn hơn độ dài hiện có của vector ta có ý tưởng thêm như sau:

Tạo một mảng con trỏ khác có tên là old lưu tất cả các giá trị hiện có của mảng con trỏ array, rồi ta tiến hành bước tiếp theo là cấp phát cho mảng array có newCapacity phần tử.

Sau khi tăng dung lượng của mảng array ta tiến hành sao chép các phần tử từ mảng old sang mảng array vừa thêm dung lượng.

Cuối cùng ta cần phải giải phóng bộ nhớ của mảng old để tránh lãng phí bộ nhớ, và kết thúc bằng câu lệnh cập nhật dung lượng hiện có của mảng capacity = newCapacity;

Xét tới các phương thức nằm trong phạm vi public:

1. Hàm tạo, ở đây mình có sử dụng biến initCapacity = 100 để khởi tạo sẵn cho vector có 100 phần tử khi chúng ta khai báo vector dạng: vector<int> a; thì vector a sẽ có dung lượng bằng 100, nếu ta khai báo vector dạng: vector<double> arr(10); thì biến initCapacity sẽ được gán = 10 và arr sẽ có dung lượng = 10.
   Hàm tạo được định nghĩa như sau:
   

   Vector(int initCapacity = 100)
   	{
   	    size = 0;
   	    capacity = initCapacity;
   	    array = new T[capacity];
   	}

   Biến size = 0 để gán cho vector đang giỗng và chưa chứa phần tử nào, câu lệnh capacity = initCapacity để cập nhật dung lượng hiện có của vector và tiếp theo chúng ta thực hiện câu lệnh array = new T[capacity]; để cấp phát bộ nhớ cho mảng array có dung lượng là capacity và kiểu dữ liệu T.

2. Hàm hủy, do hàm hủy không thể tự động giải phóng bộ nhớ của con trỏ  hay mảng con trỏ được, vì vậy  ở class Vector hàm hủy bắt buộc phải có câu lệnh giải phóng bộ nhớ, cụ thể như sau:
   

   ~Vector() 
   	{
   	    delete[] array;
   	}​

   Lưu ý: delete [] dùng để giải phóng mảng con trỏ, còn delete để giải phóng bộ nhớ của một con trỏ.
   Tại sao chúng ta phải giải phóng bộ nhớ cho mảng? Như các bạn đã biết khi ta cấp phát một mảng con trỏ tức là ta đã lấy ra ở ram rất nhiều địa chỉ, sau mỗi lần lấy ra lặp đi lặp lại thì ram sẽ báo lỗi thiếu bộ nhớ và máy tính sẽ không thể thực hiện được nữa vì vậy để tránh tình trạng thiếu địa chỉ và dư thừa các địa chỉ không được dùng tới nữa ta nên giải phóng chúng sau mỗi lần chạy.

3. Hàm nạp chồng toán tử gán một ngôi, class Vector là một lớp do chúng ta định nghĩa nên chúng không thể sử dụng phép gán thông thường như chúng ta thường gán các biến với nhau được, vì vậy muốn gán 2 vector cho nhau chúng ta cần phải nạp chồng toán tử gán, cụ thể như sau:
   

   Vector & operator=(Vector & rhs) 
   	{
   	    if (this != &rhs) // ngan can tu sao chep
   		{
   	        delete[] array;          // xoa mang hien tai
   	        size = rhs.size;         // dat kich thuoc moi
   	        capacity = rhs.capacity; // dat dung luong moi
   	        array = new T[capacity]; // tao mang moi
   	        
   			// Sao chep cac phan tu tu phai sang trai
   	        for (int i = 0; i < size; i++)
   	            array[i] = rhs.array[i];
   	    }
   	    
   	    return *this; // tra ve vector ve trai sau khi gan xong
   	}​

   Giả sử ta có 2 vector a,b và sử dụng phép gán a = b;
   Nhìn vào hàm ta thấy Vector & operator = dấu '&' ở đây cho ta biết rằng vector a có thể bị sửa đổi thông tin, và có một thêm một tham chiếu là Vector & rhs dùng để tượng trưng cho b.
   Đầu tiên ta phải so sánh địa chỉ của 2 vector a,b; this - biểu thị cho địa chỉ của vector a và &rhs - biểu thị cho địa chỉ của vector b, nếu chúng khác nhau thì ta bắt đầu thực hiện lần lượt các thao tác:
   Đầu tiên giải phóng bộ nhớ của mảng hiện tại (tức là mảng a).
   Tiếp theo cập nhật độ dài và dung lượng mới cho mảng a theo mảng b: size = rhs.size; capacity = rhs.capacity; 
   Sau đó các bạn cấp phát động bộ nhớ mới cho mảng a với cú pháp array = new T[capacity]; và sử dụng vòng lặp để sao chép các phần tử của b sang a;
   Cuối cùng ta trả về vector a, với câu lệnh return *this; lưu ý this  tượng trưng cho địa chỉ và *this tức là trả về giá trị của địa chỉ.
   Ở đây mình chỉ giải thích code nên các bạn chú ý đọc kĩ code trước rồi đọc phần chữ mình giải thích ở dưới và trên code mình cũng chú thích rất rõ ràng các câu lệnh.

4. Hàm trả về độ dài của vector:
   

   int Size() 
   	{
   	    return size;
   	}​

5. Hàm kiểm tra vector rỗng:
   

   	bool empty() 
   	{
   	    return (size == 0);
   	}​

   Do kết quả của phép so sánh size == 0 là true or false nên ta chỉ cần return(size == 0); thay vì dùng if else

6. Hàm nạp chồng toán tử truy cập chỉ số của vector:
   

   	T & operator[](int index) 
   	{
   	    return array[index];
   	}​

   Do C++ có cung cấp sẵn truy cập trực tiếp chỉ số của mảng, mà vector là một mảng động nên ở đây chúng ta chỉ cần return array[index];

7. Hàm thêm một giá trị vào cuối vector:
   

   	void push_back(T newElement) 
   	{
   	    // Gap doi dung luong neu vector day
   	    if (size == capacity)
   	        expand(2 * size);
   	    
   	    // Chen phan tu moi vao ngay sau phan tu cuoi cung
   	    array[size] = newElement;
   	
   	    // Tang kich thuoc
   	    size++;
   	}​

   Ta có tham số là một biến newElement với kiểu dữ liệu T.
   Muốn thêm một số vào cuối của vector đầu tiên ta cần phải kiểm tra dung lượng của vector đó đã đầy hay chưa, nếu đầy ta cần phải cấp phát thêm bộ nhớ cho vector.
   Do chỉ số phần tử đầu tiên của vector là 0, nên phần tử cuối cùng của vector sẽ là size -1 , vì vậy khi thêm một phần tử vào cuối vector ta chỉ cần thực hiện câu lệnh array[size] = newElement; (vị trí size nằm sau size -1 nên nó là vị trí cuối của vector)
   Sau khi thêm một phần tử vào vector ta cần phải cập nhật bộ độ dài của vector là size++;

8. Hàm xóa phần tử cuối cùng của vector:
   

   	void popBack() 
   	{
   	    size--;
   	}​

   Phần tử cuối cùng là array[size], nên khi xóa phần tử cuối cùng ta chỉ cần giảm độ dài của vector đi 1.

9. Hàm thêm phần tử vào vị trí pos với giá trị là newElement:
   

   	void insert(int pos, T newElement)
   	{
   	    // Gap doi dung luong neu vector day
   	    if (size == capacity)
   	        expand(2 * size);
   	    
   		// Dich cac phan tu sang phai de tao cho trong cho viec chen
   	    for (int i = size; i > pos; i--)
   	        array[i] = array[i - 1];
   	        
   	    // Dat phan tu moi vao vi tri chen
   	    array[pos] = newElement;
   	    
   	    // Tang kich thuoc
   	    size++;
   	}​

   Giống như khi thêm một phần tử vào cuối vector đầu tiên ta cần phải kiểm tra dung lượng của vector hiện có: if(size == capacity)
   Bản chât thêm một phần tử vào vector chính là thêm một phần tử vào mảng cho nên phần này mình không giải thích kĩ, các bạn nhìn comment code rồi tự test bằng tay nhé :D
10. Hàm xóa phần tử tại vị trí pos
    

    	void erase(int pos)
    	{
    	    // Dich cac phan tu sang trai de lap day cho trong de lai do viec xoa
    	    for (int i = pos; i < size - 1; i++)
    	        array[i] = array[i + 1];
    	
    	    // Giam kich thuoc
    	    size--;
    	}​

    Giống như mình nói ở trên bản chất của vector là một mảng, cho nên xóa phần tử tại vị trí pos cũng giống như xóa một phần tử ở mảng thông thường, các bạn đọc code và comment rồi tự test bằng tay nhé :D

11. Hàm xóa tất cả phần tử của vector:
    

    	void clear() 
    	{
    	    size = 0;
    	}​

    Độ dài thể hiện cho vector đó có bao nhiêu phần tử, vì thế khi muốn xóa tất cả phần tử của vector ta chỉ cần cho độ dài của vector bằng không tức là size = 0;

Xét hàm main:

int main()
{
	vector<int> a;
	a.push_back(1);
	a.push_back(2);
	a.pop_back();
	a.insert(0,2);
	a.clearn();
	return 0;
 }

Do chúng ta cài đặt vector bằng một template class, nên khi khởi tạo vector a chúng ta cần phải xác định kiểu dữ liệu cho vector: vector<int> a;
Khi các bạn đã học class trong C++, ta được biết một đối tượng gọi phương thức của nó ra ta sẽ dùng toán tử '.' để gọi, ví dụ a.push_back(1); thì đối tượng ở đây là a và phương thức được gọi trong class là push_back(T newElement);
Tương tự với các phương thức còn lại.

Độ Phức Thuật Toán của mỗi phương thức:

• Hàm tạo: O(1)
• Hàm hủy: O(1)
• Hàm thêm dung lượng vector: O(n)
• Hàm nạp chồng toán tử gán: O(n)
• Hàm trả về kích thước vector: O(1)
• Hàm kiểm tra vector giỗng: O(1)
• Hàm nạp chồng toán tử []: O(1)
• Hàm thêm phần tử vào cuối vector: O(1) khi vector còn dung lượng, O(n) khi vector hết dung lượng.
• Hàm xóa phần tử cuối vector: O(1)
• Hàm chèn phần tử vào vị trí pos: O(n)
• Hàm xóa tất cả phần tử vector: O(1)
• Hàm xóa phần tử tại vị trí pos: O(n)

Tổng Kết

Trong bài này mình chỉ đưa ra một số phương thức cơ bản để minh họa lớp vector được tạo như thế nào. Mong các bạn đọc bài viết xong có thể hiểu cách tạo, hoạt động của một vector và góp ý để giúp mình hoàn thiện bài viết hơn.

Cảm ơn tất cả các bạn đã đọc, hẹn gặp lại các bạn vào bài kế tiếp!