[Set] Set 집합 | C++

Set

• 집합을 관리하기 위한 data structure
• Set library는 중복을 허용하지 않는다.
• C++에서는 set library가 balanced binary search tree (== red-black tree)로 구현되어 있기 때문에 기본적인 searching과 update 모두 O(log n) 시간에 수행 가능하다.
• c++에서는 set의 element간에 순서가 정해지지 않은 경우 사용할 수 있는 unorderd_set_library를 지원한다.
  • 이는 hash table로 구현되어 있으며 모든 연산을 average O(1)에 구현 가능하다
    • 근데 이제 경진대회에서는 쓰지 않음을 곁들인...

 

 

#include <set> 헤더파일 include 진행

namespace 를 사용하면 더 효율적으로 사용 가능

#include <set>
using namespace std;

 

 

#  set 변수 선언

set<int> s;

 

 

# set.insert(n)  : set에 원소 n 삽입

int main(void) {
	set<int> s;
	s.insert(3);
	s.insert(2);
	s.insert(5);
	s.insert(6);
}

 

# set.count(n) : set의 element 중 n의 개수를 반환한다. 

• set은 중복을 포함하지 않기 때문에 0 or 1만 반환한다.
• 중복된 값을 관리하고 싶은 경우 multitest를 사용한다.

	cout << s.count(3) << '\n';  
	cout << s.count(4) << "\n";
    
    // set 안에 값이 있을 경우 1
    // set 안에 값이 없을 경우 0

 

 

# set.erase(n) : set에서 element n을 삭제한다.

• 궁금해서 set 안에 없는 원소도 삭제 해 봤는데 아무 일도 일어나지 않았다고 한다.

s.erase(3); 
s.erase(7);

 

 

 

# set의 모든 element에 접근하는 방법

•  set은 vector 처럼 index operator로 접근할 수 없다

cout << s.size() << "\n";
	for (auto x : s) {
		cout << x << "\n";
	}

 

 

# set에서 특정 element 찾기

auto it = s.find(3);
	if (it == s.end()) {
		cout << "this element is not founded\n";
	}