Đề tài STL (Standard Template Library)

terator, 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 inlucde file header algorithm
#include 
Do thư viện gồm rất nhiều hàm khác nhau, người ta phân thành các nhóm hàm 
sau:
- Nhóm các hàm không thay đổi giá trị của container
- Nhóm các hàm thay đổi giá trị của container
- Nhóm các hàm sắp xếp
- Nhóm các hàm trên danh sách được sắp xếp
- Nhóm các hàm trộn
- Nhóm các làm trên heap
- Nhóm các hàm tìm min/max.
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ếm vớ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
list l;l.push_back("hello");l.push_back("world");
cout<<(int)count(l.begin(),l.end(),"hello")<<endl;
 University of Infomation Technology Trang 23 
- Hàm count_if dùng để đếm số lượng phần tử thỏa một điều kiện nào đó trong 
một chuỗi các phần tử cho trước, hàm cần một predicate một đối số
class IsOdd
{
public:
bool operator()(int n) const{return (n%2)==1;}
};
int main(int argc, char* argv[])
{
list l;for(int i=0;i<10;i++) l.push_back(i);
cout<<(int)count_if(l.begin(),l.end(),IsOdd())<<endl;
}
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)
vector v(8); // v: 0 0 0 0 0 0 0 0
fill(v.begin(),v.begin()+4,5); // v: 5 5 5 5 0 0 0 0
fill(v.begin()+3,v.end()-2,8); // v: 5 5 5 8 8 8 0 0
– Hàm generate sẽ “sinh” từng phần tử trong khoảng nào đấy của vector bằng cách gọi 
hàm được chỉ định ( một hàm trả về cùng kiểu và không có đối số)
–
template 
void generate(ForwardIterator first, ForwardIterator last, Generator gen);
- Hàm for_each dùng để duyệt từng phần tử trong một chuỗi các phần tử cho trước
Dùng for_each để in ra các phần tử, ví dụ:
void display(const string& s){cout<<s<<endl;}
list l;l.push_back("hello");l.push_back("world");
for_each(l.begin(),l.end(),display);
- Hàm transform: phần tử được sửa đổi từng cái trong một phạm vi theo một chức năng 
mà bạn cung cấp. 
Phiên bản thứ nhất sẽ lấy tất cả phần tử từ v1.begin() đến v1.end(), transform chúng 
bằng hm increase, sau đó chép giá trị đã transform vào bắt đầu từ v2.begin()
int increase(int i){return ++i;}
vector v2;
v2.resize(v1.size());
transform(v1.begin(),v1.end(),v2.begin(),increase);
Phiên bản thứ hai sẽ lấy tất cả phần tử từ v1.begin() đến v1.end(), transform chúng bằng 
hm 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()
int addition(int i,int j){return i+j;}
vector v3;
v3.resize(v1.size());
 University of Infomation Technology Trang 24 
transform(v1.begin(),v1.end(),v2.begin(),v3.begin(),addition);
- Thay thế các giá trị (replace)
int myints[] = { 10, 20, 30, 30, 20, 10, 10, 20 };
vector a (myints, myints+8); // 10 20 30 30 20 10 10 20
replace(a.begin(), a.end(), 20, 99); // 10 99 30 30 99 10 10 99
- 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. 
vector a;
// set some values:
for (int i=1; i<10; i++) a.push_back(i); // 1 2 3 4 5 6 7 8 9
replace_if(a.begin(), a.end(), SoLe, 0); // 0 2 0 4 0 6 0 8 0
- Đảo ngược containter (reverse)
vector a;
// set some values:
for (int i=1; i<10; ++i) a.push_back(i); // 1 2 3 4 5 6 7 8 9
reverse(a.begin(),a.end()); // 9 8 7 6 5 4 3 2 1
- Copy iterator ( tương tự memcpy() đối với pointer )
int a[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(a)/sizeof(*a);
vector v1(a, a+n);
vector v2(n);
copy(v1.begin(), v1.end(), v2.begin());
//copy_n(v1.begin(), v1.size(), v2.begin());
copy(V.begin(), V.end(), ostream_iterator(cout, " "));
- Xóa với remove và remove_if
Ví dụ 1:
//remove
int A[] = {3,1,4,1,5,9};
int N = sizeof(A)/sizeof(*A);
vector V(A, A+N);
vector::iterator new_end =
remove(V.begin(), V.end(), 1);
V.resize(new_end - V.begin());
copy(V.begin(), V.end(), ostream_iterator(cout, " "));
// The output is "3 4 5 9".
- 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ản sao 
container.
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 predicate sort(A, A+N, greater() );
- Hàm is_sorted kiểm tra xem 1 chuỗi đã được sắp xếp hay chưa:
 University of Infomation Technology Trang 25 
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
assert(!is_sorted(A, A + N));
sort(A, A + N);
assert(is_sorted(A, A + N));
4. NHÓM CÁC HÀM TRÊN DANH SÁCH ĐƯỢC SẮP XẾP
Một số thuật toán như tìm kiếm, thêm vào danh sách... hoạt động nhanh hơn (độ phức tạp 
là log2n thay vì n). Thư viện hỗ trợ một số hàm làm việc riêng với các danh sách 
đã sắp xếp theo thứ tự tăng dần.
- Tìm cận dưới và cận trên (lower_bound, upper_bound)
Hàm lower_bound(first, last, value) trả về iterator của element cuối cùng trong danh sách 
đã sắp xếp có giá trị không vượt quá [value].
Hàm upper_bound(first, last, value) trả về iterator của element đầu tiên có giá trị lớn hơn 
[value].
int myints[] = {10,20,30,30,20,10,10,20};
int size = sizeof(myints)/sizeof(myints[0]);
vector v(myints,myints+size); // 10 20 30 30 20 10 10 20
vector::iterator low,up;
sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
low=lower_bound (v.begin(), v.end(), 20);
up= upper_bound (v.begin(), v.end(), 20);
cout << "lower_bound tro vao vi tri: " << int(low- v.begin()) << endl;//3
cout << "upper_bound tro vao vi tri: " << int(up - v.begin()) << endl;//6
- Tìm kiếm nhị phân (binary_search)
Hàm binary_search(first, last, value) trả về true nếu tìm thấy giá trị value trong danh sách đã 
sắp xếp từ first đến last.
int myints[] = {1,2,3,4,5,4,3,2,1};
int size = sizeof(myints)/sizeof(myints[0]);
vector v(myints,myints+size);
sort (v.begin(), v.end(), greater() );
cout << "Tim phan tu 6... ";
if (binary_search (v.begin(), v.end(), 6, LonHon))
cout << "Tim thay!\n";
else cout << "Khong tim thay!\n";
- Trộn 2 danh sách đã được sắp xếp (merge)
- Các phép toán trên tập hợp:
- Xác nhận tập con includes
int A1[] = { 1, 2, 3, 4, 5, 6, 7 };
int A2[] = { 1, 4, 7 };
int A3[] = { 2, 7, 9 };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3) / sizeof(int);
cout << "A2 contained in A1: "
<< (includes(A1, A1 + N1, A2, A2 + N2) ? "true" : "false") << endl;
 University of Infomation Technology Trang 26 
