Vector trong thư viện mẫu

1.8 Vector in the standard template library

Vùng chưa đơn giản nhất trong thư viện mẫu là vector, nó là một cấu trúc dữ liệu với các khối bộ nhớ liền kề nhau như là một mảng. Bởi vì các vị trí bộ nhớ nằm liền kề nhau, chúng có thể được truy cập ngãu nhiên để cho thời gian truy cập của một phần tử bất kỳ là không thay đổi. Bộ nhớ được quản lí tự động để khi chèn một phần tử vào một vector đã bị đầy, khối bộ nhớ lớn hơn sẽ được phân bố cho vector, các phần tử của vector được sao chép sang khối bộ nhớ mới, và khối bộ nhớ cũ được giải phóng. Do đó, vector là một mảng linh hoạt, nghĩa là, kích thước của mạng có thể thay đổi động.

Hình 1.3 liệt kê tất cả các hàm thành viên theo thứ tự bảng chữ cái Latinh. Một ứng dụng của hàm này được minh hoạt trong hình 1.4. Nội dung của các vector bị ảnh hưởng được hiển thị dưới dạng cái chú thích trên mỗi dòng trong đó các hàm thành viên được gọi. Nội dung của một vector được xuất ra bởi một hàm chung printVector(), nhưng chương trình ở hình 1.4 chỉ có một lệnh gọi được hiển thị.

Hình 1.3

Hình 1.4

Để dùng vector, chương trình phải khai báo báo thư viện cho nó:

#include <vector>

Vector có 4 hàm tạo. Khai báo sau:

vector<int> v5(5);

khai báo sử dụng tên giống như hàm tạo

vector<int> v2(3,7);

Nhưng đối với vector v5, các phần tử nó được lấp đầy bằng hàm hạo số nguyên mặc định, và bằng 0.

Vector v1 được khai báo trống và sau đó chèn thêm các phần tử mới với hàm push_back(). Việc thêm một phần tử mới vào vector thường nhanh chóng trừ khi vector đã đầy và phải sao chép vào một vùng nhớ mới. Trường hợp này xảy ra nếu kích thước của vector bằng sức chứa của nó. Nhưng nếu vector có một số ô nhớ không sử dụng, nó có thể chứa một phần tử mới ngay lập tức trong thời gian không đổi. Giá trị hiện tại của tham số có thể kiểm tra với hàm size(), nó trả về số lượng phần tử hiện tại của vector, và hàm capacity() trả về kích thước của không gian lưu trữ hiện được phân bổ cho vectơ. Nhưng nếu cần thiết, kích thước của vector có thể thay đổi với hàm reserve(). Ví dụ, sau khi thực hiện lệnh

v3.reserve(6);

vector v3 = (2 3) vẫn giữ nguyên các phần tử và kích thước mảng vẫn là 2, nhưng kích thước bộ nhớ của nó thay đổi từ 2 thành 6. Hàm reserve() chỉ tác động đến kích thước bộ nhớ của vector chứ không tác động đến giá trị của nó. Hàm resize() tác động đến giá trị và có thể là kích thước bộ nhớ của vector. Ví dụ, vector v4 = (1 2 3 4 5) có kích thước vector bằng với kích thước mà bộ nhớ cấp phát cho nó và bằng 5. sau đó thực hiện lệnh:

v4.resize(7);

bây giờ v4 = (1 2 3 4 5 0 0), kích thước bằng 7 và kích thước bộ nhớ được cấp phát là 10, sau đó gọi lại hàm resize() khác

v4.resize(3);

v4 = (1 2 3), kích thước vector bằng 4, kích thước vùng nhớ bằng 10. Ví dụ chỉ ra rằng khi một không gian mới được cấp phát cho vector, nhưng nó không được trả về.

Lưu ý không có hàm push_front(). Điều này phản ánh thực tế rằng việc thêm một phần tử mới vào phía trước một vector là một hoạt động phức tạp bởi vì nó yếu cầu tất cả các phần tử phải được di chuyển theo một vị trí để nhường chỗ cho phần tử mới. Do đó, nó là một hoạt động tốn nhiều thời gian và có thể thực hiện nó với hàm insert(). Đây cũng là một chứng năng tự động phân bổ thêm bộ nhớ cho vector nếu cần thiết. Các hàm thực hiện các tác vụ này là hàm tạo, hàm reserve(), và toán tử =.

Các phần tử vecotr được truy cập với kí hiệu sử dụng cho mảng, như là

v4[0] = n;

hoặc iterators sử dụng kí hiệu tham chiếu được sử dụng cho con trỏ, ví dụ

vector<int>::iterator i4 = v4.begin();
*i4 = n;

Lưu ý rang một số hàm thành viên có kiểu trả về là T& (có nghĩa là kiểu tham chiếu). Ví du, đối với một vector số nguyên, kí hiệu của hàm front() là:

int& front(); 

Điều này có nghĩa là, với ví dụ này, hàm front() có thể được sử dụng cả hai phía trong toán tử gán:

v5.front() = 2;
v4[1] = v5.front();

Tất cả thuật toán trong thư viện mẫu có thể áp dụng cho các vectors. Ví duj:

replace(v5.begin(),v5.end(),0,7);

