vector, list 이거 둘다

'Sequence Container' 라고 하는 것들이다.

데이터가 삽입 순서대로 나열되는 형태

• vector : 동적 배열

• list : 이중 연결 리스트

• deque : double-ended queue 데크

  벡터와 리스트 중간지점. 자주쓰지는 않고 서버에서 가끔 사용함.

이론만 알아보도록 하겠다.

필요할때마다 통을 늘려서 사용하는 느낌이다.

벡터와 유사. 그런데 통을 만들어서 사용하다보니까

capacity는 지원하지 않는다.

• 벡터와 마찬가지로 배열 기반으로 동작

• 메모리 할당 정책이 다르다.

벡터 초기화

크기는 3이고 안에 들어있는 값 1로 초기화.

deque 초기화

메모리 변화

메모리가 어떻게 변화하는지 알아보도록 하자.

벡터의 경우, 원래있던 주소에서 다른 통으로 옮긴다음

원래 주소는 쓰레기값으로 바뀜.

deque의 경우

현재 이런데 여기서 데이터를 밀어 넣으면

늘어나는데 이상태에서 다시 추가를 하면

'어딘가에 통을 만들어서' 그곳에 데이터를 넣음.

push_front를 통해서 데이터를 넣을 경우에도

어딘가에 통을 만들어서 연결해주는 상황인거같다.

이런 느낌이다.

deque의 동작원리

• 중간 삽입/삭제 =>

• 처음/끝 삽입/삭제 => GOOD / GOOD

• 임의 접근

이 3가지를 고려해봐야한다.

중간 삽입/삭제

이 1이라는 데이터를 삭제하고싶다고 가정하자.

(내생각에는 효율 안좋다)

이렇게하면 끝인가? (ㄴㄴ)

당연하게도 데이터를 하나씩 밀어야된다는 단점이 있다.

4라는 데이터 넣을 경우 크기가 4로 고정이 되어있으니까

연산이 조금 덜 걸릴거같은 방향으로 밀어준다.

즉, 중간 상빕/삭제 => BAD / BAD

임의 접근 => GOOD

Code

Block이 몇번째 블록이고 Offset도 구하는 것을 볼 수 있다.

오프셋의 경우 % 4로 구하고있다.

이것을 다차원 배열의 행과 열에 넣어서 바로 접근하는 듯.

중간 삽입/삭제가 느리다 => 임의 접근을 지원한다.

이유는 생각해봐라.