출처: http://obori.new21.net

프로그래밍 커뮤니티 www.codein.co.kr (Code人)

 

1. 개요

 

컨테이너(container), 알고리즘(algorithm), 반복자(iterator) 이 3가지가 STL에서 가장 중요한 것들이다.

컨테이너(container)란 객체들을 담아둘 수 있는 객체를 말한다.

알고리즘(algorithm)을 컨테이너에 적용하기 위해서 필요한 것이 반복자(iterator)이다.

반복자는 컨테이너 내의 특정 위치를 가리키는 포인터와 비슷한 개념이라고 보면 되며,

이 반복자를 통해 컨테이너 내의 원소들을 다양한 방법으로 다루게 되는 것이다.

 

2. 반복자(iterator)

 

1. 개요

반복자(iterator)란, 컨테이너에 저장되어 있는 모든 원소들을 전체적으로 훑어나갈 때 사용하는,

일종의 포인터와 비슷한 객체라고 할 수 있다.

알고리즘마다 각기 다른 방식으로 컨테이너를 훑어가기 때문에, 반복자에도 여러가지 종류가 있다.

 

past-the-end 원소는, 범위(range)의 끝을 나타내며, 구간의 마지막 원소 다음에 위치한 원소를 지칭한다.

 

2. 반복자의 종류

표준 라이브러리에서 사용되는 반복자들은 기본적으로 다음 5가지 형태들로 나눌 수 있다.

입력 반복자(input iterator)	읽기만 가능, 순방향 이동
출력 반복자(output iterator)	쓰기만 가능, 순방향 이동
순방향 반복자(forward iterator)	읽기/쓰기 모두 가능, 순방향 이동
양방향 반복자(bidirectional iterator)	읽기/쓰기 모두 가능, 순방향/역방향 이동
임의 접근 반복자(random access iterator)	읽기/쓰기 모두 가능, 임의접근

 

반복자는 계층적으로 분류된다.

반복자 종류	생성되는 방식
입력 반복자(input iterator)	istream_iterator
출력 반복자(output iterator)	ostream_iterator / inserter / front_inserter / back_inserter
양방향 반복자(bidirectional iterator)	list / set과 multiset / map과 multimap
임의 접근 반복자(random access iterator)	일반 포인터 / vector / deque

 

2.1 입력 반복자(input iterator)

ex)        template <class InputIterator, class T>

            InputIterator find (InputIterator first, InputIterator last, const T& value)

            {

                        while (first != last && *first != value)

                                     ++first;

                        return first;

            }

 

입력 반복자에는 다음 세가지 종류가 있다.

① 일반 포인터

② 상수 포인터

③ 컨테이너 반복자(container iterator).

표준 라이브러리가 제공하는 다양한 컨테이너로부터 생성된 반복자들은, 모두 입력 반복자가 갖추어야 할 조건을 만족한다.

컬렉션의 첫번째 원소는 begin()이라는 멤버 함수를 통해서 얻을 수 있으며,

past-the-end를 가리키는 반복자는 end()라는 멤버 함수를 통해서 얻을 수 있다.

 

반복자를 지원하는 각각의 컨테이너들은 클래스 선언안에 반복자라는 이름을 가진 타입을 제공해야 한다.

만약에 접근하고자 하는 컨테이너가 상수이거나, const_iterator를 사용하여 선언하면, 그 반복자는 상수 반복자가 된다.

 

입력 스트림 반복자(input stream iterator).

표준 라이브러리는 입력 반복자를 사용하여 입력 스트림에 대해 작업을 할 수 있는 방법을 제공한다.

이는 istream_iterator 클래스를 통해 제공된다.

 

2.2 출력 반복자(output iterator)

출력 반복자(output iterator)는 입력 반복자와는 반대되는 기능을 가진다.

출력 반복자는 시퀀스에 값을 대입하는데 사용될 수 있지만, 값을 접근하는데는 사용될 수 없다.

ex)        template <class InputIterator, class OutputIterator>

            OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)

            {

                        while (first != last)

                                     *result++ = *first++;

                        return result;

            }

 

2.3 순방향 반복자(forward iterator)

