[C++][Data Structure] std::set 컨테이너 (1)

안녕하세요! 두두코딩 입니다 ✋
오늘은 C++ Set 자료구조에 대해 알아보겠습니다.

해당 자료는 강의를 참고하여 작성되었습니다. 실제 강의를 들으면 더 도움이 되실 것 같습니다👍

🖇 소스코드에 마우스를 올리고 copy 버튼을 누를 경우 더 쉽게 복사할 수 있습니다!

궁금한 점, 보안점 남겨주시면 성실히 답변하겠습니다. 😁
+ 감상평 댓글로 남겨주시면 힘이됩니다. 🙇

std::set

C++에서 set이란 고유한 값을 특정한 순서에 따라 저장하는 컨테이너를 말한다.

set에서 중요하게 봐야할 점은 중복된 값이 존재 하지 않는 고유의 값 이라는 것이고, 해당 값들을 특정한 순서에 따라 정렬한 자료구조이다.

set을 사용하기 위해서는 header file 중 #include <set>을 추가해줘야 사용이 가능하다. 보통 set은 아래와 같이 트리형태로 구성되어져있다.

cpp_set

tree 자료구조 같은 경우 한쪽으로 치우치게 되면 성능이 무척 떨어지기 때문에 균형 트리로 구성되어져있다. 균형트리의 종류는 AVL,RB 등 다양하게 존재하지만, 현재 STL에서는 RB tree 형태로 구성되어져 있다.

따라서, STL의 set 자료구조 같은 경우 고유한 값이 들어왔을 때, 균형을 유지해 값들을 관리하게 되며, 균형트리의 특징에 따라 정렬되게 된다. 이진트리에서 균형을 유지하기 위해서는 큰 값은 오른 쪽 작은 값은 왼쪽 등으로 보내는 동작을 한다. 해당 동작을 기반으로 고유의 값들이 정렬되게 되는 것이다. (만약 이진트리를 공부한적 없다면 구글하자! 😁 엄청 쉬운내용이니 어렵지 않게 학습할 수 있을 것이다!)

아래의 예시를 통해 set을 사용하는 방법을 보도록 하자.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s;

	s.insert(30);
	s.insert(40);
	s.insert(20);
	s.insert(10);
	s.insert(45);
	s.insert(25);

	auto p = begin(s);

	while(p != end(s)) {
		cout << *p << endl;
		++p;
	}
};

위의 코드를 보면, 간단한 사용방법을 이해할 수 있다. insert()함수를 통해 값을 넣고, 반복자 (iterator)를 통해 값을 가져오거나 순서를 변경하는 것이 가능하다.

보통, 컨테이너는 반복자(iterator)를 구축해두기 때문에 우리가 일반적으로 많이 사용하는 vector 자료구조와 동일한 방식으로 동작한다고 생각하면 편하다. (물론 동일하게 동작하지 않는 부분도 있지만, 반복자 부분위주로는 비슷하다고 생각하자!😁)

Tip C++ 표준에서는 set 자료구조의 세부구현을 정의하지 않는다. 보통 우리가 set하면 당연히 tree 형태로 구성되어있지 라고 생각한다. 하지만, 엄밀히 말해 어떤 자료구조를 써서 set을 구현해도 상관 없다. 왜냐면 표준 스펙에서는 set에 대해서는 정의하지 않기 때문이다. 예를들어 list형태로 구현해도 되고, hash형태로 구현해도 된다는 말이다. C++ 표준에서는 어떻게 정의하는지는 모르겠고, 해당 동작들은 무조건 동작해야한다 라고 정의한다. 즉, 동작만 제대로 하면 정의는 알아서 해라.. 라고 하는 것이다😑

set 값을 오름차순으로..!

우리가 위의 예시 코드를 돌려보면, 내림차순 기준을 값이 뽑힐 것이다. 하지만, 해당 값들을 오름차순으로 뽑기위해서는 어떻게 해야할까?

template <
  class Key,
  class compare = std::less<Key>
  class Allocator = std::allocator<Key>
  > class set;

위의 코드는 C++ set 자료구조의 template 코드이다. 중간에 compare를 담당하는 부분이 less로 사용하는 것을 볼 수 있을 것이다. less 같은 경우 자세한 내용은 여기를 참조해서 알아보도록 하자.

