김상구.패패루 님이 쓰신 글 :
: 백일님 답변을 읽다가 갑자기 전에 했던게 생각이 나서 그러는데요..

흠... 어떤 답글이었죠? 기억이 안나네요. -_-;;

: 예전에 queue를 써야 할 일이 있었습니다.
: 그러니깐.. push_back과 pop_front가 빈번하게 일어나는 구조인데요, 크기가 고정되어 있지 않는 큐가 필요했기 때문에 순환구조는 쓸 수 없는.. 그런 상황에서 STL의 list를 써 보기로 했습니다.
제가 알기로 list는 Double Linked List 구조라고 생각했기 때문에..

queue를 구현하기 위해 굳이 list를 쓰실 필요는 없습니다.
(내부에서) 포인터 조작이 필요없는 deque(덱)을 써서 구현하는 편이 더 빠릅니다
(물론 크기 제한은 없습니다.).
그리고 STL에는 stack, queue, priority_queue가 이미 존재합니다.
기존 STL 컨테이너인 vector, deque, list에 어댑터 형식으로 사용하는
컨테이너 어댑터 클래스들입니다. 제가 올렸던 다음 글을 참고하세요.
http://www.borlandforum.com/impboard/impboard.dll?action=read&db=cpp_tip&no=4

: 그리고 평범한 Double Linked List를 하나 구현해서 두가지를 비교해본 적이 있었습니다. 수만개를 뒤쪽에 추가한 뒤 앞에서부터 하나씩 빼 내는 루틴을 만들어 비교를 해 보니 예상과는 달리 두가지의 성능차이가 너무 크게 나더군요.
:
: 자세한 테스트 결과는 저도 오래돼서 기억은 안납니다만.. 상식적인 비교에서 너무 차이가 많이 나서 결국 list를 포기하고 직접 구현한 Linked List구조를 썼던 걸로 기억하는데 혹시 원인이 뭔지 아시면 좀 답변을 부탁 드립니다.

정확히는 모르겠고요, list는 아무래도 손으로 구현한 이중 연결 리스트보다는
지원하는 기능이 많으므로 오버헤드가 있을 겁니다.
그리고, 빌더 5까지의 오래된 Rogue Wave판 STL보다는
빌더6의 STLport가 성능이 더 좋습니다. 다시 한번 테스트해보세요.
또한 STLport는 이중 연결 리스트 list뿐만 아니라,
단일 연결 리스트(singly linked list)인 slist(비표준 컨테이너)를 지원합니다.
리스트의 맨 앞(begin)과 맨 뒤(end)에서의 삽입/삭제는 list보다 빠르지만,
리스트 중간에 삽입할 때는 list보다 느립니다.
작업의 성격에 따라 선택하시면 됩니다.