기초 : C++ STL 프로그래밍(5)-덱(deque) : (2)

http://www.hanb.co.kr/network/view.html?bi_id=1616

제공 : 한빛 네트워크
저자 : 최흥배

5.5.3. deque 실습 예제

다음은 deque에서 가장 자주 사용하는 멤버들을 사용하는 전체 코드입니다. 

[리스트 1]

#include 
#include 

using namespace std;


// 서버/ 클라이언트간에 주고 받는 패킷
struct Packet
{
	unsigned short Index; // 패킷 인덱스
	unsigned short BodySize; // 패킷 보디(실제 데이터)의 크기
	char	       acBodyData[100]; // 패킷의 데이터
};


int main() 
{
	Packet Pkt1;
	Pkt1.Index = 1;		Pkt1.BodySize = 10;

	Packet Pkt2;
	Pkt2.Index = 2;		Pkt2.BodySize = 12;

	Packet Pkt3;
	Pkt3.Index = 3;		Pkt3.BodySize = 14;


	deque< Packet > ReceivePackets;


	// 뒤에 추가
	ReceivePackets.push_back( Pkt2 );
	ReceivePackets.push_back( Pkt3 );

	// 앞에 추가
	ReceivePackets.push_front( Pkt1 );

	
	// 저장된 패킷 정보 출력
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index << endl;
		cout << "패킷 바디 크기: " << iterPos->BodySize << endl;
	}

	cout << endl << "역방향으로 출력" << endl;
	for( deque< Packet >::reverse_iterator iterPos = ReceivePackets.rbegin();
		iterPos != ReceivePackets.rend();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index << endl;
		cout << "패킷 바디 크기: " << iterPos->BodySize << endl;
	}

	cout << endl << "배열 방식으로 접근" << endl;
	// 저장된 총 패킷 수
	int ReceivePacketCount = ReceivePackets.size();
	cout << "총 패킷 수: " << ReceivePacketCount << endl;
	for( int i = 0; i < ReceivePacketCount; ++i )
	{
		cout << "패킷 인덱스: " << ReceivePackets[i].Index << endl;
		cout << "패킷 바디 크기: " << ReceivePackets[i].BodySize << endl;
	}


	// 첫 번째, 마지막 위치에 있는 패킷
	Packet& FirstPacket = ReceivePackets.front();
	cout << "첫 번째 패킷의 인덱스: " << FirstPacket.Index << endl;

	Packet& LastPacket = ReceivePackets.back();
	cout << "마지막 패킷의 인덱스: " << LastPacket.Index << endl;

	// at을 사용하여 두 번째 패킷
	Packet& PacketAt = ReceivePackets.at(1);
	cout << "두 번째 패킷의 인덱스: " << PacketAt.Index << endl;


	// 첫 번째 패킷 삭제
	ReceivePackets.pop_front();
	cout << "첫 번째 패킷의 인덱스: " << ReceivePackets[0].Index << endl;

	// 마지막패킷삭제
	ReceivePackets.pop_back();
	LastPacket = ReceivePackets.back();
	cout << "마지막 패킷의 인덱스: " << LastPacket.Index << endl;

	// 모든 패킷을 삭제
	if( false == ReceivePackets.empty() )
	{
		cout << "모든 패킷을 삭제합니다." << endl;
		ReceivePackets.clear();
	}
}

결과 

5.5.3.1. insert 멤버

deque의 insert는 vector의 insert와 사용 방법이 같습니다. 지정된 위치에 삽입, 지정된 위치에 지정된 개수만큼 삽입, 지정된 위치에 반복자 구간 안에 있는 것들을 삽입이 있습니다. vector와 같이 insert는 삽입 되는 위치 이후에는 있는 모든 원소들이 뒤로 이동을 합니다. 그리고 insert의 성능은 vector 보다도 더 좋지 않습니다.

원형 : iterator insert( iterator _Where, const Type& _Val );
      void insert( iterator _Where, size_type _Count, const Type& _Val );
      template void insert( iterator _Where, InputIterator _First, 
                                            InputIterator _Last );

 
[그림 6] deque의 insert 처리 과정 

지정한 위치에 데이터 삽입. 아래는 300을 첫 번째 위치에 삽입합니다.

deque< int >::iterator iterInsertPos = deque1.begin();
deque1.insert( iterInsertPos, 300 );

