C++ STL là một phần không thể thiếu trong lập trình C++. Nếu bạn đang học đại học và muốn làm việc trong các công ty công nghệ, các câu hỏi về C++ STL sẽ thường được đặt trong buổi phỏng vấn.
C++ STL là một bộ sưu tập các cấu trúc dữ liệu và thuật toán mà chúng ta thường sử dụng khi viết code. Ví dụ, khi giải quyết một vấn đề, bạn có thể muốn sử dụng danh sách liên kết. Nhưng liệu bạn có tạo danh sách liên kết từ đầu không? Câu trả lời đó là không. Thay vào đó, bạn có thể sử dụng danh sách liên kết có sẵn trong thư viện C++ STL.
Các thuật toán
Các thuật toán trong C++ STL cung cấp nhiều hoạt động khác nhau cho các cấu trúc dữ liệu. Dưới đây là một số thuật toán nổi tiếng:
sort()- sắp xếp dữ liệu.binary_search()- tìm kiếm phần tử.
Các container
Container là lớp chứa các đối tượng và dữ liệu. Dưới đây là một số container phổ biến:
- vector
- list
- forward_list
- queue
- priority_queue
- stack
- set
- multiset
- map
- multimap
- unordered_set
Trình lặp (Iterators)
Như tên gọi, iterators được sử dụng để làm việc trên một chuỗi các giá trị.
Hàm tử (Functors)
STL bao gồm các lớp nạp chồng toán tử để gọi hàm. Các thể hiện của các lớp này được gọi là functors hoặc hàm tử.
Trước khi đi vào chi tiết, hãy tìm hiểu về Pair.
Bây giờ chúng ta sẽ bắt đầu với container cơ bản nhất là vector.
Vector - Container đa năng
Trong hàm displayVector đầu tiên, chúng ta sử dụng phương pháp thông thường. Đây là một trình lặp hằng số đối với vector của int. Ban đầu nó là một con trỏ đến phần tử đầu tiên trong vector.
Trong hàm autoVector thứ hai, chúng ta sử dụng từ khóa auto để tự động lấy kiểu dữ liệu. Tuy nhiên, auto không được hỗ trợ bởi tất cả các trình biên dịch cũ.
Hàm thứ ba là một viết tắt của hai hàm trên. Nó có nghĩa là "đối với mọi phần tử x kiểu int trong vectơ, in ra các phần tử đó".
Hãy nhớ là trong tất cả các hàm trên, chúng ta đã truyền vector bằng tham chiếu để không tạo bản sao khi truyền vector và đã đặt vector là const để đảm bảo rằng vector không bị thay đổi và trình biên dịch có thể tối ưu hóa một số tương tác với vector kiểu const.
Ma trận 2D sử dụng vector
Đây là một số phép toán cơ bản trên vector. Nhưng nếu chúng ta muốn chèn nhiều phần tử nhiều lần và thực hiện các truy vấn như lower_bound và upper_bound nhiều lần, việc sắp xếp vector nhiều lần sẽ mất thời gian O(NlogN) với chi phí (logN) để duy trì các phần tử đã sắp xếp bên trong. Vì vậy, tại đó, set trở thành ứng viên hoàn hảo để sử dụng.
Set duy trì các phần tử theo thứ tự bên trong để chúng ta không cần phải gọi phương thức sắp xếp, tiết kiệm thời gian O(NlogN) với chi phí (logN) để duy trì các phần tử đã sắp xếp bên trong set.
Bản đồ liên kết các khóa với giá trị tương ứng. Bạn có thể truy cập giá trị dựa trên khóa của chúng.
Bản đồ được triển khai như một cây tìm kiếm nhị phân (BST).
Bên trong, unordered_map được triển khai dưới dạng một mảng. Bất kể khóa bạn cung cấp, nó sẽ được chuyển thành một hàm băm (hashing function) và một chỉ mục sẽ được tạo bởi hàm băm đó, sau đó giá trị sẽ được lưu trữ tại chỉ mục tương ứng trong mảng.
Để tìm hiểu thêm về hashing, bạn có thể đọc thêm bài viết về chủ đề này.
Stack là một cấu trúc dữ liệu hoạt động theo cơ chế LIFO (Last In, First Out), có nghĩa là phần tử cuối cùng được chèn là phần tử đầu tiên được truy xuất. Hãy tưởng tượng nó như một chồng sách.
Queue là một cấu trúc dữ liệu hoạt động theo cơ chế FIFO (First In, First Out), có nghĩa là phần tử được chèn đầu tiên sẽ được truy xuất đầu tiên.
Danh sách (list) trong C++ STL được triển khai như một "danh sách liên kết kép". Điều này có nghĩa là mỗi phần tử trong danh sách lưu trữ một con trỏ đến phần tử trước và phần tử tiếp theo.
Danh sách chuyển tiếp (forward_list) được triển khai dưới dạng một "danh sách liên kết đơn". Các phần tử trong danh sách chỉ trỏ đến phần tử tiếp theo.
Đừng hiển thị danh sách như trong phương thức displayWrong dưới đây. Hãy sử dụng phương thức displayCorrect hoặc phương thức rút gọn để hiển thị danh sách đúng.
Điểm sai trong phương thức displayWrong là bạn không thể so sánh iterator với l.end() trong khi trường hợp cấu trúc dữ liệu không liên tục.
it < l.end() là sai, nó phải là it != l.end().
Hàng đợi ưu tiên là một cấu trúc dữ liệu cho phép trích xuất phần tử lớn nhất theo thời gian không đổi, với mức độ phức tạp logarit. Trình lặp theo mặc định là binary-max-heap.
Bạn cũng có thể triển khai binary-min-heap như sau:
Lưu ý rằng bạn không thể lặp lại trên priority_queue, bạn chỉ có thể lấy phần tử trên cùng và tăng nó để xem tất cả các phần tử.
priority_queue được sử dụng rộng rãi trong nhiều thuật toán tiêu chuẩn như thuật toán Dijkstra cho đường đi ngắn nhất.
Ở đây, chúng ta sử dụng macro để tiết kiệm thời gian và tăng năng suất khi làm việc với C++. Nếu bạn muốn tìm hiểu cách tăng năng suất của mình với C++, hãy tham khảo bài viết này.
C++ STL cũng cung cấp các phép toán trên tập hợp như union, intersection, và nhiều phép toán khác.
Hãy nhớ rằng trước khi áp dụng các phép toán tập hợp, vector phải được sắp xếp. Nếu không, kết quả có thể không như mong muốn. Vì vậy, xin hãy xem dòng code số 15.
Ở đây, bên phải của dấu bằng, chúng ta tạo một vector từ đầu (temp.begin()) và một iterator kết thúc. Iterator cuối cùng này được trả về bởi set_union.
Một ứng dụng khác là khi tìm các hoán vị.
Tóm lại, C++ STL cung cấp cho chúng ta một bộ công cụ mạnh mẽ để làm việc với cấu trúc dữ liệu và thuật toán. Hi vọng bài viết này giúp bạn hiểu thêm về thư viện quan trọng này và làm việc hiệu quả hơn với C++.