cout << "A3 contained in A1: "
<< (includes(A1, A1 + N2, A3, A3 + N3) ? "true" : "false") << endl;
- Hợp (set_union)
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
vector v(10);
vector::iterator it;
sort (first,first+5);
sort (second,second+5);
vector::iterator end_it=set_union (first, first+5, second, second+5, v.begin());
copy(v.begin(), end_it, ostream_iterator(cout, " "));
//5 10 15 20 25 30 40 50
- Giao (set_intersection)
int first[] = {5,10,15,20,25};
int second[] = {25,40,15,20,10};
vector v(10);
vector::iterator it;
sort (first,first+5);
sort (second,second+5);
vector::iterator end_it =set_intersection(first, first+5, second, second+5, 
v.begin()); //10 15 25
- Phép loại ( set_difference ) lấy ra các phần tử sai khác
int first[] = {5,10,10,20,25};
int second[] = {25,40,15,20,5};
vector v(10);
vector::iterator it;
sort (first,first+5);
sort (second,second+5);
vector::iterator end_it =set_difference(first, first+5, second, second+5, 
v.begin()); //10 10 15 40
- Phép trừ tập hợp ( set_symmetric_difference ) gần giống set_difference nhưng khác 
ở chỗ nếu có 1 phần tử lặp n lần ở tập 1 và m lần ở tập 2 thì nó sẽ xuất hiện |m-n| lần ở output.
5. CÁC HÀM TRÊN HEAP
Bao gồm tạo heap (make_heap), thêm phần tử vào heap (push_heap), xóa phần tử khỏi heap
(pop_heap), sắp xếp heap (sort_heap)
#include 
#include 
#include 
using namespace std;
int main ()
{
int myints[] = {10,20,30,5,15};
vector v(myints,myints+5);
vector::iterator it;
make_heap (v.begin(),v.end());
cout << "initial max heap : " << v.front() << endl;
 University of Infomation Technology Trang 27 
pop_heap (v.begin(),v.end()); v.pop_back();
cout << "max heap after pop : " << v.front() << endl;
v.push_back(99); push_heap (v.begin(),v.end());
cout << "max heap after push: " << v.front() << endl;
sort_heap (v.begin(),v.end());
cout << "final sorted range :";
for (unsigned i=0; i<v.size(); i++)
cout << " " << v[i];
return 0;
}
6,CÁC HÀM TÌM MIN & MAX
- Tìm min & max trong 1 cặp:
const int x = min(3, 9),
y = max(3, 9);
assert(x == 3);
assert(y == 9);
- Tìm min & max trong 1 tập
int A[] = {3,4,2,6,3,1,2,3,2,3,4,5,6,4,3,2,1};
int N = sizeof(A) / sizeof(*A);
cout << "So nho nhat trong mang: " << *min_element(A, A+N) << endl;
cout << "So lon nhat trong mang: " << *max_element(A, A+N) << endl;
VI: Tham Khảo:
- Thinking in C++
- Lập trình hướng đối tượng với C++ - Gs. Phạm văn Ất
- Một số tài liệu sưu tầm từ Internet.
 University of Infomation Technology Trang 28