[Algorithm] STL 리스트(List)

리스트

리스트는 요소들을 양방향 연결리스트의 형태로 관리한다.

리스트를 사용하기 위해서는 <list>를 인클루드 해야한다.

리스트는 namespace std에 정의되어 있다.

 

리스트 객체는 앵커(anchor)라 불리는 포인터 2개를 제공한다.

이 두 개의 포인터는 첫 번째와 마지막 요소를 가리킨다.

새로운 요소를 삽입하기 위해서는 이 포인터를 조작해야한다.

 

이로인해 벡터, 데크, 배열과는 다른 특성이 나타난다.

1. 리스트는 임의 접근을 제공하지 않는다.

    n번째 요소에 접근하기 위해서는 링크를 타고 가야 한다.

    양방향 리스트로 되어있기 때문에 뒤에서도 타고 갈 수 있다.

 

2. 각 위치에서 요소를 삽입하고 제거하는 연산은 빠르다.

    다른 요소의 이동이 필요 없기 때문이다.

    포인터만 몇개 고치면 바로 삽입/삭제가 가능하다.

    (단, 특정 위치에 삽입/삭제하기 위해 찾아가는 시간은 제외)

 

3. 요소 삽입/삭제로 다른 요소에 대한 포인터, 참조자와 반복자가 유요한 상태로 남는다.

    참조자, 반복자, 포인터가 다른 요소를 가리키고 있으면 삽입/삭제를 해도 무효화 되지 않는다.

 

4. 리스트의 거의 모든 연산은 성공하거나 아무런 영향을 미치지 않는 방식으로 예외처리된다.

    중간에 멈추는 예외는 없다.

 

5. 리스트는 첨자 연산자나 at() 제공하지 않는다.

   임의 접근을 허용하지 않기 때문이다.

 

6. 리스트는 용량이나 재할당을 위한 연산이 없다.

    무한이 늘릴 수 있으며 각 요소는 자신만의 메모리를 갖는다.

 

7. 리스트의 요소를 이동하거나 제거하는 연산들은 빠르다.

    값의 복사가 아닌 포인터의 조작이므로 더 빠르다.

 

리스트 연산 

생성자와 소멸자

연산	설명
list<elem> c	기본 생성자, 빈 리스트를 만든다
list<elem> c(c2)	복사 생성자, 같은 자료형의 다른 리스트를 복사한 리스트를 만든다, 모든 요소 복사
list<elem> c = c2	복사 생성자, 같은 자료형의 다른 리스트를 복사한 리스트를 만든다, 모든 요소 복사
list<elem> c(rv)	이동 생성자, rv의 내용을 갖는 새로운 리스트를 만든다 ( C++11 이후 지원 )
list<elem> c = rv	이동 생성자, rv의 내용을 갖는 새로운 리스트를 만든다 ( C++11 이후 지원 )
list<elem> c(n)	기본 생성자로 초기화된 n개의 요소를 갖는 리스트를 만든다
list<elem> c(n, elem)	elem으로 초기화된 n개의 요소를 갖는 리스트를 만든다
list<elem> c(beg,end)	범위 [beg. end) 내의 요소를 갖는 리스트를 만든다
list<elem> c(initlist)	초기화자 목록 내의 요소로 초기화된 리스트를 만든다 ( C++11 이후 지원 )
list<elem> c = initlist	초기화자 목록 내의 요소로 초기화된 리스트를 만든다
c.~list()	모든 요소를 삭제하고 메모리를 풀어준다.

 

수정하지 않는 연산

연산	설명
c.empty()	c가 비어있는지 알려준다 ( size() ==0 과 같지만 결과는 좀 더 빠를 수 있다 )
c.size()	현재 요소 수를 반환
c.max_size()	최대 저장 가능한 요소의 수를 반환
c1 == c2	c1이 c2와 같은지 반환, 모든 요소가 같아야 한다
c1 != c2	c1이 c2와 다른지 반환
c1 < c2	c1이 c2보다 작은지 반환, 첫번째 요소 비교
c1 > c2	c1이 c2보다 큰지 반환, 첫번째 요소 비교
c1 <= c2	c1이 c2보다 작거나 같은지 반환, 첫번째 요소 비교
c1 >= c2	c1이 c2보다 크거나 같은지 반환, 첫번째 요소 비교

 

 

요소 접근

리스트에 있는 모든 요소에 접근하려면 범위 기반 for문을 사용한다.

또는 반복자를 사용한다.

임의 접근이 허용되지 않기 때문에 요소에 직접 접근하기 어렵다.

연산	설명
c.front()	첫 번째 요소 반환, 첫 번째 요소가 있는지 검사하지 않음
c.back()	마지막 요소 반환, 마지막 요소가 있는지 검사하지 않음

 

 

반복자

임의접근을 허용하지 않기 떄문에 임의 접근 반복자가 필요한 알고리즘을 사용할 수 없다.

정렬이 이에 해당하는데 리스트는 전용 sort() 함수를 제공한다.