지정한 위치에 데이터를 횟수만큼 삽입. 아래는 두 번째 위치에 10을 3번 추가합니다.

iterInsertPos = deque1.begin();
++iterInsertPos;
deque1.insert( iterInsertPos, 3, 10 );

지정한 위치에 반복자의 시작과 끝 안에 있는 원소를 삽입. 아래는 두 번째 위치에 deque2의 처음과 끝에 있는 원소를 삽입합니다.

deque< int > deque2;
deuqe2.push_back( 20 );
deuqe2.push_back( 30 );
deuqe2.push_back( 40 );

iterInsertPos = deque1.begin();
deque1.insert( ++iterInsertPos, deque2.begin(),deque2.end() );

5.5.3.2. erase 멤버

지정한 위치에 있는 원소를 삭제, 지정한 범위 안에 있는 원소를 삭제합니다. vector와 사용법이 같고 또 erase를 하는 위치 이후의 모든 원소들이 앞으로 이동하는 것도 같습니다.

원형 : iterator erase( iterator _Where );
      iterator erase( iterator _First, iterator _Last );

 
[그림 7] deque의 erase 처리 과정 

지정한 위치의 요소를 삭제. 아래는 첫 번째 요소를 삭제하는 코드입니다.

deque1.erase( deque1.begin() );

지정한 반복자 구간 안의 원소를 삭제합니다. 아래는 deque1의 첫 번째 요소에서 마지막까지 모두 삭제합니다.

deque1.erase( deque1.begin(), deque1.end() );

아래는 insert와 erase 사용 예입니다. 

[리스트 2] Insert와 erase

#include 
#include 

using namespace std;


int main()
{
	Packet Pkt1;
	Pkt1.Index = 1;		Pkt1.BodySize = 10;

	Packet Pkt2;
	Pkt2.Index = 2;		Pkt2.BodySize = 12;

	Packet Pkt3;
	Pkt3.Index = 3;		Pkt3.BodySize = 14;

	Packet Pkt4;
	Pkt4.Index = 4;		Pkt4.BodySize = 16;

	deque< Packet > ReceivePackets;
	ReceivePackets.push_back( Pkt1 );
	ReceivePackets.push_back( Pkt2 );
	ReceivePackets.push_back( Pkt3 );

	cout << "< insert >" << endl;

	// 첫 번째 위치에 Pkt3을 삽입
	cout << "insert 1" << endl;
	ReceivePackets.insert( ReceivePackets.begin(), Pkt3 );

	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}

	// 두 번째 위치에 Pkt4를 2개 삽입
	cout << endl << "insert 2" << endl;
	ReceivePackets.insert( ++ReceivePackets.begin(), 2, Pkt4 );
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}


	deque< Packet > ReceivePackets2;
	ReceivePackets2.push_back( Pkt3 );
	ReceivePackets2.push_back( Pkt4 );
	ReceivePackets2.push_back( Pkt1 );

	// ReceivePackets2의 모든 것을 ReceivePackets의 첫 번째 위치에 삽입
	cout << endl << "insert 3" << endl;
	ReceivePackets.insert( ReceivePackets.begin(), ReceivePackets2.begin(), 
                                  ReceivePackets2.end() );
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}


	cout << endl << "< erase >" << endl;	
	// 두 번째 원소를 삭제한다.
	cout << "erase 1" << endl;
	ReceivePackets.erase( ++ReceivePackets.begin() );
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}

	// 두 번째 이후부터 모두 삭제한다.
	cout << endl << "erase 2" << endl;
	ReceivePackets.erase( ++ReceivePackets.begin(), ReceivePackets.end() );
	for( deque< Packet >::iterator iterPos = ReceivePackets.begin();
		iterPos != ReceivePackets.end();
		++iterPos )
	{
		cout << "패킷 인덱스: " << iterPos->Index;
		cout << "        패킷 바디 크기: " << iterPos->BodySize << endl;
	}
}

결과 

5.5.1.4 assign

vector의 assign과 같이 deque의 assign도 컨테이너를 특정 데이터로 채울 때 사용합니다. 특정 값이나 다른 deque의 특정 영역(반복자로 가리키는)에 있는 데이터로 채울 수 있습니다. assign을 사용하는 deque에 데이터가 있다면 이를 덮어쓰면서 채웁니다.

