Cùng tìm hiểu về kiểu deque trong C++. Bạn sẽ biết khái niệm deque trong c++ là gì, cách khai báo deque trong C++, cách khởi tạo deque trong C++, cách truy cập phần tử của deque, cũng như sự khác biệt giữa vector và deque trong C++ sau bài học này.
Deque trong c++ là gì
Deque trong C++ được viết tắt bởi cụm từ double-ended-queue, là một mảng động tương tự như vector nhưng lại có khả năng thêm xóa phần tử ở cả đầu lẫn cuối mảng đó với tốc độ cao O(1)
.
Do có khả năng xử lý cả 2 đầu của mảng động nên nó còn được gọi là queue kép (hàng đợi kép) và được sử dụng làm tiêu chuẩn để xử lý mảng động trong C++.
Tương tự như vector thì deque cũng được sử dụng để xử lý mảng động, nên khác với mảng truyền thống vốn có độ dài cố định thì độ dài của deque có thể được tự động thay đổi.
Về cách sử dụng cũng như các hàm thành viên trong deque thì hầu như là giống với vector trong C++, nên bạn hãy sử dụng deque thay cho vector trong các trường hợp cần xử lý ở đầu mảng động nhé.
Lưu ý, khác với vector thì các phần tử của deque không phải lúc nào cũng được lưu trữ tại các địa chỉ liên tiếp trong bộ nhớ, vì vậy việc lấy địa chỉ của một phần tử và chuyển nó dưới dạng một con trỏ đến một hàm khác có thể gây ra sự cố trong xử lý.
Ngoài ra, ngoại trừ ưu thế có thể chèn và xóa ở gần đầu mảng của deque thì hiệu suất của deque kém hơn vector, vì vậy nếu bạn không chèn và xóa thường xuyên gần đầu mảng, bạn nên sử dụng vector.
std::deque trong C++
std::deque trong C++ là một class rất thuận tiện được sử dụng làm tiêu chuẩn để xử lý deque trong C++.
std::deque được cài sẵn trong header file deque và để sử dụng được chức năng này, chúng ta cần thêm dòng 「#include <deque> 」
vào đầu chương trình.
|
Lại nữa, namespace của std::deque là std, do đó bằng cách khai báo sử dụng namespace này vào đầu chương trình mà chúng ta có thể viết gọn std::deque trong chương trình như sau:
|
Khai báo deque trong C++
Khai báo 1 deque trong C++
Để khai báo deque trong C++, chúng ta viết dòng std::deque, sau đó viết kiểu dữ liệu giữa cặp dấu <>
, và cuối cùng là tên biến như sau:
std::deque<type>
dq;
Trong đó dq
là tên biến deque và type
là kiểu dữ liệu. Chúng ta có thể dùng bất cứ kiểu dữ liệu nào có trong C++ để khai báo type, ví dụ như char, int, double, hay cấu trúc hoặc class tự tạo chẳng hạn.
Trong trường hợp đã khai báo namespace std vào đầu chương trình, chúng ta cũng có thể lược bỏ dòng std::
và dùng cú pháp khai báo deque như sau:
using namespace std;
deque<type>
dq;
Thông thường chúng ta hay khai báo namespace std vào đầu chương trình để sử dụng tới các chức năng thông dụng khác như nhập xuất chẳng hạn, nên trong 2 phương pháp khai báo deque ở trên thì phương pháp thứ 2 thường được sử dụng nhiều hơn.
Lưu ý deque được khai báo với cú pháp này sẽ có 0 phần tử bên trong nó. Sau khi khai báo deque kiểu này, chúng ta có thể sử dụng các hàm thành viên để có thể thêm phần tử vào nó sau này.
Ví dụ cụ thể:
|
Ngoài ra cách viết sử dụng cặp dấu <>
như trên được viết theo cú pháp khi sử dụng chức năng template của C++ mà chúng ta sẽ cùng học trong các chuyên đề sau.
Khai báo deque trong C++ bao gồm chỉ định số phần tử
Mặc dù kiểu deque trong C++ là loại mảng động có khả năng tự thay đổi kích thước, tuy nhiên trong trường hợp không chỉ định rõ kích thước của nó, thì việc xử lý nó trong chương trình sẽ tiêu tốn thời gian nhiều hơn so với khi biết kích thước cụ thể của nó.
Bởi vậy nếu đã biết kích thước trước của một deque, chúng ta nên chỉ định độ dài (số phần tử) khi khai báo nó, với cú pháp sau đây:
std::deque<type>
dq(length);
Trong đó length
chính là độ dài(số phần tử() của deque cần tạo.
Với cách khai báo deque này thì các phần tử trong deque sẽ được gán giá trị mặc định tùy thuộc vào kiểu dữ liệu sử dụng.
Ví dụ, nếu dùng kiểu số như int, double thì các phần tử sẽ có giá trị mặc định bằng 0 như sau:
/*Khai báo deque dq kiểu số*/ |
Tuy nhiên nếu dùng kiểu chữ như char, deque thì các phần tử sẽ có giá trị mặc định bằng Null được biểu diễn bởi trống khi in ra màn hình như sau:
/*Khai báo deque dq kiểu chữ*/ |
Khai báo đồng thời nhiều deque trong C++
Trong trường hợp cần khai báo đồng thời nhiều deque trong C++, chúng ta viết các tên các biến cách nhau bởi dấu phẩy vào đằng sau std::deque
với cú pháp sau đây:
using namespace std;
deque<type>
name1, name2, name3, ...
;
Ví dụ cụ thể:
|
Gán deque trong C++
Sau khi đã khai báo deque trong C++, tương tự như với mảng thông thường thì chúng ta có thể tiến hành gán giá trị vào biến deque đó bằng cách truy cập vào từng phần tử trong deque và gán giá trị vào như sau đây:
dq[index] = value ;
Trong đó dq
là tên biến deque, index
là vị trí phần tử cần gán giá trị và value
là giá trị gán vào phần tử đó.
Ví dụ:
|
Ngoài ra, chúng ta cũng có thể sử dụng một số hàm thành viên để gán giá trị, hoặc reset toàn bộ giá trị cho deque trong C++.
Khởi tạo deque trong C++
Khởi tạo deque trong C++ với các phần tử riêng biệt
Ngoài cách khai báo rồi gán giá trị cho deque thì chúng ta cũng có thể khởi tạo deque và gán luôn giá trị ban đầu cho biến deque đó.
Chúng ta khởi tạo deque trong C++ cách sử dụng cặp dấu ngoặc {}
với cú pháp sau đây:
std::deque<type>
dq {value1, value2, value3, ...
};
Trong đó
type
là kiểu dữ liệudq
là tên biến dequevalue
là các giá trị của deque
Ví dụ:
std::deque<string> user{"Kiyoshi", "male", "Tokyo"}; |
Khởi tạo deque trong C++ với các phần tử giống nhau
Chúng ta cũng có thể khởi tạo deque với các phần tử có giá trị giống nhau, với cú pháp sau đây:
std::deque<type>
dq(length, value);
Trong đó length
là số phần tử(độ dài), và value
là giá trị sử dụng để khai báo đồng loạt các phần tử của deque cần tạo.
Ví dụ:
//Khởi tạo deque dq kiểu int gồm 5 phần tử có giá trị bằng 8 |
Khai báo deque 2 chiều trong C++
Giống như mảng thì chúng ta cũng có thể sử dụng deque đa chiều trong C++, và loại deque đa chiều hay được sử dụng đó chính là deque 2 chiều trong C++.
Để khai báo deque 2 chiều trong C++ cũng như các loại deque đa chiều khác, chúng ta sử dụng tới cú pháp sau đây:
using namespace std;
deque<deque<type> >
dq {l1, l2, l3, ...
};
Trong đó:
dq
là tên biến deque 2 chiềul
là các deque 1 chiều được sử dụng như phần tử của deque 2 chiều
Lưu ý, chúng ta cần phải viết thêm dấu cách giữa cặp dấu > >
khi khai báo deque 2 chiều. Lý do là để phân biệt với toán tử >>
được sử dụng để dịch chuyển bit trong C++.
Ví dụ cụ thể:
|
Chúng ta cũng có thể khởi tạo các deque 1 chiều trước rồi dùng chúng để khai báo deque 2 chiều như sau:
|
Truy cập phần tử trong deque C++
Sau khi khai báo, khởi tạo và gán giá trị cho deque, chúng ta có thể truy cập tới các phần tử trong deque đó thông qua index của phần tử như sau:
dq[index];
Trong đó dq
là tên biến deque và index
là vị trí của cần truy xuất.
Ví dụ:
|
Kết quả:
Kiyoshi |
Duyệt deque trong C++
Để duyệt deque trong C++, chúng ta có thể sử dụng tới 1 trong 3 phương pháp mà Kiyoshi đã giới thiệu trong bài Duyệt deque trong C++.
Ví dụ, chúng ta có thể truy cập vào phần tử của deque 1 chiều thông qua vòng lặp dựa trên phạm vi như sau:
|
Kết quả:
Kiyoshi |
Tượng tự khi chúng ta cần truy cập vào phần tử trong deque 2 chiều trong C++:
|
Và kết quả:
Honda |
Vector vs deque trong C++
Như đã phân tích ở trên thì sự khác biệt lớn nhất giữa vector và deque trong C++ đó chính là ở deque có khả năng thêm xóa phần tử ở gần đầu mảng, còn vector thì không.
Ngoài ra thì các phần tử trong vector được lưu trong các địa chỉ liên tục trong bộ nhớ, còn trong deque thì không phải lúc nào cũng vậy.
Lại nữa, tốc độ xử lý của vector được cho là tốt hơn deque, nên ngoại trừ trường hợp cần thêm xóa phần tử ở gần đầu mảng thì thông thường chúng ta sử dụng vector để xử lý các mảng động trong C++.
Tổng kết
Trên đây Kiyoshi đã hướng dẫn bạn về deque trong C++ rồi. Để nắm rõ nội dung bài học hơn, bạn hãy thực hành viết lại các ví dụ của ngày hôm nay nhé.
Và hãy cùng tìm hiểu những kiến thức sâu hơn về C++ trong các bài học tiếp theo.
URL Link
https://laptrinhcanban.com/cpp/lap-trinh-cpp-co-ban/deque-trong-cpp/deque-trong-cpp-la-gi/
HOME › lập trình c++ cơ bản dành cho người mới học lập trình>>19. deque trong c++