STL에서 제공하는 연관 컨테이너(Associate Container)인 Set, Multiset에 대해서 알아보자
연관 컨테이너(Associate Container)의 특징은 원소들이 특정한 규칙에 따라 자동 정렬 된다는 점이다.
Set 자료구조는 균형 이진트리의 형태를 띈다. 또한 원소들의 중복을 허용하지 않는 점에 유의해야 한다.
1. 선언
우선 set을 사용하기 위해서는 set을 include 해주어야 한다. 선언 자체는 vector와 매우 유사한 점을 보인다.
2.원소 삽입 및 삭제
원소 삽입과 삭제는 각각 insert, erase 함수를 사용하여 할 수 있다.
3.Iterator
iterator란 반복자라고도 불린다. 반복자는 컨테이너에 저장되어 있는 원소들을 참조할 때 사용하는데 포인터와 상당히 유사하다.
쉽게 말해 배열에서 인덱스로 접근하는 것과 유사하게 컨테이너의 원소를 반복자로 접근할 수 있다.
여기 실행 결과에서 알 수 있는 점은 별도의 정렬을 하지 않았음에도 자동 정렬이 되었다는 점이다. set은 비교함수를 별도로 지정하지 않으면 원소들을 오름차순 정렬하게 된다. 비교함수에 대해서는 아래에서 설명하겠다.
해당 소스코드에서 begin(), end()가 쓰였는데 이름에서 알 수 있다싶이 begin()은 set의 시작 반복자를 반환하며 end()는 마지막 반복자를 반환한다.여기서 주의할 점은 end()는 마지막 원소 다음의 반복자를 반환한다는 것이다. 아래의 소스코드를 참고하자.
위에서 end()는 마지막 원소의 다음 원소 즉, 컨테이너의 가장 끝에 위치하는 빈 공간을 가리키고 있는 반복자를 반환한다. 따라서 증감 연산자로 마지막 원소를 가리키게끔 이동해주어야 한다.
4. 비교함수
비교함수는 set 자료구조의 자동정렬 규칙을 지정하는 함수이다. 아래의 사용법을 보자.
예시에서 operator에 들어가는 인자는 set의 원소로 a,b를 비교하여 정렬을 수행하게 된다.
operator함수를 용도에 맞게 구현한다면 의도한대로 set 컨테이너가 정렬된다.
begin : 첫 번째 원소의 반복자를 반환
end : 마지막 원소 다음의 반복자를 반환
erase : 특정 원소나 지정한 범위의 원소들을 삭제
find : 특정 원소의 반복자를 반환. 존재하지 않는 경우 마지막 원소 다음의 반복자를 반환
clear : 컨테이너 내우의 모든 원소들을 삭제
empty : 컨테이너가 비어있다면 true를 반환.
insert : 원소 삽입
lower_bound : 지정한 원소 이상의 첫번째 위치의 반복자를 반환
upper_bound : 지정한 원소보다 큰 첫번째 위치의 반복자를 반환
count : 원소가 있으면 1, 아니면 0을 반환
rbegin : 역방향으로 첫 번째 원소의 반복자를 반환
rend : 역방향으로 마지막 원소 다음의 반복자를 반환
size : 원소의 개수 반환
Set의 특징 중 원소의 중복을 허용하지 않는 특징이 있다. 그러나 Multiset은 Set과 매우 유사하나 중복을 허용한다는 차이점이 존재한다.
따라서 upper_bound, lower_bound같은 함수들은 multiset인 경우 좀 더 용이하게 사용할 수 있다.
이렇게 set과 multiset을 알아보았다. 자료구조는 알면 알수록 효율적인 코드를 작성하기 위한 선택지가 늘어나기 때문에 제대로 알아둘 필요가 있다.
연관 컨테이너(Associate Container)의 특징은 원소들이 특정한 규칙에 따라 자동 정렬 된다는 점이다.
Set
Set 자료구조는 균형 이진트리의 형태를 띈다. 또한 원소들의 중복을 허용하지 않는 점에 유의해야 한다. 1. 선언
우선 set을 사용하기 위해서는 set을 include 해주어야 한다. 선언 자체는 vector와 매우 유사한 점을 보인다.
|
1
2
3
4
5
6
7
8
9
10
11
|
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> test_set;
return 0;
}
|
cs |
2.원소 삽입 및 삭제
원소 삽입과 삭제는 각각 insert, erase 함수를 사용하여 할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> test_set;
test_set.insert(1);
test_set.insert(3);
test_set.insert(4);
test_set.insert(2);
test_set.erase(1);
test_set.erase(2);
test_set.erase(3);
test_set.erase(4);
return 0;
}
|
cs |
3.Iterator
iterator란 반복자라고도 불린다. 반복자는 컨테이너에 저장되어 있는 원소들을 참조할 때 사용하는데 포인터와 상당히 유사하다.
쉽게 말해 배열에서 인덱스로 접근하는 것과 유사하게 컨테이너의 원소를 반복자로 접근할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> test_set;
test_set.insert(1);
test_set.insert(3);
test_set.insert(4);
test_set.insert(2);
for (set<int>::iterator iter = test_set.begin(); iter != test_set.end(); iter++)
cout << *iter << " ";
cout << "\n";
return 0;
}
|
cs |
실행 결과
1 2 3 4
여기 실행 결과에서 알 수 있는 점은 별도의 정렬을 하지 않았음에도 자동 정렬이 되었다는 점이다. set은 비교함수를 별도로 지정하지 않으면 원소들을 오름차순 정렬하게 된다. 비교함수에 대해서는 아래에서 설명하겠다.
해당 소스코드에서 begin(), end()가 쓰였는데 이름에서 알 수 있다싶이 begin()은 set의 시작 반복자를 반환하며 end()는 마지막 반복자를 반환한다.여기서 주의할 점은 end()는 마지막 원소 다음의 반복자를 반환한다는 것이다. 아래의 소스코드를 참고하자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> test_set;
test_set.insert(1);
test_set.insert(3);
test_set.insert(4);
test_set.insert(2);
set<int>::iterator iter;
cout << "begin : " << *test_set.begin() << "\n";
cout << "end : " << *(--test_set.end()) << "\n";
return 0;
}
|
cs |
실행 결과
begin : 1
end : 4
end : 4
위에서 end()는 마지막 원소의 다음 원소 즉, 컨테이너의 가장 끝에 위치하는 빈 공간을 가리키고 있는 반복자를 반환한다. 따라서 증감 연산자로 마지막 원소를 가리키게끔 이동해주어야 한다.
4. 비교함수
비교함수는 set 자료구조의 자동정렬 규칙을 지정하는 함수이다. 아래의 사용법을 보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <iostream>
#include <set>
using namespace std;
struct compare
{
//비교함수
bool operator()(int a, int b)
{
return a > b;
}
};
int main()
{
set<int, compare> test_set;
test_set.insert(1);
test_set.insert(3);
test_set.insert(4);
test_set.insert(2);
set<int>::iterator iter;
for (iter = test_set.begin(); iter != test_set.end(); iter++)
cout << *(iter) << " ";
return 0;
}
|
cs |
실행 결과
4 3 2 1
예시에서 operator에 들어가는 인자는 set의 원소로 a,b를 비교하여 정렬을 수행하게 된다.
5. SET에 제공되는 함수
set에 제공되는 함수는 위에서 언급한 것 외에 여러가지가 있다. 이를 정리해보았다.begin : 첫 번째 원소의 반복자를 반환
end : 마지막 원소 다음의 반복자를 반환
erase : 특정 원소나 지정한 범위의 원소들을 삭제
find : 특정 원소의 반복자를 반환. 존재하지 않는 경우 마지막 원소 다음의 반복자를 반환
clear : 컨테이너 내우의 모든 원소들을 삭제
empty : 컨테이너가 비어있다면 true를 반환.
insert : 원소 삽입
lower_bound : 지정한 원소 이상의 첫번째 위치의 반복자를 반환
upper_bound : 지정한 원소보다 큰 첫번째 위치의 반복자를 반환
count : 원소가 있으면 1, 아니면 0을 반환
rbegin : 역방향으로 첫 번째 원소의 반복자를 반환
rend : 역방향으로 마지막 원소 다음의 반복자를 반환
size : 원소의 개수 반환
Multiset
Set의 특징 중 원소의 중복을 허용하지 않는 특징이 있다. 그러나 Multiset은 Set과 매우 유사하나 중복을 허용한다는 차이점이 존재한다.
따라서 upper_bound, lower_bound같은 함수들은 multiset인 경우 좀 더 용이하게 사용할 수 있다.
이렇게 set과 multiset을 알아보았다. 자료구조는 알면 알수록 효율적인 코드를 작성하기 위한 선택지가 늘어나기 때문에 제대로 알아둘 필요가 있다.
댓글