원형 : void assign( size_type _Count, const Type& _Val );
template void assign( InputIterator _First, InputIterator _Last );

 
[그림 8] deque의 assign 

지정 데이터를 지정 개수만큼 채웁니다. 숫자 7를 7개 채웁니다.

deque1.assign( 7, 7 );

다른 deque의 반복자로 지정한 영역으로 채웁니다.

deque1.erase( deque1.begin(), deque1.end() );

5.5.1.5 swap

deque1과 deque2가 있을 때 두 deque에 저장한 데이터를 서로 맞바꿀 때 사용합니다. swap 원형은 아래와 같습니다.

원형 : void swap( deque& _Right );
friend void swap( deque& _Left, deque& _Right )
template void swap(
       deque< Type, Allocator>& _Left, deque< Type, Allocator>& _Right );

deque A와 B를 swap하는 모습을 그림으로 나타내면 아래와 같습니다. 

 
[그림 9] deque의 swap 

아래는 deque1과 deque2를 swap하는 방법을 두 가지로 나타낸 코드입니다.

deque1.swap( deque2 );
swap(deque1, deque2 );

[리스트 3] assign, swap

#include 
#include 

using namespace std;

int main()
{
	deque< int > deque1;

	cout << "assign 1" << endl;
	deque1.assign( 7, 7 );
	for( deque< int >::iterator iterPos = deque1.begin();
		iterPos != deque1.end();
		++iterPos )
	{
		cout << "deque 1 : " << *iterPos << endl;
	}

	cout << endl << "assign 2" << endl;
	deque< int > deque2;
	deque2.assign( deque1.begin(), deque1.end() );
	for( deque< int >::iterator iterPos = deque2.begin();
		iterPos != deque2.end();
		++iterPos )
	{
		cout << "deque 2 : " << *iterPos << endl;
	}

	// swap
	deque< int > deque3;
	deque3.push_back(10);
	deque3.push_back(20);
	deque3.push_back(30);

	cout << endl << "swap" << endl;
	deque3.swap( deque1 );
	for( deque< int >::iterator iterPos = deque3.begin();
		iterPos != deque3.end();
		++iterPos )
	{
		cout << "deque 3 : " << *iterPos << endl;
	}

	for( deque< int >::iterator iterPos = deque1.begin();
		iterPos != deque1.end();
		++iterPos )
	{
		cout << "deque 1 : " << *iterPos << endl;
	}
}

결과 

 

deque에서 자주 사용하는 deque의 멤버를 중심으로 설명하였습니다. 여기에서 설명하지 않은 나머지 deque 멤버의 사용법은 여기(http://msdn.microsoft.com/en-us/library/8tk0b6f0.aspx)에서 참고해 주세요. 앞에서 여러 번 언급했듯이 deque 사용법이 이전 회의 vector와 거의 같습니다. 위 예제에서 deque를 vector로 바꾸어도 push_front를 제외하고는 문제없이 컴파일할 수 있습니다. deque와 vector는 사용법은 비슷하나 자료구조는 완전히 다릅니다. 앞과 끝에 데이터를 추가, 삭제하는 일이 대부분이라면 deque가 vector보다 좋지만, 그렇지 않다면 vector를 사용하는 쪽이 훨씬 더 좋습니다. STL 컨테이너는 사용이 어렵다기보다는 언제 어떤 STL 컨테이너를 사용해야 알맞은지 선택하기가 어렵습니다. STL 컨테이너를 올바른 장소에 사용하려면 컨테이너의 자료구조가 무엇인지 확실하게 알고 있어야 합니다. 만약 자료구조를 잘 모른다면 꼭 자료구조 공부를 STL 공부보다 먼저 해야 합니다.

5.6. 과제

1. deque를 사용하여 FIFO, LIFO 방식의 스택을 만들어 보세요. 

2. deque를 사용하여 Undo, Redo 구현해 보세요. 
간단한 예제로 deque의 원리만 익혀보는 과제입니다. Deque에 숫자를 저장하고 Undo를 하면 가장 마지막에 넣은 데이터를 빼고 Redo를 하면 뺀 데이터를 다시 넣습니다. deque를 2개 사용하면 횟수 제한이 없는 Undo, Redo를 구현할 수 있습니다.