C++ STL là một phần không thể thiếu của lập trình cạnh tranh trong C++. Nếu bạn đang học đại học và muốn có chân trong các công ty, thì câu hỏi từ C++ STL sẽ được hỏi trong các buổi phỏng vấn.

C++ STL là gì?

C++ STL là một tập hợp các cấu trúc dữ liệu và thuật toán mà chúng ta thường gặp trong quá trình viết code. Ví dụ, trong khi giải quyết một vấn đề bạn muốn sử dụng danh sách liên kết, vậy bạn có tạo danh sách liên kết từ đầu không? Câu trả lời là không, bạn sẽ sử dụng danh sách được xây dựng trong thư viện C++ STL. 

STL có bốn thành phần

• Các thuật toán
• Các container
• Trình lặp lại (Iterators)
• Hàm tử (functors)

Các thuật toán

Thuật toán tiêu đề xác định rất nhiều thuật toán thông dụng mà chúng ta cân nhắc. Chúng cung cấp các hoạt động khác nhau cho các container. Một số thuật toán nổi tiếng là

sort() - để sắp xếp.

binary_search() - để tìm kiếm phần tử

Các container

Container hoặc lớp container chứa các đối tượng và dữ liệu. Một số lớp container được đưa ra bên dưới:

vector, list, forward_list, queue, priority_queue, stack, set, multiset, map, multimap, unardered_set

Trình lặp lại (Iterators)

Như tên cho thấy, các trình vòng lặp đượ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 như vậy được gọi là các đối tượng hàm hoặc hàm tử.

Trước tiên, hãy hiểu một chút về Pair.

Pair 

Bây giờ bắt đầu với container cơ bản nhất

Vectơ

Vector là một loại mảng có rất nhiều chức năng phụ. Chắc hẳn bạn đã sử dụng mảng và không hài lòng với những hạn chế của mảng. Vectơ sẽ giúp bạn việc này:

Phương pháp vectơ chung

Trong hàm displayVector đầu tiên, ta đã sử dụng phương pháp bình thường. Được biết rằng  nó là một trình lặp hằng số đối với vectơ 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, từ khóa auto được sử dụng để lấy kiểu dữ liệu tự động. auto không được hỗ trợ bởi các trình biên dịch cũ.

Hàm thứ ba là ký hiệu viết tắt của hai hàm trên. Nó nói rằng: “với mọi phần tử x kiểu int trong vectơ v in ra các phần tử”

Đừng quên rằng trong tất cả các hàm trên, ta đã chuyển vectơ bằng tham chiếu để nó không tạo bản sao khi truyền vectơ và ta cũng đã đặt nó thành const, điều này đảm bảo rằng vectơ không vô tình bị thay đổi và trình biên dịch cũng có thể tạo một số tối ưu hóa trong các thực thể kiểu const.

Ma trận 2D sử dụng vectơ

Trên đây là một số phép toán cơ bản trên vector. Nhưng điều gì sẽ xảy ra nếu chúng ta muốn chèn nhiều mục nhiều lần và thực hiện các truy vấn như Lower_bound và upper_bound một số lần trong trường hợp đó, chúng ta sẽ phải sắp xếp vector nhiều lần, vì vậy tập hợp ở đây trở thành ứng cử viên hoàn hảo để sử dụng.

Set

Tập hợp duy trì các phần tử được sắp xếp bên trong nên chúng ta không cần gọi đi gọi lại phương pháp sắp xếp, điều này sẽ tiết kiệm thời gian O(NlogN) với chi phí (logN) thời gian để duy trì các phần tử được sắp xếp bên trong theo tập hợp.

Set trên Pair

Vì vậy, bây giờ, chúng ta biết rằng tập hợp duy trì một số thứ tự trong các phần tử nhưng nó so sánh ‘cặp’ các phần tử như thế nào để duy trì trật tự:

 Tổng hợp tất cả các điểm trên trong set:

1. Đặt phần tử lưu trữ theo thứ tự tăng dần (theo mặc định).
2. low_bound cho phần tử đầu tiên lớn hơn hoặc bằng một số khóa.
3. cho cặp {a, b} và {c, d}, {a, b} == {c, d} nếu a == c && b == d và {a, b} <{c, d} if (a <c) || (a == c && b <d)

