SỬ DỤNG STL VECTOR TRONG C++ pptx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.22 MB, 16 trang )
SỬ DỤNG STL VECTOR TRONG C++
Nguyễn Trí Hải
11520094
KHMT06
I) Giới thiệu:
Lớp mảng động vector<T> có sẵn trong thư viện chuẩn STL của C++ cho phép định nghĩa
một mảng động các phần tử kiểu T, vector có các tính chất sau:
– Không cần phải khai báo kích thước của mảng vector có thể tự động cấp phát bộ nhớ, bạn sẽ
không phải quan tâm đến quản lý kích thước của nó.
– Vector còn có thể cho bạn biết số lượng các phần tử mà bạn đang lưu trong nó.
– Vector có các phương thức của stack.
– Hỗ trợ tất cả các thao tác cơ bản như chèn ,xóa, sao chép
II) Vì sao dùng Vector:
…
Kiểu vector có thể coi là kiểu mảng trong lập trình C truyền thống. Mảng là tập hợp các giá
trị cùng kiểu, được sắp xếp nối tiếp nhau. Các phần tử của mảng có thể được truy cập ngẫu
nhiên qua chỉ số.
Vấn đề đặt ra: Nếu vector là mảng thì tại sao lại phải sử dụng vector khi bạn đã quá
quen thuộc với mảng?
– Nếu bạn sử dụng mảng tĩnh: Mảng này luôn được khai báo với kích thước tối đa mà bạn có
thể dùng dẫn đến tốn nhiều vùng nhớ thừa.
– Nếu bạn sử dụng mảng động: Bạn phải xin cấp phát bộ nhớ, làm việc với con trỏ. Con trỏ là
khái niệm hay trong C, C++, nhưng nó là nguyên nhân của rất nhiều rắc rối trong lập trình.
– Không thuận tiện trong việc truyền tham số kiểu mảng vào hàm hay trả lại kiểu mảng từ
hàm.
– Nhược điểm quan trọng nhất: Nếu bạn sử dụng mảng vượt chỉ số vượt quá kích thước đã
khai báo, C++ sẽ không thông báo lỗi, điều này dẫn đến lỗi dây chuyền do các lệnh lỗi đã tác
động đến các biến khác trong chương trình
Vector là một container cung cấp khả năng sử dụng mảng mềm dẻo, có kiểm soát range
check khi cần thiết, với kích thước tùy ý (mà không cần phải sử dụng con trỏ). Ngoài ra
vector cho phép bạn chèn thêm hoặc xóa đi một số phần tử chỉ bằng 1 lệnh (không phải sử
dụng vòng lặp như đối với mảng).
III) Cú pháp:
Để dùng vector thì cần thêm 1 header #include <vector> và phải có using std::vector; vì
vector được định nghĩa trong STL (Standard Template Library)
Ví dụ:
vector<int> A;
Câu lệnh trên định nghĩa 1 vector có kiểu int. Kiểu vector được đặt trong 2 dấu ngoặc nhọn.
Kích thước của vector có thể tự nâng lên nên không cần khai báo số phần tử hoặc nếu muốn
khai báo thì bạn có thể khai báo như sau:
vector<int> A(10);
Câu lệnh trên khai báo A là 1 vector kiểu int có 10 phần tử. Mặc dù size của nó bằng 10
nhưng sử dụng hơn vẫn được.
Ta có thể khởi tạo giá trị mặc định cho vector:
vector<int> A(10,2);
Câu lệnh trên khai báo 10 phần tử vector A được khởi tạo bằng 2. Đồng thời ta cũng có thể
khởi tạo cho 1 vector sẽ là bản sao của 1 hoặc 1 phần vector khác, ví dụ :
vector<int> A(10,2);
vector<int> B(A);
vector<int> C(A.begin(), A.begin() + 5 );
Để hiểu rõ vè vector, ta xem đoạn code sau:
#include <iostream> // Thư viện iostream phục vụ ghi dữ liệu ra màn hình
#include <vector> // Thư viện vector, sử dụng kiểu vector
using namespace std; // Sử dụng namespace std
int main()
{
vector<int> V(3);
// V kiểu vector số nguyên (sử dụng giống mảng int[3])
V[0] = 5;
// Gán giá trị cho các phần tử của biến V
V[1] = 6;
// Sử dụng dấu móc [] hoàn toàn giống với mảng
V[2] = 7;
for (int i=0; i<V.size(); i++)
// Ghi giá trị các phần tử của V ra màn hình
cout << V[i] << endl;
// Nếu sử dụng mảng, bạn phải có biến lưu kích thước
}
Ví dụ trên cho bạn thấy việc sử dụng vector rất đơn giản, hoàn toàn giống với mảng nhưng bộ
nhớ được quản lý tự động, bạn không phải quan tâm đến giải phóng các vùng bộ nhớ đã xin
cấp phát.
Trường hợp xác định kích thước mảng khi chương trình đang chạy, chúng ta dùng hàm dựng
mặc định (default constructor) để khai báo mảng chưa xác định kích thước, sau đó dùng
phương thức resize() để xác định kích thước của mảng khi cần. Chương trình sau đây nhập
vào n từ (word) mỗi từ là một chuỗi kiểu string:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
int iWordNum;
vector<string> arrWords;
cout << “Enter number of words = “;
cin >> iWordNum;
arrWords.resize(iWordNum);
for (int i = 0; i < arrWords.size(); i ++)
{
cout << “Enter word ” << i << ” = “;
cin >> arrWords[i];
}
cout << “After entering data ” << endl;
for (int i = 0; i < arrWords.size(); i ++)
cout << arrWords[i] << endl;
}
Ouput:
Enter number of words = 3
Enter word 1 = hello
Enter word 1 = c++’s
Enter word 1 = world
After entering data
hello
c++’s
world
Press any key to continue . . .
IV) Các phương thức:
Các phương thức của stack: push_back() và pop_back()
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int i;
vector<int> V;
for (i=0; i<5; i++)
// Lặp 5 lần, mỗi l ần đưa thêm 1 số vào vector
V.push_back(i);
// Như vậy, vector có thể được sử dụng như stack
cout << endl << “Mang ban dau:” << endl;
for (i=0; i<V.size(); i++)
// Ghi lại nội dung của mảng ra màn h.nh
cout << V[i] << endl;
V.pop_back( ); // Xóa phần tử vừa chèn vào đi
cout << endl << “Xoa phan tu cuoi:” << endl;
for (i=0; i<V.size(); i++)
// In nội dung của vector sau khi xóa
cout << V[i] << endl;
return 0;
}
Với ví dụ trên, bạn có thể thấy ta có thể sử dụng vector như 1 stack:
– Không nên dùng toán tử [] để truy xuất các phần tử mà nó không tồn tại, nghĩa là ví dụ
vector size = 10, mà bạn truy xuất 11 là sai. Để thêm vào 1 giá trị cho vector mà nó không có
size trước hoặc đã full thì ta dùng hàm thành viên push_back(), hàm này s ẽ thêm 1 phần tử
vào cuối vector.
– Tương tự với thao tác xóa một phần tử ở cuối ra khỏi vector, bạn cũng chỉ cần sử dụng 1
lệnh: pop_back( )
Xóa tại vị trí bất kỳ, xóa trắng:
#include <iostream>
#include <vector>
using namespace std;
template <class T>
void print(const vector<T>&v)
{
for (int i =0; i < v.size(); i++)
cout << v[i] << endl;
}
int main()
{
char *chao[] = {“Xin”, “chao”, “tat”, “ca”, “cac”, “ban”};
int n = sizeof(chao)/sizeof(*chao);
vector<char*> v(chao, chao + n);
//đây là 1 cách khởi tạo vector
cout << “vector truoc khi xoa” << endl;
print(v);
v.erase(v.begin()+ 2, v.begin()+ 5);
//xóa từ phần tử thứ 2 đến phần tử thứ 5
v.erase( v.begin()+1 );
//xóa phần tử thứ 1
cout << “vector sau khi xoa” << endl;
print(v);
v.clear();//Xóa toàn bộ các phần tử
cout << “Vector sau khi clear co ”
<< v.size() << ” phan tu” << endl;
return 0;
}
Output:
vector truoc khi xoa
Xin
chao
tat
ca
cac
ban
vector sau khi xoa
xin
ban
Vector sau khi clear co 0 phan tu
Phương thức chèn
iterator insert ( iterator position, const T& x );
void insert ( iterator position, size_type n, const T& x );
void insert ( iterator position, InputIterator first, InputIterator last );
Ví dụ:
// inserting into a vector
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
vector<int> v1(4,100);
v1.insert ( v1.begin()+3 , 200 );
//chèn 200 vào trước vị trí thứ 3
v1.insert ( v1.begin()+2 ,2,300);
//chèn 2 lần 300 vào trước vị trí thứ 2
vector<int> v2(2,400);
int a [] = { 501, 502, 503 };
v1.insert (v1.begin()+2, a, a+3);
//chèn mảng a (3 phần tử) vào trước vị trí thứ 2
v1.insert (v1.begin()+4,v2.begin(),v2.end());
//chèn v2 vào trước vị trí thứ 4
cout << “v1 contains:”;
for (int i =0; i < v1.size(); i ++)
cout << ” ” << v1[i];
return 0;
}
Output:
v1 contains: 100 100 501 502 400 400 503 100 200 300 300 100
Một số hàm khác và chức năng
Những toán tử so sánh: được định nghĩa cho vector: ==, <, <=, !=, >, >=
Tham chiếu back(), front()
template<class _TYPE, class _A>
reference vector::front( );
template<class _TYPE, class _A>
reference vector::back( );
Trả về tham chiếu đến phần tử đầu và cuối vector:
v.front() v[0] và v.back() v[v.size()-1]
#include <iostream>
#include <vector>
using namespace std;
int main ()
{
int a[] = {3,2,3,1,2,3,5,7};
int n = sizeof(a)/sizeof(*a);
vector<int> v(a, a+n);
cout << “phan tu dau la ” << v.front() << endl;
cout << “phan tu cuoi la ” << v.back() << endl;
cout << “gan phan tu cuoi la 9 ” << endl;
v.back() = 9;
cout << “gan phan tu dau la 100 ” << endl;
v.front() = 100;
cout << “kiem tra lai vector: “;
for (int i =0; i < v.size(); i++)
cout << v[i] << “ “;
cout << endl;
return 0;
}
Output:
phan tu dau la 3
phan tu cuoi la 7
gan phan tu cuoi la 9
gan phan tu dau la 100
kiem tra lai vector: 100 2 3 1 2 3 5 9
Press any key to continue …
Hàm thành viên empty()
Để xác định vector có rỗng hay không ta dùng hàm thành viên empty(), hàm này trả về true
nếu vector rỗng, và false ngược lại. Cú pháp :
if(v.empty() == true) {
cout << “No values in vector \n”;
}
– capacity() : Trả về số lượng phần tử tối đa mà vector được cấp phát, đây là 1 con s ố có thể
thay đổi do việc cấp phát bộ nhớ tự động hay bằng các hàm như reserve() và resize()
Sự khác biệt giữa 2 hàm size() và capacity() :
#include<vector>
#include<iostream>
int main(int argc , char **argc)
{
vector<int >so1,so2[10];
so1.reserve(10);
cout <<“Kich thuoc toi da:”<<so1.capacity();
cout <<“\n Kich thuoc hien tai cua mang 2 “<<so2.size()<<endl;
return 0 ;
}
– reserve(): cấp phát vùng nhớ cho vector, giống như realloc() của C và không giống
vector::resize(), tác dụng của reserve để hạn chế vector tự cấp phát vùng nhớ không cần
thiết.Ví dụ khi bạn thêm 1 phần tử mà vượt quá capacity thì vector sẽ cấp phát thêm, việc này
lặp đi lặp lại sẽ làm giảm performance trong khi có những trường hợp ta có thể ước lượng
được cần sử dụng bao nhiêu bộ nhớ.
Ví dụ nếu ko có reserve() thì capacity sẽ là 4 :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector< int > my_vect;
my_vect.reserve( 8 );
my_vect.push_back( 1 );
my_vect.push_back( 2 );
my_vect.push_back( 3 );
cout << my_vect.capacity() << “\n”;
return 0;
}
– swap(); hoán đổi 2 container v ới nhau (gi ống việc hoán đổi giá trị của 2 biến kiểu số). Ví
dụ : v1.swap(v2);
V.Kiểm tra tràn chỉ số mảng:
Có một vấn đề chưa được đề cập đến từ khi ta làm quen với vector, đó là khả năng kiểm tra
tràn chỉ số mảng (range check), để biết về khả năng này, chúng ta lại ti ếp tục với một ví dụ
mới :
#include <iostream>
#include <vector>
#include <conio.h>
using namespace std;
int main()
{
try { // sử dụng try catch để bẫy lỗi
vector<long> V(3, 10);
// Khởi tạo vector gồm 3 thành phần
// Tất cả gán giá trị 10
cout << “V[0]=” << V[0] << endl;
// Đưa thành phần 0 ra màn hình
cout << “V[1]=” << V[1] << endl;
// Đưa thành phần 1 ra màn hình
cout << “V[2]=” << V[2] << endl;
// Đưa thành phần 2 ra màn hình
cout << “V[3]=” << V[3] << endl;
// Thành phần 3 (lệnh này hoạt động không
// đúng vì V chỉ có 3 thành phần 0,1,2
cout << “V[4]=” << V[4] << endl;
// Thành phần 4 (càng không đúng)
// Nhưng 2 lệnh trên đều không gây lỗi
cout << “V[0]=” << V.at(0) << endl;
// Không sử dụng [], dùng phương thức at
cout << “V[1]=” << V.at(1) << endl;
// Thành phần 1, OK
cout << “V[2]=” << V.at(2) << endl;
// Thành phần 2, OK
cout << “V[3]=” << V.at(3) << endl;
// Thành phần 3: Lỗi, chương trình dừng
cout << “V[4]=” << V.at(4) << endl;
getchar();
} catch (exception &e) {
cout << “Tran chi so ! ” << endl;
}
return 0;
}
Trong ví dụ này, chúng ta lại có thêm một số kinh nghiệm sau:
– Nếu sử dụng cú pháp biến_vector[chỉ _số], chương trình sẽ không tạo ra lỗi khi s ử dụng chỉ
số mảng nằm ngoài vùng hợp lệ (giống như mảng thường). Trong ví dụ, chúng ta mới chỉ lấy
giá trị phần tử với chỉ số không hợp lệ, trường hợp này chỉ cho kết quả sai. Nhưng nếu chúng
ta gán giá trị cho phần tử không hợp lệ này, hậu quả sẽnghiêm trọng hơn nhiều vì thao tác đó
sẽ làm hỏng các giá trị khác trên bộ nhớ.
– Phương thức at(chỉ _số) có tác dụng tương tự như dùng ký hiệu [], nhưng có một sự khác
biệt là thao tác này có kiểm tra chỉ số hợp lệ. Minh chứng cho nhận xét này trong ví dụ khi
chương trình chạy đến vị trí lệnh V.at(3), lệnh này không cho ra kết quả mà tạo thành thông
báo lỗi.
VI.Mảng 2 chiều với Vector:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector< vector<int> > matrix(3, vector<int>(2,0));
//chu y viet > > de khong nham voi toan tu >>
for(int x = 0; x < 3; x++)
for(int y = 0; y < 2; y++)
matrix[x][y] = x*y;
for(int x = 0; x < 3; x++)
for(int y = 0; y < 2; y++)
cout << matrix[x][y];
cout << ‘\n’;
return 0;
}
Ví dụ này minh họa việc sử dụng mảng 2 chiều, thực chất đây là một vector của vector. Mảng
2 chiều sử dụng biện pháp này có thể có kích thước khác nhau giữa các d.ng (ví dụ mảng 2
chiều là nửa trên của ma trận)
VII.Sử dụng iterator
Container ( thùng chứa ) : Một kiểu cấu trúc dữ liệu dùng để lưu trữ thông tin. Ví dụ: mảng
(array), list, vector, deque
Container nào cũng có các phương thức sau đây
Phương thức Mô tả
size()
S
ố
lư
ợ
ng ph
ầ
n
t
ử
empty () Trả về 1 nếu container rỗng, 0 nếu ngược lại.
max_size() Trả về số lượng phần tử tối đa đã được cấp phát
== Trả về 1 nếu hai container giống nhau
!= Trả về 1 nếu hai v khác nhau
begin()
Tr
ả
v
ề
iterator đ
ầ
u tiên c
ủ
a container
end() Trả về iterator lặp cuối cùng của container
front() Trả về tham chiếu đến phần tử đầu tiên của container
back() Trả về tham chiếu đến phần tử cuối cùng của container
swap() Hoán đổi 2 container với nhau (giống việc hoán đổi giá trị của 2 biến)
Trong thư viện STL thì người ta tích hợp lớp đối tượng Iterator (bộ lặp hay biến lặp) cùng với
các container.Tư tưởng đó thể hiện như sau:
o Các đối tượng Iterator là các con trỏ đến các đối tượng của lớp lưu trữ:
typedef__gnu_cxx::__normal_iterator <pointer,vector_type> iterator;
o Khai báo lớp Iterator như là 1 lớp nằm trong lớp lưu trữ.
o Xác định trong lớp lưu trữ các phương thức thành phần như:
+ begin() – trả lại con trỏ kiểu đối tượng Iterartor đến phần tử đầu tiên của nằm trong
đối tượng lớp lưu trữ.
+ end() – trả lại con trỏ kiểu Iterator trỏ đến 1 đối tượng nào đó bên ngoài tập các
phần tử được lưu trữ. Đối tượng bên ngoài nào đó có thể có các định nghĩa khác nhau.Trong
trường hợp cụ thể như vector ta có thể hiểu là trỏ đến phần tử sau phần tử cuối cùng.
o Xác định trong lớp đối tượng kiểu Iterator các toán tử như sau:
++p hoặc p++ : chuyển iterator p đến phần tử kế tiếp.
p hoặc p : chuyển iterator p đến phần tử đằng trước nó.
*p : xác định giá trị của phần tử mà iterator p trỏ đến.
Như bạn biết, mảng và con trỏ có mối quan hệ chặt chẽ với nhau trong C++. Một mảng có thể
được truy xuất thông qua con trỏ. Sự tương đương này trong STL là mối quan hệ giữa iterator
và vector, mà tổng quát hơn là với container. Nó cung cấp cho chúng ta khả năng xử lý theo
chu kì thông qua nội dung của container theo một cách giống như là bạn sử dụng con trỏ để
tạo xử lý chu kỳ trong mảng.
Bạn có thể truy xuất đến các thành phần của một container bằng sử dụng một iterator:
<container> coll;
for (<container>::iterator it = coll.begin(); it != coll.end(); ++it)
{
*it;
//……
}
Dưới đây chúng ta xét 1 ví dụ làm việc với thư viện STL với lớp vector và con trỏ kiểu
iterator như sau:
#include<iostream>
#include<vector>
using std::vector;
void main()
{
vector<int> v;
for(int i = 10; i < 15; i++) v.push_back(i );
vector<int>::iterator it = v.begin();
while(it != v.end())
{
cout << *it << ” “;
it++;
}
}
Vì iterator định nghĩa bên trong các container – thế nào là “phần tử đầu”, “phần tử cuối”,
“phần tử tiếp theo” … nên nó “chứa” thông tin cấu trúc phục vụ cho việc duyệt container. Nó
che đi cấu trúc bên trong và cho phép ta viết các đoạn mã tổng quát để duyệt hay chọn phần
tử trên các container khác nhau mà không cần biết cấu trúc của container đó ra sao.
Trong các reversible container như vector còn định nghĩa thêm reverse_iterator (cái tên nói
lên chức năng: iterator nghịch đảo) là nested class với các “hằng” tương ứng:
vector<T>::reverse_iterator rbegin();
vector<T>::reverse_iterator rend();
Ví dụ : duyệt vector theo 2 chiều
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
using namespace std;
int main()
{
int A[] = {3,2,3,1,2,3,5,3};
int n = sizeof(A)/sizeof(*A);
vector<int> V;
for (int i=0; i<n; i++){
V.push_back(A[i]);
vector<int>::iterator vi;
cout << endl << “Duyet chieu xuoi” << endl;
for (vi=V.begin(); vi!=V.end(); vi++)
cout << *vi << endl;
vector<int>::reverse_iterator rvi;
cout << endl << “Duyet theo chieu nguoc” << endl;
for (rvi=V.rbegin(); rvi!=V.rend(); rvi++)
cout << *rvi << endl;
getchar();
}
}
Chuyển đổi qua lại giữa reverse_iterator và iterator:
+ Hàm thành viên base(): trả về một iterator trỏ đến phần tử hiện tại của reverse_iterator.
+ Tạo reverse_iterator từ iterator: Contructor reverse_iterator(RandomAccessIterator i);
Ví dụ:
vector<int> v;
vector<int>::iterator it (v.begin());
vector<int>:: reverse_iterator ri(v.rbegin());
//goi contructor
assert(ri.base()==v.end()-1);
ri=v.begin();
//goi contructor
assert(ri.base()==it);
*Lệnh assert(); dùng để kiểm tra một biểu thức điều kiện.
Iterator là 1 trong 4 thành phần chính của STL (container, iterator, algorithm và functor).
Container và algorithm giao tiếp qua nó: nhiều hàm và algorithm trong STL nhận các đối số
là iterator.Iterator gắn liền với tất cả các loại container, đây là khái ni ệm bạn cần nắm rất
vững nếu muốn làm việc tốt với STL
Bảng: các hàm thành viên lớp vector
Hàm thành phần Mô tả
template<class lnlter>
void ass
ign(lnlter start, lnlter end);
Gán giá trị cho vector theo trình tự từ start
đ
ế
n end.
Template<class Size, class T)
Void assign(Size num, const T &val = T());
Gán giá trị của val cho num phần tử của
vector.
Reference at(size_type l);
Const_reference at(size_type l) const;
Trả về một tham chiếu đến một phần tử đượ
c
chỉ định bởi i.
Reference back(size_type l);
Const_reference at(size_type l) const;
Trả về một tham chiếu đến phần tử cuôi cùng
của vector.
Iterator begin();
Const _iterator begin() const;
Trả về một biến lặp chỉ định phần tử đầu tiên
của vector.
Size_type capacity() const; Trả về dung lượng hiện thời của vector. Đây
là số lượng các phần tử mà nó có thể chứa
trư
ớ
c khi nó c
ầ
n c
ấ
p phát thêm vùng nh
ớ
.
Void clear();
Xóa t
ấ
t c
ả
các p
h
ầ
n t
ử
trong vector.
Bool empty() const; Trả về true nếu vector rỗng và trả về false
n
ế
u ngư
ợ
c l
ạ
i.
Iterator end();
Const_iterator end() const;
Trả về một biến lặp để kết thúc một vector.
iterator erase(iterator i); Xóa một phần tử được chỉ bởi i. Trả về một
biến lặp chỉ đến phần tử sau phần tử được
xóa.
Iterator erase(iterator start, iterator end); Xóa những phần tử trong dãy từ start đến
end. Trả về một biến lặp chỉ đến phần tử sau
cùng c
ủ
a vector.
Reference front();
Const_reference front() const;
Trả về một tham chiếu đến phần tử đầu tiên
c
ủ
a vector.
Allocator_type get_allocator() const;
Tr
ả
v
ề
vùng nh
ớ
đư
ợ
c c
ấ
p phát cho vector.
Iterator insert(iterator I, const T&val=T()); Chèn val trực tiếp vào trước thành phần được
chỉ định bởi i. biến lặp chỉ đến phần tử được
trả về.
Void insert(iterator I, size_type num, const T&
val);
Chèn num val một cách trực tiếp trước phần
tử được chỉ định bởi i.
Template<class lnlter>
Void insert(iterator I, lnlter start, lnltr end);
Chèn chuỗi xác định từ start đến end trực tiếp
trước một phần tử được chỉ định bởi i.
Size_type max_size() const; Trả về số lượng phần tử lớn nhất mà vector
có thể chứa.
Reference operator[](size_type i) const;
Const_reference operator[] (size_type i) const;
Trả về một tham chiếu đến phần tử được chỉ
định bởi i.
Void pop_back(); Xóa phần tử cuối cùng trong vector.
Void push_back(cons T&val); Thêm vào một phần tử có giá trị val vào cuối
của vector.
Reverse_iterator rbegin();
Const_reverse_iterator rbegin() const;
Trả về biến lặp nghịch chỉ điểm kết thúc của
vector.
Reverse_iterator rend();
Tr
ả
v
ề
m
ộ
t bi
ế
n l
ặ
p ngh
ị
ch ch
ỉ
đi
ể
m b
ắ
t đ
ầ
u
Const_reverse_iterator rend() const; của vector.
Void reverse (size_type num); Thiết lập kích thước của vector nhiều nhất là
bằng num.
Void resize (size_type num, T val =T()); Chuyển đổi kích thước của vector được xác
định bởi num. Nếu như kích thước của vector
tăng lên thì các phần tử có giá trị val sẽ được
thêm vào cuối vector.
Size_type size() const; Trả về số lượng các phần tử hiện thời của
trong vector.
Vois swap(vector<T, Allocator>&ob) Chuyển đổi những phần tử được lưu trong
vector hiện thời với những phần tử trong ob.
VIII.Dùng 1 số hàm cơ bản trong thư viện algorithm
Khởi tạo:
Bạn có thể sử dụng lệnh fill của thư viện <algorithm> để tô một vùng giá trị của 1 container
(thường là 1 mảng, 1 vector)
// fill algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void printint(const int &i)
{
cout << i << endl;
}
int main ()
{
vector<int> v(8); // v: 0 0 0 0 0 0 0 0
fill(v.begin(),v.begin()+4,5); // v: 5 5 5 5 0 0 0 0
fill(v.begin()+3,v.end()-2,8); // v: 5 5 5 8 8 8 0 0
cout << “vector contains:”;
for_each( v.begin(), v.end(), printint );
return 0;
}
template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen);
Hàm generate sẽ “sinh” từng phần tử trong khoảng nào đấy của vector bằng cách gọi hàm
được chỉ định ( một hàm
trả về cùng kiểu và không có đối số)
Ví dụ với hàm rand():
vector<int> V;
srand( time(NULL) );
//
generate( V.begin(), V.end(), rand );
Copy iterator ( tương tự memcpy() đối với pointer )
int a[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(a)/sizeof(*a);
vector<int> v1(a, a+n);
vector<int> v2(n);
copy(v1.begin(), v1.end(), v2.begin());
//copy_n(v1.begin(), v1.size(), v2.begin());
for (int i =0; i <n; i++)
cout << v2[i] << ” “;
// The output is “1 2 3 4 5 6”.
Đảo ngược (reverse) vector
Bạn có thể sử dụng lệnh reverse trong <algorithm> để đảo ngược container (ở đây là 1
vector)
// reverse algorithm example
#include <iostream>
#include <algorithm>
#include <vector> tr.nh C++ Nguyễn Phú Quảng
#include <conio.h>
using namespace std;
int main ()
{
vector<int> a;
// set some values:
for (int i=1; i<10; ++i) a.push_back(i); // 1 2 3 4 5 6 7 8 9
reverse(a.begin(),a.end()); // 9 8 7 6 5 4 3 2 1
// print out content:
cout << “a contains:”;
int i, n = a.size();
for (i=0; i<n; i++)
cout << a[i] << ” “;
cout << endl;
getchar();
}
Thay thế các giá trị (replace)
Lệnh replace tìm kiếm 1 giá trị trong container, ở đây là vector thay thế giá trị tìm được bởi
giá trị mới.
// replace algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
#include <conio.h>
using namespace std;
int main ()
{
int myints[] = { 10, 20, 30, 30, 20, 10, 10, 20 };
vector<int> a (myints, myints+8); // 10 20 30 30 20 10 10 20
replace(a.begin(), a.end(), 20, 99); // 10 99 30 30 99 10 10 99
cout << “a contains: “;
int i, n;
for (i=0, n=a.size(); i<n; i++)
cout << a[i] << ” “;
getchar();
}
Thay thế các giá trị theo điều kiện (replace_if)
Các hàm có hậu tố _if như remove_if, replace_if, find_if, count_if … sử dụng 1 con trỏ hàm
hoặc 1 functor để làm tiêu chí tìm kiếm (dạng của con trỏ hàm hoặc functor tùy vào mục đích
sử dụng)
Lệnh replace_if cho phép tìm giá trị theo điều kiện do một hàm trả về. Để sử dụng lệnh này
bạn phải khai báo 1 hàm có giá trị trả về là bool nhận tham số là giá tr ị của 1 element. Khi
hàm trả về true, giá trị tương ứng sẽ bị thay thế bởi giá trị mới. Hàm ki ểm tra nên khai báo
inline để tốc độ nhanh hơn.
// replace_if example
#include <iostream>
#include <algorithm>
#include <vector>
#include <conio.h>
using namespace std;
inline bool SoLe(int i) { return ((i%2)==1); }
int main ()
{
vector<int> a;
// set some values:
for (int i=1; i<10; i++) a.push_back(i); // 1 2 3 4 5 6 7 8 9
replace_if(a.begin(), a.end(), SoLe, 0); // 0 2 0 4 0 6 0 8 0
cout << “a contains: “;
int i, n;
for (i=0, n=a.size(); i<n; i++)
cout << a[i] << ” “;
getchar();
}
Xóa với remove và remove_if
Ví dụ 1:
//remove
int A[] = {3,1,4,1,5,9};
int N = sizeof(A)/sizeof(*A);
vector<int> V(A, A+N);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, ” “));
//The output is “3 1 4 1 5 9”.
cout << endl;
vector<int>::iterator new_end =
remove(V.begin(), V.end(), 1);
V.resize(new_end – V.begin());
copy(V.begin(), V.end(), ostream_iterator<int>(cout, ” “));
// The output is “3 4 5 9”.
Ví dụ 2:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool IsOdd(int x){
return x%2;
}
int main()
{
int a[] = {3,1,4, 8, 5, 2, 9};
int n = sizeof(a)/sizeof(*a);
vector<int> vec(a, a+n);
vector<int>::iterator new_end =
remove_if( vec.begin(), vec.end(), IsOdd );
vec.erase(new_end, vec.end());
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, ” “));
// The output is “4 8 2”.
return 0;
}
Các hàm có hậu tố _copy như remove_copy, remove_if_copy, replace_copy,
replace_if_copy, reverse_copy sử dụng tương tự nhưng tạo ra và thao tác trên bản sao
container
Sắp xếp container (ở đây là vector)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void printint(const int &i)
{
cout << i << endl;
}
int main()
{
int A[] = {3,2,3,1,2,3,5,3};
int n = sizeof(A)/sizeof(*A);
vector<int> V(A, A+n);
cout << endl << “Danh sach ban dau” << endl;
for_each( V.begin(), V.end(), printint );
V.sort();
vector<int>::iterator vi;
cout << endl << “Danh sach sau khi sap xep” << endl;
for_each( V.begin(), V.end(), printint );
getchar();
}
Trong ví dụ trên ta học được cách sử dụng hàm for_each() và sort() để thao tác với 1
container.
Tìm kiếm tuyến tính
// lineal search
#include <iostream.h>
#include <algorithm>
#include <vector>
using namespace std;
bool IsOdd(int x)
{
return x%2;
}
int main()
{
int a[] = {2,4,2,6,9,1,2,3,2,3,4,5,6,4,3,2,1};
int n = sizeof(a)/sizeof(*a);
vector<int> v(a, a+n);
int first = find(a, a+n, 1) – a;
//các hàm thuật toán hoàn toàn có thể thao tác trên mảng & con trỏ thường
cout << “[array] so thu tu cua phan tu dau tien = 1: ” << first << endl;
first = find(v.begin(),v.end(), 1) – v.begin();
cout << “[vector] so thu tu cua phan tu dau tien = 1: ” << first << endl;
//find_if
vector<int>::iterator it;
it = find_if(v.begin(),v.end(), IsOdd );
first = it – v.begin();
cout << “Phan tu le dau tien la ” << *it << ” o vi tri thu ” << first << endl;
return 0;
}
Ngoài ra còn có nhiều hàm tìm kiếm khác: hàm search() dùng để so khớp 1 chuối liên tiếp
các phần tử cho trước, hàm search_n tìm kiếm với số lần lặp xác định, hàm find_end tìm kết
quả cuối cùng, find_first_not_of(), find_last_not_of() …
Đếm & tìm min max
//counting
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool IsOdd(int x)
{
return x%2;
}
int main()
{
int a[] = {3,2,3,1,2,4,5,3};
int n = sizeof(a)/sizeof(*a);
vector<int> v(a, a+n);
cout << “So luong so 3 trong mang: ” << count(v.begin(),v.end(), 3) << endl;
cout << “So luong so le trong mang: ” << count_if(v.begin(),v.end(), IsOdd) <<
endl;
cout << “So nho nhat trong mang: ” << *min_element(v.begin(),v.end()) << endl;
cout << “So lon nhat trong mang: ” << *max_element(v.begin(),v.end()) << endl;;
return 0;
}
Hàm chuyển đổi hàng lo ạt transform()
Một trong những giải thuật thú vị hơn là transform(), phần tử được sửa đổi từng cái trong
một phạm vi theo một chức năng mà bạn cung cấp.
#include <vector>
#include <algorithm>
using namespace std;
template <class T>
T inc(T x )
//hàm dùng để chuyển đổi
{
return x+1;
}
int main()
{
int a[] = {3,2,3,1,2,3,5,3};
int n = sizeof(a)/sizeof(*a);
vector<int> v(a, a+n);
transform(v.begin(), v.end(), v.begin(), inc<int> );
copy(v.begin(), v.end(), ostream_iterator<int>(cout, ” “));
// The output is “4 3 4 2 3 4 6 4”.
return 0;
}
Ngoài ra còn nhiều hàm thuật toán khác có thể tham khảo trong tài liệu
reference của c++
Vector là một container cung cấp khả năng sử dụng mảng mềm dẻo, có kiểm soát rangecheck khi cần thiết, với kích thước tùy ý (mà không cần phải sử dụng con trỏ). Ngoài ravector cho phép bạn chèn thêm hoặc xóa đi một số phần tử chỉ bằng 1 lệnh (không phải sửdụng vòng lặp như đối với mảng).III) Cú pháp:Để dùng vector thì cần thêm 1 header #include và phải có using std::vector; vìvector được định nghĩa trong STL (Standard Template Library)Ví dụ:vector A;Câu lệnh trên định nghĩa 1 vector có kiểu int. Kiểu vector được đặt trong 2 dấu ngoặc nhọn.Kích thước của vector có thể tự nâng lên nên không cần khai báo số phần tử hoặc nếu muốnkhai báo thì bạn có thể khai báo như sau:vector A(10);Câu lệnh trên khai báo A là 1 vector kiểu int có 10 phần tử. Mặc dù size của nó bằng 10nhưng sử dụng hơn vẫn được.Ta có thể khởi tạo giá trị mặc định cho vector:vector A(10,2);Câu lệnh trên khai báo 10 phần tử vector A được khởi tạo bằng 2. Đồng thời ta cũng có thểkhởi tạo cho 1 vector sẽ là bản sao của 1 hoặc 1 phần vector khác, ví dụ :vector A(10,2);vector B(A);vector C(A.begin(), A.begin() + 5 );Để hiểu rõ vè vector, ta xem đoạn code sau:#include // Thư viện iostream phục vụ ghi dữ liệu ra màn hình#include // Thư viện vector, sử dụng kiểu vectorusing namespace std; // Sử dụng namespace stdint main()vector V(3);// V kiểu vector số nguyên (sử dụng giống mảng int[3])V[0] = 5;// Gán giá trị cho các phần tử của biến VV[1] = 6;// Sử dụng dấu móc [] hoàn toàn giống với mảngV[2] = 7;for (int i=0; i#include #include using namespace std;int main()int iWordNum;vector arrWords;cout << “Enter number of words = “;cin >> iWordNum;arrWords.resize(iWordNum);for (int i = 0; i < arrWords.size(); i ++)cout << “Enter word ” << i << ” = “;cin >> arrWords[i];cout << “After entering data ” << endl;for (int i = 0; i < arrWords.size(); i ++)cout << arrWords[i] << endl;Ouput:Enter number of words = 3Enter word 1 = helloEnter word 1 = c++’sEnter word 1 = worldAfter entering datahelloc++’sworldPress any key to continue . . .IV) Các phương thức:Các phương thức của stack: push_back() và pop_back()#include #include using namespace std;int main()int i;vector V;for (i=0; i<5; i++)// Lặp 5 lần, mỗi l ần đưa thêm 1 số vào vectorV.push_back(i);// Như vậy, vector có thể được sử dụng như stackcout << endl << “Mang ban dau:” << endl;for (i=0; i#include using namespace std;template void print(const vector&v)for (int i =0; i < v.size(); i++)cout << v[i] << endl;int main()char *chao[] = {“Xin”, “chao”, “tat”, “ca”, “cac”, “ban”};int n = sizeof(chao)/sizeof(*chao);vector v(chao, chao + n);//đây là 1 cách khởi tạo vectorcout << “vector truoc khi xoa” << endl;print(v);v.erase(v.begin()+ 2, v.begin()+ 5);//xóa từ phần tử thứ 2 đến phần tử thứ 5v.erase( v.begin()+1 );//xóa phần tử thứ 1cout << “vector sau khi xoa” << endl;print(v);v.clear();//Xóa toàn bộ các phần tửcout << “Vector sau khi clear co “<< v.size() << ” phan tu” << endl;return 0;Output:vector truoc khi xoaXinchaotatcacacbanvector sau khi xoaxinbanVector sau khi clear co 0 phan tuPhương thức chèniterator insert ( iterator position, const T& x );void insert ( iterator position, size_type n, const T& x );void insert ( iterator position, InputIterator first, InputIterator last );Ví dụ:// inserting into a vector#include #include using namespace std;int main ()vector v1(4,100);v1.insert ( v1.begin()+3 , 200 );//chèn 200 vào trước vị trí thứ 3v1.insert ( v1.begin()+2 ,2,300);//chèn 2 lần 300 vào trước vị trí thứ 2vector v2(2,400);int a [] = { 501, 502, 503 };v1.insert (v1.begin()+2, a, a+3);//chèn mảng a (3 phần tử) vào trước vị trí thứ 2v1.insert (v1.begin()+4,v2.begin(),v2.end());//chèn v2 vào trước vị trí thứ 4cout << “v1 contains:”;for (int i =0; i < v1.size(); i ++)cout << ” ” << v1[i];return 0;Output:v1 contains: 100 100 501 502 400 400 503 100 200 300 300 100Một số hàm khác và chức năngNhững toán tử so sánh: được định nghĩa cho vector: ==, <, <=, !=, >, >=Tham chiếu back(), front()templatereference vector::front( );templatereference vector::back( );Trả về tham chiếu đến phần tử đầu và cuối vector:v.front() v[0] và v.back() v[v.size()-1]#include #include using namespace std;int main ()int a[] = {3,2,3,1,2,3,5,7};int n = sizeof(a)/sizeof(*a);vector v(a, a+n);cout << “phan tu dau la ” << v.front() << endl;cout << “phan tu cuoi la ” << v.back() << endl;cout << “gan phan tu cuoi la 9 ” << endl;v.back() = 9;cout << “gan phan tu dau la 100 ” << endl;v.front() = 100;cout << “kiem tra lai vector: “;for (int i =0; i < v.size(); i++)cout << v[i] << “ “;cout << endl;return 0;Output:phan tu dau la 3phan tu cuoi la 7gan phan tu cuoi la 9gan phan tu dau la 100kiem tra lai vector: 100 2 3 1 2 3 5 9Press any key to continue …Hàm thành viên empty()Để xác định vector có rỗng hay không ta dùng hàm thành viên empty(), hàm này trả về truenếu vector rỗng, và false ngược lại. Cú pháp :if(v.empty() == true) {cout << “No values in vector \n”;- capacity() : Trả về số lượng phần tử tối đa mà vector được cấp phát, đây là 1 con s ố có thểthay đổi do việc cấp phát bộ nhớ tự động hay bằng các hàm như reserve() và resize()Sự khác biệt giữa 2 hàm size() và capacity() :#include#includeint main(int argc , char **argc)vectorso1,so2[10];so1.reserve(10);cout <<“Kich thuoc toi da:”<#include using namespace std;int main()vector< int > my_vect;my_vect.reserve( 8 );my_vect.push_back( 1 );my_vect.push_back( 2 );my_vect.push_back( 3 );cout << my_vect.capacity() << “\n”;return 0;- swap(); hoán đổi 2 container v ới nhau (gi ống việc hoán đổi giá trị của 2 biến kiểu số). Vídụ : v1.swap(v2);V.Kiểm tra tràn chỉ số mảng:Có một vấn đề chưa được đề cập đến từ khi ta làm quen với vector, đó là khả năng kiểm tratràn chỉ số mảng (range check), để biết về khả năng này, chúng ta lại ti ếp tục với một ví dụmới :#include #include #include using namespace std;int main()try { // sử dụng try catch để bẫy lỗivector V(3, 10);// Khởi tạo vector gồm 3 thành phần// Tất cả gán giá trị 10cout << “V[0]=” << V[0] << endl;// Đưa thành phần 0 ra màn hìnhcout << “V[1]=” << V[1] << endl;// Đưa thành phần 1 ra màn hìnhcout << “V[2]=” << V[2] << endl;// Đưa thành phần 2 ra màn hìnhcout << “V[3]=” << V[3] << endl;// Thành phần 3 (lệnh này hoạt động không// đúng vì V chỉ có 3 thành phần 0,1,2cout << “V[4]=” << V[4] << endl;// Thành phần 4 (càng không đúng)// Nhưng 2 lệnh trên đều không gây lỗicout << “V[0]=” << V.at(0) << endl;// Không sử dụng [], dùng phương thức atcout << “V[1]=” << V.at(1) << endl;// Thành phần 1, OKcout << “V[2]=” << V.at(2) << endl;// Thành phần 2, OKcout << “V[3]=” << V.at(3) << endl;// Thành phần 3: Lỗi, chương trình dừngcout << “V[4]=” << V.at(4) << endl;getchar();} catch (exception &e) {cout << “Tran chi so ! ” << endl;return 0;Trong ví dụ này, chúng ta lại có thêm một số kinh nghiệm sau:- Nếu sử dụng cú pháp biến_vector[chỉ _số], chương trình sẽ không tạo ra lỗi khi s ử dụng chỉsố mảng nằm ngoài vùng hợp lệ (giống như mảng thường). Trong ví dụ, chúng ta mới chỉ lấygiá trị phần tử với chỉ số không hợp lệ, trường hợp này chỉ cho kết quả sai. Nhưng nếu chúngta gán giá trị cho phần tử không hợp lệ này, hậu quả sẽnghiêm trọng hơn nhiều vì thao tác đósẽ làm hỏng các giá trị khác trên bộ nhớ.- Phương thức at(chỉ _số) có tác dụng tương tự như dùng ký hiệu [], nhưng có một sự khácbiệt là thao tác này có kiểm tra chỉ số hợp lệ. Minh chứng cho nhận xét này trong ví dụ khichương trình chạy đến vị trí lệnh V.at(3), lệnh này không cho ra kết quả mà tạo thành thôngbáo lỗi.VI.Mảng 2 chiều với Vector:#include #include using namespace std;int main()vector< vector > matrix(3, vector(2,0));//chu y viet > > de khong nham voi toan tu >>for(int x = 0; x < 3; x++)for(int y = 0; y < 2; y++)matrix[x][y] = x*y;for(int x = 0; x < 3; x++)for(int y = 0; y < 2; y++)cout << matrix[x][y];cout << ‘\n’;return 0;Ví dụ này minh họa việc sử dụng mảng 2 chiều, thực chất đây là một vector của vector. Mảng2 chiều sử dụng biện pháp này có thể có kích thước khác nhau giữa các d.ng (ví dụ mảng 2chiều là nửa trên của ma trận)VII.Sử dụng iteratorContainer ( thùng chứa ) : Một kiểu cấu trúc dữ liệu dùng để lưu trữ thông tin. Ví dụ: mảng(array), list, vector, dequeContainer nào cũng có các phương thức sau đâyPhương thức Mô tảsize()lưng phempty () Trả về 1 nếu container rỗng, 0 nếu ngược lại.max_size() Trả về số lượng phần tử tối đa đã được cấp phát== Trả về 1 nếu hai container giống nhau!= Trả về 1 nếu hai v khác nhaubegin()Triterator đu tiên ca containerend() Trả về iterator lặp cuối cùng của containerfront() Trả về tham chiếu đến phần tử đầu tiên của containerback() Trả về tham chiếu đến phần tử cuối cùng của containerswap() Hoán đổi 2 container với nhau (giống việc hoán đổi giá trị của 2 biến)Trong thư viện STL thì người ta tích hợp lớp đối tượng Iterator (bộ lặp hay biến lặp) cùng vớicác container.Tư tưởng đó thể hiện như sau:o Các đối tượng Iterator là các con trỏ đến các đối tượng của lớp lưu trữ:typedef__gnu_cxx::__normal_iterator iterator;o Khai báo lớp Iterator như là 1 lớp nằm trong lớp lưu trữ.o Xác định trong lớp lưu trữ các phương thức thành phần như:+ begin() – trả lại con trỏ kiểu đối tượng Iterartor đến phần tử đầu tiên của nằm trongđối tượng lớp lưu trữ.+ end() – trả lại con trỏ kiểu Iterator trỏ đến 1 đối tượng nào đó bên ngoài tập cácphần tử được lưu trữ. Đối tượng bên ngoài nào đó có thể có các định nghĩa khác nhau.Trongtrường hợp cụ thể như vector ta có thể hiểu là trỏ đến phần tử sau phần tử cuối cùng.o Xác định trong lớp đối tượng kiểu Iterator các toán tử như sau:++p hoặc p++ : chuyển iterator p đến phần tử kế tiếp.p hoặc p : chuyển iterator p đến phần tử đằng trước nó.*p : xác định giá trị của phần tử mà iterator p trỏ đến.Như bạn biết, mảng và con trỏ có mối quan hệ chặt chẽ với nhau trong C++. Một mảng có thểđược truy xuất thông qua con trỏ. Sự tương đương này trong STL là mối quan hệ giữa iteratorvà vector, mà tổng quát hơn là với container. Nó cung cấp cho chúng ta khả năng xử lý theochu kì thông qua nội dung của container theo một cách giống như là bạn sử dụng con trỏ đểtạo xử lý chu kỳ trong mảng.Bạn có thể truy xuất đến các thành phần của một container bằng sử dụng một iterator: coll;for (::iterator it = coll.begin(); it != coll.end(); ++it)*it;//……Dưới đây chúng ta xét 1 ví dụ làm việc với thư viện STL với lớp vector và con trỏ kiểuiterator như sau:#include#includeusing std::vector;void main()vector v;for(int i = 10; i < 15; i++) v.push_back(i );vector::iterator it = v.begin();while(it != v.end())cout << *it << ” “;it++;Vì iterator định nghĩa bên trong các container – thế nào là “phần tử đầu”, “phần tử cuối”,“phần tử tiếp theo” … nên nó “chứa” thông tin cấu trúc phục vụ cho việc duyệt container. Nóche đi cấu trúc bên trong và cho phép ta viết các đoạn mã tổng quát để duyệt hay chọn phầntử trên các container khác nhau mà không cần biết cấu trúc của container đó ra sao.Trong các reversible container như vector còn định nghĩa thêm reverse_iterator (cái tên nóilên chức năng: iterator nghịch đảo) là nested class với các “hằng” tương ứng:vector::reverse_iterator rbegin();vector::reverse_iterator rend();Ví dụ : duyệt vector theo 2 chiều#include #include #include #include using namespace std;int main()int A[] = {3,2,3,1,2,3,5,3};int n = sizeof(A)/sizeof(*A);vector V;for (int i=0; i::iterator vi;cout << endl << “Duyet chieu xuoi” << endl;for (vi=V.begin(); vi!=V.end(); vi++)cout << *vi << endl;vector::reverse_iterator rvi;cout << endl << “Duyet theo chieu nguoc” << endl;for (rvi=V.rbegin(); rvi!=V.rend(); rvi++)cout << *rvi << endl;getchar();Chuyển đổi qua lại giữa reverse_iterator và iterator:+ Hàm thành viên base(): trả về một iterator trỏ đến phần tử hiện tại của reverse_iterator.+ Tạo reverse_iterator từ iterator: Contructor reverse_iterator(RandomAccessIterator i);Ví dụ:vector v;vector::iterator it (v.begin());vector:: reverse_iterator ri(v.rbegin());//goi contructorassert(ri.base()==v.end()-1);ri=v.begin();//goi contructorassert(ri.base()==it);*Lệnh assert(); dùng để kiểm tra một biểu thức điều kiện.Iterator là 1 trong 4 thành phần chính của STL (container, iterator, algorithm và functor).Container và algorithm giao tiếp qua nó: nhiều hàm và algorithm trong STL nhận các đối sốlà iterator.Iterator gắn liền với tất cả các loại container, đây là khái ni ệm bạn cần nắm rấtvững nếu muốn làm việc tốt với STLBảng: các hàm thành viên lớp vectorHàm thành phần Mô tảtemplatevoid assign(lnlter start, lnlter end);Gán giá trị cho vector theo trình tự từ startn end.TemplateVoid insert(iterator I, lnlter start, lnltr end);Chèn chuỗi xác định từ start đến end trực tiếptrước một phần tử được chỉ định bởi i.Size_type max_size() const; Trả về số lượng phần tử lớn nhất mà vectorcó thể chứa.Reference operator[](size_type i) const;Const_reference operator[] (size_type i) const;Trả về một tham chiếu đến phần tử được chỉđịnh bởi i.Void pop_back(); Xóa phần tử cuối cùng trong vector.Void push_back(cons T&val); Thêm vào một phần tử có giá trị val vào cuốicủa vector.Reverse_iterator rbegin();Const_reverse_iterator rbegin() const;Trả về biến lặp nghịch chỉ điểm kết thúc củavector.Reverse_iterator rend();Trt bin lp nghch chđim bt đConst_reverse_iterator rend() const; của vector.Void reverse (size_type num); Thiết lập kích thước của vector nhiều nhất làbằng num.Void resize (size_type num, T val =T()); Chuyển đổi kích thước của vector được xácđịnh bởi num. Nếu như kích thước của vectortăng lên thì các phần tử có giá trị val sẽ đượcthêm vào cuối vector.Size_type size() const; Trả về số lượng các phần tử hiện thời củatrong vector.Vois swap(vector&ob) Chuyển đổi những phần tử được lưu trongvector hiện thời với những phần tử trong ob.VIII.Dùng 1 số hàm cơ bản trong thư viện algorithmKhởi tạo:Bạn có thể sử dụng lệnh fill của thư viện để tô một vùng giá trị của 1 container(thường là 1 mảng, 1 vector)// fill algorithm example#include #include #include using namespace std;void printint(const int &i)cout << i << endl;int main ()vector v(8); // v: 0 0 0 0 0 0 0 0fill(v.begin(),v.begin()+4,5); // v: 5 5 5 5 0 0 0 0fill(v.begin()+3,v.end()-2,8); // v: 5 5 5 8 8 8 0 0cout << “vector contains:”;for_each( v.begin(), v.end(), printint );return 0;template void generate(ForwardIterator first, ForwardIterator last, Generator gen);Hàm generate sẽ “sinh” từng phần tử trong khoảng nào đấy của vector bằng cách gọi hàmđược chỉ định ( một hàmtrả về cùng kiểu và không có đối số)Ví dụ với hàm rand():vector V;srand( time(NULL) );//generate( V.begin(), V.end(), rand );Copy iterator ( tương tự memcpy() đối với pointer )int a[] = {1, 2, 3, 4, 5, 6};int n = sizeof(a)/sizeof(*a);vector v1(a, a+n);vector v2(n);copy(v1.begin(), v1.end(), v2.begin());//copy_n(v1.begin(), v1.size(), v2.begin());for (int i =0; i để đảo ngược container (ở đây là 1vector)// reverse algorithm example#include #include #include tr.nh C++ Nguyễn Phú Quảng#include using namespace std;int main ()vector a;// set some values:for (int i=1; i<10; ++i) a.push_back(i); // 1 2 3 4 5 6 7 8 9reverse(a.begin(),a.end()); // 9 8 7 6 5 4 3 2 1// print out content:cout << “a contains:”;int i, n = a.size();for (i=0; i#include #include #include using namespace std;int main ()int myints[] = { 10, 20, 30, 30, 20, 10, 10, 20 };vector a (myints, myints+8); // 10 20 30 30 20 10 10 20replace(a.begin(), a.end(), 20, 99); // 10 99 30 30 99 10 10 99cout << “a contains: “;int i, n;for (i=0, n=a.size(); i#include #include #include using namespace std;inline bool SoLe(int i) { return ((i%2)==1); }int main ()vector a;// set some values:for (int i=1; i<10; i++) a.push_back(i); // 1 2 3 4 5 6 7 8 9replace_if(a.begin(), a.end(), SoLe, 0); // 0 2 0 4 0 6 0 8 0cout << “a contains: “;int i, n;for (i=0, n=a.size(); i V(A, A+N);copy(V.begin(), V.end(), ostream_iterator(cout, ” “));//The output is “3 1 4 1 5 9″.cout << endl;vector::iterator new_end =remove(V.begin(), V.end(), 1);V.resize(new_end – V.begin());copy(V.begin(), V.end(), ostream_iterator(cout, ” “));// The output is “3 4 5 9″.Ví dụ 2:#include #include #include using namespace std;bool IsOdd(int x){return x%2;int main()int a[] = {3,1,4, 8, 5, 2, 9};int n = sizeof(a)/sizeof(*a);vector vec(a, a+n);vector::iterator new_end =remove_if( vec.begin(), vec.end(), IsOdd );vec.erase(new_end, vec.end());copy(vec.begin(), vec.end(), ostream_iterator(cout, ” “));// The output is “4 8 2”.return 0;Các hàm có hậu tố _copy như remove_copy, remove_if_copy, replace_copy,replace_if_copy, reverse_copy sử dụng tương tự nhưng tạo ra và thao tác trên bản saocontainerSắp xếp container (ở đây là vector)#include #include #include using namespace std;void printint(const int &i)cout << i << endl;int main()int A[] = {3,2,3,1,2,3,5,3};int n = sizeof(A)/sizeof(*A);vector V(A, A+n);cout << endl << “Danh sach ban dau” << endl;for_each( V.begin(), V.end(), printint );V.sort();vector::iterator vi;cout << endl << “Danh sach sau khi sap xep” << endl;for_each( V.begin(), V.end(), printint );getchar();Trong ví dụ trên ta học được cách sử dụng hàm for_each() và sort() để thao tác với 1container.Tìm kiếm tuyến tính// lineal search#include #include #include using namespace std;bool IsOdd(int x)return x%2;int main()int a[] = {2,4,2,6,9,1,2,3,2,3,4,5,6,4,3,2,1};int n = sizeof(a)/sizeof(*a);vector v(a, a+n);int first = find(a, a+n, 1) – a;//các hàm thuật toán hoàn toàn có thể thao tác trên mảng & con trỏ thườngcout << “[array] so thu tu cua phan tu dau tien = 1: ” << first << endl;first = find(v.begin(),v.end(), 1) – v.begin();cout << “[vector] so thu tu cua phan tu dau tien = 1: ” << first << endl;//find_ifvector::iterator it;it = find_if(v.begin(),v.end(), IsOdd );first = it – v.begin();cout << “Phan tu le dau tien la ” << *it << ” o vi tri thu ” << first << endl;return 0;Ngoài ra còn có nhiều hàm tìm kiếm khác: hàm search() dùng để so khớp 1 chuối liên tiếpcác phần tử cho trước, hàm search_n tìm kiếm với số lần lặp xác định, hàm find_end tìm kếtquả cuối cùng, find_first_not_of(), find_last_not_of() …Đếm & tìm min max//counting#include #include #include using namespace std;bool IsOdd(int x)return x%2;int main()int a[] = {3,2,3,1,2,4,5,3};int n = sizeof(a)/sizeof(*a);vector v(a, a+n);cout << “So luong so 3 trong mang: ” << count(v.begin(),v.end(), 3) << endl;cout << “So luong so le trong mang: ” << count_if(v.begin(),v.end(), IsOdd) <#include using namespace std;template T inc(T x )//hàm dùng để chuyển đổireturn x+1;int main()int a[] = {3,2,3,1,2,3,5,3};int n = sizeof(a)/sizeof(*a);vector v(a, a+n);transform(v.begin(), v.end(), v.begin(), inc );copy(v.begin(), v.end(), ostream_iterator(cout, ” “));// The output is “4 3 4 2 3 4 6 4”.return 0;Ngoài ra còn nhiều hàm thuật toán khác có thể tham khảo trong tài liệureference của c++
