[자료구조] Set

Set

list와 map 사이의 개념 정도 | 수학의 집합과 비슷

특징

• 데이터를 순서대로 저장하지 않는다.
• 중복을 허용하지 않는다.
• 이럴때 사용
  • 순서는 상관없지만 데이터의 중복을 허용하고 싶지 않을 때
  • 집합 관련 문제
  • 중복 처리를 해야하고 빠르게 처리해야할 때

 

set의 종류

   1. Hash set

• set과 hash 알고리즘을 적용한 자료구조
  • hash 알고리즘
    • 입력된 key(키)를 해시 코드로 변환
    • 해시 코드를 인덱스로 한 array의 해당 인덱스를 찾아서 저장한다. (if. 배열 길이가 초과하는 경우 길이의 나머지를 구하여 링크드 리스트로 추가한다.)
      • 즉, 해시코드가 가리키는 인덱스, 배열에서 해당 인덱스에 값을 저장한다. (= 키가 배열의 인덱스를 가리킴)
      • key(키) -> 해시코드 -> 배열의 인덱스
• 가장 빠름

출처 : 위키피디아(https://en.wikipedia.org/wiki/Hash_table)

   2. Tree set

• 저장된 데이터의 값에 따라 정렬되는 구조
• tree set 작동원리
  
  • 새로운 데이터가 들어오면 루트부터 비교
  • 해당 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동한다.
  • 더 이상 비교할 수 없을 때까지 해당 노드와 들어온 값의 크기를 비교한다.

   3. Linked Hash set

• 중복 허용 X
• linked의 개념을 이용하여 데이터가 순서대로 쌓아지는 구조

 

멤버함수 예시

#include <set> //set 라이브러리 사용
using namespace std;

set<string> s1; //문자열 set인 s1 선언 (오름차순)
set<string, greater<>> s2; //문자열set인 s2 선언(내림차순)

//자주 사용하는 멤버함수들

//insert(요소) : 요소 삽입
s1.insert("a"); //s1 = {a}
s1.insert("b"); //s1 = {a, b}
s1.insert("b"); //s1 = {a, b} b를 한번 더 추가해도 a,b,b가 아닌 a,b 그대로임 (중복허용 X)

//erase(요소) : 요소 삭제
s1.erase("a"); //s1 = {b}

//count(요소) : 해당 요소가 있으면 1, 없으면 0 리턴
cout << s1.count("a"); //출력 : 0
cout << s1.count("b"); //출력 : 1

//clear() : 모든 요소 지움
s1.clear(); //s1 = {}

//size() :원소 개수 반환
//empty() : set에 원소 있으면 0, 없으면 1 리턴