+8

Set và Map trong C++

I. Kiểu dữ liệu Set trong C++

1. Khái niệm kiểu dữ liệu set

SetSet là một dạng cấu trúc dữ liệu dùng để lưu trữ các phần tử không trùng lặp và được sắp xếp theo thứ tự tăng dần hoặc giảm dần. (Mặc định trong setset là tăng dần và chúng ta có thể viết lại hàm so sánh theo mục đích của chúng ta)

Trong môn Toán lớp 66, chúng ta đã tiếp xúc với khái niệm tập hợp, và biết đến tính chất không có hai phần tử nào trùng nhau trong một tập hợp. Và kiểu dữ liệu setset có tính ưu việt hơn so với một tập hợp, ngoài tính chất không có hai phần tử nào giống nhau mà setset còn có tính tự sắp xếp các phần tử (Có thể rút gọn một số công đoạn sắp xếp của bài toán).

2. Sử dụng container set

Để sử dụng container setset bạn cần khai báo:

#include<set>

Để khai báo một biến kiểu setset, ta có công thức chung sau:

set<kiểu dữ liệu> tên biến;

stack<int> a;
stack<vector<int>> b;

Ví dụ về viết lại hàm thay đổi thứ tự sắp xếp các phần tử trong setset:

struct cmp{
	bool operator() (int a,int b) {return a>b;}
};
// khai báo thêm biến cmp
set<int, cmp> s;

3.Các phép toán cơ bản của set

  • Khi duyệt các phần tử của setset, ta sử dụng con trỏ, khai báo như sau:
set<kiểu dữ liệu>::iterator it; // khai báo con trỏ it
  • Thêm một phần tử vào setset:
s.insert(a); // thêm phần tử a vào set
  • Trả về số phần tử của setset:
s.size();
  • Kiểm tra setset rỗng hoặc không:
s.empty(); // trả về true nếu rỗng, false nếu không rỗng
  • Xóa tất cả phần tử của setset:
s.clear();
  • Kiểm tra một giá trị có tồn tại trong setset hoặc không, nếu có sẻ trả về con trỏ trỏ đến xx, nếu không trả về s.end():
s.find(x);
  • Để xóa phần tử xx trong setset:
s.erase(x);
  • Xóa phần tử thứ kk trong setset:
set<int>::iterator it = s.begin(); // tạo con trỏ trỏ vào phần tử đầu tiên
advance(it,k); // trỏ đến số thứ k trong s
s.erase(it); //  xóa phần tử thứ k
  • Con trỏ trỏ đến vị trí phần tử nhỏ nhất mà lớn hơn khóa xx, nếu không tìm thấy trả về vị trí s.end():
s.upper_bound(x);
  • Con trỏ trỏ đến vị trí phần tử nhỏ nhất mà lớn hơn hoặc bằng khóa xx, nếu không tìm thấy trả về vị trí s.end():
s.lower_bound(x);

II. Kiểu dữ liệu Map trong C++

1. Khái niệm kiểu dữ liệu map

MapMap là một kiểu dữ liệu với mỗi phần tử là ánh xạ giữa yếu tố key (khóa) với giá trị (value) của nó. Tương tự setset, mapmap không chứa hai phần tử nào giống nhau và các phần tử trong mapmap được sắp xếp theo một thứ tự nào đó. Mỗi phần tử trong mapmap có yếu tố keykey dùng để xác định valuevalue của nó, điều này cũng có nghĩa là keykeyvaluevalue có thể có kiểu khác nhau.

2. Sử dụng container map

Để sử dụng container mapmap bạn cần khai báo:

#include<map>

Để khai báo một biến kiểu mapmap, ta có công thức chung sau:

map<kiểu dữ liệu, kiểu dữ liệu> tên biến;

map<int, int> a;
map<char, int> b;

Ví dụ về viết lại hàm thay đổi thứ tự sắp xếp các phần tử trong mapmap:

struct cmp{
	bool operator() (char a, char b) {return a>b;}
};
// khai báo thêm biến cmp
map<char, int, cmp> m;

3.Các phép toán cơ bản của map

  • Trả về kích thước hiện tại của mapmap:
m.size();
  • Kiểm tra mapmap có rỗng hoặc không:
m.empty(); // trả về true nếu map rỗng, false nếu không rỗng
  • Truy cập phần tử trong mapmap:
m[x]; // truy cập value của khóa x
  • Chỉnh sửa phần tử trong mapmap (phần tử chỉnh sửa phải ở dạng "cặp"):
m.insert(x);
  • Xóa phần tử trong mapmap:
m.erase(x);
  • Xóa tất cả phần tử trong mapmap:
m.clear();
  • Con trỏ trỏ đến vị trí phần tử nhỏ nhất mà lớn hơn khóa xx, nếu không tìm thấy trả về vị trí m.end():
m.upper_bound(x);
  • Con trỏ trỏ đến vị trí phần tử nhỏ nhất mà lớn hơn hoặc bằng khóa xx, nếu không tìm thấy trả về vị trí m.end():
m.lower_bound(x);

III. Phân biệt set và map

  • Mỗi phần tử của setset chỉ lưu một giá trị là khóa, trong khi mỗi phần tử của mapmap lưu hai giá trị là khóa và giá trị của khóa.
  • Ta thường sử dụng mapmap cho các bài toán có các giá trị liên quan mật thiết với nhau.
  • mapmap sử dụng giá trị keykey để xác định các phần tử, còn setset là tập hợp các keykey.

All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.