Vector trong C++

Khai báo vector:

Vector có thể hiểu là một mảng có trình tự, giống như với danh sách liên kết hay một chuỗi thông thường nhưng “vector” khác với chuỗi hoăc mảng thông thường là chúng ta có thể thay đổi kích thước của nó và cũng có thể truy cập trực tiếp đến các phần tử, điều này làm cho việc sử dụng “vector” linh hoạt hơn so với “list”…

#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ú ý 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:

  • 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”.

 

Một vài ví dụ:

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 thì sẽ dẫn đến sai khi duyệt !!!
      */

      /*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");
}
Ví dụ 2: Cho đồ thị vô hướng G có n đỉnh (các đỉnh đánh số từ 1 đến n) và m cạnh và không có khuyên (đường đi từ 1 đỉnh tới chính đỉnh đó).

Cài đặt đồ thị bằng danh sách kề và in ra các cạnh kề đối với mỗi cạnh của đồ thị. Dữ liệu vào:

  • Dòng đầu chứa n và m cách nhau bởi dấu cách
  • M dòng sau, mỗi dòng chứa u và v cho biết có đường đi từ u tới Không có cặp đỉnh u,v nào chỉ cùng 1 đường đi.

Dữ liệu ra:

  • M dòng: Dòng thứ i chứa các đỉnh kề cạnh i theo thứ tự tăng dần và cách nhau bởi dấu cách.

Giới hạn: 1 <= n,m <= 10000 Ví dụ:

INPUT OUTPUT
6 7 2 3 5 6
1 2 1 3 6
1 3 1 2 5
1 5  
2 3 1 3
2 6 1 2
3 5  
6 1  

 

Chương trình mẫu:

#include <iostream>
#include <vector> using namespace std;
vector < vector <int> > a (10001);
 
//Khai báo vector 2 chiều với 10001 vector 1 chiều rỗng int m,n,i,j,u,v;
main() {
      /*Input data*/ cin >> n >> m;
      for (i=1;i<=m;i++) { cin >> u >> v; a[u].push_back(v);
      a[v].push_back(u);
      }
      /*Sort cạnh kề*/ for (i=1;i<=m;i++)
      sort(a[i].begin(),a[i].end());
      /*Print Result*/
      for (i=1;i<=m;i++) {
      for (j=0;j<a[i].size();j++) cout << a[i][j] << " "; cout << endl;
      }
      system("pause");
}

Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây……

Speak Your Mind

*