std::deque

#include <deque>

Container std::deque (Double-Ended Queue) trong C++ là một container tuần tự (sequence container) cho phép chèn và xóa phần tử hiệu quả ở cả hai đầu. Container std::deque thuộc thư viện chuẩn C++ và được định nghĩa trong header <deque>.

template <class T, class Alloc = allocator<T>> class deque;

Tham số

T

• Kiểu dữ liệu của các phần tử trong deque.

Alloc

• Kiểu cấp phát bộ nhớ, mặc định là std::allocator<T>. Thường bạn không cần quan tâm đến tham số này.

deque

• Tên của deque bạn muốn tạo.

Đặc điểm

1. Hỗ trợ thao tác hai đầu:
   • Cho phép chèn/xóa nhanh ở cả hai đầu (đầu và cuối) với độ phức tạp trung bình O(1).
   • Thao tác chèn/xóa giữa các phần tử có độ phức tạp O(n).
2. Kích thước của std::deque có thể thay đổi động.
3. Truy cập phần tử nhanh:
   • Truy cập ngẫu nhiên tới các phần tử với độ phức tạp O(1), tương tự như std::vector.
4. Cấu trúc bộ nhớ linh hoạt:
   • Không lưu trữ dữ liệu trong một khối liên tục như std::vector.
   • Được tổ chức thành nhiều khối nhỏ để quản lý linh hoạt hơn khi thêm/xóa.
5. Hiệu năng:
   • Phù hợp khi cần chèn/xóa cả ở đầu và cuối dãy.
   • Kém hiệu quả hơn std::vector khi chỉ cần thao tác ở cuối hoặc cần duy trì bộ nhớ liên tục.
6. Không có capacity() và reserve():
   • std::deque không có các hàm capacity() và reserve() như std::vector. Việc quản lý bộ nhớ được thực hiện tự động và linh hoạt hơn.
7. Có thể làm thay đổi iterator:
   • Các thao tác chèn hoặc xóa phần tử trong std::deque có thể làm thay đổi (invalidate) các iterator đang trỏ đến các phần tử khác trong deque, ngoại trừ chèn hoặc xóa ở cuối deque.
8. Khi nào nên sử dụng std::deque:
   • Khi bạn cần thường xuyên chèn và xóa phần tử ở cả hai đầu.
   • Khi bạn cần truy cập ngẫu nhiên các phần tử.
   • Khi bạn không biết trước số lượng phần tử tối đa, nhưng cần hiệu suất chèn/xóa ở hai đầu tốt hơn std::vector.

Ví dụ:

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {1, 2, 3};

    // Thêm phần tử
    dq.push_front(0);
    dq.push_back(4);

    // Xóa phần tử
    dq.pop_front();
    dq.erase(dq.begin() + 1);

    // Truy cập và duyệt
    for (int val : dq) {
        std::cout << val << " ";
    }

    return 0;
}

Các cách phổ biến khai báo và khởi tạo một std::deque

1. Khai báo deque rỗng:

   Khai báo một deque mà không khởi tạo bất kỳ phần tử nào.

   std::deque<int> dq;           // deque rỗng lưu số nguyên
   std::deque<std::string> dq2;  // deque rỗng lưu chuỗi

2. Khởi tạo với số lượng và giá trị mặc định:

   std::deque<int> dq(5);        // deque có 5 phần tử, giá trị mặc định là 0
   std::deque<int> dq2(5, 10);   // deque có 5 phần tử, giá trị mặc định là 10

3. Khởi tạo từ danh sách khởi tạo (initializer list):

   Sử dụng phương thức fill() để gán tất cả phần tử bằng cùng một giá trị sau khi khai báo.

   std::deque<int> dq = {1, 2, 3, 4, 5};
   std::deque<std::string> dq2{"A", "B", "C"};

4. Sao chép từ deque khác:

   std::deque<int> originalDeque = {1, 2, 3};
   std::deque<int> copiedDeque(originalDeque); // Sao chép từ originalDeque

5. Khởi tạo từ một phạm vi (range):

   Sử dụng các iterator để khởi tạo từ phạm vi của một container khác.

   std::vector<int> vec = {1, 2, 3, 4};
   std::deque<int> dq(vec.begin(), vec.end()); // Khởi tạo từ vector