순방향 반복자(forward iterator)는 입력 반복자와 출력 반복자의 특징을 결합한 것이다.

값을 접근하고 갱신하는 것이 가능하게 된 것이다.

ex)        template <class ForwardIterator, class T>

            void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)

            {

                        while (first != last) {

                                     if (*first == old_value)

                                                 *first = new_value;

                                     ++first;

                        }

            }

 

2.4 양방향 반복자(bidirectional iterator)

양방향 반복자(bidirectional iterator)는 순방향 반복자와 상당히 비슷하다.

다만, 양방향 반복자는 감소 연산자(--)를 지원하므로, 컨테이너내의 원소들을 순방향이나 역방향으로 이동하는 것이 허용된다.

ex)        template <class BidirectionalIterator, class OutputIterator>

            OutputIterator reverse_copy (BidirectionalIterator first,

                        BidirectionalIterator last, OutputIterator result)

            {

                        while (first != last)

                                     *result++ = *--last;

                        return result;

            }

 

2.5 임의접근 반복자(random access iterator)

임의접근 반복자(random access iterator)들은 첨자에 의한 접근이 가능하고,

다른 반복자와의 차를 구할 수 있고, 산술연산을 통해 값을 수정할 수 있는 등

기존의 일반 포인터가 했던 모든 것을 할 수 있다.

 

임의접근 반복자를 사용하는 알고리즘에는 정렬과 이진검색과 같은 연산등을 포함한다.

ex)        template <class RandomAccessIterator>

            void mixup(RandomAccessIterator first, RandomAccessIterator last)

            {

                        while (first < last) {

                                     iter_swap(first, first + randomInteger(last - first));

                                     ++first;

                        }

            }

 

2.6 역 반복자(reverse iterator)

역 반복자(reverse iterator)는 표준 반복자가 부여받은 순서와는 반대되는 순서로 값들을 접근한다.

즉, vector나 list에서 역 반복자는 마지막 원소를 맨 먼저 접근하고, 첫번째 원소를 맨 마지막에 접근한다.

set에서는 가장 큰 원소가 맨 먼저 얻어지고, 가장 작은 원소가 마지막에 접근된다.

엄격히 말해서, 역반복자는 새로운 종류의 반복자가 아니다.

 

list, set, map 타입은 역 양방향 반복자를 생성하는 멤버 함수를 한쌍 가지고 제공하고 있다.

rbegin()과 rend() 함수는 해당 컨테이너를 역순으로 훑는 반복자를 생성한다.

역 반복자에 대한 증가연산은 후퇴를 의미하고, 감소연산은 전진을 의미한다.

 

유사하게, vector와 deque 타입에서는 역 임의접근 반복자를 생성하는 멤버함수(rbegin()과 rend())를 가지고 있다.

뿐만아니라, 첨자와 덧셈 연산 역시 후퇴를 의미한다.

 

3. 스트림 반복자(stream iterator)

스트림 반복자는 반복자 연산을 이용하여 입력 또는 출력 스트림을 접근하는데

사용된다.

 

3.1 입력 스트림 반복자(input stream iterator)

표준 라이브러리는 입력 스트림을 입력 반복자로 변환하는 방식을 istream_iterator에 의해 제공한다.

선언할 때, 4개의 템플릿 인자가 필요한데,

원소의 타입, 스트림 문자의 타입, 문자 trait 타입, 그리고 원소간의 거리를 측정하는 타입이 필요하다.

마지막 2개는 디폴트로 char_traits와 ptrdiff_t를 가진다.

istream_iterator의 생성자로 들어가는 인자는 단 하나인데, 이는 접근할 스트림을 나타낸다.

 

입력 스트림 반복자에 대해 증가 연산자(++)가 적용될 때마다

스트림으로부터 새로운 값을 읽어(>> 연산자 사용) 저장한다. 이 값은 참조 연산자(*)를 사용하여 얻을 수 있다.

 

ex)        istream_iterator<int, char> intstream(cin), eof;

            istream_iterator<int, char>::iterator where =

                        find(intstream, eof, 7);

 

3.2 출력 스트림 반복자(output stream iterator)

출력 스트림 반복자(output stream iterator)는,

