Bài giảng Kỹ thuật lập trình - Chương 7, Phần 2: Thư viện STL
Bài 7_2
Thư viện STL
(Standard Template Library)
Khái niệm
STL là thư viện chuẩn của C++, được xây dựng sẵn
Cài đặt các cấu trúc dữ liệu và thuật toán thông dụng
Bao gồm các lớp và hàm khuôn mẫu, cho phép làm việc
với dữ liệu tổng quát
Nằm trong một namespace có tên std
Các phần chính:
Các lớp dữ liệu cơ bản: string, complex
Xuất nhập (IO)
Các lớp chứa (containers): list, vector, deque, stack, map, set,…
Duyệt phần tử của các lớp chứa (iterators)
Một số thuật toán thông dụng: tìm kiếm, so sánh, sắp xếp,…
Quản lý bộ nhớ, con trỏ
Xử lý ngoại lệ (exception handling)
2
Xử lý chuỗi
#include <string>
Lớp stringcho chuỗi ASCII và wstringcho Unicode
Cá c thao tá c cơ bản: +, += (nối chuỗi); ==, !=, >, <, >=, <= (so sá nh); <<
(xuất), >>(nhập)
Độ dài chuỗi: int string::length() const
Chuỗi con: string string::substr(int off, int count) const
Tì m chuỗi con: int string::find(const char* str, int pos) const
Đổi sang chuỗi của C: const char* string::c_str() const
Ví dụ:
string s1, s2("test123");
cin >> s1;
s1 += "123";
cout << (s2==s1 ? "same" : "different") << endl;
int pos = s2.find("est");
string s3 = s2.substr(pos, 4);
char s4[100];
strcpy(s4, s3.c_str());
cout << s4 << endl;
3
Mảng: vector
Là mảng động
Có thể chứa dữ liệu kiểu bất kỳ (template): vector<type>
#include <vector>
Ví dụ khai báo:
/* tạo vector rỗng kiểu dữ liệu int */
vector <int> first;
//tạo vector với 4 phần tử là 100
vector <int> second (4,100);
// lấy từ đầu đến cuối vector second
vector <int> third (second.begin(),second.end())
//copy từ vector third
vector <int> four (third)
/* Tạo vector 2 chiều rỗng */
vector < vector <int> > v;
/* khai báo vector 5×10 */
vector < vector <int> > v (5, 10) ;
/* khai báo 5 vector 1 chiều rỗng */
4 vector < vector <int> > v (5) ;
Mảng: vector
Ví dụ sử dụng:
int p[] = {4, 2, 6};
vector<int> a(p, p+3);
a.push_back(1);
// khởi tạo từ mảng C
// thêm vào cuối
a.insert(a.begin() + 2, 3); // thêm ở vị trí 2
a.insert(a.end() - 1, 5);
a[3] = 10;
// thêm ở vị trí 1 từ cuối
// phần tử thứ 4
vector<int>::iterator i; // duyệt xuôi
for (i = a.begin(); i != a.end(); i++) *i += 5;
vector<int>::reverse_iterator j; // duyệt ngược
for (j = a.rbegin(); j != a.rend(); j++)
cout << *j << ' ';
5
Mảng: vector - Các hàm thành viên:
Capacity:
size : trả về số lượng phần tử của vector.
empty : trả về true(1) nếu vector rỗng, ngược lại là false(0).
Truy cập tới phần tử:
operator [] : trả về giá trị phần tử thứ [].
at : tương tự như trên.
front: trả về giá trị phần tử đầu tiên.
back: trả về giá trị phần tử cuối cùng.
Chỉnh sửa:
push_back : thêm vào ở cuối vector.
pop_back : loại bỏ phần tử ở cuối vector.
insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể là phần tử hay
iterator của 1 đoạn phần tử…).
erase : xóa phần tử ở vị trí iterator.
swap : đổi 2 vector cho nhau (ví dụ: first.swap(second);).
clear: xó a vector.
6
Deque (Hàng đợi hai đầu)
Deque là từ viết tắt của double-ended queue (hàng đợi hai đầu).
Deque có các ưu điểm như:
Các phần tử có thể truy cập thông cua chỉ số vị trí của nó.
Chèn hoặc xóa phần tử ở cuối hoặc đầu của dãy.
#include <deque>
Ví dụ :
push_back : thêm phần tử vào ở cuối deque.
push_front : thêm phần tử vào đầu deque.
pop_back : loại bỏ phần tử ở cuối deque.
pop_front : loại bỏ phần tử ở đầu deque.
…
7
iterator
Các lớp chứa của STL (vector, list,…) có định nghĩa kiểu
iteratortương ứng để duyệt các phần tử (theo thứ tự
xuô i)
Mỗi iteratorchứa vị trí của một phần tử
Cá c hàm begin()và end()trả về một iteratortương ứng
với các vị trí đầu và cuối
Các toán tử với iterator:
i++
i--
*i
phần tử kế tiếp
phần tử liền trước
giá trị của phần tử
Tương tự, có reverse_iteratorđể duyệt theo thứ tự
ngược
Cá c hàm rbegin()và rend()
8
Danh sách liên kết: list
Có thể chứa dữ liệu kiểu bất kỳ (template): list<type>
#include <list>
Duyệt danh sách dùng iteratortương tự như với vector
Ví dụ sử dụng:
double p[] = {1.2, 0.7, 2.2, 3.21, 6.4};
list<double> l(p, p+5); // khởi tạo từ mảng C
l.push_back(3.4);
l.pop_front();
// thêm vào cuối
// xoá phần tử đầu
list<double>::iterator i = l.begin(); // phần tử đầu
*i = 4.122;
i++;
// gán giá trị
// phần tử kế tiếp
l.insert(i, 5.0); // chèn phần tử
l.erase(i);
l.sort();
// xoá phần tử
// sắp xếp (tăng dần)
for (i = l.begin(); i != l.end(); i++) // duyệt xuôi
cout << *i << ' ';
9
Stack (Ngăn xếp)
Stack là một loại container adaptor, được thiết kế để hoạt động theo
kiểu LIFO
#include <stack>
Cá c hàm:
size : trả về kích thước hiện tại của stack.
empty : true stack nếu rỗng, và ngược lại.
push : đẩy phần tử vào stack.
pop : loại bỏ phẩn tử ở đỉnh của stack.
top : truy cập tới phần tử ở đỉnh stack.
10
Stack (Ngăn xếp)
Ví dụ:
11
Queue (Hàng đợi)
Queue là một loại container adaptor, được thiết kế để hoạt động theo
kiểu FIFO
Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front),
nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử
cuối cùng được thêm vào.
#include <queue>
Cá c hàm:
size : trả về kích thước hiện tại của queue.
empty : true nếu queue rỗng, và ngược lại.
push : đẩy vào cuối queue.
pop: loại bỏ phần tử (ở đầu).
front : trả về phần tử ở đầu.
back: trả về phần tử ở cuối.
12
Queue (Hàng đợi)
Ví dụ:
#include <iostream>
#include <queue>
using namespace std;
queue <int> q;
int i;
main() {
for (i=1;i<=5;i++) q.push(i); // q={1,2,3,4,5}
q.push(100);
cout << q.front() << endl;
q.pop();
cout << q.back() << endl;
cout << q.empty() << endl;
cout << q.size() << endl;
system("pause");
// q={1,2,3,4,5,100}
// In ra 1
// q={2,3,4,5,100}
// In ra 100
// In ra 0
// In ra 5
}
13
Priority Queue (Hàng đợi ưu tiên)
Priority queue là một loại container adaptor, được thiết kế đặc biệt để
phần tử ở đầu luôn luôn lớn nhất (theo một quy ước về độ ưu tiên
nào đó) so với các phần tử khác.
Nó giống như một heap, mà ở đây là heap max, tức là phần tử có độ
ưu tiên lớn nhất có thể được lấy ra và các phần tử khác được chèn
vào bất kì.
#include <queue>
Cá c hàm:
size : trả về kích thước hiện tại của priority queue.
empty : true nếu priority queue rỗng, và ngược lại.
push : đẩy vào priority queue.
pop: loại bỏ phần tử ở đỉnh priority queue.
top : trả về phần tử ở đỉnh priority queue.
14
Queue (Hàng đợi)
Ví dụ:
15
Pair
Pair: được định nghĩa trong tệp header <utility> bao gồm hai phần tử
hoặc đối tượng dữ liệu.
Phần tử đầu tiên được tham chiếu là ‘first’ và phần tử thứ hai là
‘second’ và thứ tự được cố định (first, second).
Cặp được sử dụng để kết hợp với nhau hai giá trị có thể khác nhau
về kiểu. Cặp cung cấp một cách để lưu trữ hai đối tượng không đồng
nhất như một đơn vị duy nhất.
#include <utility>
Ví dụ:
16
Thuật toán: tìm kiếm
Phần tử lớn nhất, bé nhất:
vector<float>::iterator p =
max_element(a.begin()+2, a.end()-3);
list<string>::iterator p =
min_element(l.begin(), l.end());
Dựa trên các toán tử so sánh → cần định nghĩa nếu chưa có
Tìm đúng giá trị:
list<float>::iterator p = find(p1, p2, 2.5f);
Tìm theo tiêu chuẩn: cần định nghĩa một hàm đánh giá
bool isOdd(int i) { return i%2 == 1; }
list<int>::iterator p = find_if(p1, p2, isOdd);
Tìm kiếm và thay thế, xoá:
replace_if(p1, p2, isOdd, 10);
remove_if(p1, p2, isOdd);
17
Thuật toán: sắp xếp
Sắp xếp mảng:
Dùng toán tử so sánh:
sort(a.begin(), a.end());
Phải định nghĩa toán tử “<” cho kiểu dữ liệu được chứa
Dùng hàm so sánh tự định nghĩa:
bool compare(const table& a, const table& b) {
return a.c1 < b.c1 ||
(a.c1 == b.c1 && a.c2 < b.c2);
}
sort(a.begin(), a.end(), compare);
Sắp xếp danh sách:
l.sort();
l.sort(compare);
18
Câu hỏi 1
Cho một danh sách móc nối với các phần tử trong danh
sách có kiểu S1 được định nghĩa như sau:
struct S1{int info; struct S1 *next;} *head;
Biết con trỏ head lưu địa chỉ của phần tử đầu tiên trong
danh sách. Nhóm câu lệnh nào sau đây thêm một phần
tử mới p vào đầu danh sách:
A) head->next = p; p = head;
B) Không có phương án nào đúng.
C) p->next = head; head = p;
D) p->next = head; head = p-> next;
19
Câu hỏi 2
Với đoạn mã sau, nếu n=13, trong các phần tử được bổ
sung vào ngăn xếp S theo thứ tự nào?
while (n!= 0){
R = n % 2;
S.push(R);
n /= 2;
}
A) 1 , 1 , 0 , 1
B) 1, 0 , 1 , 1
C) 6 , 3 , 1
D) 1 , 3 , 6
20
Tải về để xem bản đầy đủ
36 trang
21500
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Chương 7, Phần 2: Thư viện STL", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_ky_thuat_lap_trinh_chuong_7_phan_2_thu_vien_stl.pdf
