C++ STL for newbies - Điêu Xuân Mạnh

8 năm, 9 tháng trước

Lời nói đầu

“C++ được đánh giá là ngôn ngữ mạnh vì tính mềm dẻo, gần gũi với ngôn ngữ máy. Ngoài ra, với khả năng lập trình theo mẫu ( template ), C++ đã khiến ngôn ngữ lập trình trở thành khái quát, không cụ thể và chi tiết như nhiều ngôn ngữ khác. Sức mạnh của C++ đến từ STL, viết tắt của Standard Template Library - một thư viện template cho C++ với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của C. Với khái niệm template, những người lập trình đã đề ra khái niệm lập trình khái lược (generic programming), C++ được cung cấp kèm với bộ thư viện chuẩn STL.

Bộ thư viện này thực hiện toàn bộ các công việc vào ra dữ liệu (iostream), quản lý mảng (vector), thực hiện hầu hết các tính năng của các cấu trúc dữ liệu cơ bản (stack, queue, map, set...). Ngoài ra, STL còn bao gồm các thuật toán cơ bản: tìm min, max, tính tổng, sắp xếp (với nhiều thuật toán khác nhau), thay thế các phần tử, tìm kiếm (tìm kiếm thường và tìm kiếm nhị phân), trộn. Toàn bộ các tính năng nêu trên đều được cung cấp dưới dạng template nên việc lập trình luôn thể hiện tính khái quát hóa cao. Nhờ vậy, STL làm cho ngôn ngữ C++ trở nên trong sáng hơn nhiều.”

Trích “Tổng quan về thư viện chuẩn STL”

STL khá là rộng nên tài liệu này mình chỉ viết để định hướng về cách sử dụng STL cơ bản để các bạn ứng dụng trong việc giải các bài toán tin học đòi hỏi đến cấu trúc dữ liệu và giải thuật.
Mình chủ yếu sử dụng các ví dụ, cũng như nguồn tài liệu từ trang web www.cplusplus.com , các bạn có thể tham khảo chi tiết ở đó nữa.
Để có thể hiểu được những gì mình trình bày trong này, các bạn cần có những kiến thức về các cấu trúc dữ liệu, cũng như một số thuật toán như sắp xếp, tìm kiếm...
Việc sử dụng thành thạo STL sẽ là rất quan trọng nếu các bạn có ý định tham gia các kì thi như Olympic Tin Học, hay ACM. “STL sẽ nối dài khả năng lập trình của các bạn” (trích lời thầy Lê Minh Hoàng).
Mọi ý kiến đóng góp xin gửi về địa chỉ: [email protected]
Thư viện mẫu chuẩn STL trong C++ chia làm 4 thành phần là:
- Containers Library : chứa các cấu trúc dữ liệu mẫu (template)
  - Sequence containers
    - Vector
    - Deque
    - List
  - Containers adpators
    - Stack
    - Queue
    - Priority_queue
  - Associative containers
    - Set
    - Multiset
    - Map
    - Multimap
    - Bitset
