[C++ STL] Set, Multiset

1. Set

- 저장 데이터의 값이 유일한 자료구조이다.(중복이 허용되지 않는다.)

- 노드 기반 컨테이너이다.

- 임의 접근이 불가능하다.

- 균형 이진 트리로 구현되어있다.

- 각 노드는 pair<T,T>로 구성되었다.

- multiset은 set에서 중복이 허용된다는 것 말고는 다른게 없기 때문에 함께 정리한다.

2. Include

#include <set> // multiset도 set에 포함되어있음

 

3. 생성자

std::set<T> name; // 기본 오름차순(== set<T,less<T>>)
std::set<T> name(const key_compare& _Pred); // 정렬 방법을 _Pred로 설정한다. (== set<T, _Pred>)
std::set<T> name(const set& otherSet);
std::set<T> name(_Iter first, _Iter last); // [first,last)
std::set<T> name(_Iter first, _Iter last, const key_compare& _Pred);

namespace std를 사용. (less, grater 도 std에 포함)

기존의 set을 복사하여 생성 가능.

2개의 반복자 사이에 있는 원소들로 초기화 가능.

생성시 정렬기준을 설정 가능.

템플릿 <T>에 <T, _Pred<T>> 와 같이 정렬 방법을 넣어 줄 수 있다. (기본값은 less<T>)

 

4. function

// set에 원소를 삽입한다.
void insert(initializer_list<T> _Ilist)
void insert(_Iter first, _Iter last) [first,last)
_Pairib insert(T&& value) // 삽입원소를 가리키는 반복자와 성공 여부 bool값의 pair 객체 반환.
_Pairib insert(const T& value)
// iter부터 value를 빠르게 삽입한다.(삽입 위치를 지정해서 시간을 줄임), 반환값은 삽입원소를 가리키는 반복자.
iterator insert(const_iterator iter, T&& value) 
iterator insert(const_iterator iter, const T& value)

// key값에 해당하는 원소를 찾아 반복자 반환. 
iterator find(const T& key) // == lower_bound(const T& key)

// key값에 해당하는 원소가 시작되는 주소를 가리키는 반복자 반환
iterator lower_bound(const T& key)

// key값에 해당하는 원소가 끝나는 다음 주소를 가리키는 반복자 반환
iterator upper_bound(const T& key)

// key값에 해당하는 원소의 갯수를 반환
size_type count(const T& key)

// set의 원소 수를 반환
size_type size()

// set이 비어있으면 true를 반환
bool empty()

// set의 모든 원소를 제거
void clear()

// 두 set의 내용을 바꾼다.
void swap(set<T>& _Right)

// set의 첫 번째 원소를 가리키는 반복자 반환
iterator begin()
const_iterator cbegin() // 순회 불가능

// set의 마지막 원소 다음의 공간을 가리키는 반복자 반환
iterator end()
const_iterator cend() // 순회 불가능

// set의 마지막 원소를 가리키는 역순 반복자 반환
reverse_iterator rbegin()
const_reverse_iterator crbegin() // 순회 불가능

// set의 첫 번째 원소 이전의 공간을 가리키는 반복자 반환
reverse_iterator rend()
const_reverse_iterator crend() // 순회 불가능

// key에 해당하는 원소 모두제거. 반환값은 제거한 원소의 수.
size_type erase(const T& key) 
// set의 원소를 제거. 반환값은 제거한 원소의 다음 원소를 가리키는 반복자.
iterator erase(iterator iter) // 반복자가 가르키는 원소 제거
iterator erase(const_iterator iter)
iterator erase(const_iterator first, const_iterator last) // [first,last) 사이의 원소 모두 제거

// T의 생성자에 파라미터를 넘겨서 T객체 생성후 삽입, 반환값은 삽입된 원소를 가리키는 반복자와 성공여부 bool값 페어
_Pairib emplace(_Valty&&... _Val)
// iter가 가르키는 곳에 삽입, 반환값은 삽입된 원소를 가리키는 반복자
iterator emplace_hint(const_iterator iter,_Valty&&... _Val)

// key 정렬방식 반환 
key_compare key_comp()

// value 정렬 기준 반환 set에서는 key_comp()와 같다.
value_compare value_comp()