Thư viện STL và lập trình C++ – Phần I

Chủ đề: Thư viện bản mẫu chuẩn, C++, OOP, STL, Standard Template Library, Iterator, Functor
Lời nói đầu
Trong bài viết này tôi sẽ trình bày những khái niệm cơ bản về thư viện STL, một trong những thư viện quan trọng và hiệu quả nhất của lập trình hướng đối tượng (OOP) với C++.
Thành thạo thư viện STL sẽ mang lại nhiều lợi ích: giúp bạn tiết kiệm thời gian lập trình trong các cuộc thi lập trình (Olympiad, Online Programming Contest), cho phép bạn viết code nhanh hơn, gọn gàng hơn, hiểu được những gì mà các coder khác viết trong chương trình của họ. Bên cạnh đó học lập trình C++ với STL còn mang lại hiểu biết sâu sắc về C++ và lập trình generic, một xu hướng đang được ứng dụng và phát triển rộng rãi hiện nay.
1. Nguồn gốc của thư viện STL và lập trình Generic
STL là viết tắt của cụm từ Standard Template Library, dịch sang tiếng Việt một cách đơn giản là: Thư viện bản mẫu chuẩn. STL cung cấp các lớp được cài đặt sẵn, chẳng hạn như các lớp chứa (container class), cho phép sử dụng với bất kỳ kiểu dữ liệu có sẵn nào của C/C++ (built-in data types) cũng như các kiểu dữ liệu do người dùng định nghĩa (user-defined) hỗ trợ một số thao tác cơ bản (chẳng hạn như cấu tử copy hay toán tử gán). Các thuật toán do STL cung cấp là độc lập với các lớp chứa, điều này làm giảm đáng kể sự phức tạp trong thiết kế và cài đặt của thư viện STL cũng như các ứng dụng sử dụng STL.
Sức mạnh của STL có được là do tận dụng triệt để khái niệm bản mẫu (template) của C++. Cách tiếp cận này cho phép thực hiện cơ chế đa hình (polymorphism) vào thời điểm biên dịch chương trình, hiệu quả hơn so với cơ chế đa hình thực hiện vào thời điểm chạy chương trình. Các trình biên dịch hiện đại đều có khả năng giảm thiểu các mã thừa đối với các chương trình sử dụng thư viện STL một cách hiệu quả. Sự thành công của STL cho thấy việc sử dụng lại mã nguồn chương trình (vốn là mục đích và nguyên tắc của lập trình hướng đối tượng) vẫn có thể thực hiện được mà không cần nhờ tới các mô hình kế thừa của các lớp.
Thư viện STL là thư viện đầu tiên có các cấu trúc dữ liệu và thuật toán theo hướng generic với bốn khái niệm cơ bản: lập trình generic, trừu tượng hóa, mô hình tính toán Von Neumann và các giá trị ngữ nghĩa.
Kiến trúc của STL phần lớn được đưa ra bởi Alexander Stepanov, một trong những người có ảnh hưởng nhiều nhất tới sự phát triển của ngôn ngữ C++. Các ý tưởng ban đầu được hình thành vào năm 1979 với sự tham gia của David Musser và Deepak Kapur (những người đầu tiên đưa ra khái niệm lập trình generic). Năm 1987 Stepanov và Musser đã đưa ra thư viện mang những ý tưởng đầu tiên về lập trình generic bằng ngôn ngữ Ada. Năm 1992 Stepanov chuyển sang làm cho HP và tham gia một dự án phát triển thuật toán. Trong dự án đó Stepanov và Meng Lee (một người có ảnh hưởng lớn khác tới sự phát triển của C++) đã đưa ra thư viện STL, với ý tưởng về lập trình generic, cho phép sử dụng các thuật toán (ở dạng thư viện) mang tính trừu tượng cao mà không làm mất đi tính hiệu quả của chúng.
Sau rất nhiều cố gắng và công sức lao động của các tác giả Stepanov, Lee và Musser, STL đã được công nhận là một chuẩn ANSI/ISO của C++ vào tháng 7 năm 1994. Và với sự đồng ý của hãng HP, tháng 8 năm 1994, cài đặt của STL cũng được công bố rộng rãi trên mạng Internet. Kể từ thời điểm đó (một số phần mềm thương mại đã sử dụng STL trước khi nó được chấp nhận là chuẩn) STL đã trở thành một phần của ngôn ngữ C++, được cung cấp bởi nhiều trình biên dịch, đóng góp vào sự thành công của vô số các phần mềm được phát triển với ngôn ngữ C++.
Để sử dụng thư viện STL trong lập trình C++, có thể lựa chọn một trong các IDE sau: DevCpp, C-Free, Visual C++ 6.0, Visual Studio 2010.
2. Bốn thành phần cơ bản của thư viện STL
2.1. Khái niệm bản mẫu (template)
2.1.1. Hàm bản mẫu
Nhân tố chính trong mô hình lập trình hướng thủ tục là các thủ tục (procedure) hay còn gọi là các hàm (function). Các hàm là nhân tố chính của các chương trình hướng thủ tục vì chúng cho phép chúng ta viết các thuật toán độc lập với các giá trị của tham số và có thể sử dụng cho một loạt các giá trị khác nhau của các tham số. Ví dụ ta viết một hàm tính giai thừa mà tham số là một số nguyên, sau đó có thể gọi tới hàm này nhiều lần trong một chương trình hoặc nhiều lần trong các chương trình khác nhau mà không cần phải viết lại. Trong trường hợp này giá trị input của hàm đã được tham số hóa một cách hình thức bởi 1 tham số của hàm.
Trong lập trình hướng đối tượng chúng ta làm việc với các đối tượng, là sự kết hợp giữa các dữ liệu có liên quan và các hành vi mà đối tượng có thể thực hiện, tuy nhiên cách thức làm việc của các hàm và các phương thức với các giá trị tham số vẫn không thay đổi so với lập trình hướng thủ tục.
Khái niệm bản mẫu phát triển hơn nữa việc tham số hóa các giá trị input của các hàm trong lập trình hướng đối tượng. Với các hàm thông thường, chúng ta chỉ tham số hóa các giá trị input, còn với kỹ thuật bản mẫu chúng ta tham số hóa kiểu của các giá trị input. Có nghĩa là hàm bản mẫu không những có thể làm việc với các giá trị tham số khác nhau mà còn có thể làm việc với các kiểu tham số khác nhau.
Như vậy chúng ta có thể định nghĩa bản mẫu như sau: Bản mẫu là một cơ chế của lập trình hướng đối tượng cho phép tham số hóa kiểu của các tham số của các hàm và các phương thức của lớp. Từ đây chúng ta có hai khái niệm là hàm bản mẫu và lớp bản mẫu (với các phương thức là các hàm bản mẫu).
Ví dụ về hàm bản mẫu: Chúng ta sẽ xem xét một ví dụ đơn giản về hàm bản mẫu và qua đó so sánh sự khác nhau giữa hàm bản mẫu và khái niệm chồng hàm (overloading function), đó là hàm đổi chỗ phần tử exchange().
Giả sử chúng ta cần một hàm vừa có thể đổi chỗ hai số nguyên, lại vừa có thể đổi chỗ hai số thực, và đổi chỗ hai đối tượng thuộc lớp Sinhvien chẳng hạn. Khi đó với cách tiếp cận sử dụng chồng hàm chúng ta sẽ cần 3 hàm cùng tên như sau:
void exchange(int &a, int &b){
int tam = a;
// ***
a = b;
b = tam;
} // tương tự với kiểu số thực float
void exchange(Sinhvien &a, Sinhvien &b){
Sinhvien tam = a;
// như *** ở trên
}
Còn nếu sử dụng hàm bản mẫu, chúng ta sẽ chỉ cần 1 hàm như sau:
template
void exchange(T &a, T&b)
{
T tam = a;
a = b;
b = tam;
}
Việc gọi tới hàm exchange() trong trường hợp chồng hàm được tiến hành bình thường, còn trong trường hợp hàm bản mẫu thì có hai cách: chúng ta có thể tiến hành gọi giống như đối với hàm bản mẫu hoặc có thể gọi tường minh như ví dụ sau:
int a = 8, b = 90;
float x = 9.8f, y = 1.34f;
exchange(a, b); // tương tự như exchange(a, b);
exchange(x, y); // tương tự như exchange(x, y);
Qua ví dụ này chúng ta có thể thấy chồng hàm thực chất là nhiều hàm có cùng tên nhưng các kiểu tham số (hoặc số tham số trong trường hợp các tham số cùng kiểu) khác nhau (C/C++ không quan tâm tới kiểu của hàm khi xem xét hai hàm có khác nhau về nguyên mẫu hay không) còn hàm bản mẫu là một mẫu hàm nhưng có thể làm việc với nhiều kiểu dữ liệu khác nhau. Về bản chất trong ví dụ trên chúng ta có một mẫu hàm exchange() chung và hai hàm exchange() cụ thể do trình biên dịch của C++ tự động sinh ra và khớp với các kiểu dữ liệu int và float để làm việc, ở đây có sự tương tự giữa khái niệm lớp sinh ra các đối tượng với hàm bản mẫu sinh ra các hàm cụ thể làm việc với các kiểu dữ liệu cụ thể.
Chú ý: Để một lớp có thể sử dụng với các hàm bản mẫu thì lớp đó phải có đầy đủ các hàm toán tử được gọi tới trong cài đặt của hàm bản mẫu, chẳng hạn đối với hàm exchange() ở trên thì lớp sử dụng với nó (chẳng hạn như lớp Sinhvien) phải có cài đặt của hàm toán tử gán. Cần chú ý điều này đặc biệt là khi trong cài đặt của hàm chúng ta có sử dụng các toán tử so sánh, toán tử toán học …
2.1.2. Lớp bản mẫu
Lớp bản mẫu thông thường là những lớp chứa mà chúng ta sẽ xem xét ở phần tiếp theo trong đó các thuộc tính của lớp sẽ là kiểu trừu tượng (bản mẫu) và các phương thức của lớp (có thể tất cả) là các hàm bản mẫu, nghĩa là các thuộc tính dữ liệu của lớp sẽ có thể là kiểu bản mẫu và các phương thức có truy cập tới các thuộc tính này (hay sử dụng kiểu bản mẫu) sẽ là các hàm bản mẫu. Chúng ta sẽ xem xét cụ thể hơn khái niệm này trong phần lớp chứa.
2.2. Lớp chứa (containers class)
Có lẽ không ít lập trình viên cảm thấy khó khăn đối với khái niệm lớp chứa của C++. Chúng ta có các lớp thuộc loại built-in của ngôn ngữ cung cấp sẵn, hoặc có thể xây dựng các lớp theo yêu cầu của bài toán mà chúng ta cần giải quyết (chẳng hạn như lớp Hình tròn, lớp Hình tam giác, lớp Sinh viên, lớp ngăn xếp Stack …) nhưng đó có phải là lớp chứa hay không và thế nào là một lớp chứa? Câu trả lời là lớp Stack là một lớp chứa và lớp chứa là lớp chứa các đối tượng của một lớp khác.
Để đáp ứng các yêu cầu khác nhau, STL cung cấp các nhiều loại lớp chứa chẳng hạn như vector, dequeue, list, set, multiset, map, multimap… Các lớp này được chia thành 2 loại:
1. Các lớp chứa thuộc loại sequence container hay là các tập hợp phần tử có thứ tự trong đó mỗi phần tử có một vị trí nhất định. Vị trí này phụ thuộc vào thời gian và vị trí của việc chèn phần tử vào lớp chứa, không phụ thuộc vào giá trị của phần tử. Chẳng hạn nếu như chúng ta chèn 6 phần tử vào một đối tượng lớp chứa bằng cách thêm mỗi phần tử vào cuối thì các phần tử này sẽ ở đúng theo thứ tự mà chúng ta chèn chúng vào. STL có 3 lớp chứa thuộc loại này là vector, deque và list.
2. Các lớp chứa associative là các tập hợp chứa các phần tử được sắp thứ tự trong đó vị trí các phần tử phụ thuộc vào giá trị của nó dựa trên một tiêu chí sắp xếp nào đó. Nếu chúng ta chèn 6 phần tử vào một lớp chứa loại này thì thứ tự của chúng sẽ chỉ phụ thuộc vào giá trị, thứ tự của việc chèn vào không ảnh hưởng tới các thứ tự này. STL có các lớp sau thuộc loại này: priority_queue, set, multiset, map, multimap.
Một lớp chứa thuộc loại associative cũng có thể xem là một loại đặc biệt của các lớp chứa sequence vì các tập phần tử được sắp xếp dựa trên một điều kiện sắp xếp. Các lớp chứa của STL có các cài đặt khác nhau và không kế thừa từ nhau.
2.3. Các lớp iterator
Trong các lớp chứa của STL, iterator là công cụ phổ biến nhất để có thể truy cập vào các phần tử. Có thể xem iterator là một con trỏ tới một phần tử của một lớp chứa, cung cấp các thao tác cơ bản giống như một con trỏ của C và đôi chút giống với tham chiếu của C++:
+ tham chiếu tới giá trị (tức là phép toán *)
+ tăng/giảm một đơn vị (toán tử ++/–) tương ứng với tăng/giảm một giá trị địa chỉ bằng với kích thước của một phần tử
+ cộng thêm một đại lượng vào iterator tương đương với việc dịch chuyển lên một số vị trí.
+ lấy hiệu của hai iterator (như pháp trừ địa chỉ của hai con trỏ).
+ thực hiện các so sánh !=, ==, >
Để hiểu được iterator các bạn cần hiểu rõ khái niệm con trỏ mảng trong C/C++, ví dụ như sau:
int a[100];
vector vi;
int * p = a; // p trỏ tới phần tử a[0] – tương đương p = &a[0];
vector::iterator it = vi.begin();
cout << *(p+2); // in ra a[2];
cout << *(it+2); // in ra giá trị vi[2];
p++; // p trỏ tới a[1];
it ++; // it là vi[1];
Tất cả các lớp chứa đều có một hàm begin() trả về giá trị iterator trỏ tới phần tử đầu tiên của nó và hàm end() trả về một iterator tương ứng với vị trí cuối cùng của lớp chứa (không phải là phần tử nào cả – tương đương với giá trị NULL của một con trỏ).

