Thư viện mẫu trong lập trình hướng đối tượng C++

1.7 The Standard Template Library

C++ là ngôn ngữ lập trình hướng đối tượng, các tiện ích mở rộng gần đây mang lại cho C++ lên một cấp độ cao hơn. Bổ sung quan trọng nhất cho ngôn ngữ là thư viện Standard Template Library (STL), được phát triển chủ yếu bởi Alexander Stepanov và Meng Lee. Thư viện này bao gồm 3 loại thực thể chung: containers, iterators, và algorithms. Các thuật toán là các hàm được sử dụng thường xuyên có thể được áp dụng cho các cấu trúc dữ liệu khác nhau. Ứng dụng được dàn xếp thông qua các trình vòng lặp để xác định thuật toán có thể áp dụng cho loại đối tượng nào. Thư viện Standard Template Library (STL) giúp các lập trình viên không phải viết các khai báo của riêng họ đối với các lớp và các hàm khác nhau. Thay vào đó thì họ có thể sử dụng những khai báo chung được đóng gói sẵn phù hợp với vấn đề đang xử lý.

1.7.1 Containers

Container là một cấu trúc dữ liệu chứa một số đối tượng thường dùng cùng một loại. Các container khác nhau thì tổ chức quản lý bên trong chúng khác nhau. Mặc dù về mặt lý thuyết số lượng các thành viên khác nhau trong cấu trúc dữ liệu là không giới hạn, chỉ một số nhỏ trong số đó có ý nghĩa thiết thực và các cấu trúc dữ liệu thường xuyên sử dụng nhất được đưa vào thư viện mẫu. Thư viện mẫu bao gồm các container như: deque, list, map, multimap, set, multiset, stack, queue, priority_queue và vector.

Các container trong thư viên viện mẫu được triển khai dưới dạng các lớp, bao gồm các hàm và dữ liệu hoặc cấu trúc dữ liệu. Các hàm dùng để mô tả các hoạt động có thể thực hiện trên cấu trúc dữ liệu đó. Một số hàm có thể được tìm thấy trên tất các cả container, mặc dù chúng có thể được cài đặt khác nhau. Các hàm thành viên chung cho tất cả các container: hàm tạo bảo sao (copy constructor), hàm hủy (destructor), empty(), max_size(), size(), swap(), toán tử =, và ngoại trừ priority_queue, sáu toán tử so sánh trong quan hệ hàm (toán tử <, v.v). Ngoài ra, nó còn có các hàm chung để quan lý bộ nhớ, riêng stack, queue và priority_queue là không có. Các hàm đó bao gồm là: begin(), end(), rbegin(), rend(), erase() và clear().

Các kiểu dữ liệu nào cũng có thể trong container, và chúng phải cung cấp ít nhất một hàm tạo mặc định, một hàm hủy, và một toán tử gán. Điều này đặc biệt quan trọng đối với những kiểu mà chính người dùng tự định nghĩa. Một số trình biên dịch cũng có thể yêu cầu các toán tử quan hệ (ít nhất là toán từ == và <, nhưng cũng có thể là != và >) mặc dù chương trình không sử dụng đến chúng. Ngoài ra, một hàm tạo bản sao và toán tử hàm = nên được cung cấp nếu các thành viên dữ liệu là các con trỏ bởi vì hoạt động chèn sử dụng bản sao của các phần tử đang được chèn chứ không phải chính phần tử đó.

1.7.2 Iterators

Một iterator là một đối tượng được sử dụng tham chiếu đến các phần tử được lưu trong vùng chứa. Do đó, nó chính là sự tổng quát của con trỏ. Một iterator cho phép truy cập các thông bao gồm các vùng chứa để các hoạt động mong muốn có thể được thực hiện trên các phần tử này.

Như là một sự tổng quát của con trỏ, iterators giữ nguyên các ký hiệu tương ứng. Ví dụ, *i là một phần được tham chiếu bởi iterator i. Ngoài ra, phép toán của iterator tương tự với các phép toán của con trỏ, mặc dù tất cả hoạt động trên iterators không được chấp thuận trong tất cả các vùng chứa.

Không iterators nào hỗ trợ cho vùng chứa stack, queue, và priority_queue. Các hoạt động của iterators đối với các lớp như: list, map, multipamp. set và multiset như (i1 và i2 là iterators, n là một số nguyên):

i1++, ++i1, i1--, --i1 i1 = i2 i1 == i2, i1 != i2 *i1

Ngoài các toán tử trên, các toán tử của iterator đối với lớp deque và vector được thể hiện như sau:

i1 < i2, i1 <= i2, i1 > i2, i1 >= i2 i1 + n, i1 - n i1 += n, i1 -= n i1[n]

1.7.3 Algorithms

