티스토리 뷰
여러 가지에 사용되는 Set 컨테이너에 대해서 알아보겠습니다.
Set에 대한 정보는 C++ Reference를 참고했습니다.
1. Set의 특성
Set은 Unique한 원소들을 특별한 순서에 따라 저장하는 컨테이너입니다.
여기서 Unique한 원소들은 정수를 예를 들면, 1이라는 원소는 Set 컨테이너 안에 단 1개(Unique)만 있을 수 있음을 의미합니다.
Set안에 한 번 삽입한 데이터는 수정할 수 없습니다. 하지만 Insert, remove를 통해서 삽입 제거는 할 수 있습니다.
Set은 보통 이진 탐색 트리로 구현되어 있습니다.
마지막으로 원소는 컨테이너 내에서 절대적인 위치로 존재하는 것이 아닌 키에 의해서 서로서로 연관되어 위치해있다.(정렬 규칙에 의해 상대적인 위치에 있음. 즉, 서로 연관되어 있음.)
2. Set의 구성
2.1) 생성자
priority queue처럼 컨테이너에 담을 자료형과 정렬순서를 지정할 수 있습니다.
생성자에는 5가지가 있습니다.
그냥 가장 무난한 텅 빈 생성자 (디폴트)
일반 배열 or Set의 iterator를 받아서 생성하는 생성자
또 다른 Set을 받는 복사 생성자,
★사용자 정의 비교자 함수를 사용한 Set이 있습니다.
그리고 특별하게 함수 포인터도 담는 Set이 있었습니다. 이건 개발 쪽에서 유용하게(?) 쓰일 것 같습니다.. (신기..)
알고리즘 문제 풀이를 할 때 사용자 정의 비교자 함수를 사용하여 Set을 만들 줄 알아야 응용문제를 풀 수 있습니다.
#include <iostream>
#include <set>
using namespace std;
class comp
{
public:
bool operator()(const int &lhs, const int &rhs) const {
return lhs > rhs; //lhs가 크면 True이고 lhs가 앞에 있어야 함을 의미. (내림차순)
}
};
int main()
{
set<int> s1; //Default constructor
int myints[] = { 10,20,30,40,50 };
set<int> s2(myints, myints + 3); //range constructor
set<int> s3(s2); //copy constructor
set<int> s4(s2.begin(), --s2.end()); //range constructor
set<int, comp> s5(myints, myints + 3); //My comparator
cout << "s1 : ";
for (auto iter = s1.begin(); iter != s1.end(); ++iter)
cout << *iter << " ";
cout << "\ns2 : ";
for (auto iter = s2.begin(); iter != s2.end(); ++iter)
cout << *iter << " ";
cout << "\ns3 : ";
for (auto iter = s3.begin(); iter != s3.end(); ++iter)
cout << *iter << " ";
cout << "\ns4 : ";
for (auto iter = s4.begin(); iter != s4.end(); ++iter)
cout << *iter << " ";
cout << "\ns5 : ";
for (auto iter = s5.begin(); iter != s5.end(); ++iter)
cout << *iter << " ";
return 0;
}
예상대로 잘 출력하는 것을 알 수 있습니다.
s1는 Default 생성자로, 원소로 아무것도 안 가지고 있습니다.
그다음 range를 갖는 생성자는 myint배열의 0번 원소부터 2번 원소까지 [0,3) 잘 가지고 있음을 알 수 있습니다.
복사생성자도 잘 동작하고, set의 iterator를 넣어서 초기화한 생성자도 잘 동작합니다.
가장 눈여겨봐야 할 것이 s5의 사용자 정의 비교자를 order로 하는 set입니다.
원리는 주석으로 달아놓았습니다. 다른 글을 잘 찾아보면 정렬하는 방식을 외우기만 하고 왜? 내림차순으로 정렬되는지에 대해서는 이유를 잘 안 적어 놓은 곳이 많습니다. 원리를 Effective STL이란 책을 보고 알았습니다.
실행결과에 나오듯이, s5도 내림차순으로 잘 작동하는 것을 알 수 있습니다.
그럼 여기서 응용으로, pair<int,int>를 갖는 set을 만들어 봅시다.
그리고 첫 번째 원소를 내림차순으로 두고, 같다면 두 번째 원소는 오름차순으로 구현해봅시다.
#include <iostream>
#include <set>
using namespace std;
class comp
{
public:
bool operator()(const pair<int,int> &lhs, const pair<int,int> &rhs) const {
if (lhs.first == rhs.first)
{ //같은 경우에
return lhs.second < rhs.second; // 작은 lhs가 앞에 (오름차순)
}
else
return lhs.first > rhs.first; //같지 않으면 큰 lhs가 앞에. (내림차순)
}
};
int main()
{
set<pair<int, int>, comp> s6;
s6.insert({ 1,1 });
s6.insert({ 1,2 });
s6.insert({ 1,3 });
s6.insert({ 4,1 });
s6.insert({ 5,7 });
s6.insert({ 6,1 });
s6.insert({ 7,1 });
s6.insert({ 2,1 });
s6.insert({ 2,2 });
s6.insert({ 2,0 });
cout << "----s6----\n";
for (auto iter = s6.begin(); iter != s6.end(); ++iter)
cout << "(" << (*iter).first<< "," << (*iter).second << ")\n";
return 0;
}
pair에서 첫 번째 원소에 대한 조건과 두 번째 원소에 대한 조건을 모두 기술해주었습니다.
그런데 만약 pair으로 받지만 비교자 함수에서 첫 번째 원소를 내림차순으로 하라는 비교자 함수밖에 안 들어 있다,라고 하면
위의 실행결과에서 (1, x) (2, x)에 대한 원소들도 1개밖에 안 들어있을 것입니다.
2.2) 반복자
Set의 iterator는 Bidirectional Iterator입니다.
즉, ++, --연산까지 가능합니다.
set은 []을 사용하여 접근 불가능하므로 iterator를 사용하여 접근해야 합니다.
접근할 iterator를 반환받는 데는 다른 컨테이너들과 마찬가지로
.begin(), .end(), .rbegin(), .rend()가 있습니다.
사용법은 다른 컨테이너들과 똑같으므로 특별히 코드로 예를 들지는 않겠습니다.
2.3) 매서드
우선 가장 기본적인 삽입, 삭제에 대해서 알아보고 추가적인 size 관련하여도 간단히 알아보겠습니다.
시작할 때 말씀드린 것처럼 이진트리로 구성되어 있기 때문에 삽입, 삭제에는 O(logn)의 시간이 걸리게 됩니다. 저장되는 위치는 반복자 함수에 따라서 자동으로 자리 잡게 됩니다.
원소가 자동으로 자리잡기 때문에 다른 컨테이너들의 삽입 함수에서 'iter의 위치에 x라는 값을 넣어라' iter가 많이 빠져있습니다.
set은 그냥 'x값을 넣어라'만 매개변수로 넘겨줘도 충분하기 때문입니다. 그런데 set의 insert 중 (iterator, value)를 매개변수로 받는 것도 있습니다. 여기서의 iterator는 hint로 조금 더 빨리 삽입을 할 수 있도록 시작 지점을 지정해주는? 그런 역할을 합니다.
Insert입니다.
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s1;
set<int> ::iterator iter;
pair<set<int>::iterator, bool> ret;
for (int i = 1; i <= 5; ++i)
s1.insert(i*10);
ret = s1.insert(20); //이미 존재하면 false, 아니면 true.
if (ret.second == false) iter = ret.first;
s1.insert(iter, 25); //최대 효율의 inserting
s1.insert(iter, 24); //동일
s1.insert(iter, 26); //최대 효율이 아닌 inserting
int myints[] = { 5,10,15 };
s1.insert(myints, myints + 3);
cout << "s1 : ";
for (iter = s1.begin(); iter != s1.end(); ++iter)
cout << ' ' << *iter;
cout << '\n';
return 0;
}※예가 좋아서 C++ reference의 코드를 참조했습니다.
디폴트 생성자를 사용해서 s1을 초기화합니다.
그리고 insert(value)를 사용해서 값을 넣어줍니다.
여기서 중요한 점은 insert(value)에도 반환 값이 있다는 것인데, pair<set<T>::iterator, bool>의 형태로 반환하게 됩니다.
first에 위치한 Iterator는 삽입에 성공, 실패한 경우 모두 삽입한 or 삽입하려고 한 숫자의 위치를 나타내는 반복자를 나타냅니다. second는 삽입하려고 했을 때, 삽입하려고 하는 값이 이미 set에 있다면 false, 없었다면 true를 반환하게 됩니다.
그리고 아까 말씀드린 iterator과 값을 매개변수로 갖는 insert입니다. 그냥 조금 더 빨리 insert를 수행할 수 있도록 시작 위치를 지정해주는 역할을 합니다.
마지막으로, 배열의 주소를 입력받아 한번에 삽입하는 경우도 있습니다.
다음은 Erase를 보겠습니다.
erase도 간단합니다. 3가지 종류가 있는데 값으로 삭제하는 경우, iterator로 삭제하는 경우, 2개의 iterator로 범위로 삭제하는 경우. 범위는 역시 [first, last)를 나타냅니다.
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s1;
set<int> ::iterator iter;
for (int i = 1; i <= 9; ++i)
s1.insert(i*10);
iter = s1.begin(); //*iter = 10
++iter; //*iter = 20
s1.erase(iter); // iterator를 사용해서 20삭제
s1.erase(40); // value를 사용해서 40삭제
iter = s1.find(60);
s1.erase(iter, s1.end()); //60부터 끝까지 삭제
cout << "s1 : ";
for (iter = s1.begin(); iter != s1.end(); ++iter)
cout << ' ' << *iter;
cout << '\n';
return 0;
}※예가 좋아서 C++ reference의 코드를 참조했습니다.
다시 한번 말씀드리지만, iterator를 사용해서 원소를 지우면 그 iterator는 쓰레기 값을 가리키게 됩니다. 반드시 다시 초기화해주어야 합니다.
. size()나. empty()는 다른 컨테이너들과 동일하므로 넘어가도록 하겠습니다.
그냥 원소의 개수를 반환하고, empty()는 size가 0이면 True 아니면 false를 반환합니다.
이제 Set에서 가장 중요하다고 할 수 있는 find, count, lower_bound, upper_bound에 대해서 알아보도록 하겠습니다.
여기 있는 매서드들은 모두 logn의 시간 복잡도를 가집니다.
find는 매개변수로 값을 넣고 값이 있다면 그 값을 나타내는 iterator를, 아니라면 end()를 반환합니다.
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s1;
set<int> ::iterator iter;
for (int i = 1; i <= 9; ++i)
s1.insert(i*10);
iter = s1.find(10);
if (iter != s1.end())
s1.erase(iter);
cout << "s1 : ";
for (iter = s1.begin(); iter != s1.end(); ++iter)
cout << ' ' << *iter;
cout << '\n';
return 0;
}
find(10)를 사용해서 10의 iterator를 구하고 그게 end()가 아니라면 삭제하도록 했습니다.
iter에 end()가 들어가 있는데 erase에 매개변수로 넣으면 에러가 발생합니다.
count는 원소의 개수를 반환합니다. 있다면 0, 없다면 1이 되겠죠? set은 중복 원소를 가질 수 없기 때문에..
간단하기 때문에 코드로 작성하지는 않겠습니다.
다음은 lower_bound, upper_bound입니다.
algorithm헤더에 있는 것과 같은 역할을 합니다. 그런데 멤버 함수인만큼 좀 더 set에 최적화되어있습니다.
두 매서드 모두 값을 찾는다면 조건을 만족하는 원소의 iterator를 반환합니다.
lower_bound(value)는 value보다 크거나 같은 가장 작은 원소의 iterator를 반환합니다. value ≤ x
upper_bound(value)는 value 보다 큰 가장 작은 원소의 iterator를 반환합니다. value < x
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s1;
set<int> ::iterator lower, upper;
for (int i = 1; i <= 9; ++i)
s1.insert(i*10);
lower = s1.lower_bound(30); //30보다 보다 크거나 같은 가장 작은 원소 ->30
upper = s1.upper_bound(60); //60보다 큰 가장 작은 원소 ->70
cout << "s1.lower_bound(30) : " << *lower << '\n';
cout << "s1.upper_bound(60) : " << *upper << '\n';
lower = s1.lower_bound(9); //9보다 보다 크거나 같은 가장 작은 원소 ->10
upper = s1.upper_bound(11); //11보다 큰 가장 작은 원소 ->20
cout << "s1.lower_bound(9) : " << *lower << '\n';
cout << "s1.upper_bound(11) : " << *upper << '\n';
return 0;
}
잘 실행되는 것을 볼 수 있습니다.
마치며..
Set 역시 은근히 자주 쓰이는 자료구조입니다.
정렬하는 순서만 잘 숙지한다면 사용하는데 큰 문제는 없을 것입니다.
주워들은 것이 있다면 lower bound같이 algorithm헤더에도 있고, 멤버 함수로도 있는데 이런 경우에는
멤버 함수로 구현된 것이 좀 더 최적화(?)되어 있다고 될 수 있으면 멤버 함수를 사용하는 것이 좋다는 것입니다.
지적 댓글 환영입니다~ :)
'개발 > C++' 카테고리의 다른 글
| [C++ / 2인용] 테트리스 개발 ( 구현 , 실행 화면, 코드 공유 ) (0) | 2020.08.31 |
|---|---|
| [C++ / 2인용] 테트리스 개발 ( Class 부분 ) (0) | 2020.08.27 |
| [C++/Library] String 분석 (0) | 2020.08.09 |
| [C++ / STL] Queue, Priority Queue 분석 (2) | 2020.08.01 |
| [C++ / STL] Stack 분석 (0) | 2020.07.31 |