Các vùng chứa của STL

Thuộc phần Lập trình hướng đối tượng trong hành trình C++ của Coddy. Bài học 71 trên 104.

Các vùng chứa STL là những lớp mẫu dùng để lưu trữ và sắp xếp các tập hợp đối tượng. Mỗi loại vùng chứa được tối ưu hóa cho các kiểu truy cập và thao tác khác nhau. Chọn đúng vùng chứa theo nhu cầu có thể ảnh hưởng đáng kể đến hiệu suất chương trình của bạn.

Các vùng chứa tuần tự duy trì các phần tử theo một thứ tự cụ thể:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Mảng động, truy cập ngẫu nhiên nhanh
vec.push_back(4);                   // Thêm vào cuối: O(1) trung bình
int x = vec[2];                     // Truy cập bằng chỉ số: O(1)

std::list<int> lst = {1, 2, 3};    // Danh sách liên kết đôi
lst.push_front(0);                  // Thêm vào đầu: O(1)
lst.push_back(4);                   // Thêm vào cuối: O(1)

Các vùng chứa kết hợp lưu trữ phần tử theo thứ tự đã sắp xếp để tra cứu nhanh:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Các phần tử không trùng lặp, được sắp xếp: {1, 3, 4}
s.insert(2);                        // Chèn: O(log n)
bool found = s.count(3);            // Kiểm tra sự tồn tại: O(log n)

std::map<std::string, int> ages;   // Các cặp khóa và giá trị, sắp xếp theo khóa
ages["Alice"] = 25;                 // Chèn/cập nhật: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Truy cập: O(log n)

Các vùng chứa không có thứ tự dùng bảng băm để tra cứu nhanh hơn trong trường hợp trung bình:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Chèn: trung bình O(1)
scores["player2"] = 200;
std::cout << scores["player1"];    // Truy cập: trung bình O(1)

Dùng vector khi bạn cần truy cập ngẫu nhiên nhanh, list khi thường xuyên chèn phần tử vào giữa, map/set khi cần dữ liệu được sắp xếp và unordered_map khi tốc độ tra cứu rất quan trọng còn thứ tự thì không.

Thử thách

Dễ

Hãy xây dựng một hệ thống quản lý điểm của học sinh để minh họa cách các vùng chứa STL khác nhau phục vụ những mục đích khác nhau. Bạn sẽ dùng nhiều kiểu vùng chứa để sắp xếp dữ liệu học sinh hiệu quả, chọn vùng chứa phù hợp cho từng tác vụ.

Bạn sẽ tạo hai tệp để sắp xếp code:

GradeManager.h: Định nghĩa một lớp GradeManager dùng nhiều vùng chứa STL để quản lý thông tin học sinh.
Lớp của bạn nên dùng:
- Một std::vector<std::string> để lưu tên học sinh theo thứ tự các em được thêm vào
- Một std::map<std::string, int> để liên kết tên mỗi học sinh với điểm của em đó
- Một std::set<int> để theo dõi tất cả điểm duy nhất đã được gán
Triển khai các phương thức sau:
- addStudent(const std::string& name, int grade): thêm học sinh cùng điểm của em đó vào cả ba vùng chứa
- getGrade(const std::string& name): dùng map để trả về điểm của học sinh có tên đã cho
- printRoster(): in tất cả tên học sinh theo thứ tự các em được thêm vào (từ vector), mỗi tên trên một dòng mới
- printGrades(): in tất cả học sinh cùng điểm theo thứ tự bảng chữ cái (map tự xử lý việc này), theo định dạng name: grade trên mỗi dòng
- printUniqueGrades(): in tất cả điểm duy nhất theo thứ tự tăng dần (set tự xử lý việc này), cách nhau bằng dấu cách và theo sau là ký tự xuống dòng
main.cpp: Đọc đầu vào và minh họa cách mỗi kiểu vùng chứa phục vụ một mục đích khác nhau.
Đọc sáu đầu vào (mỗi đầu vào trên một dòng riêng):
1. Tên học sinh thứ nhất
2. Điểm của học sinh thứ nhất (số nguyên)
3. Tên học sinh thứ hai
4. Điểm của học sinh thứ hai (số nguyên)
5. Tên học sinh thứ ba
6. Điểm của học sinh thứ ba (số nguyên)
Tạo một GradeManager rồi thêm cả ba học sinh. Sau đó, minh họa cách hoạt động khác nhau của các vùng chứa:
1. In Roster (insertion order):, sau đó gọi printRoster()
2. In Grades (alphabetical):, sau đó gọi printGrades()
3. In Unique grades:, sau đó gọi printUniqueGrades()
4. Tra cứu điểm của học sinh thứ hai rồi in <name>'s grade: <grade>

Ví dụ, với đầu vào Charlie, 85, Alice, 90, Bob, 85:

Roster (insertion order):
Charlie
Alice
Bob
Grades (alphabetical):
Alice: 90
Bob: 85
Charlie: 85
Unique grades:
85 90 
Alice's grade: 90

Lưu ý rằng vector giữ nguyên thứ tự thêm vào (Charlie, Alice, Bob), map tự động sắp xếp theo khóa (Alice, Bob, Charlie), còn set chỉ lưu các giá trị duy nhất theo thứ tự đã sắp xếp (85 chỉ xuất hiện một lần, không phải hai lần). Mỗi kiểu vùng chứa đều phù hợp với những tác vụ khác nhau!

Tự làm thử

#include <iostream>
#include <string>
#include "GradeManager.h"

using namespace std;

int main() {
    // Đọc đầu vào của ba học sinh
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Tạo một đối tượng GradeManager
    
    // TODO: Thêm cả ba học sinh vào GradeManager
    
    // TODO: In ra "Roster (insertion order):" và gọi printRoster()
    
    // TODO: In ra "Grades (alphabetical):" và gọi printGrades()
    
    // TODO: In ra "Unique grades:" và gọi printUniqueGrades()
    
    // TODO: Tra cứu điểm của học sinh thứ hai và in ra "<name>'s grade: <grade>"
    
    return 0;
}