연산	설명
c.begin()	첫 번째 요소에 대한 양방향 반복자 반환
c.end()	마지막 요소 다음 위치에 대한 양방향 반복자 반환
c.cbegin()	첫 번째 요소에 대한 양방향 상수 반복자 반환 ( C++11 이후 지원 )
c.cend()	마지막 요소 다음 위치에 대한 양방향 상수 반복자 반환 ( C++11 이후 지원 )
c.rbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 반복자 반환
c.rend()	역방향 반복에서의 마지막 요소 다음 위치에 대한 역방향 반복자 반환
c.crbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )
c.crend()	역방향 반복에서의 마지막 요소 다음 위치에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )

 

 

요소 삽입/제거

연산	설명
c.push_back(elem)	elem의 복사본을 끝에 넣음
c.pop_back()	마지막 요소 삭제, 반환값 없음
c.push_front(elem)	elem의 복사본을 맨 앞에 넣음
c.pop_front()	첫 번째 요소 삭제, 반환값 없음
c.insert(pos, elem)	반복자 위치 pos 앞에 elem의 복사본을 삽입 후 새 요소의 위치 반환
c.insert(pos, n, elem)	반복자 위치 pos 앞에 elem의 복사본 n개를 삽입 후 새 요소 중 첫 번째 요소 위치 반환, 새 요소가 없으면 pos 반환
c.insert(pos, beg, end)	반복자 위치 pos 앞에 범위 [beg, end) 내 모든 요소의 복사본 삽입 후 새 요소 중 첫 번째 위치 반환, 새 요소가 없는 경우 pos 반환
c.insert(pos, initlist)	반복자 위치 pos 앞에 초기화자 목록 내 모든 요소의 복사본 삽입 후 새 요소 중 첫 번째 위치 반환, 새 요소가 없는 경우 pos 반환, ( C++11 이후 지원 )
c.emplace(pos, args...)	반복자 위치 pos 앞에 인자 args로 초기화된 요소의 복사본을 삽입 후 새 요소의 위치 반환 ( C++11 이후 지원 )
c.emplace_back(args...)	인자 args로 초기화된 요소의 복사본을 맨 끝에 삽입, 반환값 없음 ( C++11 이후 지원 )
c.emplace_front(args...)	인자 args로 초기화된 요소의 복사본을 맨 앞에 삽입, 반환값 없음 ( C++11 이후 지원 )
c.erase(pos)	반복자 위치 pos에 있는 요소 삭제 후 다음 요소 위치 반환
c.erase(beg, end)	범위 [beg, end)내 모든 요소 삭제 후 다음 요소의 위치 반환
c.remove(val)	값이 val인 모든 요소 제거
c.remove_if(op)	op(elem)이 참인 모든 요소 제거
c.resize(num)	요소의 수를 num개로 바꿈, size()가 커지는 경우 새 요소는 기본 생성자로 초기화
c.resize(num, elem)	요소의 수를 num개로 바꿈, size()가 커지는 경우 elem으로 초기화
c.clear()	모든 요소를 제거

 

 

리스트만의 수정 연산

연산	설명
c.unique()	연속한 요소 중 같은 값을 가지는 중복 제거
c.unique(op)	연속한 요소 중 op()이 참인 중복 요소 제거
c.splice(pos, c2)	c2의 모든 요소를 c의 반복자 위치 pos 앞으로 이동 )
c.splice(pos, c2, c2pos)	c2의 위치 c2pos에 있는 요소를 c의 위치 pos로 이동
c.splice(pos, c2, c2beg, c2end)	c2의 범위 [c2beg, c2end) 내 모든 요소를 c의 위치 pos 앞으로 이동
c.sort()	모든 요소를 연산자 < 기준으로 정렬
c.sort(op)	모든 요소를 op()기준으로 정렬
c.merge(c2)	두 컨테이너가 모두 정렬되어 있을 때 c2의 모든 요소를 c와 합치고 정렬된 상태 유지
c.merge(c2, op)	두 컨테이너가 모두 정렬 기준 op()에 따라 정렬되어 있을 때 c2의 모든 요소를 c와 합치고 정렬된 상태 유지
c.reserve()	모든 요소의 순서를 뒤집음

 

 

예외 처리 

리스트는 STL의 표준 컨테이너 중 가장 예외에서 안전한 컨테이너이다.

연산	예외 보장
push_back()	성공하거나 아무런 영향을 미치지 않음
push_front()	성공하거나 아무런 영향을 미치지 않음
insert()	성공하거나 아무런 영향을 미치지 않음
pop_back()	예외를 던지지 않음
pop_front()	예외를 던지지 않음
erase()	예외를 던지지 않음
clear()	예외를 던지지 않음
resize()	성공하거나 아무런 영향을 미치지 않음
remove()	만약 요소 비교 연산이 예외를 던지지 않는다면 예외를 던지지 않음
remove_if()	만약 조건자가 예외를 던지지 않는다면 예외를 던지지 않음
unique()	만약 요소 비교 연산이 예외를 던지지 않는다면 예외를 던지지 않음
splice()	예외를 던지지 않음
merge()	만약 요소 비교 연산이 예외를 던지지 않는다면 성공하거나 아무런 영향을 미치지 않음
reverse()	예외를 던지지 않음
swap()	예외를 던지지 않음