- Algorithms Library: một số thuật toán để thao tác trên dữ liệu
- Iterator Library: giống như con trỏ, dùng để truy cập đến các phần tử dữ liệu của container.
- Numeric library:
Để sử dụng STL, bạn cần khai báo từ khóa “using namespace std;” sau các khai báo thư viện (các “#include”, hay “#define”,...)
Ví dụ:

#include <iostream>
#include <stack>       //khai  báo sử dụng container  stack

#define n  100

using  namespace std;  //khai  báo  sử  dụng  STL

main()  {

    ....

}

Việc sử dụng các hàm trong STL tương tự như việc sử dụng các hàm như trong class. Các bạn đọc qua một vài ví dụ là có thể thấy được quy luật.

I. ITERATOR (BIẾN LẶP):

Trong C++, một biến lặp là một đối tượng bất kì, trỏ tới một số phần tử trong 1 phạm vi của các phần tử (như mảng hoặc container), có khả năng để lặp các phần tử trong phạm vi bằng cách sử dụng một tập các toán tử (operators) (như so sánh, tăng (++),...)
Dạng rõ ràng nhất của iterator là một con trỏ: Một con trỏ có thể trỏ tới các phần tử trong mảng, và có thể lặp thông qua sử dụng toán tử tăng (++). Tuy nhiên, cũng có các dạng khác của iterator. Ví dụ: mỗi loại container (chẳng hạn như vector) có một loại iterator được thiết kế để lặp các phần tử của nó một cách hiệu quả.
Iterator có các toán tử như:
- So sánh: “==” , “!=” giữa 2 iterator.
- Gán: “=” giữa 2 iterator.
- Cộng trừ: “+”,”-“ với hằng số và ”++”,”—“.
- Lấy giá trị: “*”.

II. CONTAINERS (THƯ VIỆN LƯU TRỮ)

Một container là một đối tượng cụ thể lưu trữ một tập các đối tượng khác (các phần tử của nó). Nó được thực hiện như các lớp mẫu (class templates).
Container quản lý không gian lưu trữ cho các phần tử của nó và cung cấp các hàm thành viên (member function) để truy cập tới chúng, hoặc trực tiếp hoặc thông qua các biến lặp (iterator – giống như con trỏ).
Container xây dựng các cấu trúc thuờng sử dụng trong lập trình như: mảng động - dynamic arrays (vector), hàng đợi – queues (queue), hàng đợi ưu tiên – heaps (priority queue), danh sách kiên kết – linked list (list), cây – trees (set), mảng ánh xạ - associative arrays (map),...
Nhiều container chứa một số hàm thành viên giống nhau. Quyết định sử dụng loại container nào cho nhu cầu cụ thể nói chung không chỉ phụ thuộc vào các hàm được cung cấp mà còn phải dựa vào hiệu quả của các hàm thành viên của nó (độ phức tạp (từ giờ mình sẽ viết tắt là ĐPT) của các hàm). Điều này đặc biệt đúng với container dãy (sequence containers), mà trong đó có sự khác nhau về độ phức tạp đối với các thao tác chèn/xóa phần tử hay truy cập vào phần tử.

1. Iterator:

Tất cả các container ở 2 loại: Sequence container và Associative container đều hỗ trợ các iterator như sau (ví dụ với vector, những loại khác có chức năng cũng vậy).

/*khai  báo iterator  “it”*/
vector <int> :: iterator  it;

/* trỏ  đến vị  trí phần  tử  đầu tiên  của vector */
it=vector.begin();

/*trỏ  đến vị trí kết  thúc (không  phải  phần tử  cuối  cùng nhé) của vector)  */
it=vector.end();

/* khai  báo iterator ngược  “rit” */
vector <int> :: reverse_iterator rit; rit =  vector.rbegin();

/* trỏ  đến vị  trí kết thúc của vector theo  chiều  ngược (không phải  phần tử đầu tiên  nhé*/
rit =  vector.rend();

Tất cả các hàm iterator này đều có độ phức tạp O(1)

2. Vector (Mảng động):

Khai báo vector:

#include <vector>

...

/*  Vector 1 chiều */


/* tạo vector rỗng kiểu dữ liệu int */
vector <int> first;


//tạo vector với 4 phần tử là 100
vector <int> second (4,100);


// lấy từ đầu đến cuối vector second
vector <int> third (second.begin(),second.end())


//copy từ vector third
vector <int> four (third)


/* Vector 2 chiều*/


/* Tạo vector 2 chiều rỗng */
vector < vector <int> > v;


/* khai báo vector 5×10 */
vector < vector <int> > v (5,  10);


/* khai báo 5  vector 1 chiều rỗng */
vector < vector <int> >  v (5);


//khai báo vector 5*10 với các phần tử khởi tạo giá trị là 1
vector < vector <int> >  v (5, vector <int> (10,1));

Các bạn chú ý, trước C++11, 2 dấu “ngoặc” không được viết liền nhau, ví dụ như sau là sai:

/*Khai  báo vector  2  chiều SAI*/
vector <vector  <int>> v;

Các hàm thành viên: Capacity:

size : trả về số lượng phần tử của vector. ĐPT O(1).
empty : trả về true(1) nếu vector rỗng, ngược lại là false(0). ĐPT O(1).

Truy cập tới phần tử:

operator [] : trả về giá trị phần tử thứ []. ĐPT O(1).
at : tương tự như trên. ĐPT O(1).
front: trả về giá trị phần tử đầu tiên. ĐPT O(1).
back: trả về giá trị phần tử cuối cùng. ĐPT O(1).

Chỉnh sửa:

push_back : thêm vào ở cuối vector. ĐPT O(1).
pop_back : loại bỏ phần tử ở cuối vector. ĐPT O(1).
insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể là phần tử hay iterator của 1 đoạn phần tử…). ĐPT O(n).
erase : xóa phần tử ở vị trí iterator. ĐPT O(n).
swap : đổi 2 vector cho nhau (ví dụ: first.swap(second);). ĐPT O(1).
clear: xóa vector. ĐPT O(n).