Thay tất cả các số 0 có trong vector v5 = (3 9 0 9 0) thành vector v5 = (3 9 7 9 7), sau đó gọi:

sort(v5.begin(),v5.end());

vector v5 sẽ được sắp xếp theo thứ tự tăng dần. Một số thuật toán cho phép sử dụng các tham số. Ví dụ, nếu chương trình khai báo định nghĩa hàm sau:

bool f1(int n) {
    return n < 4;
}

và sau đó gọi

replace_if(v5.begin(),v5.end(),f1,7);

hàm f1() sẽ áp dụng cho tất cả các phần tử của vector v5 và thay thế tất cả các phần tử bén hơn 4 với giá trị là 7. Trong trường hợp này, ban đầu v5 = (3 9 0 9 0) sau đó v5 =(7 9 7 9 7). Tình cờ, một cách khó hiểu là để đạt được kết quả tương tự mà không cần định nghĩa hàm f1() bằng cách:

replace_if(v5.begin(),v5.end(),bind2nd(less<int>(),4),7);

Trong đoạn mã này, bind2nd(op,a) là một hàm chung hoạt động như thể là nó chuyển đổi một hàm gồm có hai đối tượng hàm là tham số thành một hàm chỉ có một đối tượng hàm là tham số bằng cách cung cấp (ràng buộc) tham số thứ hai. Nó thực hiện điều này bằng cách tạo hai đối tượng hàm trong đó op là toán tử, a là tham số thứ 2.

Các thuật toán sắp xếp cho phép sự linh động như nhau. Trong ví dụ sắp xếp vector v5 được sắp xếp theo thứ tự tăng dần. làm thế nào để chúng ta có thể sắp xếp nó theo thứ tự giảm dần? Có một cách đó chính là sắp xếp nó theo thứ tự tăng dần rồi sau đó sử dụng thuật toán reverse(). Một cách khác là buộc sort() phải sử dụng toán tử > trong khi thực hiện. Điều này được thực hiện trực tiếp bằng cách sử dụng một đối tượng hàm làm tham số.

sort(v5.begin(),v5.end(),greater<int>());

hoặc bằng cách gián tiếp:

sort(v5.begin(),v5.end(),f2);

trong đó f2 được định nghĩa như sau:

bool f2(int m, int n) {
    return m > n;
}

Phương pháp đầu tiên là thuận tiện hơn, nhưng điều này chỉ có thể thực hiện được vì đối tượng hàm greater đã được định nghĩa trong thư viện mẫu. Đối tượng hàm này được định nghĩa là một cấu trúc khuôn mẫu, về bản chất toán tử được sử dụng là >. Do đó, greater<int>() có nghĩa là phép toán nên được sử dụng cho các số nguyên.

Phiên bản này của thuật toán sort(), lấy một tham số chức năng, đặc biệt hưu ích khi chúng ta cần sắp xếp các đối tượng phức tạp hơn số nguyên và chúng ta cần sử dụng các tiêu chí khác nhau. Xét định nghĩa của lớp sau:

 class Person {
	public:
        Person(char *n = "", int a = 0) {
            name = strdup(n);
        }
        ~Person() {
            free(name);
        }
        bool operator==(const Person& p) const {
            return strcmp(name,p.name) == 0 && age == p.age;
        }
        bool operator<(const Person& p) const {
            return strcmp(name,p.name) < 0;
        }
        bool operator>(const Person& p) const {
            return !(*this == p) && !(*this < p);
        }
	private:
        char *name;
        int age;
        friend bool lesserAge(const Person&, const Person&);
};

bây giờ, khai báo

vector<Person> v6(1,Person("Gregg",25));

thêm vào v6 hay đối tượng

v6.push_back(Person("Ann",30));
v6.push_back(Person("Bill",20));

và thực hiện lệnh

sort(v6.begin(),v6.end());

v6 thay đổi từ v6 = = ((“Gregg”, 25) (“Ann”, 30) (“Bill”, 20)) thành v6 = ((“Ann”, 30)(“Bill”, 20) (“Gregg”, 25)) đã được sắp xếp theo thứ tự tăng dần bởi vì phiên bản của thuật toán sort() chỉ gồm hai tham số của trình lặp sử dụng toán tử < được nạp chồng trong lớp Person.

sort(v6.begin(),v6.end(),greater<Person>());

v6 thay đổi từ v6 = = ((“Ann”, 30) (“Bill”, 20) (“Gregg”, 25)) thành v6 = = ((“Gregg”, 25) (“Bill”,20) (“Ann”, 30)) đã được sắp xếp theo thứ tự giảm dần bởi vì lần này phiên bản thuật toán sort() sử dụng toán tử > trong lớp đó. Để sắp xếp các đối tượng theo độ tuổi của chúng thì chúng ta cần làm gì? Trong trường hợp này chúng ta cần định nghiã một hàm

bool lesserAge(const Person& p1, const Person& p2) {
    return p1.age < p2.age;
}

và sau đó sử dụng tham số để gọi thuật toán sort():

sort(v6.begin(),v6.end(),lesserAge);

nó làm cho v6 = ((“Gregg”, 25) (“Bill”, 20) (“Ann”, 30)) thay đổi thành v6 = ((“Bill”,20) (“Gregg”, 25) (“Ann”, 30)).