C++ toàn tập

Đây là ngôn ngữ rất phổ biến được nhiều người lựa chọn và nó có cơ hội việc làm thu nhập rất cao nếu bạn thông thạo nó. Vì vậy Blog đã viết một loạt bài về C++ với mục đích giúp các bạn tiện tra cứu và học hỏi.

Cơ bản:

STL

  • Stack (ngăn xếp)
  • Vector trong C++
  • Queue (hàng đợi)
  • Deque (hàng đợi hai đầu)
  • Priority queue (hàng đợi ưu tiên)
  • Set (tập hợp)
  • List (danh sách liên kết)
  • Multiset (tập hợp)
  • Priority queue (hàng đợi ưu tiên) trong C++

    Priority queue là một loại container adaptor, được thiết kế đặc biệt để phần tử ở đầu luôn luôn lớn nhất (theo một quy ước về độ ưu tiên nào đó) so với các phần tử khác.

    Nó giống như một heap, mà ở đây là heap max, tức là phần tử có độ ưu tiên lớn nhất có thể được lấy ra và các phần tử khác được chèn vào bất kì.

    Phép toán so sánh mặc định khi sử dụng priority queue là phép toán less (Xem thêm ở thư viện functional)

    Để sử dụng priority queue một cách hiệu quả, các bạn nên học cách viết hàm so sánh để sử dụng cho linh hoạt cho từng bài toán.

    Khai báo: #include <queue>

    /*Dạng 1 (sử dụng phép toán mặc định là less)*/ 
    priority_queue <int> pq;
    
    /* Dạng 2 (sử dụng phép toán khác) */
    priority_queue <int,vector<int>,greater<int> > q; //phép toán greater
    

    Phép toán khác cũng có thể do người dùng tự định nghĩa. Ví dụ:

    Cách khai báo ở dạng 1 tương đương với:

    /* Dạng sử dụng class so sánh tự định nghĩa */ struct cmp{
    
    bool operator() (int a,int b) {return a<b;}
    
    };
    
    main() {
    
    …
    
    priority_queue <int,vector<int>,cmp > q;
    
    }
    

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

    • size : trả về kích thước hiện tại của priority queue. ĐPT O(1)
    • empty : true nếu priority queue rỗng, và ngược lại. ĐPT O(1).
    • push : đẩy vào priority queue. ĐPT O(logN).
    • pop: loại bỏ phần tử ở đỉnh priority queue. ĐPT O(logN).
    • top : trả về phần tử ở đỉnh priority queue. ĐPT O(1).

    Chương trình demo:

    #include <iostream>
     
    #include <queue>
     
    #include <vector>
     
    using namespace std;
     
    main() {
     
        priority_queue <int> p;	// p={}
     
        p.push(1);	// p={1}
     
        p.push(5);	// p={1,5}
     
        cout << p.top() << endl; // In ra 5
     
        p.pop();	// p={1}
     
        cout << p.top() << endl; // In ra 1
     
        p.push(9);	// p={1,9}
     
        cout << p.top() << endl; // In ra 9
     
        system("pause");
     
    }

    Chương trình Demo 2:

    #include <iostream>
     
    #include <queue>
     
    #include <vector>
     
    using namespace std;
     
    main() {
        priority_queue < int , vector <int> , greater <int> > p;	// p={}
        p.push(1);     //p={1}
        p.push(5);     //p={1,5}
        cout << p.top() << endl;    //In ra 1
        p.pop();       //p={5}
        cout << p.top() << endl;     //In ra 5
        p.push(9);    //p={5,9}
        cout << p.top() << endl; // In ra 5
        system("pause");
    }

    Chương trình Demo 3:

    #include <iostream>
     
    #include <queue>
     
    #include <vector>
     
    using namespace std;
     
    struct cmp{
        bool operator() (int a,int b) {return a<b;}
    };
     
    main() {
        priority_queue < int , vector <int> , cmp > p;	// p={}
        p.push(1);    //p={1}
        p.push(5);    //p={1,5}
        cout << p.top() << endl;     //In ra 1
        p.pop();    //p={5}
        cout << p.top() << endl;     //In ra 5
        p.push(9);    //p={5,9}
        cout << p.top() << endl; // In ra 5
    system("pause");
    }

    Queue (hàng đợi) trong C++

    Queue là một loại cấu trúc dữ liệu và một loại container adaptor, được thiết kế để hoạt động theo kiểu FIFO (First – in first – out) (vào trước ra trước), tức là một kiểu danh sách mà việc bổ sung được thực hiển ở cuối danh sách và loại bỏ ở đầu danh sách.

    Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào.

    Khai báo: #include <queue>

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

    • size : trả về kích thước hiện tại của queue. ĐPT O(1).
    • empty : true nếu queue rỗng, và ngược lại. ĐPT O(1).
    • push : đẩy vào cuối queue. ĐPT O(1).
    • pop: loại bỏ phần tử (ở đầu). ĐPT O(1).
    • front : trả về phần tử ở đầu. ĐPT O(1).
    • back: trả về phần tử ở cuối. ĐPT O(1).

    Chương trình demo:

    #include <iostream>
    
    #include <queue>
    
    using namespace std;
    
    queue <int> q;
    
    int i;
    
    main() {
      for (i=1;i<=5;i++) q.push(i);
      // q={1,2,3,4,5}
      q.push(100);
      // q={1,2,3,4,5,100}
      cout << q.front() << endl;
      // In ra 1
      q.pop();
      // q={2,3,4,5,100}
      cout << q.back() << endl;
      // In ra 100
      cout << q.empty() << endl;
      // In ra 0
      cout << q.size() << endl;
      // In ra 5
      system("pause");
    }
    

    Stack (ngăn xếp) trong C++

    Stack là một loại container adaptor, được thiết kế để hoạt động theo kiểu LIFO (Last – in first – out) (vào sau ra trước), tức là một kiểu danh sách mà việc bổ sung và loại bỏ một phần tử được thực hiển ở cuối danh sách. Vị trí cuối cùng của stack gọi là đỉnh (top) của ngăn xếp.

     

    Khai báo: #include <stack>

     

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

    • size : trả về kích thước hiện tại của stack. ĐPT O(1).
    • empty : true stack nếu rỗng, và ngược lại. ĐPT O(1).
    • push : đẩy phần tử vào stack. ĐPT O(1).
    • pop : loại bỏ phẩn tử ở đỉnh của stack. ĐPT O(1).
    • top : truy cập tới phần tử ở đỉnh stack. ĐPT O(1).

    Chương trình demo:

    #include <iostream>
    
    #include <stack>
    
    using namespace std;
    
    stack <int> s;
    
    int i;
    
    main() {
    
      for (i=1;i<=5;i++) s.push(i); // s={1,2,3,4,5} 
      s.push(100); // s={1,2,3,4,5,100} 
      cout << s.top() << endl; // In ra 100 
      s.pop(); // s={1,2,3,4,5} 
      cout << s.empty() << endl; // In ra 0 
      cout << s.size() << endl; // In ra 5 system("pause");
    
    }
    

    List (danh sách liên kết) trong C++

    • List được thực hiện như danh sách nối kép (doubly-linked list). Mỗi phần tử trong danh sách nối kép có liên kết đến một phần tử trước đó và một phần tử sau nó.
    • Do đó, list có các ưu điểm như sau:
      1. Chèn và loại bỏ phần tử ở bất cứ vị trí nào trong container. O(1).
    • Điểm yếu của list là khả năng truy cập tới phần tử thông qua vị trí. O(n).
    • Khai báo: #include <list>

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

    Capacity:

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

     

    Truy cập phần tử:

    • 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 phần tử vào ở cuối list. ĐPT O(1).
    • push_front : thêm phần tử vào đầu list. ĐPT O(1).
    • pop_back : loại bỏ phần tử ở cuối list. ĐPT O(1).
    • pop_front : loại bỏ phần tử ở đầu list. Đ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 là số phần tử thêm vào.
    • erase : xóa phần tử ở vị trí iterator. ĐPT là số phần tử bị xóa đi.
    • swap : đổi 2 list cho nhau (ví dụ: first.swap(second);). ĐPT O(1).
    • clear: xóa list. ĐPT O(n).

     

    Operations:

    • splice : di chuyển phần tử từ list này sang list khác. ĐPT O(n).
    • remove (const) : loại bỏ tất cả phần tử trong list bằng const. ĐPT O(n).
    • remove_if (function) : loại bỏ tất các phần tử trong list nếu hàm function return true . ĐPT O(n).
    • unique : loại bỏ các phần tử bị trùng lặp hoặc thỏa mãn hàm nào đó. ĐPT O(n). Lưu ý: Các phần tử trong list phải được sắp xếp.
    • sort : sắp xếp các phần tử của list. O(NlogN)
    • reverse : đảo ngược lại các phần tử của list. O(n).

    Deque (hàng đợi hai đầu) trong C++

    Deque hay còn được gọi là hàng đợi hai đầu

    • Deque (thuờng được phát âm giống như “deck”) là từ viết tắt của double-ended queue (hàng đợi hai đầu).
    • Deque có các ưu điểm như:
    1. Các phần tử có thể truy cập thông cua chỉ số vị trí của nó. O(1)
    2. Chèn hoặc xóa phần tử ở cuối hoặc đầu của dãy. O(1)

    Khai báo: #include <deque>

     

    Capacity:

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

    Truy cập 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 phần tử vào ở cuối deque. ĐPT O(1).
    • push_front : thêm phần tử vào đầu deque. ĐPT O(1).
    • pop_back : loại bỏ phần tử ở cuối deque. ĐPT O(1).
    • pop_front : loại bỏ phần tử ở đầu deque. Đ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 deque cho nhau (ví dụ: first.swap(second);). ĐPT O(n). clear: xóa vector. ĐPT O(1).

    Điểm khác nhau giữa double và float

    Đối với các số thực, chúng ta thường sử dụng float, double và double double.

    floatdouble có gì khác nhau?

    double có độ chính xác gấp 2 lần float.

    float là 32 bit IEEE 754 single precision Floating Point Number, 1 bit cho dấu, (8 bit cho số mũ và 23 * cho giá trị), tức là float có 7 chữ số thập phân có độ chính xác.

    double là 64 bit IEEE 754 double precision Floating Point Number (1 bit cho dấu, 11 bit cho số mũ và 52 bit cho giá trị), nghĩa là double có 15 chữ số thập phân có độ chính xác.

    Hàm atoi trong C/C++ – chuyển xâu thành số nguyên

    Mô tả

    Chuyển chuỗi kí tự thành số nguyên

    Khai báo

    int atoi(const char *str)

    • str là chuỗi ký tự cần chuyển sang số nguyên. VD: str=”5678123″

    Ví dụ:

    • atoi(“101”);
    • atoi(‘5’);

    Cần khai báo thư viện stdlib.h trước khi sử dụng.

    Giá trị trả về

    Trả về số nguyên kiểu int. Nếu xâu không có dạng số nguyên thì trả về giá trị 0

    Ví dụ

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    int main () {
       int val;
       char str[20];
     
       strcpy(str, "98993489");
       val = atoi(str);
       printf("String value = %s, Int value = %d\n", str, val);
     
       strcpy(str, "tutorialspoint.com");
       val = atoi(str);
       printf("String value = %s, Int value = %d\n", str, val);
     
       return(0);
    }

    Kết quả:

    String value = 98993489, Int value = 98993489
    String value = tutorialspoint.com, Int value = 0