Map (ánh xạ) trong C++

Map là một loại associative container. Mỗi phần tử của map là sự kết hợp của khóa (key value) và ánh xạ của nó (mapped value). Cũng giống như set, trong map không chứa các khóa mang giá trị giống nhau.

Trong map, các khóa được sử dụng để xác định giá trị các phần tử. Kiểu của khóa và ánh xạ có thể khác nhau.

Và cũng giống như set, các phần tử trong map được sắp xếp theo một trình tự nào đó theo cách so sánh.

Map được cài đặt bằng red-black tree (cây đỏ đen) – một loại cây tìm kiếm nhị phân tự cân bằng. Mỗi phần tử của map lại được cài đặt theo kiểu pair (xem thêm ở thư viện utility).

Khai báo: 

#include <map>

map <kiểu_dữ_liệu_1,kiểu_dữ_liệu_2>

// kiểu dữ liệu 1 là khóa, kiểu dữ liệu 2 là giá trị của khóa.

 

Sử dụng class so sánh:

Dạng 1:

struct cmp{

bool operator() (char a,char b) {return a<b;}

};

.....

map <char,int,cmp> m;
  • Truy cập đến giá trị của các phần tử trong map khi sử dụng iterator: Ví dụ ta đang có một iterator là it khai báo cho map thì:
  • (*it).first;   // Lấy giá trị của khóa, kiểu_dữ_liệu_1
    
    (*it).second;  // Lấy giá trị của giá trị của khóa, kiểu_dữ_liệu_2
    
    (*it)          // Lấy giá trị của phần tử mà iterator đang trỏ đến, kiểu pair
    
    it->first;  // giống như (*it).first
    
    it->second; // giống như (*it).second
    
    

    Capacity:

    • size : trả về kích thước hiện tại của map. ĐPT O(1)
    • empty : true nếu map rỗng, và ngược lại. ĐPT O(1).

     

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

    • operator [khóa]: Nếu khóa đã có trong map, thì hàm này sẽ trả về giá trị mà khóa ánh xạ đến. Ngược lại, nếu khóa chưa có trong map, thì khi gọi [] nó sẽ thêm vào map khóa đó. ĐPT O(logN)

    Chỉnh sửa

    • insert : Chèn phần tử vào map. Chú ý: phần tử chèn vào phải ở kiểu “pair”. ĐPT O(logN).
    • erase :

    o xóa theo iterator ĐPT O(logN)

      1. xóa theo khóa: xóa khóa trong map. ĐPT: O(logN).
    • clear : xóa tất cả set. ĐPT O(n).
    • swap : đổi 2 set cho nhau. ĐPT O(n).

    Operations:

    • find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy iterator trỏ về “end” của map. ĐPT O(logN).
    • lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
    • upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
    • count : trả về số lần xuất hiện của khóa trong multiset. ĐPT O(logN)

    Chương trình demo:

    #include <iostream>
    
    #include <map>
    
    #include <vector>
    
    using namespace std;
    
    main() {
    
        map <char,int> m;
    
        map <char,int> :: iterator it;
    
        m['a']=1;
        m.insert(make_pair('b',2));
        m.insert(pair<char,int>('c',3) );
    
        // m={{'a',1}}
        // m={{'a',1};{'b',2}}
        // m={{'a',1};{'b',2};{'c',3}}
    
        cout << m['b'] << endl; m['b']++;     // In ra 2
    
        // m={{'a',1};{'b',3};{'c',3}}
    
        it=m.find('c');    // it trỏ tới phần tử khóa 'c'
    
        cout << it->first << endl; 
        cout << it->second << endl;
        // In ra 'c'
        // In ra 3
    
        m['e']=100;
        //m={{'a',1};{'b',3};{'c',3};{'e',100}}
    
        it=m.lower_bound('d'); 
        cout << it->first << endl; 
        cout << it->second << endl;
        // it tỏ tới phần tử khóa 'e'
        // In ra 'e'
        // In ra 100
        system("pause");
    }
    

Multiset (tập hợp) trong C++

Multiset giống như Set nhưng có thể chứa các khóa có giá trị giống nhau.

Đọc thêm về Set tại: https://yeulaptrinh.pw/938/set-trong-c/

Khai báo : giống như set.

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

Capacity:

  • size : trả về kích thước hiện tại của multiset. ĐPT O(1)
  • empty : true nếu multiset rỗng, và ngược lại. ĐPT O(1).

Chỉnh sửa:

  • insert : Chèn phần tử vào set. ĐPT O(logN).
  • erase :
    • xóa theo iterator ĐPT O(logN)
    • xóa theo khóa: xóa tất cả các phần tử bằng khóa trong multiset. ĐPT: O(logN) + số phần tử bị xóa.
  • clear : xóa tất cả set. ĐPT O(n).
  • swap : đổi 2 set cho nhau. ĐPT O(n).

Operations:

  • find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy itarator trỏ về “end” của set. ĐPT O(logN). Dù trong multiset có nhiều phần tử bằng khóa thì nó cũng chỉ iterator đến một phần tử.
  • lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của set. ĐPT O(logN).
  • upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của set.. ĐPT O(logN).
  • count : trả về số lần xuất hiện của khóa trong multiset. ĐPT O(logN) + số phần tử tìm được.

Chương trình Demo:

#include <iostream>

#include <set>

using namespace std;

main() {
    multiset <int> s;

    multiset <int> :: iterator it;

    int i;

    for (i=1;i<=5;i++) s.insert(i*10); // s={10,20,30,40,50}
    s.insert(30);    // s={10,20,30,30,40,50}
    cout << s.count(30) << endl;    // In ra 2
    cout << s.count(20) << endl;    // In ra 1
    s.erase(30);    // s={10,20,40,50}

    /* Duyet set */
    for (it=s.begin();it!=s.end();it++) {
    cout << *it <<  " ";
    }

    //In ra 10 20 40 50 
    cout << endl; system("pause");
}

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).