현재 set 템플릿 내에서는 기본 값으로 less functor를 이용해 내림차순으로 정렬하고 있다. 이를 우리는 greater functor로 변환해주면된다. 클래스가 사용하고 있는 정책을 템플릿인자로 전달하게 될 경우 변환이 가능하다. 따라서, 템플릿인자로 greater를 넘겨주게 될 경우 쉽게 “오름차순”형식으로 바꿀 수 있다.

int main()
{
  // set<int> s;

  // 위의 코드를 아래와 같이 바꾸게 된다면
  // 오름차순 정렬이 가능해진다.
  set<int,greater<int> > s;
  ...
}

Tip 클래스가 사용하고 있는 정책을 템플릿인자로 전달해 변환하는 방식을 단위전략 디자인 (Policy Base Design)이라고 말한다.

set 사용방법

set 자료구조를 사용하는 방법에 대해 알아보자.

🌱 데이터 삽입

set 자료구조에서 요소를 삽입하는 방법은 insert() 혹은 emplace()를 활용해 값을 넣을 수 있다.

int main()
{
  set<int> s;

  // 데이터
  s.insert(10);
  s.emplace(20);

  // 값을 보고 싶다면, 위의 코드를 참고해라!
  ...
}

우리가 흔히 사용하는 vector, array등과 같은 “선형자료구조” 는 push_front 혹은 push_back으로 데이터를 삽입했다. 하지만, Tree자료구조에서는 데이터를 넣을 때 무작정 맨 끝에 넣는것이 아니라 첫번째 노드 부터 비교해가면서 본인의 자리를 찾아가는 방법으로 데이터를 넣어야한다. 따라서, 함수가 insert() 혹은 emplace()라는 이름으로 따로 정의되어져 있다.

Tip set 자료구조에서는 반복자를 통해 값을 변경할 수 없다. 우리가 반복자를 통해 값을 변경하게 될 경우 tree의 구조가 깨지기 때문에 허용하지 않도록 구축되어져 있다.

🌱 데이터 삭제

int main()
{
  set<int> s;

  s.insert(10);
  s.emplace(20);

  s.erase(20);
  s.clear();
  ...
}

데이터를 삭제하기 위해서는 erase()를 사용하게 되고, 키값을 전달해 특정 키 값을 제거하도록 한다. 만약 전체를 지우고 싶다면 clear()를 사용하면된다. 해당 함수를 사용할 경우 set 자료구조 내 존재하는 데이터가 전부 지워진다.

🌱 데이터 검색

우리는 set에서 데이터를 검색하기 위해 find()를 활용한다.

int main()
{
  set<int> s;

  s.insert(10);
  s.insert(20);
  s.insert(5);

  auto p2 = find(begin(s), end(s), 5);
  cout << *p2 << endl;
}

위의 코드와 같이 find()를 사용하면 값을 찾을 수 있다. 하지만, 해당 코드에서는 문제가 있는데.. 어디가 문제일까? 🤔

바로 find()함수이다.

해당 find()는 일반적으로 사용되는 함수로 왼쪽 마지막 부터 차례대로 즉, 값을 찾기위해 선형적으로 검사하는 함수이다. 따라서, 해당 find()를 사용할 경우 tree자료구조에서는 성능이 떨어질 수 있다.

C++에서 가장 조심해야할 부분인데.. find()를 위의 예시코드처럼 써도 Compiler에서는 오류를 내지 않는다는 점이다. Compile상 오류는 없고 성능 문제임으로 아주 좋은 최신 컴파일러는 경고 메세지를 낼 수 있지만, 대부분 오류 혹은 경고 메세지를 주지 않는다.

그렇다면 tree에 맞는 find()는 어디에 있을까? 바로 set 자료구조 내 멤버함수로 따로 구현되어져있다.

int main()
{
  set<int> s;

  s.insert(10);
  s.insert(20);
  s.insert(5);

  // 멤버함수 사용
  auto p2 = s.find(5);
  cout << *p2 << endl;
}

멤버함수로 구현된 find()를 사용해야하며 해당 함수가 선형 find()보다 훨씬 빠르다는점을 기억해야한다.

글이 5분이 넘어가는 것 같아, 지루함을 피하기 위해 한숨 돌리도록 하자! 너무 오래 쉬지말고 1분 정도 쉬고 여기를 클릭해 따라오기 바란다😙

[C++][Data Structure] std::set 컨테이너 (1)

C++ set 자료구조 사용하는 방법을 알아보자😚

std::set

set 값을 오름차순으로..!

set 사용방법

Table of Content