Nhận xét:

Sử dụng vector sẽ tốt khi:

Truy cập đến phần tử riêng lẻ thông qua vị trí của nó O(1)
Chèn hay xóa ở vị trí cuối cùng O(1).

Vector làm việc giống như một “mảng động”.

Ví dụ 1: Ví dụ này chủ yếu để làm quen sử dụng các hàm chứ không có đề bài cụ thể.

#include <iostream>
#include <vector>
using  namespace std;
vector <int> v;                         // Khai báo vector
vector <int>::iterator  it;             // Khai báo iterator
vector <int>::reverse_iterator  rit;    // Khai báo iterator ngược
int i;

main()  {
    for (i=1;i<=5;i++) v.push_back(i);  // v={1,2,3,4,5}
    cout <<  v.front() <<  endl;        // In ra  1
    cout <<  v.back()  <<  endl;        // In ra  5
    cout <<  v.size()  <<  endl;        // In ra  5
    v.push_back(9);                     // v={1,2,3,4,5,9}
    cout <<  v.size()  <<  endl;        // In ra  6

    v.clear();                          // v={}
    cout <<  v.empty() <<  endl;        // In ra 1  (vector rỗng)

    for (i=1;i<=5;i++) v.push_back(i);  // v={1,2,3,4,5}
    v.pop_back();                       // v={1,2,3,4}
    cout <<  v.size()  <<  endl;        // In ra  4

    v.erase(v.begin()+1);               // Xóa  ptử  thứ  1  v={1,3,4}
    v.erase(v.begin(),v.begin()+2);     // v={4}
    v.insert(v.begin(),100);            // v={100,4}
    v.insert(v.end(),5);                // v={100,4,5}

    /*Duyệt  theo  chỉ  số  phần tử*/
    for (i=0;i<v.size();i++) 
        cout <<  v[i] <<  " ";          // 100   4  5
    cout <<  endl; 



    /*
    Chú ý: Không nên viết
    for (i=0;i<=v.size()-1;i++) ...
    Vì nếu vector v rỗng, v.size() là kiểu unsigned int, nên v.size()-1 sẽ bằng 2^32-1
    */

    /*Duyệt  theo  iterator*/
    for (it=v.begin();it!=v.end();it++)
        cout <<  *it  <<  " " ;         // In ra giá trị ma iterator đang trỏ tới "100 4 5"
    cout <<  endl;

    /*Duyệt  iterator  ngược*/
    for (rit=v.rbegin();rit!=v.rend();rit++)
        cout <<  *rit  <<  " ";         // 5 4 100
    cout <<  endl;

    system("pause");
}

.....

Bài viết của anh Mạnh hơi dài nên mình chỉ up đến đây thôi nhé, phần còn lại mọi người download theo đường link:

http://www.mediafire.com/download/5o1gllos4gjkz3k/STL.pdf

Cảm ơn vì đã đọc và xin lỗi vì sự bất tiện này ^_^

▲

▼