[Data Structure] set, multiset (C++)

 c++ set 라이브러리에 정의되어 있는 자료구조인 set, multiset에 대해서 정리해보자. 먼저 set은 노드기반 이진 탐색 트리 구조로 삽입, 삭제, 탐색 모두 O(logN)의 복잡도를 가진다. 요소가 고유하고 자동으로 정렬되어야 할 때 유용하게 사용된다. multiset은 중복을 허용하는 set이다.

 set은 일반적인 vector와 조금 다르게 사용한다. 반드시 이터레이터를 통해서 탐색해야 한다는 조건을 가진다. 앞서 말했듯이 노드기반 이진 탐색 트리 구조이고 중위순회를 하면 항상 정렬된 값을 찾을 수 있다. set은 이터레이터를 통해서 탐색하면 알아서 중위순회를 해준다. 즉 주소값에 직접적으로 연산을 하거나 myset[3]<- 이런 방식으로 탐색하지 않고 이터레이터를 통해서 순회해야한다.

#include <iostream>
#include <set>

using namespace std;

int main() {
	set<int> myset;
	myset.insert(1);
	myset.insert(3);
	myset.insert(2);

	for (auto it = myset.begin(); it != myset.end(); it++) 
		cout << *it << ' ';
    
    for(auto it:myset)// 이렇게도 사용이 가능하다.
    	cout << it << ' ';

	return 0;
}

---

Set 기본 함수들

1. insert()
   set에 새로운 요소를 삽입한다. 이미 존재하는 요소는 삽입되지 않는다.

	set<int> mySet;
	mySet.insert(10);
	mySet.insert(5);

2. erase()
   set에서 특정 요소를 제거. 제거할 요소가 없으면 아무 일도 일어나지 않는다.

 	mySet.erase(10);

3. find()
   특정 요소를 set에서 찾는다. 값이 존재하면 그 값에 대한 이터레이터를 반환하고, 그렇지 않으면 set.end()를 반환한다.

  auto it = mySet.find(5);
  if (it != mySet.end()) {
      cout << "Element found: " << *it << endl;
  }

4. count()
   특정 요소가 set에 있는지 확인한다. set에서는 요소가 중복되지 않기 때문에 존재하면 1, 그렇지 않으면 0을 반환한다.

	int count = mySet.count(5); // count는 1 또는 0

5. size()
   set의 요소 개수를 반환한다.

	cout << "Set size: " << mySet.size() << endl;

6. clear()
   set을 비운다.

	mySet.clear();

7. begin() & end()
   set의 시작과 끝을 가리키는 반복자를 반환한다. begin()은 첫 번째 요소를, end()는 마지막 요소의 다음 위치를 가리킨다.

  for(auto it = mySet.begin(); it != mySet.end(); ++it) {
      cout << *it << " ";
  }

8. empty()
   set이 비어 있는지 여부를 확인

  if (mySet.empty()) {
      cout << "Set is empty" << std::endl;
  }

9. lower_bound() & upper_bound()
   lower_bound()는 주어진 값보다 크거나 같은 첫 번째 요소의 반복자를 반환하고, upper_bound()는 주어진 값보다 큰 첫 번째 요소의 반복자를 반환한다. 주로 멀티셋에서 사용하고 그냥 셋에서는 find와 큰 차이가 없다.

	auto itLow = mySet.lower_bound(5);
	auto itUp = mySet.upper_bound(5);

10. emplace()
    요소를 set에 삽입하는 함수로, insert()와 유사하지만 객체를 생성하는 과정을 건너뛸 수 있어 더 빠르다.

	mySet.emplace(20);

이러한 함수들을 사용하면 set 자료구조에서 요소를 삽입, 삭제, 검색, 순회할 수 있다.

 멀티셋은 셋과 거의 동일하고 중복을 허용한다는 차이점만 있기 때문에 후술하진 않고 특별한 경우 한가지만 보자. 멀티셋에서 erase함수를 사용할 때, s.erase(1) 이런 식으로 값을 넣으면 모든 1값이 삭제된다. 하지만 s.erase(s.find(1))이런 식으로 반복자를 사용해서 삭제하면 하나의 값만 삭제할 수 있다.

#include <iostream>
#include <set>

using namespace std;

int main() {
	multiset<int> s;
	s.insert(1);
    s.insert(1);
    s.insert(2);
	s.insert(2);
	s.insert(3);
	s.insert(4);

	for (auto it : s)
		cout << it << ' ';
	cout << '\n';

	s.erase(1);
	s.erase(s.find(2));

	for (auto it : s)
		cout << it << ' ';

	return 0;
}