[STL] list

list

-> 노드를 기반으로 하는 컨테이너 이다 

-> 배열 기반 컨테이너가 아니기떄문에 인덱스 접근이 불가능하다.

-> 더블 링크드 리스트로 구현되어 있다.

-> 앞,뒤 노드의 삽입 및 삭제가 가능하다

각 노드는 연속적인 메모리를 사용하는 것이 아니고,

비 연속적인 메모리에 여기저기 저장되지만 포인터로 각 노드를 연결하여

마치 연속된 메모리를 사용하는 것처럼 보인다.

-> 임의 접근이 불가능

-> 탐색하고자하는 원소가 나올 떄까지 모든 노드를 순회해야함

-> 선형시간 O(n)

삽입 삭제 시에는 단순 포인터의 해제 및 연결만 하기 떄문에

메모리를 밀고 당길 필요가 없어 빠르다.(상수 시간 O(1))

메모리의 재할당 및 복사가 필요 없기 떄문에 런타임 시에도 삽입 삭제가 용이하다.

 

 

 

list의 사용

 

 

list의 선언

 

 

list의 원소 삽입

list는 앞에서도 원소를 삽입할 수 있기에 push_front 함수를 지원한다.

 

여기서 원소를 출력해야하는데 list는 배열 기반 컨테이너가 아니므로 인덱스접근이 불가능하다.

list의 모든 원소를 순회하기 위해서는 반복자를 활용해야한다.

그런데 반복자가 아닌 list의 원소를 확인할 수 있는 방법이 있다.

그것은 '범위가반 for문' 과 'auto'이다.

 

 

auto

-> C++11 문법.

-> auto 자료형이다.

-> 사용자가 초기화하는 데이터의 타입으로 자동 매칭된다.

-> 단, 가독성이 떨어진다.

-> 변수 선언 시 사용하지 않는다.

-> 선언과 동시에 초기화를 진행해야만 한다

 

 

 

범위기반 for문

-> 반복 횟수가 정해져있는 컨테이너/배열의 모든 원소를 순회하는데 사용한다.

-> 단, 범위 기반 for문을 사용 중 원소의 개수가 바뀌게 되면 오류가 발생한다.

-> 그러므로 단순 순회 용도로만 사용한다.

컨테이너 또는 배열의 원소를 하나씩 선언한 변수에 대입해준다.

모든 원소를 순회할떄까지

 

선언한 a에 단순 대입이 진행된다.

-> 복사가 진행된다

복사 연산을 줄이기 위해서 레퍼런스형으로 참조시켜서 사용하자.

 

 

list 원소 삭제

 

 

list의 멤버함수

 

 

 

 

list의 반복자

-> list는 임의 접근 반복자를 사용하지 않는다.

-> 양 방향 접근 반복자를 사용한다.

 

 

 

 

list의 반복자를 이용한 중간삽입

 

list는 vector와 달리 메모리를 밀고 당길 필요가 없다.

단순 빈 공간에 원소를 삽입 후 포인터 연결만 해제 및 재연결하면 되기 떄문에

반복자(begin 과 end)의 위치가 변경되지 않아 무효화가 발생하지 않는다.

 

 

 

 

 

list의 중간 삭제

 

 

 

 

 

list의 정렬

-> list는 멤버 함수로 sort를 지원한다.

-> list의 sort는 아무런 조건도 명시하지 않을 경우 기본 오름차순 정렬이 된다.

-> list의 멤버함수 sort와 reverse를 함께 사용하면 기본 오름차순 에서 내림차순 정렬로 바뀌게된다.