Tổng quan
- 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).
- Khi duyệt set theo iterator từ begin đến end, các phần tử của set sẽ tăng dần theo phép toán so sánh.
- Mặc định của set là sử dụng phép toán less, bạn cũng có thể viết lại hàm so sánh theo ý mình.
- Set được thực hiện giống như cây tìm kiếm nhị phân (Binary search tree).
Khai báo:
#include <set> set <int> s; set <int, greater<int> > s;Hoặc viết class so sánh theo ý mình:
struct cmp{
bool operator() (int a,int b) {return a<b;}
};
set <int,cmp > myset ;
Capacity:
- size : trả về kích thước hiện tại của set. ĐPT O(1)
- empty : true nếu set rỗng, và ngược lại. ĐPT O(1).
Thay đổi:
- insert : Chèn phần tử vào set. ĐPT O(logN).
- erase : có 2 kiểu xóa: xóa theo iterator, hoặc là xóa theo khóa. ĐPT O(logN).
- clear : xóa tất cả set. ĐPT O(n).
- swap : đổi 2 set cho nhau. ĐPT O(n).
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. Đ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 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 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ó. ĐPT O(logN).
Chương trình Demo 1:
#include <iostream>
#include <set>
using namespace std;
main() {
set <int> s;
set <int> ::iterator it; s.insert(9); // s={9}
s.insert(5); // s={5,9} cout << *s.begin() << endl; //In ra 5 s.insert(1); // s={1,5,9} cout << *s.begin() << endl; // In ra 1
it=s.find(5);
if (it==s.end()) cout << "Khong co trong container" << endl; else cout << "Co trong container" << endl;
s.erase(it); // s={1,9}
s.erase(1); // s={9}
s.insert(3); // s={3,9}
s.insert(4); // s={3,4,9}
it=s.lower_bound(4);
if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 4" << endl; else cout << "Phan tu be nhat khong be hon 4 la " << *it << endl; // In ra 4
it=s.lower_bound(10);
if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 10" << endl; else cout << "Phan tu be nhat khong be hon 10 la " << *it << endl; // Khong co ptu nao
it=s.upper_bound(4);
if (it==s.end()) cout << "Khong co phan tu nao trong set lon hon 4" << endl; else cout << "Phan tu be nhat lon hon 4 la " << *it << endl; // In ra 9
/* Duyet set */
for (it=s.begin();it!=s.end();it++) { cout << *it << " ";
}
// In ra 3 4 9
cout << endl; system("pause");
}
Lưu ý: Nếu bạn muốn sử dụng hàm lower_bound hay upper_bound để tìm phần tử lớn nhất “bé hơn hoặc bằng” hoặc “bé hơn” bạn có thể thay đổi cách so sánh của set để tìm kiếm. Mời bạn xem chương trình sau để rõ hơn:
#include <iostream>
#include <set>
#include <vector> using namespace std;
main() {
set <int, greater <int> > s;
set <int, greater <int> > :: iterator it; // Phép toán so sánh là greater
s.insert(1); // s={1}
s.insert(2); // s={2,1}
s.insert(4); // s={4,2,1}
s.insert(9); // s={9,4,2,1}
/* Tim phần tử lớn nhất bé hơn hoặc bằng 5 */ it=s.lower_bound(5);
cout << *it << endl; // In ra 4
/* Tim phần tử lớn nhất bé hơn 4 */ it=s.upper_bound(4);
cout << *it << endl; // In ra 2
system("pause");
}
[Chú ý: Đừng nhầm lẫn Java với JavaScript, vì JavaScript là một ngôn ngữ hoàn toàn khác được sử dụng cho lập trình web – chúng ta sẽ nói về nó trong bài viết sau].
Tiềm năng kiếm tiền: 
Objective-C/ Cocoa
Tiềm năng kiếm tiền: 
Recent Comments