list

리스트(std::list)

장 점

1. 더블 링크드 리스트 형식
2. 삽입 삭제 시에도 속도가 빠르다.

단 점

1. 임의 접근이 불가능하다.

 

가능한점

1. 크기 변경
2. 중간 삽입 삭제
3. 순차 접근

 

원본>  http://blog.naver.com/bravedog/100005053219

■ list의 능력

list의 내부 자료구조는 vector, deque와는 완전히 다르다. 그러므로 vector, deque와 비교를 할 때

다음과 같은 차이점이 보인다

  ● list는 랜덤 액세스를 지원하지 않는다. 예를 들어, 5번째 원소를 액세스하기 위해서 list는 앞의

     1~4번째 원소를 거쳐서 액세스하게 된다. 그러므로 특정 위치의 원소를 액세스하는 경우 속도

     는 느릴 것이다.

  ● 어떠한 위치에서건 삽입과 삭제가 빠르게 이루어진다. 다른 원소들은 이동될 필요가 없기

     때문에 삽입, 삭제 동작은 상수 시간 복잡도를 가지게 된다. 내부적으로 보자면, 단지 포인터

     값들만 조작하면 그만이다.

  ● 삽입과 삭제 동작이 모든 포인터와 레퍼런스, 그리고 반복자를 무효화시키지는 않는다.

  ● list는 거의대부분의 동작들이성공하거나 아니면 아무런 영향도 받지않는 예외핸들링을 제공한다.

list의 멤버 함수들은 vector와 deque와의 다른 점들을 반영한다

  ● list는 [] 연산자와 at()을 제공하지 않는다. 왜냐하면, 랜덤 액세스를 지원하지 않기 때문이다.

  ● list는 용량과 재할당과 관련된 함수들을 제공하지 않는다. 왜냐하면, 두 함수 모두 필요없기

    때문이다.

    각각의 원소들은 자신만의 메모리를 가지고 있으며 이것은 원소가 지워지기 전까지 유효하다.

  ● list는 원소를 이동시키기 위한 특별한 멤버 함수들을 제공한다. 이 멤버 함수들은 같은 이름의

    STL 알고리즘보다 빠르게 동작한다. 왜냐하면, 알고리즘은 이들을 복사한 후 이동하지만,

    멤버 함수으 lruddn는 단지 포인터 값만 재지정하기 때문이다.

 

■ list의 생성자와 소멸자
동작	효과
list<Elem> c	원소 원이 빈 list를 생성한다
list<Elem> c1(c2)	같은 타입의 다른 list를 복사하여 생성한다(모든 원소들은 복사된다)
list<Elem> c(n)	디폴트 생성자에 의해서 생성되는 n개의 원소와 함깨 list를 생성한다
list<Elem> c(n,elem)	elem 원소의 n개의 복사본으로 list를 초기화하여 생성한다
list<Elem> c(begn,elem)	[beg,end) 범위의 원소로 list를 초기화하여 생성한다
c.~list<Elem>()	모든 원소들을 파괴하고 메모리를 해제한다

 

■ list의 수정하지 않는 동작들
동작	효과
c.size()	실제 원소의 개수를 반환한다
c.empty()	컨테이너가 비어있는지를 판단한다 (size()==0와 동일하나 더 빠르다).
c.max_size()	컨테이너가 가질 수 있는 최대 원소의 개수를 반환한다.
c1 == c2	c1과 c2가 같은지 판단한다
c1 != c2	c1과 c2가 다른지 판단한다 ( !(c1==c2)와 동일하다 ).
c1 < c2	c1이 c2보다 작은지를 판단한다
c1 > c2	c1이 c2보다 큰지를 판단한다( c2<c1과 동일하다 ).
c1 <= c2	c1이 c2보다 작거나 같은지를 판단한다 ( !(c2<c1)와 동일하다 ).
c1 >= c2	c1이 c2보다 크거나 같은지를 판단한다 ( !(c1<c2)와 동일하다 ).

 

■ list의 할당 연산자
동작	효과
c1 = c2	c2의 모든 원소들을 c1에 할당한다
c.assign(n, elem)	elem 원소의 n개의 복사본을 할당한다
c.assign(beg, end)	[beg,end) 범위의 원소를 할당한다
c1.swap(c2)	c1과 c2의 데이터를 교체한다.
swap(c1,c2)	동일하다(전역 함수).

 

■ list의 원소 액세스 관련 동작
동작	효과
c.front()	첫 번째 원소를 반환한다(원소가 있는지 검사하지 않는다)
c.back()	마지막 원소를 반환한다(원소가 있는지 검사하지 않는다)

 