값들이 반복자로 대입될 때마다 >> 연산자를 사용하여 해당 출력 스트림으로 출력한다.

출력 스트림 반복자를 생성하기 위해서는 생성자의 인자로 출력 스트림을 지정해야 한다.

생성자의 생략 가능한 두번째 인자는 출력되는 값들 사이의 분리자로 사용될 문자열을 나타낸다.

 

ex)        copy(newdata.begin(), newdata.end(), ostream_iterator<int, char>(cout, " "));

 

4. 삽입 반복자(insert iterator)

삽입 반복자에는 3가지 형태가 있는데, 이들 모두 복사 연산을 삽입 연산으로 바꾸는데 사용된다.

가장 일반적인 형태로 inserter()가 있다.

inserter는 두개의 인자를 취하는데, 컨테이너와 컨테이너내의 반복자가 그것으로, 원소들을 컨테이너의 특정 위치로 복사한다.

front_inserter() 사용하여 얻어진 반복자는 해당 컨테이너의 앞쪽에 값들을 삽입한다.

back_inserter()를 통해 얻은 반복자는 해당 컨테이너의 뒤쪽에 값들을 삽입한다.

두가지 형태 모두 list와 deque와 함께 사용될 수 있으나, set과 vector에는 사용될 수 없다.

 

void main()

{

            int threeToOne[] = {3, 2, 1};

            int fourToSix[] = {4, 5, 6};

            int sevenToNine[] = {7, 8, 9};

 

            list<int> aList;

 

            copy(threeToOne, threeToOne+3, front_inserter(aList));          // first insert into the front

 

            copy(sevenToNine, sevenToNine+3, back_inserter(aList));        // then insert into the back

 

            // find the seven, and insert into middle

            list<int>::iterator seven = find(aList.begin(), aList.end(), 7);

            copy(fourToSix, fourToSix+3, inserter(aList, seven));

 

            // copy result to output

            copy(aList.begin(), aList.end(), ostream_iterator<int,char>(cout, " "));

            cout << endl;

}

 

5. 반복자 연산(iterator operation)

표준 라이브러리는 반복자를 다루는데 사용되는 두개의 함수를 제공한다.

advance() 함수는 하나의 반복자와 하나의 숫자값을 인자로 받아서, 반복자를 주어진 값만큼 이동시킨다.

 

            void advance(InputIterator& iter, Distance& n);

 

두번째 함수인 distance()는 두 반복자간의 거리를 반환한다.

 

            void distance(InputIterator first, InputIterator last, Distance& n);

 

3. 함수(function)와 조건자(predicate)

 

1. 함수(function)

표준 라이브러리에서 제공하는 알고리즘 중에는 함수를 인자로 요구하는 것들이 많다.

예를 들어, for_each(), transform() 알고리즘은 컨테이너에 담긴 각각의 원소에 인자로 넘겨받은 함수를 적용한다.

 

2. 조건자(predicate)

조건자(predicate)는 불값(true/false) 또는 정수값을 리턴하는 함수이다.

 

            bool isLeapYear(unsigned int year)   // 'year'가 윤년이면 참을 리턴한다.

            {

            int flag = false;

 

            if ((year % 4) == 0) {       // 4년마다 윤년이고,

                        flag = true;

                        if((year % 100) == 0) {     // 그중 100년마다 윤년이 아니고,

                                     flag = false;

                                     if((year % 400) == 0) {     // 그중 400년마다 윤년

                                                 flag = true;

                                     }

                        }

            }

            return flag;

            }

 

3. 함수 객체(function object)

함수 객체(function object)는 괄호 연산자를 멤버함수로 가지고 있는 클래스의 객체이다.

일반 함수 대신에 함수 객체를 사용하는 이유는 다음과 같다.

첫째, 새로운 함수를 만들지 않고 표준 라이브러리에서 제공되는 함수객체를 사용하고,

둘째, 인라인 함수를 호출함으로써 수행속도를 향상시키고자 하며,

마지막으로, 함수객체로 하여금 자신이 가지고 있는 상태정보를 접근하고, 갱신할 수 있도록 한다.

표준 라이브러리에서 제공되는 함수객체는 다음과 같다.

