Giao diện
STL Container Challenges
🎯 Mục tiêu
🎯 Sau bài thực hành này, bạn sẽ:
- Sử dụng thành thạo vector, map, set trong bài toán thực tế
- Áp dụng iterator patterns để duyệt và biến đổi dữ liệu
- Viết custom comparators cho sorted containers
Mô tả bài tập
STL containers là công cụ quan trọng nhất của C++. Bài tập giúp bạn chọn đúng container và thao tác hiệu quả.
Yêu cầu
Bài 1: Vector — Quản lý sinh viên
Viết chương trình: thêm sinh viên, loại bỏ GPA < 2.0, sắp xếp GPA giảm dần.
cpp
struct Student { std::string name; double gpa; };
void sortByGPA(std::vector<Student>& students); // sort giảm dần
void removeFailing(std::vector<Student>& students); // erase-remove GPA < 2.0
int main() {
std::vector<Student> s = {{"An",3.5}, {"Binh",1.8}, {"Chi",3.9}, {"Dung",1.5}};
removeFailing(s);
sortByGPA(s); // Chi(3.9), An(3.5)
}Bài 2: Map — Đếm tần suất từ
Dùng std::map đếm tần suất, tìm top-K từ xuất hiện nhiều nhất.
cpp
std::map<std::string, int> countFrequency(const std::vector<std::string>& words);
std::vector<std::pair<std::string, int>> topKWords(
const std::map<std::string, int>& freq, int k);
int main() {
std::vector<std::string> words = {"hello","world","hello","cpp","world","hello"};
auto top2 = topKWords(countFrequency(words), 2);
// hello: 3, world: 2
}Bài 3: Custom Comparator — Task Queue
Viết comparator sắp xếp tasks theo priority (nhỏ = ưu tiên cao).
cpp
struct Task { std::string name; int priority; int id; };
struct TaskCompare {
bool operator()(const Task& a, const Task& b) const {
// TODO: priority tăng dần, cùng priority thì id tăng dần
}
};
int main() {
std::set<Task, TaskCompare> q;
q.insert({"Bug fix", 1, 101});
q.insert({"Feature", 3, 102});
q.insert({"Hotfix", 1, 103});
}Gợi ý
Gợi ý Bài 1
Erase-remove: students.erase(std::remove_if(...), students.end()). Sort với lambda cho GPA giảm dần.
Gợi ý Bài 2
Đếm: freq[word]++. Top-K: chuyển sang vector rồi partial_sort.
Lời giải tham khảo
Xem lời giải
cpp
void sortByGPA(std::vector<Student>& s) {
std::sort(s.begin(), s.end(),
[](const Student& a, const Student& b) { return a.gpa > b.gpa; });
}
void removeFailing(std::vector<Student>& s) {
s.erase(std::remove_if(s.begin(), s.end(),
[](const Student& x) { return x.gpa < 2.0; }), s.end());
}
std::map<std::string, int> countFrequency(const std::vector<std::string>& words) {
std::map<std::string, int> freq;
for (const auto& w : words) freq[w]++;
return freq;
}
std::vector<std::pair<std::string, int>> topKWords(
const std::map<std::string, int>& freq, int k) {
std::vector<std::pair<std::string, int>> v(freq.begin(), freq.end());
std::partial_sort(v.begin(), v.begin() + k, v.end(),
[](const auto& a, const auto& b) { return a.second > b.second; });
v.resize(k);
return v;
}
struct TaskCompare {
bool operator()(const Task& a, const Task& b) const {
if (a.priority != b.priority) return a.priority < b.priority;
return a.id < b.id;
}
};