[C++] std::list

개요

C++에서는 동적 크기를 갖는 배열로 표준 라이브러리의 list를 사용할 수 있습니다.

list<int> li { 1, 2, 3, 4, 5 };

list는 std::vector와 매우 비슷하지만, 내부 구현 방식과 특성이 다르기 때문에 상황에 맞게 적절한 컨테이너를 사용해야 합니다.

특징

동적 컨테이너 크기
- 요소를 추가하거나 삭제할 때 컨테이너의 크기가 자동으로 조절됩니다.
이중 연결 리스트 (Double-linked List)
- 각 요소는 실제 데이터, 이전 및 다음 데이터에 대한 포인터를 갖는 노드로 구성됩니다.
- 빠른 양방향 순회
  - 각 노드가 이전 및 다음 데이터에 대한 포인터를 갖고 있으므로, 빠른 양방향 순회가 가능합니다.
- 빠른 삽입 및 삭제
  - std::vector에 비해 빠른 요소 삽입 및 삭제가 가능합니다.
  - 삽입 및 삭제하는 속도 자체는 빠르나, 컨테이너 중간에 값을 삽입 및 삭제할 때 iterator를 통해 순회해야 하므로 순회 시간이 추가로 걸릴 수 있습니다.
- 인덱스를 이용한 접근 지양
  - 실제 데이터는 메모리에 불연속적으로 저장되어 임의 인덱스 접근이 불가하고 std::vector에 비해 인덱스로 접근하는 속도가 느립니다.
  - 인덱스로 접근하기 위해서는 첫 요소부터 해당 인덱스 수 만큼 거쳐서 접근해야 합니다. (또는 순회하는 방법이 있음)
추가적인 메모리 오버헤드
- 각 노드가 두 개의 포인터를 가지므로 std::vector에 비해 추가적인 메모리를 사용합니다.

#include <list>

list를 사용하기 위해서 다음과 같이 <list> 헤더를 포함해야 합니다.

선언 및 초기화

템플릿 매개변수

list<_Ty, _Alloc = allocator<_Ty>> li;

list의 타입을 선언할 때, 최대 2개의 템플릿 매개변수를 받습니다.

_Ty은 실제 데이터의 형식을 나타냅니다.
_Alloc은 할당자(Allocator)를 나타내며 지정하지 않으면 기본 할당자가 사용됩니다.

생성자

list<int> li { 1, 2, 3, 4, 5 }; // 컨테이너는 { 1, 2, 3, 4, 5 }로 초기화

list를 선언과 동시에 초기화하기 위해서 중괄호를 이용해 컨테이너의 초기 요소들을 설정할 수 있습니다.

크기와 초기값 지정

list<_Ty> li(_Count, _Value);

list의 크기와 초기값을 설정합니다.

_Count는 컨테이너의 크기를 나타냅니다.
_Value는 요소의 초기값을 나타냅니다.

iterator 복사

list<_Ty> li(_First, _Last);

다른 컨테이너의 iterator를 이용하여 요소를 복사합니다.

_First는 복사할 컨테이너의 첫 iterator를 나타냅니다.
_Last는 복사할 컨테이너의 마지막 iterator를 나타냅니다.

list 복사

list<_Ty> li(_Right);

다른 list를 복사하여 새로운 list를 생성합니다.

_Right는 복사할 list를 나타냅니다.

주요 함수

size()

list<int> li { 1, 2, 3, 4, 5, 6 };
size_t s = li.size(); // 6을 반환합니다.

list의 크기를 반환합니다.

empty()

list<int> li { 1, 2, 3, 4, 5, 6 };
bool is_empty = li.empty(); // false를 반환합니다.

list가 비어있는지 여부(크기가 0이면 true, 그렇지 않으면 false)를 반환합니다.

front()

list<int> li { 1, 2, 3, 4, 5, 6 };
int f = li.front(); // 1을 반환합니다.

