[Cpp-STL] Map1

Bài tập.

Cho một chuỗi s, hãy đưa ra một dãy lần lượt là các ký tự và số lần xuất hiện của nó, các ký tự sắp xếp theo thự tự từ điển.

Ví dụ:

• Với s = "aacccd" thì countChar = ["a 2", "c 3", "d 1"].
  
  
• Với s = "aabbbca" thì countChar = ["a 3", "b 3", "c 1"].

Giới thiệu về Map.

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

Lý thuyết.

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.

Khóa sắp xếp tăng dần:

struct cmp{
 bool operator() (char a,char b) {return a<b;}
};
.....
map <char,int,cmp> m; 

Khóa sắp xếp giảm dần:

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. Độ phức tạp O(1).
• empty: true nếu map rỗng, false nếu ngược lại. Độ phức tạp 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 đó. Độ phức tạp 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”. Đô phức tạp O(logN).
• erase:
  • Xóa theo iterator Độ phức tạp O(logN).
  • Xóa theo khóa: xóa khóa trong map. ĐPT: O(logN).
• clear: Xóa tất cả set. Độ phức tạp O(n).
• swap: Đổi 2 set cho nhau. Độ phức tạp 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. Độ phức tạp 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. Độ phức tạp là 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. Độ phức tạp là 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={{'a',1}}
 m.insert(make_pair('b',2)); // m={{'a',1};{'b',2}}
 m.insert(pair<char,int>('c',3) ); // m={{'a',1};{'b',2};{'c',3}}

 cout << m['b'] << endl; // In ra 2
 m['b']++; // m={{'a',1};{'b',3};{'c',3}}

 it=m.find('c'); // it point to key 'c'

 cout << it->first << endl; // In ra 'c'
 cout << it->second << endl; // In ra 3

 m['e']=100; //m={{'a',1};{'b',3};{'c',3};{'e',100}}

 it=m.lower_bound('d'); // it point to 'e'
 cout << it->first << endl; // In ra 'e'
 cout << it->second << endl; // In ra 100
}

Hướng dẫn.

Code mẫu:

std::vector<std::string> countChar(std::string s)
{
    map<char, int> mp;
    vector<string> v;
    for (auto x : s)
    {
        mp[x]++;
    }
    for (auto x : mp)
    {
        string ans = " ";
        ans =  x.first + ans + to_string(x.second);
        v.push_back(ans);
    }
    return v;
}