산술 함수(arithmetic function)

            plus(), minus(), multiplies(), divides(), modulus(), negate()        // +, -, *, /, %, ~

비교 함수(comparison function)

            equal_to(), not_equal_to(), greater(), less(), greater_equal(), less_equal()          // ==, !=, >, <, >=, <=

논리 함수(logical function)

            logical_and(), logical_or(), logical_not()         // &&, ||, !

 

4. 함수 어댑터(function adaptor)

함수 어댑터(function adaptor)는

함수를 함수객체로 사용할 수 있도록 전역함수 또는 멤버함수를 바꿔주는 클래스의 객체이다.

각각의 함수 어댑터는 전역 함수 또는 멤버 함수를 인자로 하는 생성자를 가지고 있다.

 

5. 부정자(negator)와 바인더(binder)

부정자(negator)와 바인더(binder)는

기존에 있던 함수 객체로부터 새로운 함수 객체를 만드는데 사용되는 함수 어댑터이다.

이들은 다른 함수나 generic 알고리즘을 호출하기에 앞서

인자 리스트를 구성하는 과정의 일부로 사용되는 것이 보통이다.

 

부정자 not1()와 not2()는 각각 단항과 이항 조건자 객체를 인자로 받아들여,

원래 값의 반대값을 내뱉는 새로운 함수 객체를 생성한다.

 

바인더는 두개의 인자를 가지는 함수를 받아서,

첫번째 인자나 두번째 인자를 특정 값으로 바인드시켜 한개의 인자를 가지는 함수를 만들어 낸다.

이 때, 바인더의 인자로 넘어오는 함수는 binary_function 클래스의 하위 클래스에 속해야 한다.

 

4. 컨테이너(container) 클래스

 

1. 개요

표준 라이브러리는 약 10가지 종류의 컨테이너를 제공한다.

이름	특징
vector	임의접근이 가능하며, 뒤에서의 삽입이 빠름
list	위치에 상관없이 삽입과 삭제가 빠름
deque	임의접근이 가능하며, 앞과 뒤에서의 삽입이 빠름
set	원소들을 순서대로 관리하며, 소속검사와 삽입,삭제가 빠름
multiset	중복을 허용하는 set
map	키를 통해 값을 접근하며, 삽입과 삭제가 빠름
multimap	중복키를 허용하는 map
stack	top 에서만 삽입과 삭제가 가능
queue	삽입은 뒤쪽에서, 삭제는 앞쪽에서
priority_queue	가장 큰값의 접근과 삭제가 빠름

 

 

2. 컨테이너 선택하기

1) 콜렉션내의 값들을 어떤 방식으로 접근하는가?

임의접근이 필요하다면, vector와 deque를 사용하라

 

2) 콜렉션내의 값들에 순서를 매길 것인가?

컨테이너가 유지되는 동안 계속 순서가 유지되어야 한다면, set을 선택해야 한다.

set에 삽입을 하면 자동적으로 순서에 맞게 놓여진다.

반면에, 순서가 어느 한시점에서만 중요시된다면, list나 vector에 값들을 삽입하고,

적절한 때에 해당 컨테이너를 정렬을 하는 것이 더 수월하다.

만약에 데이터구조 내에서 유지되는 값들의 순서가 삽입하는 순서에 관계가 있다면,

stack이나 queue또는 list가 최상의 선택이 될 것이다.

 

3) 실행중에 데이터 구조의 크기가 광범위하게 변하는가?

그렇다면, list나 set를 선택하는 것이 가장 좋다.

vector나 deque은 콜렉션으로부터 원소들을 제거한 뒤에도 커다란 버퍼를 계속 유지하고 있다.

만약에, 콜렉션의 크기가 상대적으로 고정되어 있다면, vector나 deque가

같은 수의 원소를 지니고 있는 list나 set보다는 적은 메모리를 사용한다.

 

4) 콜렉션의 크기를 추정할 수 있는가?

vector는 원하는 크기의 메모리 블럭을 미리 할당받을 수 있다(reserve() 멤버함수를 사용).

이는 다른 컨테이너에서는 제공되지 않은 기능이다.

 

5) 어떤 값이 콜렉션내에 포함되어 있는지를 자주 확인하는가?

