Jisang Yoo 님이 쓰신 글 :
: STL에 있는 수많은 Data structure 들 중에
: 어떤 pointer들을 안에 저장하고 있는 리스트 비슷한 것으로,
: 아래의 설명을 만족하는 structure가 무엇인가요?(STL에서 그러한 데이타스트럭쳐를 구현한 클레스의 이름이 무엇인가요?)
:
: 1. push와 pop동작을 지원한다.
: 3. pop()은 그 안에서 포함된 포인터 하나를 제거한 후 그 포인터를 리턴하는 것, 즉 , 포인터 하나를 밖으로 빼내는 동작을 하되, 어떤 순서로 빼낸다는 것에 대한 제약상황은 (구하는 자가) 상관하지 않는다. 즉, 처음 들어간 것이 먼저 나오는 스트럭쳐여도 괜찮고, 늦게 들어간게 먼저 나오는 것이여도 괜찮고, 무작위로 나오는 것이라도 괜찮다. 그러나, pop의 time-complexity는 log N 이하이어야 한다. (N은 안에 저장된 포인터의 갯수)
: 2. push(i)는 포인터 i를 그 안에 넣는 동작을 하되, 그 안에 이미 같은 포인터(주소가 같은 포인터)가 들어있을 경우에는 넣지 않는다. push는 (이미 같은 포인터가 있는지를 확인하는 과정을 포함함에도 불구하고) time complexity가 log N 이하이다.

이러한 자료구조를 우선순위 큐(priority queue) 또는 힙(heap)이라고 합니다.
힙에 대한 설명은 다음을 참고하시고요.
http://www.borlandforum.com/impboard/impboard.dll?action=read&db=cpp_tip&no=21

이러한 힙 연산 알고리듬을 사용하여,
우선순위 큐로서의 기능을 편리하게 사용할 수 있게 하는
컨테이너 어댑터(container adaptor)로 priority_queue가 있습니다.
컨테이너 어댑터에 대한 설명은 다음을 참고하세요.
http://www.borlandforum.com/impboard/impboard.dll?action=read&db=cpp_tip&no=4

가장 핵심 문단만 인용하죠.
--------------------------------------------------------------------------------------
stack<int>, queue<int>, priority_queue<int> 라고 쓰면
다음과 같이 deque를 사용해서 구현한 스택, 큐, 우선순위 큐가 만들어집니다.
stack<int, deque<int> >, queue<int, deque<int> >, priority_queue<int, deque<int> >
내부의 자료구조를 vector나 list로 바꾸고 싶으면
stack<int, vector<int> >, queue<int, vector<int> >, priority_queue<int, vector<int> >
stack<int, list<int> >, queue<int, list<int> >, priority_queue<int, list<int> >
--------------------------------------------------------------------------------------

STL 컨테이너에서는 포인터를 다루실 때 주의하셔야 합니다.
"new로 생성한 포인터의 컨테이너를 사용할 때는, 컨테이너가 소멸되기 전에 포인터를 delete하는 것을 잊지 마셔야 합니다."('Effective STL'의 Item 7에서)
이렇게 수동으로 delete하지 않고 자동으로 삭제되게 하려면,
따로 Boost C++ Library의 shared_ptr과 같은 스마트 포인터(smart pointer) 라이브러리를 사용해야 합니다.