6. Khởi tạo với constructor di chuyển:

   Di chuyển tài nguyên từ một deque khác, thường khi deque ban đầu không còn cần thiết.

   std::deque<int> originalDeque = {1, 2, 3};
   std::deque<int> movedDeque(std::move(originalDeque)); // originalDeque giờ rỗng

7. Khởi tạo bằng con trỏ hàm hoặc generator:

   Sử dụng std::generate để khởi tạo deque với giá trị từ hàm generator.

   #include <deque>
   #include <algorithm>
   #include <iostream>
   
   int main() {
       std::deque<int> dq(5); // deque có 5 phần tử
       int value = 0;
       std::generate(dq.begin(), dq.end(), [&value]() { return value++; });
   
       for (int num : dq) {
           std::cout << num << " "; // In ra: 0 1 2 3 4
       }
   
       return 0;
   }

8. Khởi tạo từ một mảng tĩnh:

   Sử dụng constructor phạm vi để khởi tạo deque từ một mảng tĩnh.

   int arr[] = {1, 2, 3, 4};
   std::deque<int> dq(std::begin(arr), std::end(arr));

9. Khai báo std::deque với kiểu tùy chỉnh:

   Dùng với các kiểu dữ liệu tự định nghĩa như struct hoặc class.

   struct Student {
       std::string name;
       int age;
   };
   
   std::deque<Student> students = {{"Alice", 20}, {"Bob", 22}};

10. Khởi tạo với điều kiện mặc định:

    Dùng vòng lặp để khởi tạo deque khi cần logic phức tạp.

    std::deque<int> dq;
    for (int i = 1; i <= 5; ++i) {
        dq.push_back(i * 2); // Khởi tạo: 2, 4, 6, 8, 10
    }

Các kiểu dữ liệu đặc biệt của std::deque

lưu ý

Ngoài các kiểu dữ liệu cơ bản như int, float, double,... std::deque còn có thể lưu trữ bất kỳ kiểu dữ liệu hợp lệ nào trong C++ như struct, class, con trỏ, con trỏ thông minh, container lồng nhau, enum, tuple và pair.

1. Structs (Cấu trúc):

   #include <deque>
   #include <iostream>
   #include <string>
   
   struct Student {
       std::string name;
       int age;
   };
   
   int main() {
       std::deque<Student> students = {{"Alice", 20}, {"Bob", 22}};
   
       students.push_back({"Charlie", 25});
   
       for (const auto& student : students) {
           std::cout << student.name << " (" << student.age << ")\n";
       }
   
       return 0;
   }

2. Classes (Lớp):

   std::deque có thể chứa các đối tượng của một lớp. Nếu lớp có tài nguyên động, hãy đảm bảo sử dụng constructor sao chép hoặc di chuyển phù hợp.

   #include <deque>
   #include <iostream>
   #include <string>
   
   class Car {
   public:
       std::string brand;
       Car(std::string b) : brand(std::move(b)) {}
       void display() const { std::cout << "Car: " << brand << "\n"; }
   };
   
   int main() {
       std::deque<Car> cars;
       cars.emplace_back("Toyota");
       cars.emplace_back("Ford");
   
       for (const auto& car : cars) {
           car.display();
       }
   
       return 0;
   }

3. Pointers:

   #include <deque>
   #include <iostream>
   
   int main() {
       std::deque<int*> dq;
   
       // Khởi tạo con trỏ
       for (int i = 0; i < 5; ++i) {
           dq.push_back(new int(i));
       }
   
       // Sử dụng và giải phóng bộ nhớ
       for (int* ptr : dq) {
           std::cout << *ptr << " ";
           delete ptr; // Giải phóng bộ nhớ
       }
   
       return 0;
   }

4. Smart Pointers (Con trỏ thông minh):

   #include <deque>
   #include <memory>
   #include <iostream>
   
   int main() {
       std::deque<std::shared_ptr<int>> dq;
   
       for (int i = 0; i < 5; ++i) {
           dq.push_back(std::make_shared<int>(i));
       }
   
       for (const auto& sp : dq) {
           std::cout << *sp << " ";
       }
   
       return 0;
   }

5. Containers lồng nhau (Nested Containers):

   Một std::deque có thể chứa các container khác như std::vector, std::deque, hoặc std::set.

   #include <deque>
   #include <vector>
   #include <iostream>
   
   int main() {
       std::deque<std::vector<int>> dq;
   
       dq.push_back({1, 2, 3});
       dq.push_back({4, 5});
   
       for (const auto& vec : dq) {
           for (int val : vec) {
               std::cout << val << " ";
           }
           std::cout << "\n";
       }
   
       return 0;
   }   