만약에 그렇다면, set이나 map을 선택하는 것이 좋겠다.

set이나 map에서는 어떤 값이 컨테이너에 속해 있는지를 검사하는 것이 매우 빠르지만,

다른 종류의 콜렉션에서는 이를 검사하기 위해서 컨테이너에 저장된 모든 원소들을 일일이 비교해야 한다.

 

6) 콜렉션에 대해 인덱싱이 가능한가? 다시말해, 콜렉션을 키와 값의 쌍으로 생각할

수 있는가?

키들이 0과 어떤 상한선 사이의 정수값이라면, vector와 deque를 선택해야 한다.

반면에, 키값들이 어떤 순서가 있는 데이터형이라면(문자나 문자열 또는 사용자 정의 타입과 같은) map을 사용한다.

 

7) 값들간에 서로 연관성이 있는가?

표준 라이브러리가 제공하는 컨테이너에 속한 모든 값들이 다른 값과 같은지를 비교할 수 있어야 한다.

하지만, 모든 컨테이너가 less-than 연산자를 제공할 필요는 없다.

그러나, less-than 연산자를 사용해서는 순서가 유지될 수 없는 값들은 set이나 map에 저장하면 안된다.

 

8) 콜렉션으로부터 가장 큰 값을 찾아서 제거하는 연산이 자주 일어나는가?

그렇다면, priority_queue가 최선의 컨테이너이다.

 

9) 데이터 구조의 어느 위치로 값들이 삽입되고 제거되는가?

중간쯤에서 값들이 삽입되고 제거된다면, list가 최선의 선택이다.

값들이 앞쪽에만 삽입된다면, deque나 list가 더 좋겠고,

끝에서만 삽입과 삭제가 이루어진다면, stack이나 queue가 좋을 것이다.

 

10) 두개 이상의 수열을 하나로 합치는 일이 자주 일어나는 연산인가?

그렇다면, set이나 list가 좋은 선택이 될 것이다.

이 둘 중에 어느 것을 선택할 지는 순서가 유지되는가의 여부에 따라 결정하면 된다.

두 개의 set을 합치는 것은 매우 효율적인 연산이다.

콜렉션의 순서가 유지되지 않고, list가 제공하는 효율적인 splice() 멤버함수를 사용하면,

list를 선택하는 것이 좋겠다. 왜냐하면, 이 연산은 다른 컨테이너에서는 제공하지 않는 연산이기 때문이다.

 

3. STL에 없는 컨테이너 타입들

전통적으로 많이 사용되고 있는 컨테이너 타입들 중 표준 라이브러리에는 들어 있지 않은 것들이 꽤 있다.

그 이유는 대부분의 경우, 이미 제공된 컨테이너들을 적절하게 이용하면

보다 아주 광범위한 용도로 다양하게 사용될 수 있기 때문이다.

 

우선 tree 콜렉션이 없다. 그러나, set 타입은 내부적으로 이진 검색트리의 형태를 사용하여 구현되어 있다.

다차원 배열도 없다. 그러나, vector를 원소로 가지는 vector로 만들어 낼 수 있다.

그래프가 없다. 그렇지만, graph에 대한 표현은 다른 맵을 원소로 하는 맵으로 만들어 낼 수 있다.

sparse 배열도 없다. 이 문제에 대한 해결책은 graph 표현방식이 될 수 있겠다.

해쉬 테이블도 없다. 그러나, 해쉬 테이블은 list나 set을 원소로 하는 vector나 deque로 만들어낼 수 있다.

 

5. vector

 

1. vector 개요

vector 컨테이너 클래스는 기존 C 배열의 개념을 일반화시킨 것이다.

배열과 마찬가지로, vector도 첨자에 의한 접근이 가능하다.

배열과 vector는 다음과 같은 차이점을 가지고 있다.

-> vector의 크기는 동적으로 변할 수 있다. 새로운 원소를 vector의 끝이나 중간에 삽입할 수 있다.

            메모리 관리는 효율적이고 자동적으로 다루어진다.

            그러나, vector 중간에 원소를 삽입할 때는 list처럼 효율적이지 않다는 점에 주목해야 한다.

            많은 삽입 연산을 수행한다면, vector대신에 list를 사용하는 것이 좋다.

 

