리스트(list) 컨테이너는 이중 연결 리스트를 템플릿으로 추상화한 버전이다. 동일한 자료의 집합을 관리한다는 용도면에서는 벡터와 같고 실제로 서로 대체도 가능하다. 용도가 같기 때문에 인터페이스도 거의 유사하다. 생성자는 완전히 똑같고 삽입, 삭제 등 주요 멤버 함수의 원형도 벡터와 일치하며 대입, 비교 등의 연산자도 동일하게 제공된다.
제공하는 내부 타입도 value_type, iterator, reference 등 이름이 동일하다. 물론 두 컨테이너의 내부 구조가 판이하게 다르므로 이 타입들의 실제 구현은 상당히 다르다. 벡터의 반복자는 요소를 직접 가리키는 포인터로 되어 있을 것이고 리스트의 반복자는 링크를 가리키는 포인터로 구현되어 있을 것이다. 내부 구현이 다르더라도 인터페이스가 동일하므로 사용하는 방법은 동일하다.
두 컨테이너를 비슷한 방법으로 사용할 수 있지만 차이점도 역시 존재하는데 각각의 장단점을 잘 파악해야 실무에 필요한 컨테이너를 지혜롭게 선택할 수 있다. 다음은 벡터와 리스트 컨테이너의 주요 차이점인데 내부 구조가 다름으로 인해 성능이나 제공하는 기능 목록에서 약간의 차이가 있다.
① 가장 큰 차이점은 반복자의 레벨인데 벡터는 요소들이 인접해 있으므로 임의 접근이 가능하지만 리스트는 노드들이 흩어져 있으므로 양방향으로만 이동할 수 있을 뿐이다. 반복자가 +n 연산을 지원하지 않으므로 순서값으로 요소를 액세스하는 [ ] 연산자를 지원하지 않으며 at 함수도 당연히 지원되지 않는다. 임의 위치를 상수 시간에 액세스할 수 없으며 반드시 순회를 해야만 원하는 요소를 찾을 수 있다. 임의 접근 반복자를 요구하는 sort나 binary_search 알고리즘은 리스트에는 사용할 수 없다.
② 각 요소들이 노드로 할당되어 링크에 의해 논리적으로 연결되어 있으므로 링크만 조작해서 삽입, 삭제를 수행할 수 있다. 요소들이 인접하지 않아도 상관없어 삽입, 삭제시에 메모리 이동을 할 필요가 없으며 그래서 위치에 상관없이 상수 시간내에 삽입, 삭제를 할 수 있다. 제일 앞에 요소를 삽입, 삭제하는 push_front, pop_front 멤버 함수도 제공된다. 이에 비해 벡터는 중간에서 삽입, 삭제할 때 요소들을 밀고 당겨야 하므로 속도가 다소 느리다. 속도 희생없이 언제든지 크기를 늘리거나 줄일 수 있으므로 처음부터 미리 크기를 결정할 필요가 없으며 capacity, reserve도 불필요하다.
③ 링크 구조로 인해 메모리 소모량은 벡터보다 훨씬 더 많다. 요소를 저장하는 노드는 무조건 동적 할당해야 하며 요소간의 순서를 기억하기 위한 링크도 별도의 메모리를 소모한다. 게다가 삽입, 삭제시마다 노드를 할당, 해제하는 과정을 계속 반복하므로 메모리 단편화도 심해 시스템의 메모리 관리 능력에도 좋지 않은 영향을 미친다.
④ 삽입, 삭제에 의해 요소들의 물리적인 위치가 바뀌지 않으므로 반복자가 무효화되지 않는다. 반복자가 무효화되는 유일한 경우는 반복자가 가리키는 대상을 삭제했을 때 뿐인데 요소가 완전히 사라졌으므로 이때는 어쩔 수 없다.
두 컨테이너의 모든 차이점은 요소 인접 구조과 링크 방식의 차이점에 기인한다. 이 둘의 차이점을 요약하자면 벡터는 읽기에 강하고 리스트는 쓰기에 강한 컨테이너라고 정리할 수 있다. 읽기 속도가 중요하면 벡터를 선택하는 것이 좋고 삽입, 삭제가 아주 빈번하다면 리스트가 더 나은 선택이다.
그럼, 이제 리스트의 생성자부터 연구해 보자. 리스트의 생성자는 모두 4개 제공되는데 벡터의 생성자와 원형이 동일하다. 똑같은 목적에 사용하는 컨테이너이므로 생성하는 방법부터 같을 수밖에 없다. 잘 사용되지 않는 할당기 인수는 원형에서 생략했다.
explicit list();
explicit list(size_type n, const T& v = T());
list(const list& x);
list(const_iterator first, const_iterator last);
각각 디폴트 생성자, v값 n개를 가지는 생성자, 복사 생성자, 구간 복사 생성자이다. 리스트는 실행중에 크기를 얼마든지 늘릴 수 있으므로 통상 빈 리스트로 생성하는 디폴트 생성자를 사용한다. 리스트에 요소를 삽입, 삭제할 때 push(pop)_front(back) 함수를 사용하는데 양끝에서 자유롭게 요소를 첨삭할 수 있으며 링크만 조작하면 되므로 속도도 아주 빠르다. 다음 예제는 정수형의 빈 리스트를 만들고 앞 뒤에서 요소들을 추가한다.
|
예 제 : listcon |
#include <iostream>
#include <list>
using namespace std;
void main()
{
list<int> li;
list<int>::iterator it;
li.push_back(8);
li.push_back(9);
li.push_front(2);
li.push_front(1);
for (it=li.begin();it!=li.end();it++) {
printf("%d\n",*it);
}
}
리스트는 list 헤더 파일에 정의되어 있으므로 이 헤더 파일을 반드시 인클루드해야 한다. 반복자로 리스트를 처음부터 끝까지 순회하면서 요소값을 출력해 보았다.
1
2
8
9
물론 잘 출력된다. push_back으로 추가한 것은 뒤쪽에 붙고 push_front로 넣은 것은 앞쪽에 붙는다.