list ᅡ とは ？란?list 헤더에 정의된 list ᅳᆫ는 자료 유형 T 객체를 이중 링크드 리스트로 구현한 것이다.이중 링크드 리스트로 구현한 것이므로 어느 위치에서도 원소 추가 제거가 가능하며, 더욱이 이는 배열 구조를 사용한 vector와 deque와 비교하면 매우 빠르다.
다만 이중 링크드 리스트인 것처럼 포인터를 사용하여 연결한 것이므로 원소에 대한 임의 접근이 불가능하다. 즉 [] 사용하지 못하고 원소에 접근하려면 오로지 반복자의 증감 연산을 통해서만 가능하다.반복자 역시 임의 접근 반복자가 아닌 양방향 반복자이기 때문에 vector와 deque처럼 반복자에 상수 계산은 불가능하고 오로지 증감 연산만 가능하다.
이중 링크드리스트를 자세히 알고 싶다면 내가 쓴 이중 링크드리스트 게시물을 참고하여 약소하게 알려준다면 node를 구성하는 클래스에 원소를 저장하고, 이 node의 끝과 처음을 아는 즉 head와 tailnode를 list 클래스가 가지고 있다.따라서 head와 tail을 제외한 node는 앞뒤가 서로 연결되어 결합되어 있는 형태라고 보면 된다.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()함수도 있는데, 이는 인접한 중복원소를 제거한다.인수로 이항 조건자를 받을 수도 있다.
list를 정리하는 기존의 vector와 deque와는 달리 일반 알고리즘 헤더에 있는 sort를 사용할 수 없다.이는 list가 양방향 반복자이기 때문에 임의 접근 반복자가 필요한 sort() 전역 함수는 사용할 수 없지만 sort() 멤버 함수는 사용할 수 있다.sort()를 그대로 사용하면 오름차순으로 정렬하여 sort()에게 조건식을 인수로 전달할 수 있다.이는 sort() 내에 람다함수 혹은 펑터를 사용할 수 있다.
또한, ()연사자를 오버로드하여 임의의 팬을 만들어 sort()내에 사용할 수도 있다.
merge( )라는 함수도 있는데, 그 이름과 같이 병합이다.merge() 함수는 동일한 list 객체여야 하며 오름차순으로 정렬되어 있어야 한다.그리고 복제를 하는 것이 아니라 이동연산으로 이동시킨다.splice()함수도 있는데, 이 함수는 원자에서 받은 리스트의 원소를 현재 컨테이너의 특정 위치 앞으로 전송한다.여러 가지 버전이 있다.splice()함수에서 첫 번째 인수는 삽입할 위치, 두 번째 인수는 목록(여기까지 있으면 통째로 옮긴다) 세 번째 인수는 두 번째 목록의 반복자 1(여기까지 있으면 두 목록에서 3에 해당하는 원소만 옮긴다) 네 번째 인수는 두 번째 목록의 반복자 끝(여기까지 있으면 3~4번째 인수가 지정해주는 범위만큼 옮긴다)
splice()도 핵심은 이동 연산이라는 것이다.
원소 접근은 다소 어렵다.추가와 제거 효율을 높인 대신 임의 접근이 불가능하므로 반복적으로 원소를 조사해야 한다.단, front( )와 back()함수로 첫 번째 원소 마지막 원소는 알린다.begin(),end(),cbegin(),cend(),rbegin(),rend()함수로 반복자를 얻어 증감연산(+,–)으로 원소에 접근할 수 있다.