vector와 deque 모두 인덱싱이 가능한 자료구조이다.

이 둘의 가장 큰 차이점은 deque은 컨테이너의 앞과 끝에서의 삽입이 효율적인 반면에,

vector에서는 끝에서 삽입할 때만 효율적이라는 것이다.

일반적으로 vector를 사용하는 것이 좀더 작은 실행화일을 만들 수 있는 반면에,

deque은 수행되는 연산의 종류에 따라 조금 빠른 프로그램을 만들기도 한다.

 

vector를 사용하려면 vector 헤더화일을 포함시켜야 한다.

            #include <vector>

 

2. vector가 제공하는 함수들

1) 벡터의 선언과 초기화

vector는 템플릿 클래스이므로 원소의 타입을 명시해주어야 한다.

            ex) vector<int> vec_one(10);

 

2) 타입 정의

            ex) vector<int>::iterator location;

 

3) 함수들...

assign()

swap()

at() : 첨자 연산자와 동일한 인자를 가지고 동일한 값을 반환한다.

front() : vector의 맨 앞에 있는 원소를 반환

back() : 맨 마지막 원소를 반환

 

size() : 현재 vector가 가지고 있는 원소의 갯수

capacity() : 새로운 메모리 할당없이 vector가 확장될 수 있는 최대 사이즈

max_size() : vector가 가질 수 있는 사이즈의 상한선

reserve()

empty()

resize()

push_back(), pop_back(), insert(), erase()

begin(), end(), rbegin(), rend()

find(), count()

sort(), merge()

 

cf) 유용한 generic 알고리즘들

이름	용도
fill	주어진 초기값으로 벡터를 채운다.
copy	수열을 복사한다.
generate	발생기(generator)가 생성한 값을 벡터에 집어넣는다.
find	조건을 만족하는 원소를 찾는다.
adjacent_find	연속적으로 중복된 원소를 찾는다.
search	벡터내에서 서브 시퀀스를 찾는다.
max_element, min_element	최대 또는 최소 원소를 찾는다.
reverse	원소의 순서를 뒤집는다.
replace	원소들을 새로운 값들로 대치한다.
rotate	가운데점을 중심으로 원소들을 순환시킨다.
partition	원소들을 두그룹으로 쪼갠다.
next_permutation	순열(permutation)을 생성한다.
inplace_merge	벡터내에서의 합병?
random_shuffle	벡터내의 원소들을 임의로 섞는다.
count	조건을 만족하는 원소들의 갯수를 센다.
accumulate	벡터로부터의 정보를 가지고 하나의 값을 만들어 낸다.
inner_product	두 벡터의 내적을 구한다.
equal	두벡터를 한쌍씩 비교하여 같은지를 검사한다.
lexicographical_compare	사전식 비교
transform	벡터에 변환을 적용한다.
partial_sum	값들의 부분합을 구한다.
adjacent_difference	이웃하는 값들의 차를 구한다.
for_each	각 원소들에 대해 함수를 수행한다.

 

 

3. vector<bool>

flip() : 호출되었을 때, 이 함수는 벡터의 모든 비트를 뒤집는다.

swap()

 

6. list

 

1. list 개요

list는 앞쪽과 뒷쪽에서 새로운 값을 삽입하거나 삭제할 수 있으며,

반복자로 위치를 지정하여 list의 중간에서도 원소들을 추가하거나 삭제할 수 있다.

list는 선형 구조이다. list의 원소들은 첨자에 의해서는 접근이 불가능하고,

원소들을 접근하려면 모든 값들을 선형적으로 순회해야 한다.

 

list를 사용할 때는 반드시 list 헤더 화일을 포함해야 한다.

            #include <list>

 

2. list 가 제공하는 함수들

1) list의 선언과 초기화

            ex) list<int> list_one;

 

2) 타입 정의

            ex) list<int>::iterator location;

 

3) 함수들...

push_back(), push_front(), insert(), splice(), merge(), splice()

pop_front(), pop_back(), erase(), remove(), remove_if(), unique()

front(), back(), begin(), end(), rbegin(), rend()