Bản đồ

Bản đồ nói các khóa với giá trị. Bạn có thể truy cập giá trị từ khóa của họ.

Bản đồ nội bộ được triển khai dưới dạng Cây tìm kiếm nhị phân (BST).

Bản đồ bất trật tự

Unordered_map trông giống nhau về chức năng lập bản đồ nhưng có sự khác biệt về cách chúng được triển khai bên trong.

Unordered_map bên trong được triển khai dưới dạng một mảng. Bất kể khóa nào bạn đưa ra đều được chuyển thành một hàm băm (hashing function) và một chỉ mục được tạo bởi hàm băm đó, sau đó giá trị được lưu trữ tại chỉ mục đó của mảng.

Để tìm hiểu thêm về hashing, hãy xem bài viết này.

Stack

Stack là cấu trúc dữ liệu cuối cùng trong phương pháp xuất trước (LIFO), tức là phần tử được chèn sau cùng là phần tử đầu tiên xuất hiện. Hãy tưởng tượng nó giống như một chồng sách.

Queue

Queue là cấu trúc dữ liệu xuất trước (FIFO), tức là phần tử được chèn đầu tiên sẽ xuất hiện trước

Danh sách

Danh sách trong C++ STL được triển khai dưới dạng "danh sách liên kết kép". Có nghĩa là mọi phần tử trong danh sách đều theo dõi cả phần tử trước và phần tử tiếp theo.

Không hiển thị danh sách như trong phương thức displayWrong đưa ra bên dưới, hãy sử dụng phương pháp shorthand hoặc hiển thị như phương thức displayCorrect.

Điều sai trong phương pháp displayWrong là bạn không thể so sánh trình lặp nhỏ hơn hoặc lớn hơn trong trường hợp cấu trúc dữ liệu cấp phát bộ nhớ không liền nhau.

it <l.end() là sai, nó phải là it ! = l.end()

Danh sách chuyển tiếp (Forward List)

Danh sách chuyển tiếp thực hiện "danh sách liên kết đơn". Có nghĩa là mọi phần tử trong danh sách đều trỏ đến phần tử bên cạnh nó.

Priority Queue

Hàng đợi ưu tiên là một vùng chứa cung cấp trích xuất theo thời gian không đổi của phần tử lớn nhất, với chi phí chèn logarit. Việc triển khai bên trong của priority_queue là binary-max-heap.

Bạn vẫn 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 phải lấy phần tử trên cùng rồi bật lên để xem tất cả các phần tử.

priority_queue tìm thấy ứng dụng của chúng trong một số thuật toán tiêu chuẩn như thuật toán Dijkstra cho đường đi ngắn nhất.

Tuple và Tie

 Ở đây ta đã sử dụng watch marco để hiển thị nội dung biến cùng với tên của nó. Đây là một macro rất phổ biến, vì vậy bạn nên bắt đầu sử dụng nó.

Thuật toán

Bây giờ chúng ta hãy xem xét một số hàm thường được sử dụng.

Ta đã sử dụng macro để tiết kiệm rất nhiều thời gian và tăng năng suất của mình với tư cách là một lập trình viên C++. Nếu bạn muốn tìm hiểu thêm về cách tăng năng suất của mình với tư cách là một lập trình viên C++ thì hãy xem bài viết này.

Nhiều khi chúng ta muốn thực hiện các thao tác trên các tập hợp như union, intersection… tất cả các thao tác này đều được xây dựng trong thư viện C++ STL.

Hãy nhớ rằng trước khi áp dụng các phép toán tập hợp này, véc tơ phải được sắp xếp nếu không chúng sẽ cho ra kết quả không mong muốn. Vì vậy, chúng ta hãy xem xét dòng #15

Ở đây, ở phía bên phải của dấu bằng, ta đang tạo một vectơ chuyển từ đầu (temp.begin()) và trình vòng kết thúc. Trình lặp cuối này được trả về bởi set_union.

Một trường hợp sử dụng khác là khi tìm các hoán vị.

Tổng hợp việc làm IT - Software trên VietnamWorks
VietnamWorks InTECH
Theo medium