Tổng quan về thư viện chuẩn STL

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); 
S T L ( S t a n d a r d T e m p l a t e L i b r a r y ) | 65 
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) 
// range heap example 
#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; 
 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. CÁC BỘ TƯƠNG THÍCH 
S T L ( S t a n d a r d T e m p l a t e L i b r a r y ) | 66 
1.CONTAINER ADAPTER (CÁC BỘ TƯƠNG THÍCH LƯU TRỮ) 
Bao gồm stack, queue và priority_queue 
Gọi là các bộ tương thích bởi vì nó làm các bộ lưu trữ khác trở nên tương thích với nó bằng cách đóng 
gói (encapsulate) các bộ lưu trữ khác trở thành bộ lưu trữ cơ sở của nó. Ví dụ: 
stack > s; 
Khi đó vector trở thành bộ lưu trữ cơ sở của bộ tương thích stack. 
Nếu không khai báo bộ lưu trữ cơ sở, stack và queue mặc định sử dụng deque làm bộ lưu trữ cơ sở, 
trong khi priority_queue mặc định sử dụng vector làm bộ lưu trữ cơ sở, có nghĩa là khi khai báo 
stack s; thực ra là stack > s; 
Lưu ý 2 cả stack và queue đều có các hàm sau 
void push(T) thêm phần tử vào 
void pop(T) gỡ phần tử ra 
stack có thêm hàm T top() truy xuất phần tử ở đỉnh 
queue có thêm hàm: 
T front() truy xuất phần tử tiếp theo 
T back() truy xuất phần tử cuối cùng của queue 
priority_queue là queue trong đó phần tử đầu tiên luôn luôn là phần tử lớn nhất theo một tiêu chuẩn sắp 
xếp nào đó, priority_queue giống như khái niệm heap (đống) mà ta đã biết (heap và giải thuật heapsort 
trong môn CTDL) 
Thực ra priority_queue chỉ là queue mặc định có cài sẵn thêm comparator less giống như các 
associative container thôi. Ta có thể cài lại comparator do ta định nghĩa cho nó (ví dụ bài dưới đây cài 
greater) 
#include 
class Plane{ 
 int fuel; 
public: Plane(int fuel){(*this).fuel=fuel;} 
 friend ostream& operator<<(ostream& os,const Plane& p){ 
 os<<p.fuel<<endl;return os;} 
 bool operator>(const Plane& p) const{ 
 return fuel>p.fuel;} 
}; 
typedef priority_queue,greater > PriorityQueuePlane; 
int main(){ 
 vector vP; 
 vP.push_back(Plane(4));vP.push_back(Plane(7)); 
 vP.push_back(Plane(3));vP.push_back(Plane(9)); 
 PriorityQueuePlane v(vP.begin(),vP.end()); 
 while(!v.empty()){ 
 cout<<v.top();v.pop(); 
 } 
 return 0; 
} 
S T L ( S t a n d a r d T e m p l a t e L i b r a r y ) | 67 
Lưu ý là priority_queue có push, pop và top, không có front và back 
2.ITERATOR ADAPTER (CÁC BỘ TƯƠNG THÍCH CON TRỎ) 
Các bộ tương thích iterator thay đổi các vận hành của iterator, thường là làm container và iterator khác 
trở nên tương thích với nó, bằng cách đóng gói (encapsulate) các container và iterator khác trở thành 
container và iterator cơ sở của nó. Chúng có dạng khai báo cơ bản như sau: 
#include 
template 
class IteratorAdapter 
{ 
 //nội dung 
}; 
IteratorAdapter,vector::iterator> vectorIntAdapter; 
Một số Adapter thường được sử dụng là reverse_iterator, insert_iterator, back insert iterator, front insert 
iterator 
list L; 
L.push_front(3); 
back_insert_iterator > ii(L); 
*ii++ = 0; 
*ii++ = 1; 
*ii++ = 2; 
copy(L.begin(), L.end(), ostream_iterator(cout, " ")); 
// The values that are printed are 3 0 1 2 
Không học thêm về iterator adapter 
3.FUNCTION ADAPTER (CÁC BỘ TƯƠNG THÍCH HÀM) 
Có 2 bộ tương thích hàm chúng ta đã học trước đó là bind1st và bind2nd. Chúng ta sắp học not1, not2, 
mem_fun, mem_fun_ref và ptr_fun. Tất cả đều nằm trong thư viện functional 
- not1 
Đổi giá trị trả về của một unary predicate từ false thành true và ngược lại, unary predicate phải được định 
nghĩa là unary_function 
Ví dụ dùng IsOdd tìm các số chẵn (nghĩa là IsOdd trả về not(true)) 
class IsOdd:public unary_function{ 
public:bool operator()(const int& n) const{return n%2;} 
}; 
int main(int argc, char* argv[]){ 
 int a[] = {1,2,3,4,5}; 
 cout<<count_if(a,a+5,not1(IsOdd()))<<endl; 
 return 0; 
} 
S T L ( S t a n d a r d T e m p l a t e L i b r a r y ) | 68 
- not2 
Đổi giá trị trả về của một binary predicate từ false thành true và ngược lại, binary predicate phải được 
định nghĩa là binary_function 
Ví dụ dùng compare để so sánh 2 mảng với các phần tử không bằng nhau (nghĩa là compare trả về 
not(true)) 
class compare:public binary_function{ 
public:bool operator()(int i,int j) const{return i==j;} 
}; 
int main(int argc, char* argv[]){ 
 int a[] = {1,2,3,4,5}; 
 int b[] = {6,7,8,9,10}; 
 cout<<equal(a,a+5,b,not2(compare()))<<endl; 
 return 0; 
} 
- ptr_fun 
Chuyển một con trỏ hàm (function pointer) thành một functor. Bạn đọc có thể thắc mắc functor hơn 
function pointer ở điểm nào mà lại cần chuyển như vậy. Câu trả lời là tốc độ: 
“A suitably-defined object serves as well as - and often better than - a function. For example, it is easier to 
inline the application operator of a class than to inline a function passed as a pointer to function. 
Consequently, function objects often execute faster than do ordinary functions”- Stroustrup. 
Đại ý là nếu kết hợp với từ khóa inline thì functor cho tốc độ cao hơn function 
int addition(int a,int b){return a+b;} 
int output(int a){cout<<a<<endl;return 0;} 
int(*cong)(int,int) = addition; 
int(*xuat)(int) = output; 
int main() 
{ 
 int a[] = {1,2,3,4,5}; 
 int b[] = {6,7,8,9,10}; 
 int c[5]; 
 transform(a,a+5,b,c,ptr_fun(cong)); 
 for_each(c,c+5,ptr_fun(xuat)); 
 return 0; 
} 
Ở đây chúng ta có binary function là addition và unary function là output, và binary function pointer là 
cong và unary function pointer là xuat, và ta dùng ptr_fun để chuyển các con trỏ hàm này thành binary 
functor và unary functor để đóng vai trò predicate dùng trong hai hàm transform và for_each 
Xét 1 ví dụ khác: 
#include 
double acc(double total, double elements){ 
 return total+elements; 
} 
int main(){ 
 multiset s; 
 for(int i=0;i<6;i++) s.insert(0.3); 
S T L ( S t a n d a r d T e m p l a t e L i b r a r y ) | 69 
 double sum = accumulate(s.begin(),s.end(),0.0,ptr_fun(acc)); 
} 
Ở đây dáng chú ý có hàm accumulate ( của thư viện ).Hàm này được truyền vào functor acc 
(do ptr_fun chuyển từ function thành functor) tham số là total = 0.0 và lần lượt là các phần tử của set, sau 
đó acc tính tổng total và các element rồi trả về để accumulate tích lũy và cuối cùng trả giá trị ra biến sum. 
ptr_fun chỉ dùng cho stand-alone và static member function, với non-static member function phải 2 hàm 
dưới đây: 
- mem_fun và mem_fun_ref 
+mem_fun 
Chuyển một hàm thành viên (member function) của một lớp thành một functor và truyền vào functor này 
các đối số là các con trỏ mà trỏ đến các đối tượng của lớp đó 
class Person{ 
 int age; 
public: 
 Person(int age):age(age){} 
 int display(){cout<<age<<endl;return 0;} 
}; 
int main(){ 
 list l; 
 l.push_back(new Person(4)); 
 l.push_back(new Person(5)); 
 for_each(l.begin(),l.end(),mem_fun(&Person::display)); 
 return 0; 
} 
+mem_fun_ref 
Chuyển một hàm thành viên (member function) của một lớp thành một functor và truyền vào functor này 
các đối số là các tham chiếu mà tham chiếu đến các đối tượng của lớp đó 
class Person{ 
 int age; 
public: 
 Person(int age):age(age){} 
 int display(){cout<<age<<endl;return 0;} 
}; 
int main(){ 
 list l; 
 l.push_back(Person(4)); 
 l.push_back(Person(2)); 
 l.push_back(Person(5)); 
 for_each(l.begin(),l.end(),mem_fun_ref(&Person::display)); 
 return 0; 
} 
Mục đích chính là để tăng hiệu suất chương trình, thứ cực kì quan trọng trong lập trình game. Tưởng 
tượng bạn sẽ phải gọi 1 câu lệnh như thế này 
for(list::iterator i=l.begin();i!=l.end();i++) (**i).display(); 
S T L ( S t a n d a r d T e m p l a t e L i b r a r y ) | 70 
gọi tới từng hàm thành viên của từng phần tử của list, giảm hiệu suất kinh khủng 
Thay vào đó dùng mem_fun hay mem_fun_ref, chỉ cần truyền vào một con trỏ hay một tham chiếu tới 
hàm thành viên, tăng hiệu suất rõ rệt. 
KHUYẾN CÁO: ptr_fun và mem_fun hay mem_fun_ref, cả 3 hàm này đều trả lại functor, được sử dụng 
rất nhiều không vì tăng tốc độ và hiệu suất chương trình. So sánh giữa các ngôn ngữ với nhau, nhờ vào 
những đặc điểm như con trỏ, etc, cùng với những hàm tiện ích đặc biệt trong STL nhất là 3 hàm này, để 
cùng đạt được một mục đích thì dùng C++ đạt được tốc độ và hiệu suất hơn bất kì ngôn ngữ bậc cao 
nào khác. Do đó hiểu và sử dụng nhuần nhuyễn 3 hàm này giúp tăng performance của chương trình.