STL 컨테이너 - List

멤버 함수

• 생성자 : 리스트를 생성한다.
• 소멸자 : 리스트를 소멸한다.
• operator= : 리스트의 내용을 복사한다.

반복자

• begin : 시작 부분 (첫번째 원소) 을 가리키는 반복자를 리턴한다.
• end : 끝 부분 (마지막 원소 바로 다음) 을 가리키는 반복자를 리턴한다.
• rbegin : 역순으로 첫번째 (즉, 마지막 원소) 를 가리키는 반복자를 리턴한다.
• rend : 역순으로 끝 부분 (즉, 첫번째 원소 바로 이전) 을 가리키는 반복자를 리턴한다.

할당 관련

• size : 리스트의 size 를 리턴한다 (현재 원소의 개수)
• max_size : 리스트 최대 크기를 리턴한다.
• resize : 리스트가 size 개의 원소를 포함하도록 변경한다.
• empty : 리스트가 비었는지 체크한다.

임의 접근

• front : 첫번째 원소에 접근한다.
• back : 마지막 원소에 접근한다.

수정자 (Modifier)

• assign : 리스트에 원소를 집어넣는다.
• push_back : 리스트 끝에 원소를 집어 넣는다.
• push_front : 리스트 맨 앞에 원소를 집어 넣는다.
• pop_back : 마지막 원소를 제거한다.
• pop_front : 첫번째 원소를 제거한다.
• insert : 리스트 중간에 원소를 추가한다.
• erase : 원소를 제거한다.
• swap : 다른 리스트와 원소를 바꿔치기 한다.
• clear : 원소를 모두 제거한다.

특별한 작업들

• splice : 리스트와 리스트 사이에서 원소를 이동한다.
• remove : 특정 값을 지닌 원소를 삭제한다.
• remove_if : 특정 조건을 만족시 원소를 삭제한다.
• unique : 중복된 값을 삭제한다.
• merge : 정렬된 리스트를 합친다.
• sort : 컨테이너의 원소를 정렬한다.
• reverse : 원소들의 순서를 거꾸로 뒤집는다.

할당자

• get_allocator : 할당자(allocator) 을 얻는다.

벡터와의 차이점

인덱스 기반으로 자료에 접근하는 것이 불가능하다. 반드시 이터레이터를 활용해 for문으로 자료에 접근해야 함.

 

벡터의 경우 기존에 할당된 메모리 이상으로 자료를 넣으면 메모리를 재할당하고 모든 값을 복사해야 하므로 시간 소요가 클 확률이 존재함. 리스트는 이중 연결 리스트로 구현되어 있으므로 추가할 메모리를 할당하고 해당 포인터를 가리켜 준 다음 값만 삽입하면 끝. (O(1)로 삽입 가능)

 

벡터에 비해 단점이라고 한다면 해당 노드 자기 자신의 앞에 해당하는 포인터와 뒤에 해당하는 포인터를 갖고 있어야 해서 메모리 낭비가 심할 수 있음.