Chẳng hạn để duyệt qua các phần tử của một danh sách liên kết ta có thể thực hiện đoạn chương trình sau:
list li;
for(list::iterator it=li.begin();it!=li.end();it++)
cout << *it << endl;
Như vậy mỗi lớp chứa có các iterator tương ứng với chúng (khớp với các tham số bản mẫu của lớp) và được khai báo như sau:
class_name:: ;
Mỗi lớp chứa có một vài loại iterator khác nhau dựa trên việc chúng ta có thể sử dụng chúng để đọc hay ghi dữ liệu vào lớp chứa. Một số loại iterator cho phép cả hai thao tác. Một tiêu chí khác để phân biệt các loại iterator là cách chúng có thể duyệt qua các đối tượng thuộc lớp chứa: theo một chiều từ phần tử đầu tiên tới phần tử cuối cùng hay ngược lại, hoặc cả hai chiều.
Một số loại iterator: iterator, const_iterator (không thay đổi giá trị của phần tử thuộc lớp chứa), reserve_iterator, const_reserve_iterator.
Các lớp chứa còn cung cấp các hàm rbegin() và rend() trả về các iterator đảo ngược.
Sự tồn tại của các iterator là do:
+ thứ nhất các iterator cho phép chúng ta duyệt qua các phần tử của các lớp chứa
+ thứ hai chúng cho phép thực hiện các đoạn chương trình với các kiểu dữ liệu trừu tượng khác nhau, miễn là các kiểu dữ liệu đó cung cấp đủ các hàm toán tử mà đoạn chương trình gọi ra, ví dụ ta muốn tìm phần tử có giá trị lớn nhất của một lớp chứa:
vector vi;
vector::iterator p = vi.begin();
for(vector::iterator it = vi.begin(); it!=vi.end();it++)
if(*it > * p)
p = it;
Đoạn chương trình trên không thay đổi khi ta làm việc với vector hay bất cứ loại dữ liệu, lớp nào, miễn là loại dữ liệu, lớp đó có hàm so sánh >. Điều này đặc biệt quan trọng vì một trong những phần làm nên linh hồn của STL chính là các thuật toán phổ biến như tìm kiếm nhị phân, sắp xếp … đều làm việc với các iterator.
2.4. Các lớp đối tượng hàm (functional objects)
Khi bạn gặp một câu lệnh chẳng hạn như f1(); thì bạn sẽ hiểu đó là câu lệnh gì? Chắc chắn đây là một lời gọi hàm đối với một chương trình C, nhưng điều này sẽ không còn đúng với một chương trình C++ vì đó có thể là một đối tượng gọi tới hàm toán tử gọi hàm của nó. Chính vì vậy một hàm bản mẫu sẽ không thể phát hiện ra tham số mà ta truyền cho nó là một con trỏ tới đối tượng hay là một lớp có cài đặt hàm toán tử gọi hàm (operator()()). Chúng ta có thể xem xét ví dụ sau:
#include
using namespace std;
void f()
{
cout << "Call f() function" << endl;
}
class X
{
public:
void operator()()
{
cout << "X::operator()" << endl;
}
};
template
void test_func ( T f1 )
{
f1();
}
int main()
{
X a;
test_func(f );
test_func(a);
return 0;
}
Kết quả chạy chương trình sẽ là:
Call f() function
X::operator()
Các đối tượng hàm – functional objects (đối tượng thuộc lớp có cài đặt hàm toán tử gọi hàm) còn được gọi là các functor có thể được xem như là các đối tượng sinh (generator) và không có tham số, hoặc các hàm có 1 tham số, hai tham số. Một trường hợp đặc biệt của các hàm chính là các vị từ (các hàm trả về giá trị bool có 1 tham số hoặc hai tham số). STL có một file header functional chứa một tập các bản mẫu tự động sinh ra các đối tượng hàm cho chúng ta. Điều này rất tiện không chỉ vì đó là một thư viện mà còn vì nó cung cấp cho các lập trình viên các từ khóa để nghĩ về việc giải quyết vấn đề, đó là một framework để tạo ra các công cụ khác.
2.5. Các lớp thuật toán (algorithms class)
Hầu hết các lớp thuật toán được khai báo trong file header algorithm. Đầu tiên là ba thuật toán đơn giản min(a, b), max(a, b) và swap(a, b).
Thuật toán được sử dụng nhiều nhất có lẽ là thuật toán dùng để sắp xếp các phần tử (các thuật toán sắp xếp trong). STL cung cấp 6 phương pháp sắp xếp có thể sử dụng cho các mục đích khác nhau: qsort(), sort(),stable_sort(), patial_sort(),list::sort(), set/multiset. Theo [1] thì qsort() là chậm trong các trường hợp có thể so sánh với sort() và stable_sort(), còn list::sort() và việc sử dụng set/multiset rất thích hợp với các lớp chứa đặc thù (chẳng hạn như các cây). Cũng cần lưu ý là hàm sort() chỉ làm việc với các iterator truy cập ngẫu nhiên nên nó không thể làm việc với tất cả các lớp chứa. Ví dụ để sắp một vector ta có thể gọi hàm:
sort(vi.begin(), vi.end());
Cài đặt chi tiết của sort() và stable_sort() đảm bảo thuật toán có độ phức tạp là O(N*log(N)) với N là số phần tử, stable_sort() chậm hơn sort() và giữ nguyên thứ tự của các phần tử bằng nhau (kỳ lạ là nó không đòi hỏi tham số bản mẫu phải có hàm so sánh ==).
Một thuật toán khác hay sử dụng là hàm find() với cú pháp find(begin, end, value) sẽ trả về iterator trỏ tới phần tử đầu tiên bằng với giá trị cần tìm, hoặc end nếu như không tìm thấy. Anh em của hàm find() là hàm count() với cú pháp tương tự cho phép đếm số phần tử bằng một giá trị cho trước. Các lớp chứa set và map có các hàm find() và count() của riêng chúng và do cài đặt của chúng sử dụng các cây đỏ đen (Red Black Tree) nên các thao tác này có độ phức tạp thuật toán là O(log(N)) thay vì O(N) như đối với các lớp chứa khác.
Các thuật toán trên chưa có thuật toán nào sử dụng khái niệm đối tượng hàm và vị từ đã trình bày, chúng ta sẽ xem xét một vài thuật toán như vậy.
Ví dụ sau đây sử dụng các thuật toán for_each và remove_if với đối tượng hàm và vị từ: giả sử ta có một danh sách sinh viên, ta muốn in ra danh sách các sinh viên phải thi lại và loại bỏ các sinh viên bị buộc thôi học:

#include
#include
#include
#include
using namespace std;
class Sinhvien
{
public:
// … cac ham va cac thuoc tinh can thiet
private:
string ten, masv;
int d1, d2, d3;
};
class print_if_thilai
{
public:
void operator() (const Sinhvien & s) const
{
// in ra ten va cac thuoc tinh lien quan neu thi lai
}
};
class thoihoc
{
public:
bool operator() (const Sinhvien & s) const
{
// tra ve true neu sinh vien bi buoc thoi hoc
}
};
int main()
{
list sv;
while (more_sinhvien())
{
Sinhvien temp;
temp.read();
sv.push_back (temp);
}
for_each (sv.begin(), sv.end(), print_if_thilai())
remove_if (sv.begin(), sv.end(), thoihoc());
return 0;
}
Tài liệu tham khảo
1. Matthew H. Austern, The Standard Librarian: Sorting in the Standard Library
2. Nicolai M. Josuttis. The C++ Standard Library: A Tutorial and Referenc. Addison Wesley. 1999.
3. Nicolas A. Solter, Scott J. Kleper. Professional C++. Wiley Publishing, Inc. 2005.
4. Dmitry Korolev, Power up C++ with the Standard Template Library: Part I & II

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s