list S+++

llist ᅡᆫ란?list 헤더에 정의된 list ᅳᆫ는 자료 유형 T 객체를 이중 링크드 리스트로 구현한 것이다.이중 링크드 리스트로 구현한 것이므로 어느 위치에서나 원소 추가 제거가 가능하며, 더욱이 이는 배열 구조를 사용한 vector와 deque와 비교할 때 매우 빠르다.

다만 이중 링크드 리스트인 것처럼 포인터를 사용하여 연결한 것이므로 원소에 대한 임의 접근이 불가능하다. 즉, 사용되지 않고 원소에 접근하려면 오로지 반복자의 증감 연산을 통해서만 가능하다.반복자 역시 임의 접근 반복자가 아닌 양방향 반복자이기 때문에 vector와 deque처럼 반복자에 정수 계산은 불가능하고 오로지 증감 연산만 가능하다.

이중링크드리스트가 자세히 궁금하면 내가 쓴 이중링크드리스트 게시물을 참고해서 조금씩 알려주면 node를 구성하는 클래스에 원소를 저장하고 이 node의 끝과 처음을 아는 즉 head와 tailnode를 list 클래스가 가지고 있다.따라서 head와 tail을 제외한 노드는 앞뒤가 서로 연결되어 결합되어 있는 형태라고 보면 된다.head와 tail을 각각 시작과 마지막에는 nullptr을 가리킨다. 이로써 원소의 시작과 끝을 판단할 수 있다.

list를 사용해 보는 list는 기본적으로 다른 컨테이너와 사용법이 비슷하다.약간의 차이만 있을 뿐 대체로 많이 닮았다.아마도 이는 알고리즘과 자료 구조를 나눈 덕분이다.

먼저 생성자부터 살펴보자.생성자는 모든 컨테이너가 같다고 봐도 무방하다.list에서 중요한 점은 반복자가 정수 연산을 못한다는 것이다.오로지 증감 연산자만 가능하다.

또한 begin(), end()역방향 반복자, const 반복자도 있다.

list 원소 추가, 삭제 원소 추가 면에서는 deque와 같다고 보면 된다.push_back(), push_front()와 같이 앞뒤로 추가가 가능하며 emplace_back()과 emplace_front()와 같이 앞뒤로 생성자를 사용하여 추가도 가능하다.

단, 임의 액세스가 불가능하기 때문에 [ ] 연산자를 사용하거나 at ( ) 연산자는 불가능하다.

insert ( )함수도 동일하게 사용할 수 있다.여기서 insert 함수를 사용했다고 해서 기존의 반복자가 vector와 deque와 달리 비활성화되지 않는다.

원소 제거도 마찬가지다.clear( )는 원소 전체의 소거erase( )는 지정된 범위 소거 remove( )는 지정된 인수 소거 remove_if( )는 매개 변수로 주어진 팬터 혹은 람다 조건식으로 true를 반환하는 것만 지운다.

또한 unique( ) 함수도 있는데 이는 인접한 중복 원소를 제거한다.인수로 이항 조건자를 받을 수도 있다.

목록을 정리하는 기존의 vector와 deque와 달리 일반 알고리즘 헤더에 있는 스폿을 사용할 수 없다.이는 list가 양방향 반복자이기 때문에 임의 접근 반복자가 필요한 sort( ) 전역 함수는 사용할 수 없지만 sort( ) 멤버 함수는 사용할 수 있다.sort()를 그대로 사용하면 오름차순으로 정렬하고 sort()에 조건식을 인수로 전달할 수 있다.이는 sort() 내에 람다 함수 또는 팬터를 사용할 수 있다.

또한, ( ) 연사자를 오버로드하여 임의의 팬터를 만들어 sort ( )내에 사용할 수도 있다.

merge( )라는 함수도 있는데 이름 그대로 병합이다.merge( ) 함수는 동일한 list 객체여야 하며 오름차순으로 정렬되어 있어야 한다.그리고 복제를 하는 것이 아니라 이동 연산으로 이동시킨다.splice( ) 함수도 있는데, 이 함수는 원자에서 받은 목록의 원소를 현재 컨테이너의 특정 위치 전에 전송한다.여러 가지 버전이 있다.splice( ) 함수에서 첫 번째 인수는 삽입할 위치, 두 번째 인수는 목록(여기까지 있으면 3~4번째 인수가 지정해주는 범위만 옮김), 네 번째 인수는 두 번째 목록의 반복자 끝(여기까지 있으면 3~4번째 인수가 지정해주는 범위만 옮김)

splice()도 핵심은 이동 연산이라는 것이다.

원소 접근은 다소 어렵다.추가와 제거 효율을 높인 대신 임의 접근이 불가능하므로 반복자로서 원소를 알아봐야 한다.단, front( )와 back( )함수로 첫 원소 마지막 원소는 알린다.begin(), end(), cbegin(), cend(), rbegin(), rend( ) 함수에서 반복자를 얻어 증감 연산(+, –)으로 원소에 접근할 수 있다.

error: Content is protected !!