forward_list, list, deque

Oak_Cassia·2021년 12월 3일
0

리스트를 구현하려면 포인터를 가지고 있어야 하고, new와 delete 연산자를 이용해 메모리를 할당하고 해제할 수 있어야 한다.

forward_list

  • 리스트의 크기를 반환할 수 없다.
  • 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않는다.
    front()는 있지만 back()은 없다.
  • push_front(): 연결 리스트 맨 앞에 원소 추가
  • insert_after(): 인자로받는 반복자의 다음 위치에 원소 추가
  • emplace_front(), emplace_after(): 추가적인 복사나 이동을 하지않고 원소 삽입
  • pop_front(): 맨 앞의 원소 삭제
  • erase_after(it): 반복자 다음 원소 삭제
  • remove(), remove_if(): 등호 연산에 근거하여 원소를 삭제, remove_if는 bool 값을 반환하는 조건자 함수를 인자로 받는다.
  • vector와 array는 공용 sort()를 사용할 수 있지만 forward_list는 멤버 함수로 쓴다. 반복자 또한 이들과 다르다
    • list1.sort(std::greater<int>()); //기본은 less<value_type>
    • O(nlogn)
  • revers(): 저장된 원소의 순서를 역순으로 변경, O(n)
  • unique(): 중복되는 원소 첫 원소만 남기고 제거

list

이중 연결리스트
노드로 구현

front 첫번째 원소
back 마지막 원소
size 크기
capacity는 없다. vector와 다르게
[] 임의 접근도 없다. 노드에서 포인터로 다음 노드 가리키니까

begin 맨 앞의 원소를 가리키는 iterator 반환
end 맨 뒤의 원소의 다음을 가리킨느 iterator 반환
insert(it,k) iterator로 삽입할 위치 지정. 삽입한 원소 위치 iterator로 반환
push_back(), pop_back()
erase iterator로 삭제
pop_front
remove(10) 10을 모두 삭제
list의 반복자는 양방향으로 이동할 수 있어서 양방향 반복자라고 부른다. 반복자를 이용하여 특정 위치로 이동하는 작업은 선형시간 복잡도를 가진다.

vector의 경우에 메모리 재할당을 한 경우 기존의 반복자와 포인터, 참조는 무효화 된다. 하지만 list는 그럴 걱정이 없다.

deque(double-ended queue)

  • push_front(), pop_front(), push_back(), pop_back() O(1)시간 복잡도로 동작한다.
  • erase(iter, iter)
  • 모든 원소에 대해 임의접근 O(1) 시간복잡도로 동작한다.
  • 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n/2 단계로 동작한다.

여러 메모리 블록 할당. 필요시 메모리 블록 추가
vector 처럼 기존의 것 삭제하고 새로 만들지 않음

중간에서 삽입되거나 삭제되면 데이터들의 이동이 발생
(벡터와 달리 앞으로 늘어나거나 뒤로 늘어난다. 데이터가 적은 쪽)
[]를 사용해 임의 접근 가능

임의 접근 반복자

profile
rust로 뭐할까

0개의 댓글