6. Enums (Kiểu liệt kê):

   #include <deque>
   #include <iostream>
   
   enum Color { RED, GREEN, BLUE };
   
   int main() {
       std::deque<Color> colors = {RED, GREEN, BLUE};
   
       for (Color c : colors) {
           std::cout << c << " "; // In ra giá trị số nguyên tương ứng
       }
   
       return 0;
   }

7. Tuples:

   #include <deque>
   #include <tuple>
   #include <iostream>
   
   int main() {
       std::deque<std::tuple<int, std::string, float>> dq;
   
       dq.push_back({1, "Alice", 9.5});
       dq.push_back({2, "Bob", 8.3});
   
       for (const auto& tup : dq) {
           std::cout << std::get<0>(tup) << ", " << std::get<1>(tup) << ", " << std::get<2>(tup) << "\n";
       }
   
       return 0;
   }

8. Pairs:

   #include <deque>
   #include <iostream>
   #include <utility>
   
   int main() {
       std::deque<std::pair<int, std::string>> dq;
   
       dq.emplace_back(1, "Alice");
       dq.emplace_back(2, "Bob");
   
       for (const auto& p : dq) {
           std::cout << p.first << ": " << p.second << "\n";
       }
   
       return 0;
   }

Các hàm thành viên

=	Gán nội dung

Trình lặp (Iterators)

begin	Trả về một iterator trỏ đến phần tử đầu tiên của deque
end	Trả về một iterator trỏ đến phần tử sau phần tử cuối cùng của deque
rbegin	Trả về một reverse iterator trỏ đến phần tử cuối cùng của deque
rend	Trả về một reverse iterator trỏ đến phần tử trước phần tử đầu tiên của deque
cbegin	Trả về một iterator hằng (constant iterator) trỏ đến phần tử đầu tiên của deque
cend	Trả về một iterator hằng (constant iterator) trỏ đến phần tử sau phần tử cuối cùng của deque
crbegin	Trả về một const_reverse_iterator trỏ đến phần tử cuối cùng của deque
crend	Trả về một const_reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của deque

Dung lượng (Capacity)

size	Lấy số lượng phần tử hiện có trong deque
max_size	Trả về số lượng phần tử tối đa mà deque có thể chứa
resize	Thay đổi kích thước của deque
empty	Kiểm tra xem deque có rỗng hay không
shrink_to_fit	Gửi một yêu cầu đến deque giảm thiểu việc sử dụng bộ nhớ sao cho phù hợp với kích thước hiện tại

Truy cập phần tử

[]	Truy cập đọc/ghi giá trị trực tiếp vào các phần tử của deque thông qua chỉ số (index) của chúng
at	Cung cấp cách thức truy cập an toàn đến các phần tử của deque thông qua chỉ số (index)
front	Trả về tham chiếu đến phần tử đầu tiên trong deque
back	Trả về tham chiếu đến phần tử cuối cùng trong deque

Thay đổi nội dung (Modifiers)

assign	Gán các phần tử mới cho deque, thay thế nội dung hiện tại của nó
push_back	Thêm một phần tử mới vào cuối deque
push_front	Thêm một phần tử mới vào đầu deque
pop_back	Xóa phần tử cuối cùng của deque
pop_front	Xóa phần tử đầu tiên của deque
insert	Chèn một hoặc nhiều phần tử mới vào một vị trí cụ thể trong deque
erase	Xóa một hoặc nhiều phần tử khỏi deque tại một vị trí cụ thể hoặc trong một phạm vi
swap	Hoán đổi nội dung của hai deque với nhau
clear	Xóa tất cả các phần tử khỏi deque, làm cho deque trở thành rỗng
emplace	Xây dựng một phần tử mới trực tiếp tại một vị trí cụ thể trong deque
emplace_front	Xây dựng một phần tử mới trực tiếp tại đầu deque
emplace_back	Xây dựng một phần tử mới trực tiếp tại cuối deque

Cấp phát (Allocator)

get_allocator	Trả về một bản sao của bộ cấp phát (allocator) được liên kết với deque

Toán tử quan hệ	Các toán tử quan hệ trong deque