Báo cáo bài tập lớn lập trình C++

TRƯỜNG ĐẠI HỌC NÔNG NGHIỆP HÀ NỘIKHOA CÔNG NGHỆ THÔNG TIN******** LẬP TRÌNH HƯỚNG ĐỐI TƯỢNG ĐỀ TÀI: “Tìm hiểu về thư viên STL: Tổng quan về STL, Algorithms, Iterators và FunctionObject. Viết chương trình nhập vào một danh sách n sinh viên, mỗi sinh viên có cácthông tin về họ tên, lớp, điểm TBC. Tìm sinh viên có tên nhập vào từ bàn phím. Yêucầu trong chương trình có sử dụng container list để chứa các đối tượng sinh viên,algorithms find_if và đối tượng hàm tự tạo để tìm kiếm”Giáo viên hướng dẫn: NGÔ CÔNG THẮNGLớp : THC_K52Sinh viên thực hiện : 1. VŨ THỊ MAI HOA2. LÊ THỊ HỒNG NHUNG3. BÙI THỊ THU NGÂN 4. NHÂM THỊ NHÀN Phân công công việc:Phần I:1. Tìm hiểu về thư viện chuẩn STL: Bùi Thị Thu Ngân2. Tìm hiểu về thư viện Algorithm: Vũ Thị Mai Hoa3. Tìm hiểu về Iterator: Nhâm Thị Nhàn4. Tìm hiểu về Function Object: Lê Thị Hồng NhungPhần II: Chương trình cả nhóm cùng làmMỞ ĐẦU C++ được đánh giá là ngôn ngữ mạnh vì tính mềm dẻo, gần gũi với ngôn ngữ máy. Ngoài ra, với khả năng lập trình theo mẫu [ template ], C++ đã khiến ngôn ngữ lập trình trở thành khái quát, không cụ thể và chi tiết như nhiều ngôn ngữ khác. Sức mạnh của C++ đến từ STL, viết tắt của Standard Template Library - một thư viện template cho C++với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của C. Với khái niệm template, những người lập trình đã đề ra khái niệm lập trình khái lược [generic programming], C++ được cung cấp kèm với bộ thư viện chuẩn STL PHẦN I: LÝ THUYẾTI/. Giới thiệu thư viện chuẩn STL: 1/. Giới thiệu STL:STL, viết tắt của Standard Template Library - một thư viện template cho C++ vớinhững cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụngđược hiệu năng và tốc độ của C. Với khái niệm template, những người lập trình đã đề rakhái niệm lập trình khái lược [generic programming], C++ được cung cấp kèm với bộthư viện chuẩn STL.2/. Các thành phần chính của STLSTL gồm các thành phần chính:• Container [các bộ lưu trữ dữ liệu] là các cấu trúc dữ liệu phổ biến đã template hóadùng để lưu trữ các kiểu dữ liệu khác nhau. Các container chia làm 2 loại:o Sequential container [các ctdl tuần tự] bao gồm list, vector và dequeo Asociative container [các ctdl liên kết] bao gồm map, multimap, set vàmultiset• Iterator [biến lặp] giống như con trỏ, tích hợp bên trong container• Algorithm [các thuật toán ] là các hàm phổ biến để làm việc với các bộ lưu trữnhư thêm, xóa, sửa, truy xuất, tìm kiếm, sắp xếp • Function object [functor]: Một kiểu đối tượng có thể gọi như 1 hàm, đúng ra đâylà 1 kỹ thuật nhưng trong STL nó được nâng cao và kết hợp với các algorithm• Các adapter [bộ tương thích] , chia làm 3 loại:o container adapter [các bộ tương thích lưu trữ] bao gồm stack, queue vàpriority_queueo iterator adapter [các bộ tương thích con trỏ]o function adapter [các bộ tương thích hàm]Những thành phần này làm việc chung với các thành phần khác để cung cấp cácgiải pháp cho các vấn đề khác nhau của chương trình.Bộ thư viện này thực hiện toàn bộ các công việc vào ra dữ liệu [iostream], quản lýmảng [vector], thực hiện hầu hết các tính năng của các cấu trúc dữ liệu cơ bản [stack,queue, map, set ]. Ngoài ra, STL còn bao gồm các thuật toán cơ bản: tìm min, max,tính tổng, sắp xếp [với nhiều thuật toán khác nhau], thay thế các phần tử, tìm kiếm [tìmkiếm thường và tìm kiếm nhị phân], trộn. Toàn bộ các tính năng nêu trên đều được cungcấp dưới dạng template nên việc lập trình luôn thể hiện tính khái quát hóa cao. Nhờ vậy,STL làm cho ngôn ngữ C++ trở nên trong sáng hơn nhiều.Đặc điểm thư viện STL là được hỗ trợ trên các trình biên dịch ở cả hai môi trườngWINDOWS lẫn UNIX, vì vậy nên khi sử dụng thư viện này trong xử lý thuận tiện choviệc chia sẽ mã nguồn với cộng đồng phát triển.Vì thư viện chuẩn được thiết kế bởi những chuyện gia hàng đầu và đã được chứngminh tính hiệu quả trong lịch sử tồn tại của nó, các thành phần của thư viện này đượckhuyến cáo sử dụng thay vì dùng những phần viết tay bên ngoài hay những phương tiệncấp thấp khác. Thí dụ, dùng std::vector hay std::string thay vì dùng kiểu mảng đơn thuầnlà một cách hữu hiệu để viết phần mềm được an toàn và linh hoạt hơn.Các chức năng của thư viện chuẩn C++ được khai báo trong namespace std;II/. Thư viện ALGORITHM: 1/. Giới thiệu:Như đã giới thiệu trong các phần trước, STL cung cấp các thuật toán cơ bản nhằmmục đích giúp bạn không phải code lại những giải thuật quá cơ bản như [sắp xếp, thaythế, tìm kiếm ]. Các công cụ này không những giúp bạn rút ngắn thời gian lập trình màcòn cả thời gian gỡ rối khi thuật toán cơ bản được cài đặt không chính xác.Ngoài ra, với STL Algorithm, bạn có nhiều lựa chọn cho những thuật toán cơ bản.Ví dụ, với thuật toán sắp xếp, bạn có thể lựa chọn giữa thuật toán sắp xếp nhanh[quicksort] cho kết quả rất nhanh với độ phức tạp NlogN trong đa số các trường hợp,nhưng lại có độ phức tạp N*N trong trường hợp xấu nhất và thuật toán sắp xếp vungđống [heapsort] chạy chậm hơn quicksort nhưng có độ phức tạp trong mọi trường hợp làNlogN.Chú ý rằng các thuật toán của STL Algorithm có thể áp dụng cho mọi kiểu iterator,kể cả con trỏ thường[không phải là iterator của STL]. Như vậy, các thuật toán sắp xếp,tìm kiếm, thay thế không những áp dụng được cho các kiểu vector, list mà còn có thểáp dụng cho mảng thông thường.Để khai báo sử dụng STL algorithm, các bạn phải include file header algorithm:#include 2/. Các nhóm hàm trong thư viện Algorithm:2.1/ Nhóm các hàm không thay đổi Container: Các thuật toán tìm kiếm, bao gồm find[], find_if[] tìm theo điều kiện, search[]dùng để so khớp 1 chuỗi liên tiếp các phần tử cho trước, hàm search_n tìm kiếmvới số lần lặp xác định, hàm find_end tìm kết quả cuối cùng, find_first_not_of[],find_last_not_of[] … Các thuật toán đếm:• Hàm count dùng để đếm số lượng phần tử trong một chuỗi các phần tử cho trước• Hàm count_if dùng để đếm số lượng phần tử thỏa một điều kiện nào đó trongmột chuỗi các phần tử cho trước, hàm cần một predicate một đối số 2.2/ Nhóm các hàm thay đổi Container: Hàm fill để tô một vùng giá trị của 1 container [thường là 1 mảng, 1 vector] Hàm generate sẽ “sinh” từng phần tử trong khoảng nào đấy của vector bằngcách gọi hàm được chỉ định [ một hàm trả về cùng kiểu và không có đối số] Hàm for_each dùng để duyệt từng phần tử trong một chuỗi các phần tử chotrước: Dùng for_each để in ra các phần tử,  Hàm transform: phần tử được sửa đổi từng cái trong một phạm vi theo mộtchức năng mà bạn cung cấp. Hàm này có hai phiên bản:Phiên bản thứ nhất sẽ lấy tất cả phần tử từ v1.begin[] đến v1.end[], transform chúngbằng hàm increase, sau đó chép giá trị đã transform vào bắt đầu từ Phiên bản thứ hai sẽ lấy tất cả phần tử từ v1.begin[] đến v1.end[], transform chúngbằng hàm addition với đối số thứ hai là tất cả phần tử từ v2.begin[], sau đó chép giá trịđã transform vào bắt đầu từ v3.begin[]- Thay thế các giá trị [replace] Hàm replace_if cho phép tìm giá trị theo điều kiện do một hàm trả về. Để sửdụng lệnh này bạn phải khai báo 1 hàm có giá trị trả về là bool nhận tham sốlà giá trị của 1 element. Khi hàm trả về true, giá trị tương ứng sẽ bị thay thếbới giá trị mới. Hàm kiểm tra nên khai báo inline để tốc độ nhanh hơn. Đảo ngược containter [reverse] Copy iterator [ tương tự memcpy[] đối với pointer ] Xóa với remove và remove_if- Các hàm có hậu tố _copy như remove_copy, remove_if_copy, replace_copy,replace_if_copy, reverse_copy sử dụng tương tự nhưng tạo ra và thao tác trên bảnsao container.2.3/ Nhóm các hàm sắp xếp:- Hàm sort [ quicksort ]Hàm này có 2 phiên bản: Sắp xếp lại một chuỗi phần tử theo thứ tự tăng dần [ascending] sort [v.begin[],v.end[]]; Sắp xếp lại một chuỗi phần tử thỏa một binary predicatesort[A, A+N, greater[] ];Hoặc:templateclass Bigger{public:bool operator[][const T& t1,const T& t2]{return t1>t2;}};templateclass Output{public:void operator[][const T& t]{cout