STL for newbies: STL ALGORITHMS (Thư viện thuật toán) - part 5

STL ALGORITHMS (THƯ VIỆN THUẬT TOÁN): 

-  Khai báo sử dụng: #include <algorithm> 
-  Các hàm trong STL Algorithm khá nhiều nên mình chỉ giới thiệu sơ qua về một số 
hàm hay sử dụng trong các bài toán. 
-  Có một lưu ý nhỏ cho các bạn là khi sử dụng các hàm mà thực hiện trong một đoạn 
phần tử liên tiếp nào đó thì các hàm trong c++ thuờng có tác dụng trên nửa đoạn [..). 
Ví dụ như: bạn muốn hàm f có tác dụng trong đoạn từ 1->n thì các bạn phải gọi hàm 
trong đoạn từ 1 ->n+1. 


Min, max: 
1.1.  min:trả về giá trị bé hơn theo phép so sánh (mặc định là phép toán less): 
Ví dụ: min(‘a’,’b’) sẽ return ’a’; 
 min(3,1) sẽ return 1; 
1.2.  max thì ngược lại với hàm min: 
Ví dụ: max(‘a’,’b’) sẽ return ‘b’ 
 max(3,1) sẽ return 1. 
1.3.  next_permutation:hoán vị tiếp theo. Hàm này sẽ return 1 nếu có hoán vị 
tiếp theo, 0 nếu không có hoán vị tiếp theo. 
Ví dụ: 
// next_permutation 
#include <iostream> 
#include <algorithm> 
using namespace std; 
int main () { 
int myints[] = {1,2,3}; 
cout << "The 3! possible permutations with 3 elements:\n"; 
do { 
cout << myints[0] << " " << myints[1] << " " << myints[2] << endl; 
} while ( next_permutation (myints,myints+3) ); 
return 0; 
} 
Output: 
The 3! possible permutations with 3 elements: 
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3  1 2 
4  2 1 
1.4.  prev_permution: ngược lại với next_permutation



Sắp xếp: 
-  sort: sắp xếp đoạn phần tử theo một trình tự nào đó. Mặc định của sort là sử dụng 
operator <. 
-  Bạn có thể sử dụng hàm so sánh, hay class so sánh tự định nghĩa để sắp xếp cho linh 
hoạt. 
-  Chương trình mẫu: 
// sort algorithm example 
#include <iostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 
bool myfunction (int i,int j) { return (i<j); } 
struct myclass { 
bool operator() (int i,int j) { return (i>j);} 
} myobject; 
int main () { 
int myints[] = {32,71,12,45,26,80,53,33}; 
// using default comparison (operator <): 
sort (myints, myints+4);  //(12 32 45 71)26 80 53 33
// using function as comp 
sort (myints+4, myints+8, myfunction);  // 12 32 45 71(26 33 53 80) 
for (int i=0;i<8;i++) cout << myints[i] << " "; 
cout << endl; 
// using object as comp
sort (myints, myints+8, myobject);  //(80 71 53 45 33 32 26 12) 
for (int i=0;i<8;i++) cout << myints[i] << " "; 
cout << endl; 
system("pause"); 
return 0; 
} 
Tìm kiếm nhị phân (các hàm đối với đoạn đã sắp xếp): 
3.1.  binary_search: 
-  tìm kiếm xem khóa có trong đoạn cần tìm không. Lưu ý: đoạn tìm kiếm phải được sắp 
xếp theo một trật tự nhất đinh. Nếu tìm được sẽ return true, ngược lại return false. 
-  Dạng 1: binary_search(vị trí bắt đầu, vị trí kết thúc, khóa); 
-  Dạng 2: binary_search(vị trí bắt đầu, vị trí kết thúc, khóa, phép so sánh); 
// binary_search example 
#include <iostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 
bool myfunction (int i,int j) { return (i<j); } 
int main () { 
int myints[] = {1,2,3,4,5,4,3,2,1}; 
vector<int> v(myints,myints+9);  // 1 2 3 4 5 4 3 2 1
// Sử dụng toán tử so sánh mặc định 
sort (v.begin(), v.end()); 
cout << "looking for a 3... "; 
if (binary_search (v.begin(), v.end(), 3)) 
cout << "found!\n"; else cout << "not found.\n"; 
// sử dụng hàm so sánh tự định nghĩa: 
sort (v.begin(), v.end(), myfunction); 
cout << "looking for a 6... "; 
if (binary_search (v.begin(), v.end(), 6, myfunction)) 
cout << "found!\n"; else cout << "not found.\n"; 
return 0; 
} 
3.2.  lower_bound: 
-  Hàm lower_bound và upper_bound tương tự như ở trong container set hay map. 
-  Trả về iterator đến phần tử đầu tiên trong nửa đoạn [first,last] mà không bé hơn khóa 
tìm kiếm. 
-  Dạng 1: lower_bound( đầu , cuối , khóa ); 
-  Dạng 2: lower_bound( đầu , cuối , khóa , phép toán so sánh của đoạn) 
3.3.  upper_bound 
-  Trả về iterator đến phần tử đầu tiên trong nửa đoạn [first,last] mà lớn hơn khóa tìm 
kiếm. 
-  Dạng 1: upper_bound ( đầu , cuối , khóa ); 
-  Dạng 2: upper_bound ( đầu , cuối , khóa, phép toán so sánh của đoạn) 
-  Chương trình demo: 
// lower_bound/upper_bound example 
#include <iostream>
#include <algorithm> 
#include <vector> 
using namespace std; 
int main () 
{ 
 int myints[] = {10,20,30,30,20,10,10,20}; 
 vector<int> v(myints,myints+8);  // 10 20 30 30 20 10 10  vector<int>::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 at position " << int(low- v.begin()) << endl; 
 cout << "upper_bound at position " << int(up - v.begin()) << endl; 
 return 0; 
} 
Output: 
lower_bound at position 3 

upper_bound at position 6