Thư viện mẫu cung cấp khoảng 70 hàm chung, được gọi là các thuật toán, có thể được áp dụng cho các vùng chứa của thư viện mẫu và cho các mảng. Danh sách tất cả các thuật toán nằm trong phụ lục B. Các thuật toán này thường xuyên được sử dụng trong việc triển khai các chương trình, như xác định vị trí các phần tử trong vùng chứa, chèn một phần tử vào chuỗi các phần tử, xóa một một tử khỏi chỗi phần tử, chỉnh sửa các phẩn tử, so sánh các phần tử, tìm kiếm mọt giá trị dựa trên một chuỗi phần tử, sắp xếp chuỗi phần tử và v.v. Hầu hết tất cả các thuật toán trong thư viện mẫu sử dụng dụng iterators để chỉ ra phạm vi của phần tử khi chúng hoạt động. Đầu tiên, iterator tham chiếu phần tử đầu tiên của phạm vi. sau đó, iterator tham chiếu đến phần tử cuối cùng của phạm vi. Do đó, nó luôn được giả định rằng đạt được vị trí mà nó mong muốn bởi iterator thứ hai bằng cách tăng iterator thứ nhất. Dưới dây là một số ví duj:

Gọi hàm sau:

random_shuffle(c.begin(), c.end());

sắp xếp lại ngẫu nhiên tất cả các phần tử của vùng nhớ c.

i3 = find(i1, i2, el);

iterator trả về vị trí của phần tử e1 trong phạm vi từ i1, nhưng không bao gồm i2 (i1 <= e1 < e2)

n = count_if(i1, i2, oddNum);

thuật toán count_if() đếm các phần tử ở trong phạm vi i1 và i2 được chỉ ra bởi iterator với tham số được người dùng định nghĩa hàm booleanoddNUM() trả về true.

Thuật toán là các hàm được bổ sung cho các hàm thành viên được cung cấp bởi vùng chứa. Tuy nhiên, một số thuật toán cũng định nghĩa như là các hàm thành viên để cung cấp hiệu suất tốt hơn.

1.7.4 Function Objects

Trong C++, các toán tử gọi hàm () được coi như bất kì toán tử nào khác, đặc biệt chúng có thể nạp chồng hàm. Nó có thể trả về bất kỳ kiểu nào và nhận bất kì số lượng tham số, nhưng giống như toán tử gán, nó chỉ có thể nạp chồng một hàm thành viên. Bất kì đối tượng nào bao gồm định nghĩa của toán tử gọi hàm được gọi là đối tượng hàm. Một hàm đối tượng là một đối tượng, nhưng nó hoạt động như thể nó là một hàm. Khi một đối tượng hàm được gọi, các tham số của nó trở thành các tham số của toán tử gọi hàm.

Xét ví dụ về về tìm tổng các số từ việc áp dụng hàm f cho các số nguyên dương trong khoảng [n,m]. Việc thực hiện hàm sum() được trình bày trong phần 1.4.5 dựa vào cách sử dụng con trỏ hàm làm tham số cho hàm sum(). Tương tự chúng cũng có thể thực hiện bằng cách định nghĩa một lớp nạp chồng toán tử để gọi hàm:

class classf {
    public:
        classf() {
        }
        double operator() (double x) {
            return 2*x;
        }
    };

và sau đó định nghĩa:

double sum2(classf f, int n, int m) {
    double result = 0;
    for (int i = n; i <= m; i++)
        result += f(i);
    return result;
}

nó chỉ khác sum() ở tham số đầu tiên, là một đối tượng hàm, không phải là một hàm, còn không có tham số là đối tượng hàm thì nó giống nhau. Một hàm mới có thể được gọi, như dưới đây:

classf cf;
cout << sum2(cf,2,5) << endl;

hoặc đơn giản hơn

cout << sum2(classf(),2,5) << endl;

Cách gọi hàm sau yêu cầu một định nghĩa của hàm tạo classf() (ngay cả khi không có phần thân) để tạo một đối tượng thuộc kiểu classf() khi sum2() được gọi.

Tượng tự có thể thực hiện mà không gọi các toán tử nạp chồng hàm, được ví dụ trong hai định nghĩa sau:

class classf2 {
	public:
        classf2 () {
        }
    double run (double x) {
        return 2*x;
    }
};
double sum3 (classf2 f, int n, int m) {
    double result = 0;
    for (int i = n; i <= m; i++)
        result += f.run(i);
    return result;
}

và sau đó gọi:

cout << sum3(classf2(),2,5) << endl;

Thư viện mẫu phụ thuộc rất nhiều vào các đối tượng hàm. Cơ chế của các con trỏ hàm không đủ cho các toán tử được cài đặt sẵn. Làm thể nào để truyền dấu - đến hàm sum(). Cú pháp sum(-,2,5) là không hợp lệ. Để giải quyết vấn đề này, thư viện mẫu định nghĩa một đối tượng hàm cho các toán tử C++ trong <functional>. Ví dụ:

template<class T>
struct negate : public unary_function<T,T> {
    T operator()(const T& x) const {
        return -x;
    }
};

Bây giờ, sau khi định nghĩa lại hàm sum() nó trở thành một hàm chung:

template<class F>
double sum(F f, int n, int m) {
    double result = 0;
    for (int i = n; i <= m; i++)
        result += f(i);
return result;
}

Hàm cũng được gọi với đối tượng hàm negate:

sum(negate<double>(),2,5).