Bài 5: Set – Khái niệm – Sử dụng thư viện chuẩn STL cho C/C++

Posted on by mtoplistChuyên mục:Top List

Đăng bởi: Admin | Lượt xem: 8122 | Chuyên mục: C/C++

Giới thiệu về Set :

  Set là một loại associative containers để lưu trữ các phần tử không bị trùng lặp (unique elements), và các phần tử này chính là các khóa (keys).
Ví dụ như là không tồn tại một set có  2 phần tử giống nhau như {1,2,2}, {3,4,4,4,5}.  

Khi duyệt set, ta sử dụng con trỏ iterator từ begin đến end

Các hàm của set :

  • size : trả về kích thước hiện tại của set.
  • empty : true nếu set rỗng, và ngược lại.
  • insert : Chèn phần tử vào set. 
  • erase : xóa phần tử, có 2 kiểu xóa: xóa theo iterator, hoặc là xóa theo khóa
  • clear : xóa tất cả set. 
  • swap : đổi 2 set cho nhau.

Truy cập phần tử :

  • 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. 
  • 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. 
  • 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.
  • count : trả về số lần xuất hiện của khóa trong container. Nhưng trong set, các phần tử chỉ xuất hiện một lần, nên hàm này có ý nghĩa là sẽ return 1 nếu khóa có trong container, và 0 nếu không có.

Set được thực hiện giống như cây tìm kiếm nhị phân (Binary search tree).

Để sử dùng set ta cần dùng thư viện :

#include&ltset&gt
set &ltKiểu_dữ_liệu&gt tên_Set;
//Ví dụ: set &ltint&gt s;

Để thêm một giá trị và set s ta sử dụng hàm insert(). (Độ phức tạp O(logN). Khi thêm vào một phần tử thì size() của set sẽ tự tăng thêm một.

set &ltint&gt s;
	
s.insert(1);  // s={1}
	
s.insert(4);  // s={1,4}
	
s.insert(2);  // s={1,2,4}
	
s.insert(9);  // s={1,2,4,9}

**Lưu ý: trong một set sẽ không có hai phần tử cùng giá trị, nên khi bạn gọi hàm insert(x) mà trong set đó đã tồn tại giá trị x rồi thì set đó sẽ không thêm phần tử đó vào nữa.  

Bài tập ví dụ 

Cho một vector chứa các số nguyên. Hãy đưa ra số lượng phần tử khác nhau trong vector đó.

  •   Với inputVector = [1, 3, 3, 2], thì differentNumbers(inputVector ) = 3.
    Giải thích: Có 3 phần tử khác nhau trong vector là: 1, 3, 2
  •   Với inputVector = [3, 3, 3], thì differentNumbers(inputVector ) = 1.    

Đầu tiên ta cần input phần tử vào set , dưới đây là input phần tử theo thứ tự tăng dần và in ra s.size():

#include&ltiostream&gt
#include&ltset&gt
using namespace std;

struct cmp{
	bool operator() (int a,int b) {return a&gtb;}
}; 

int main() {

	set &ltint,cmp&gt s;

	s.insert(1);  // s={1}
	
	s.insert(4);  // s={4,1}
	
	s.insert(2);  // s={4,2,1}
	
	s.insert(9);  // s={9,4,2,1}
	
	for (set&ltint&gt:: iterator it = s.begin(); it != s.end(); it++){
		cout&lt&lt *it &lt&lt " ";
	}
        cout &lt&lt s.size();
        return 0;

}

Ở bài sau chúng ta sẽ làm quen với các bài tập về set. Chúc các bạn học tốt <3

mtoplist