수학과의 좌충우돌 프로그래밍

[C++] stl container set, multiset 본문

알고리즘/C++

[C++] stl container set, multiset

ssung.k 2020. 4. 14. 17:22

이번 포스팅에서는 C++ stl container인 setmutiset에 대해서 알아보도록 하겠습니다.

 

set

set 은 데이터를 저장할 수 있는 container입니다.

가장 기본적인 container와 다른 점은 자동으로 정렬이 된다는 점입니다.

새로운 값이 삽입, 삭제 될 때마다 이 정렬 상태를 유지하고 있어야 하므로 set 은 기본적으로 binary search tree로 구현이 되어 있습니다.

 

set 선언

set 을 사용하기 위해서는 헤더 파일을 포함해야합니다.

#include <set>

 

그 후에는 보통 container들과 마찬가지로 다음과 같이 선언할 수 있습니다.

set <자료형> 이름;

 

int 자료형을 저장할 s라는 이름의 set을 만들기 위해서는 다음과 같이 선언해줍니다.

set <int> s;

 

선언 시, 어떠한 기준으로 정렬할지 지정해줄 수 있습니다.

set <자료형, 비교함수> 이름;

 

비교함수가 단순히 기본자료형이 아닌 pair나 struct의 값을 기준으로 비교하기 위해선 다음과 같이 해줄 수 있습니다.

class Player
{
public:
   Player() {}
   ~Player() {}

   int m_HP;
};

template< typename T >
struct HP_COMPARE : public binary_function< T, T, bool >
{
   bool operator() (T& player1, T& player2) const 
   { 
      return player1.m_HP > player2.m_HP;
   }
};

int main()
{
   set< Player, HP_COMPARE > set1;
   return 0;
}

 

set 삽입, insert

set에 데이터를 삽입하기 위해서는 insert를 사용합니다.

set <int> s;
s.insert(10);

 

iterable한 데이터를 한 번에 삽입할 수 도 있습니다.

vector<int> v;
v.push_back(0);
// 생략
v.push_back(100);

set<int> s;
s.insert(v.begin(), v.end());

 

set 순회, iterator, reverse_iterator

set 자료형의 값들을 순회하여 확인할 수 있습니다.

이 때는 iternator를 사용해야합니다.

set<int> s;
for (int i=0;i<100;i++) 
  s.insert(i);

set<int>::iterator iter;

for (iter=s.begin();iter!=s.end();iter++)
  cout << *iter << " ";

// 출력값 : 0 1 2 ... 99

 

역방향으로 순회도 가능합니다.

이 때는 역방향 iterator인 reverse_iterator와 rbegin(), rend()를 사용해야합니다.

set<int>::reverse_iterator iter;

for (iter=s.begin();iter!=s.end();iter++)
  cout << *iter << " ";

// 출력값 : 99 98 97 ... 0

 

데이터 검색, find

원하는 값을 찾기 위해서는 find를 사용합니다.

해당 값이 있을 경우에는 그 값의 iterator를 반환하고 아닐 경우에는 end()의 iterator를 반환합니다.

set<int> s;
for (int i=0;i<100;i++) 
  s.insert(i);
set<int>::iterator iter = s.find(10);
if (iter == s.end()){
  cout << "값 없음\n";
}
else {
  cout << *iter << "\n";
}

// 10

 

데이터 삭제, clear와 erase

데이터를 삭제하기 위해서는 두 가지 함수를 사용합니다.

우선 전체 데이터를 삭제할 수 있는 clear 입니다.

그리고 empty를 통해 set이 비어있는지 확인할 수 있습니다.

set<int> s;
for (int i=0;i<100;i++) 
  s.insert(i);

s.clear();

if (s.empty()){
  cout << "set이 비었습니다.\n";
}

 

다음으로는 특정값을 삭제할 수 있는 erase 입니다.

erase를 통해 값을 제거하는 방법도 다양합니다.

 

우선 iterator를 이용하여 제거하는 방법입니다.

가장 앞의 원소와 가장 뒤의 원소를 제거하는 방법으로 s.end()는 마지막 값 다음을 가르키고 있으므로 하나 뒤로 와서 삭제를 해줍니다.

s.erase(s.begin());
s.erase(--s.end());

 

두 번째로 값을 통해 삭제하는 방법입니다.

10에 해당하는 값이 삭제됩니다.

s.erase(10);

 

multiset

multisetset과 전체적으로 유사합니다.

하지만 차이점이라고 하면 set 은 같은 값을 중복으로 저장할 수 없는 반면, multiset 을 사용하면 이러한 문제를 해결할 수 있습니다.

그 밖에 사소하게 맴버함수의 반환값이 조금씩 다르지만 대체로 비슷합니다.

'알고리즘 > C++' 카테고리의 다른 글

[C++] BAEKJOON 2407 조합  (0) 2020.08.21
[C++] string 문자열 나누는 split  (3) 2020.03.15
[C++] BAEKJOON 17968 Fire on Field (acm-icpc)  (0) 2019.11.13
[C++] BAEKJOON 11404 플로이드  (0) 2019.11.10
[C++] BAEKJOON 11559 Puyo Puyo  (0) 2019.11.04
Comments