■ list의 반복자 함수
동작	효과
c.begin()	첫 번째 원소를 가리키는 랜덤 액세스 반복자를 반환한다
c.end()	맨 마지막 원소 뒤를 가리키는 랜덤 액세스 반복자를 반환한다
c.rbegin()	역방향에서 첫 번째 원소의 역방향 반복자를 반환한다
c.rend()	역방향에서 마지막 원소 뒤를 가리키는 역방향 반복자를 반환한다

 

■ vector 원소의 삽입 및 제거 동작
동작	효과
c.insert(pos,elem)	반복자 pos위치에 elem의 복사본을 삽입한다 그리고 새로운 원소의 위치를 반환한다
c.insert(pos,n,elem)	elem의 n개의 복사본을 반복자 pos 위치에 삽입한다. 반환값은 없다.
c.insert(pos,beg,end)	[beg,end) 범위의 모든 원소들을 복사하여 반복자 pos 위치에 삽입한다. 반환값은 없다.
c.push_back(elem)	끝부분에 elem의 복사본을 추가한다.
c.pop_back()	마지막 원소를 제거한다(제거된 원소를 반환하지 않는다.)
c.push_front(elem)	앞부분에 elem의 복사본을 추가한다
c.pop_front()	첫 번째 원소를 제거한다(제거된 원소를 반환하지 않는다)
c.remove(val)	값이 val인 모든 원소를 제거한다
c.remove_if(op)	op(elem)가 true를 반환하는 모든 원소를 제거한다
c.erase(pos)	반복자 pos 워치의 원소를 제거한다. 그리고 다음 원소의 위치를 반환한다.
c.erase(beg,end)	[beg,end)범위의 모든 원소들을 제거한다. 그리고 다음 원소의 위치를 반환
c.resize(num)	원소의 개수를 num개로 변경한다 (만약 size()가 증가된다면, 새로운 원소들은 그들의 디폴트 생성자에 의해서 생성된다.)
c.resize(num,elem)	원소의 개수를 num개로 변경한다 (만약 size()가 증가된다면, 새로운 원소는 elem의 복사본이다).
c.clear()	모든 원소들을 제거한다(빈 컨테이너로 만든다).

 

■ list의 원소를 특별하게 수정하는 동작
동작	효과
c.unique()	같은 값을 가지는 연속된 원소들의 중복을 제거한다. (1,2,3,3,4,3 -> 1,2,3,4,3)
c.unique(op)	op()가 true를 반환하는 연속된 원소들의 중복을 제거한다.
c1.splice(pos,c2)	c2의 모든 원소들을 c1의 pos 위치 앞으로 이동한다
c1.splice(pos,c2,c2pos)	c2의 c2pos에 있는 원소를 c1의 pos 위치 앞으로 이동한다
c1.splice(pos,c2,c2beg,c2end)	c2의 [c2beg, c2end)의 원소들을 c1의 pos 위치 앞으로 이동한다
c.sort()	< 연산자를 정렬 기준으로 정렬한다
c.sort(op)	op()를 정렬 기준으로 정렬한다
c1.merge(c2)	두 컨테이너 모두 정렬되어 있다는 가정하에 c2의 모든 원소들을 c1로 이동한다. 그러므로 모든 원소들은 병합되며 정렬 기준에 어긋나지 않게 정렬되어 있다.
c1.merge(c2,op)	두 컨테이너 모두 op() 정렬 기준에 의해 정렬되어 있다는 가정하에 c2으 lahems 원소들을 c1로 이동한다. 그러므로 모든 원소들은 병합되며, 정렬 기준 op()에 어긋나지 않게 정렬되어 있다.
c.reverse()	모든 원소들의 순서를 뒤바꾼다.

 

■ 예외에 대해서 보장해 주는 동작들
동작	효과
push_back()	성공하거나 아무런 영향도 받지 않는다
push_front()	성공하거나 아무런 영향도 받지 않는다
insert()	성공하거나 아무런 영향도 받지 않는다
pop_back()	예외를 던지지 않는다
pop_front()	예외를 던지지 않는다
erase()	예외를 던지지 않는다
clear()	예외를 던지지 않는다
resize()	성공하거나 아무런 영향도 받지 않는다
remove()	원소를 비교하는 도중 예외를 던지지 않는다면 예외를 던지지 않는다.
remove_if()	조건자가 예외를 던지지 않는다면 예외를 던지지 않는다
unique()	원소를 비교하는 도중 예외를 던지지 않는다면 예외를 던지지 않는다.
splice()	예외를 던지지 않는다
merge()	원소를 비교하는 도중 예외를 던지지 않는다면 예외를 던지지 않는다.
reverse()	예외를 던지지 않는다
swap()	예외를 던지지 않는다