list에서 첫 번째 요소의 값을 반환합니다.

back()

list<int> li { 1, 2, 3, 4, 5, 6 };
int b = li.back();

list에서 마지막 요소의 값을 반환합니다.

begin()

list<int> li { 1, 2, 3, 4, 5, 6 };
auto it = li.begin();

list에서 첫 번째 요소의 iterator를 반환합니다.

end()

list<int> li { 1, 2, 3, 4, 5, 6 };
auto it = li.end();

list에서 마지막 요소의 iterator를 반환합니다.

push_front(value)

list<int> li { 1, 2, 3, 4, 5, 6 };
li.push_front(0); // 컨테이너는 { 0, 1, 2, 3, 4, 5, 6 } 상태임

list의 가장 앞에 요소를 추가합니다.

push_back(value)

list<int> li { 1, 2, 3, 4, 5, 6 };
li.push_back(7); // 컨테이너는 { 1, 2, 3, 4, 5, 6, 7 } 상태임

list의 가장 뒤에 요소를 추가합니다.

pop_front()

list<int> li { 1, 2, 3, 4, 5, 6 };
li.pop_front(); // 컨테이너는 { 2, 3, 4, 5, 6 } 상태임

list의 첫 번째 요소를 제거합니다.

pop_back()

list<int> li { 1, 2, 3, 4, 5, 6 };
li.pop_back(); // 컨테이너는 { 1, 2, 3, 4, 5 } 상태임

list의 마지막 요소를 제거합니다.

insert(pos, value)

list<int> li { 1, 2, 3, 4, 5, 6 };
for (auto it = li.begin(); it != li.end(); it++)
{
	if (*it == 3) // 값이 3이라면
	{
		li.insert(it, 0); // 그 자리에 0을 삽입
		break;
	}
}
// 컨테이너는 { 1, 2, 0, 3, 4, 5, 6 } 상태임

list에서 특정 위치의 값을 삽입합니다. (list는 임의 인덱스에 접근할 수 없으므로 순회를 통해 특정 위치를 찾아야 합니다.)

pos는 값을 넣을 위치의 iterator를 나타냅니다.

erase(pos)

list<int> li { 1, 2, 3, 4, 5, 6 };
for (auto it = li.begin(); it != li.end(); it++)
{
	if (*it == 3)
	{
		li.erase(it);
		break;
	}
}

list에서 특정 위치의 값을 삭제합니다. (list는 임의 인덱스에 접근할 수 없으므로 순회를 통해 특정 위치를 찾아야 합니다.)

pos는 값을 삭제할 위치의 iterator를 나타냅니다.

clear()

list<int> li { 1, 2, 3, 4, 5, 6 };
li.clear(); // 컨테이너는 { } 상태임

list의 모든 요소를 삭제합니다.

sort()

list<int> li { 6, 5, 4, 3, 2, 1 };
li.sort(); // 컨테이너는 { 1, 2, 3, 4, 5, 6 } 상태임

list의 요소를 오름차순 정렬합니다.

reverse()

list<int> li { 1, 2, 3, 4, 5, 6 };
li.reverse(); // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태임

list의 요소 순서를 반대로 뒤집습니다.

resize(count)

list<int> li { 1, 2, 3, 4, 5, 6 };
li.resize(4); // 컨테이너는 { 1, 2, 3, 4 } 상태임

list의 크기를 변경합니다.

원래 크기보다 커지면 요소가 list의 뒤에 추가되고, 작아지면 그만큼 list의 뒷 요소를 삭제합니다.

swap(list)

list<int> li1 {  1,  2,  3,  4,  5,  6 };
list<int> li2 { 11, 22, 33, 44, 55, 66 };
li1.swap(li2);
// li1 컨테이너는 { 11, 22, 33, 44, 55, 66 } 상태임
// li2 컨테이너는 {  1,  2,  3,  4,  5,  6 } 상태임

list의 모든 요소를 교환합니다.

개요

특징