size(), empty(), resize()

sort()

 

7. stack과 queue

 

1. 개요

stack의 예로는, 책상위에 놓은 서류철이나 찬장에 놓인 접시들이 있다.

즉, stack에서 제거되는 아이템은 가장 최근에 stack에 추가된 아이템이다.

한편, queue의 예로 은행에 선 줄이나 영화관 앞에 선 줄을 들 수 있다.

여기서 삽입은 queue의 뒤에서 이루어지고(사람이 새로 줄을 설 때처럼),

아이템의 삭제는 queue의 앞에서 이루어진다(관객이 영화관에 들어가는 것처럼).

queue에서의 삭제순서는 stack과는 반대이다.

queue에서는 삭제된 아이템이 queue에 가장 오랫동안 있었던 원소이다.

표준 라이브러리에서는 stack과 queue가 모두 어댑터(adaptor)이고,

이들은 실질적으로 값을 저장하는데 사용하는 컨테이너를 바탕으로 만들어진다.

stack은 vector, list, deque으로부터 만들어지고, queue는 list나 deque으로부터 만들어진다.

 

2. stack 개요

stack은 다음 연산들을 구현한 객체로 정의되어 있다.

empty()           stack이 비었으면 참(true)을 반환

size()            stack에 담긴 원소의 갯수를 반환

top()             stack의 맨 위에 위치한 원소를 반환(지우지는 않는다)

push(newElement)  stack의 맨 위에 원소를 새로 추가

pop()             stack의 맨 위에 위치한 원소를 삭제(반환하지는 않는다)

 

front 원소를 접근하는 연산과 삭제하는 연산은 별도의 연산으로 제공된다는 점을 명심해야 한다.

stack을 사용하는 프로그램은 stack을 밑받침하고 있는 컨테이너 타입(예를 들면, vector)에 대한 헤더 화일 뿐만아니라

stack 헤더화일을 포함해야 한다.

            #include <stack>

            #include <vector>

 

3. stack의 선언과 초기화

stack의 선언은 두개의 인자를 명시해야 한다.

하나는 stack이 담게될 원소의 타입이고, 나머지 하나는 원소들을 담는데 사용할 컨테이너이다.

stack은 컨테이너로 vector나 deque를 가장 많이 쓰고, list도 컨테이너로 사용할 수 있다.

deque를 사용하면 좀 더 빠르고, vector를 사용하면 크기가 좀 작아진다.

            stack<int, vector<int> > stackOne;

            stack<double, deque<double> > stackTwo;

            stack<Part*, list<Part* > > stackThree;

 

4. queue 개요

queue는 일반적으로 다음 연산들을 구현한 객체로서 정의된다.

empty()           queue가 비었으면 참(true)을 반환

size()            queue에 담긴 원소의 갯수를 반환

front()           queue의 맨 앞에 위치한 원소를 반환(삭제하지 않는다)

back()            queue의 맨 뒤에 위치한 원소를 반환

push(newElement)  queue의 맨 뒤에 원소를 새로 추가

pop()             queue의 맨 앞에 위치한 원소를 삭제(반환하지 않는다)

 

queue의 맨앞에 위치한 원소를 접근하는 연산과 삭제하는 연산은 별도의 연산으로 수행된다는 점을 주의해야 한다.

queue는 반복자를 구현하지 않기 때문에, generic 알고리즘들은 queue에 적용할 수 없다.

queue를 사용하는 프로그램은 queue의 컨테이너 타입(예를 들어, list)에 대한 헤더파일뿐만 아니라,

queue 화일을 포함해야 한다.

            #include <queue>

            #include <list>

 

5. queue의 선언과 초기화

queue에 대한 선언은 값을 담고 있는 컨테이너와 원소 타입을 명시해야 한다.

queue는 컨테이너 타입으로 list나 deque를 가장 많이 사용한다.

list를 사용하면 코드가 작아지는 반면에, deque를 사용하면 코드가 좀 빨라진다.

다음은 queue를 선언하는 예이다.

            queue<int, list<int> > queueOne;

            queue<double, deque<double> > queueTwo;

            queue<Part*, list<Part* > > queueThree;