Bài tập OOP: mức nâng cao
Các bài luyện về sao chép sâu, con trỏ thông minh, template, RAII và thiết kế tổng hợp.
Bài 1: chuỗi ký tự tự quản bộ nhớ
Viết lớp ChuoiKyTu bọc một char* cấp phát động. Cài đủ ba thứ theo Rule of Three:
hàm hủy, copy constructor sao chép sâu, và toán tử gán operator=.
Gợi ý
Hàm hủy delete[]. Copy constructor cấp new char[] riêng rồi chép từng ký tự.
operator= cần kiểm tra tự gán (this != &o), giải phóng vùng cũ, cấp vùng mới, chép,
rồi return *this. Xem lại bài Sao chép đối tượng.
Bài 2: cây nhị phân với unique_ptr
Viết lớp Node cho cây nhị phân, dùng unique_ptr<Node> cho con trái và con phải để
bộ nhớ tự dọn khi cây bị hủy.
Gợi ý
unique_ptr<Node> trai, phai; và tạo nút con bằng make_unique<Node>(...). Khi nút gốc
bị hủy, các unique_ptr con tự hủy theo dây chuyền, không cần delete tay. Xem lại
bài Cấp phát động và con trỏ thông minh.
Bài 3: ngăn xếp tổng quát
Viết một class template Stack<T> với các phương thức push, pop, top, rong().
Thử với Stack<int> và Stack<string>.
Gợi ý
Đặt template <typename T> trước class Stack. Bên trong dùng một vector<T> để lưu;
push gọi push_back, pop gọi pop_back, top trả về back(). Cùng một định nghĩa
phục vụ mọi kiểu. Xem lại bài Template.
Bài 4: tìm phần tử lớn nhất tổng quát
Viết hàm template timMax<T>(const vector<T>& v) trả về phần tử lớn nhất. Thử với
vector<int> và vector<double>.
Gợi ý
Khởi tạo kết quả bằng v[0], duyệt phần còn lại, cập nhật khi gặp phần tử lớn hơn. Kiểu
T cần hỗ trợ operator>. Cẩn thận trường hợp vector rỗng. Xem lại bài Template.
Bài 5: vẽ nhiều hình qua con trỏ thông minh
Cho interface trừu tượng Hinh với dienTich(). Tạo một vector<unique_ptr<Hinh>>
gồm nhiều hình khác nhau, rồi tính tổng diện tích.
Gợi ý
Kết hợp đa hình và RAII: vector<unique_ptr<Hinh>> chứa con trỏ thông minh tới các hình
con. Duyệt cộng dồn h->dienTich(). Khi vector bị hủy, mọi hình tự giải phóng. Hủy tử
của Hinh nên là virtual. Xem lại các bài Lớp trừu tượng và Cấp phát động.
Bài 6: mô hình thư viện
Thiết kế lớp Sach (tên, tác giả) và lớp ThuVien chứa một vector<Sach>. ThuVien
có phương thức them(Sach) và timTheoTen(string) trả về sách khớp tên.
Gợi ý
ThuVien có nhiều Sach (composition với một danh sách). Dùng vector<Sach> làm
thuộc tính; them gọi push_back; timTheoTen duyệt vector so sánh tên. Bài này gộp
composition, đóng gói và làm việc với danh sách đối tượng.
Bài 7: máy đa năng tránh kim cương
Cho lớp ThietBi (có id). Hai lớp MayIn và MayQuet cùng kế thừa ThietBi. Lớp
MayDaNang kế thừa cả MayIn lẫn MayQuet. Làm sao để một MayDaNang chỉ có đúng
một id.
Gợi ý
Đây là sơ đồ kim cương. Cho MayIn và MayQuet kế thừa ảo: class MayIn : virtual public ThietBi. Nhờ virtual inheritance, MayDaNang chỉ giữ một bản ThietBi chung thay vì hai
bản trùng lặp, tránh nhập nhằng khi truy cập id. Xem lại bài Đa thừa kế.
Bài 8: sở hữu chia sẻ với shared_ptr
Nhiều đối tượng NguoiDoc cùng tham chiếu tới một TaiLieu. Dùng shared_ptr<TaiLieu>
sao cho tài liệu chỉ được giải phóng khi người đọc cuối cùng buông nó ra.
Gợi ý
shared_ptr đếm số chủ sở hữu; mỗi lần sao chép làm bộ đếm tăng, mỗi lần hủy làm giảm, và
vùng nhớ được dọn khi bộ đếm về 0. Tạo bằng make_shared<TaiLieu>(...). Cẩn thận vòng
tham chiếu (dùng weak_ptr để cắt vòng). Xem lại bài Cấp phát động và con trỏ thông minh.
Bài 9: mảng động tổng quát tự quản
Viết class template Mang<T> bọc một T* cấp phát động với kích thước cho trước. Cài
hàm hủy, copy constructor sao chép sâu và operator= để dùng an toàn cho mọi kiểu T.
Gợi ý
Gộp template và Rule of Three. Đặt template <typename T> trước lớp và để cả định nghĩa
trong header vì template chỉ sinh mã khi biết kiểu cụ thể. Hàm hủy delete[]; copy
constructor cấp new T[n] mới rồi chép từng phần tử (sao chép sâu, không dùng chung con
trỏ); operator= kiểm tra tự gán, giải phóng vùng cũ rồi cấp và chép vùng mới. Xem lại
các bài Template và Sao chép đối tượng.
Bài 10: lớp cặp tổng quát
Viết một class template Cap giữ hai giá trị có thể khác kiểu, với getter dau() và
cuoi(). Thử với một cặp string và int.
Gợi ý
Dùng hai tham số kiểu, ví dụ template <typename A, typename B>. Vì là template nên đặt
cả định nghĩa trong header.
#include <iostream>
#include <string>
using namespace std;
template <typename A, typename B>
class Cap {
A a;
B b;
public:
Cap(A x, B y) : a(x), b(y) {}
A dau() const { return a; }
B cuoi() const { return b; }
};
int main() {
Cap<string, int> tuoi("Lan", 20);
cout << tuoi.dau() << " " << tuoi.cuoi() << "\n"; // Lan 20
return 0;
}
Xem lại bài Template.
Bài 11: quản lý tài nguyên bằng unique_ptr
Viết lớp TaiNguyen in thông báo khi tạo và khi hủy. Dùng unique_ptr<TaiNguyen> để tài
nguyên tự giải phóng khi ra khỏi phạm vi, không cần delete tay.
Gợi ý
Tạo bằng make_unique. Khi unique_ptr ra khỏi phạm vi, hủy tử của tài nguyên tự chạy.
Đây chính là tinh thần RAII: vòng đời tài nguyên gắn với vòng đời một biến.
#include <iostream>
#include <memory>
using namespace std;
class TaiNguyen {
public:
TaiNguyen() { cout << "mo\n"; } // acquire
~TaiNguyen() { cout << "dong\n"; } // release
void dung() { cout << "dang dung\n"; }
};
int main() {
unique_ptr<TaiNguyen> r = make_unique<TaiNguyen>();
r->dung();
// no manual delete: the resource is released when r goes out of scope
return 0;
}
Xem lại bài Cấp phát động và con trỏ thông minh.
Bài 12: quy tắc năm
Viết lớp Bo bọc một con trỏ thô int*. Cài đủ năm hàm đặc biệt: hàm hủy, copy
constructor, toán tử gán sao chép, move constructor và toán tử gán di chuyển.
Gợi ý
Khi lớp quản lý tài nguyên thô và bạn muốn hỗ trợ cả di chuyển, hãy cài đủ năm hàm. Bản
sao chép cấp vùng mới (sao chép sâu), bản di chuyển cướp con trỏ rồi để lại nullptr.
Chính chỗ nullptr đó sinh ra một cái bẫy mà nhiều người bỏ sót. Khi lớp có phép di
chuyển, một đối tượng bị lấy mất ruột (moved-from) vẫn là đối tượng hợp lệ, nhưng nó giữ
data == nullptr. Vì vậy mọi hàm chạm vào *o.data hay *data đều phải tính tới khả
năng con trỏ rỗng, nếu không thì a = d với a đã bị move sẽ giải tham chiếu con trỏ
rỗng, tức là hành vi không xác định. Hàm hủy thì không lo, vì delete nullptr vốn an toàn.
#include <iostream>
#include <utility>
using namespace std;
class Bo {
int* data; // owns a raw pointer, may be null after a move
public:
Bo(int x) : data(new int(x)) {} // constructor
~Bo() { delete data; } // destructor, delete nullptr is safe
// copy constructor (deep); a moved-from source has no cell to copy
Bo(const Bo& o) : data(o.data ? new int(*o.data) : nullptr) {}
Bo& operator=(const Bo& o) { // copy assignment
if (this != &o) {
if (o.data == nullptr) { // source is empty: become empty too
delete data;
data = nullptr;
} else if (data == nullptr) { // we are empty: allocate a fresh cell
data = new int(*o.data);
} else { // both own a cell: copy the value in place
*data = *o.data;
}
}
return *this;
}
Bo(Bo&& o) noexcept : data(o.data) { o.data = nullptr; } // move constructor
Bo& operator=(Bo&& o) noexcept { // move assignment
if (this != &o) { delete data; data = o.data; o.data = nullptr; }
return *this;
}
bool rong() const { return data == nullptr; }
int lay() const { return *data; } // precondition: not moved-from
};
int main() {
Bo a(5);
Bo b = a; // deep copy
Bo c = move(a); // move, a.data becomes null
cout << b.lay() << " " << c.lay() << "\n"; // 5 5
Bo d(9);
a = d; // assign onto a moved-from object: takes the null branch
cout << a.lay() << "\n"; // 9
return 0;
}
Chú ý lay() vẫn giải tham chiếu thẳng, nên nó chỉ gọi được trên đối tượng còn giữ tài
nguyên. Đó là hợp đồng chuẩn của một đối tượng moved-from: chỉ bảo đảm gán lại hoặc hủy
được, muốn dùng tiếp thì kiểm tra rong() trước.
Xem lại bài Sao chép đối tượng.
Bài 13: hàng đợi vòng tổng quát
Viết một class template HangDoiVong sức chứa cố định, lưu phần tử trong mảng và dùng chỉ
số quay vòng để tái dùng ô đã lấy ra. Cài them và lay theo kiểu vào trước ra trước.
Gợi ý
Giữ chỉ số đầu và số phần tử. Vị trí ghi mới là (dau + so) % N, khi lấy thì dời dau
theo modulo. Nhờ chia lấy dư, mảng quay vòng mà không cần dịch phần tử.
#include <iostream>
using namespace std;
template <typename T, int N>
class HangDoiVong {
T data[N];
int dau = 0, so = 0; // head index and count
public:
bool day() const { return so == N; }
bool rong() const { return so == 0; }
void them(T x) {
if (day()) return;
data[(dau + so) % N] = x; // wrap around with modulo
++so;
}
T lay() {
T x = data[dau];
dau = (dau + 1) % N;
--so;
return x;
}
};
int main() {
HangDoiVong<int, 3> q;
q.them(1);
q.them(2);
cout << q.lay() << "\n"; // 1
q.them(3);
q.them(4); // wraps into the freed slot
cout << q.lay() << "\n"; // 2
cout << q.lay() << "\n"; // 3
return 0;
}
Xem lại bài Template.
Bài 14: truyền functor và lambda vào hàm template
Viết hàm template apDung nhận một vector<T> và một đối tượng gọi được (functor hoặc
lambda), rồi áp nó lên từng phần tử. Thử với một functor nhân đôi và một lambda cộng một.
Gợi ý
Cho kiểu của hàm gọi được là một tham số template riêng, nhờ vậy cùng một apDung nhận
được cả functor lẫn lambda. Functor là struct có nạp chồng operator().
#include <iostream>
#include <vector>
using namespace std;
// apply any callable f to every element
template <typename T, typename F>
void apDung(vector<T>& v, F f) {
for (T& x : v) x = f(x);
}
struct NhanDoi { // a functor
int operator()(int x) const { return x * 2; }
};
int main() {
vector<int> v = {1, 2, 3};
apDung(v, NhanDoi()); // pass a functor
apDung(v, [](int x) { return x + 1; }); // pass a lambda
for (int x : v) cout << x << " "; // 3 5 7
cout << "\n";
return 0;
}
Xem lại bài Template.
Câu hỏi tự kiểm
- 1Một lớp bọc char* nhưng không tự viết copy constructor. Khi sao chép đối tượng thì điều gì xảy ra?
- 2Cấp phát bằng new char[n] thì phải giải phóng bằng gì?
- 3Vì sao định nghĩa của một class hoặc hàm template thường đặt trong header?
- 4Trong sơ đồ kim cương, để lớp cháu chỉ có MỘT bản của lớp cơ sở chung, ta dùng cách nào?