Chapter3. 컨테이너 어댑터와 비트셋 컨테이너
1. 컨테이너 어댑터
컨테이너 어댑터란 다른 순차 컨테이너를 바탕으로 하여 인터페이스를 다르게 래핑한 것을 말한다. 보다 단순화된 인터페이스를 제공하는 것이 목적이기 때문에 이들은 복수 항목을 한 번에 삽입, 삭제하는 메서드나 항목 순회를 위한 반복자를 지원하지 않는다.
표준에서 제공되는 컨테이너 어댑터는 queue, priority_queue, stack 세 가지가 있다. 경우에 따라 표준 컨테이너 어댑터의 인터페이스가 너무 제약이 되어 바탕 컨테이너를 직접 사용하거나, 커스텀 어댑터를 작성하여 사용해야 할 수 있다.
1) queue
queue는 헤더에 정의되어 있고 표준적인 선입선출(FIFO) 시맨틱을 구현하고 있다. 템플릿의 정의는 다음과 같다.
template <typename _Ty, typename _Container = deque<_Ty>> class queue;두 번째 템플릿 파라미터가 바로 바탕이 되는 컨테이너를 지정하는 것이다. 물론 항목의 타입은 _Ty이므로 바탕 컨테이너 또한 _Ty를 항목 타입으로 가져야 한다. 기본 값이 deque으로 지정되어 있는데 queue의 바탕 클래스로서 가능한 컨테이너는 deque과 list이다.
queue는 뒤에서 넣고 앞에서 빼내는 인터페이스를 가지기 때문에 바탕 클래스가 push_back 메서드와 pop_front 메서드를 지원해야 한다는 제약사항이 있다. 때문에 vector는 불가능하고(pop_front를 지원하지 않으므로) deque 또는 list를 선택 가능하다. 보통은 디폴트 타입인 deque을 사용하는 것으로 충분하다.
- 생성 및 비교
당연하지만 복사 생성자와 이동 생성자, 복사 대입, 이동 대입 연산들을 제공한다. 조금 특별한 생성자는 바탕 컨테이너를 참조로 전달하여 생성하는 버전인데, 이렇게 하면 기존에 사용하던 deque 또는 list로 복사 생성한 컨테이너를 바탕 컨테이너로 사용하게 된다. 보통은 디폴트 생성자로 충분하고 이 경우 바탕 컨테이너의 디폴트 생성자를 호출하여 만들어진다.
#include <queue>
#include <deque>
#include <list>
using namespace std;
queue<int> q1;
deque<int> dq{ 1,2,3,4,5 };
queue<int> q2{ dq };
list<int> lst{ 1,2,3,4,5 };
queue<int, list<int>> q3{ lst };
//list를 참조전달하여 생성하려면 두 번째 템플릿 파라미터가 list여야 함queue의 비교 연산은 queue가 가진 항목열을 사전순으로 비교해주는데 queue의 용도상 비교 연산을 수행해야 하는 경우는 거의 없다.
- 룩업 메서드
front() : 첫 번째 항목을 참조로 리턴한다.
back() : 마지막 항목을 참조로 리턴한다.
- 삽입 메서드
push() : 항목 타입의 인자를 받아 마지막 항목으로서 추가한다.
emplace() : 항목 타입의 생성자 인수 목록을 전달하여 메서드 내부에서 항목 타입의 객체를 생성하여 마지막 항목으로서 추가한다.
- 삭제 메서드
pop() : 첫 번째 항목을 제거한다. 항목을 반환하지 않는다.
다음 코드는 전반적인 큐의 활용 방법을 보여준다.
#include <queue>
#include <iostream>
using namespace std;
int main()
{
queue<pair<int, int>> q;
q.emplace(0, 0); //pair를 생성하기 위한 인수 목록 전달
q.push({5, 5}); //pair 임시객체를 생성하여 전달
cout << "queue size is " << q.size() << endl;
q.pop();
cout << q.front().first << ',' << q.front().second;
q.pop();
cout << boolalpha << q.empty();
}2) priority_queue
우선순위 큐는 선입선출 순이 아니라 우선순위가 높은 항목이 가장 앞에 오도록 하는 큐이다. 우선순위가 같은 항목들 사이에서도 선입선출 순을 보장해주지 않는다. 헤더에 함께 정의 되어 있으며 정의는 다음과 같다.
template <typename _Ty, typename _Container = vector<_Ty>, typename _Pr = less<_Ty>>
class priority_queue;두 번째 파라미터가 바탕 컨테이너이며 vector 외에도 deque을 사용할 수 있다.
세 번째 파라미터는 우선순위의 비교에 사용될 비교 연산을 나타내는 타입이다. less 템플릿 또는 greater 템플릿의 인스턴스가 오거나 클로져와 같은 functor가 올 수 있다. 기본 값인 less 템플릿의 인스턴스는 operator <를 기준으로 비교를 해주고, 작은 쪽이 더 낮은 우선순위를 갖는다. 즉 기본적으로 priority_queue는 최대힙과 같이 동작한다.
사용자 정의 타입에 대한 priority_queue를 인스턴스화 한다면 해당 타입에 대해서 operator <가 반드시 구현되어 있어야 한다.
인터페이스는 queue와 유사하고, 다른 점은 front()나 back()을 지원하지 않고 top() 메서드로서 룩업을 지원하다는 점이다. 이름이 top인 이유는 priority_queue의 구현이 일반적으로 힙 구조이기 때문이다.
#include <functional>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
template<typename T>
void print_queue(T q) { //출력을 위해 pop을 하므로 값 전달하여 복제
while (!q.empty()) {
cout << q.top() << ' ';
q.pop();
}
cout << '\n';
}
int main() {
const auto data = { 1,8,5,6,3,4,0,9,7,2 };
priority_queue<int> pq1; //최대 힙
for (int n : data)
pq1.push(n);
print_queue(pq1);
priority_queue<int, vector<int>, std::greater<int>> pq2(data.begin(), data.end()); //최소 힙
print_queue(pq2);
auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
std::priority_queue<int, std::vector<int>, decltype(cmp)> pq3(cmp); //클로져의 타입을 알기 위해 decltype 사용
for (int n : data)
pq3.push(n);
print_queue(pq3);
}위 코드는 priority_queue를 생성하는 몇 가지 방법을 보여준다. 가장 단순하게는 pq1처럼 항목의 타입만 템플릿 인자로 줘서 생성하는 것이며 이런 경우 최대힙처럼 동작한다.
세 번째 템플릿 인자를 전달하기 위해서는, 순서상 두 번째 템플릿 인자도 함께 전달해주어야 하고 이 때는 vector 또는 deque를 전달해주면 된다. pq2가 이러한 방식으로 생성하는 방법을 보여주는데, 더불어 초기 데이터를 넣어주며 생성하는 방법도 보여준다. 생성자의 인자로 반복자 쌍을 넘기면 해당 반복자가 순회하는 항목열을 초기 값으로서 넣어주는데 이때 힙 구조를 유지하면서 넣어주기 때문에 항목열 크기 N에 대해 O(NlogN)의 시간복잡도를 갖는다.
pq3과 같이 비교함수를 직접 작성하여 전달해줄 수도 있다. operator()를 오버라이딩한 커스텀 클래스의 객체를 줘도 되고 람다식으로 만들어낸 클로져를 넘겨줘도 된다. 템플릿 인자로 형식을 전달해야 하는데 클로져의 형식을 decltype을 통해 알아내서 넘겨줄 수 있다.
항목의 타입이 부호가 있는 수라면 최소힙으로 만드는 다른 방법도 있다. 항목을 추가하거나 읽을 때 부호를 반전시키는 방법이다. 부호가 반전되면서 정렬 순이 뒤집히는 것이다. 그렇게 하면 두 번째, 세 번째 템플릿 인자를 넘기지 않고도 최소힙을 만들 수 있기 때문에 유용하다.
3) stack
stack은 헤더에 정의되어 있으면 선입후출(FILO) 시맨틱을 구현한다. 정의는 다음과 같다.
template <typename _Ty, typename _Container = deque<_Ty>> class stack;끝에서만 삽입 및 삭제가 발생하기 때문에 바탕 컨테이너는 vector, list, deque 모두 가능하다. 인터페이스는 priority_queue와 같다.
2. 비트셋 컨테이너
비트셋 컨테이너는 비트별로 on/off 상태를 저장하도록 관리되는 특수한 컨테이너이다. 플래그 집합등을 표현하는데 유용하게 사용될 수 있다. bool이 1byte를 차지하는 것과 달리 비트셋에서의 각 비트는 실제로 1bit 크기만 차지하며 operator[] 등으로 접근하면 bool 타입의 proxy 객체를 리턴해주어 bool 타입을 다루는 것과 같은 환상을 준다.
#include <bitset>
using namespace std;
bitset<10> bs;
bs.set(3);
bs.set(6);
bs[8] = true; //operator[]를 이용한 비트 쓰기
bs[9] = bs[3]; //operator[]를 이용한 비트 읽기
if (bs.test(3)) //bs[3] == true
cout << "Bit 3 is set!" << endl;
cout << bs << endl; //1101001000bitset은 0과 1로 이루어진 string으로부터 생성될 수 있으며 비트 연산자를 통해 집합 연산을 수행할 수 있다.
auto str1 = "0011001100";
auto str2 = "0000111100";
bitset<10> bitsOne(str1);
bitset<10> bitsTwo(str2);
auto bitsThree = bitsOne & bitsTwo;
cout << bitsThree << endl; //0000001100
bitsThree <<= 4;
cout << bitsThree << endl; //0011000000