면접전 최종 자료구조 정리..(게임프로그래를 위한 자료구조 책)

정렬 알고리즘이 가져야할 최소한의 복잡도는 O(nlogn)

만약 C++ new에서 동적배열의 크기를 -1로 하면 당연히 안만들어지지만...만약에 0으로하면 항복이 하나도 없는 배열을 가리키는

유효한 포인터가 생성되어 나두면 메모리릭이 발생한다.

---

배열

메모리 계층들 중 가장 낮은 곳에 위치한 것은 레지스터다.

컴퓨터 전체에서 가장 빠른 메모리이다. x86 기준 8개밖에 없다.

그런데 다행히도 대부분의 프로세서들은 레지스터와 거의 비슷하게 빠르되 용량이 좀 더 큰 메모리 영역이 있다. 그것이 바로 캐시다.(보통 L1 캐시라고 한다)

먼저 레지스터에서 자료를 찾고 없으면 L1캐시에서 찾고 또 없으면 다른 메모리 수준에서 찾는다..근데 이러면 시간이 오래 걸린다.

그런데 메모리의 특징이 하나 더 있다. 

메모리는 한 수준에서 다른 수준으로 이동할대(L1에서 레지스터로 이동하는 것은 예외다) 항상 커다란 덩어리 상태로 이동하는데..

따라서 배열에 한 항목에 접근하는 경우 그 항목 하나뿐만이 아니라 그 항목을 포함한 주변의 여러 항목들이 한 덩어리로 L1캐시에 로드된다.

배열의 크기 변경은 O(n)이다 클수록 걸리는 시간도 길어진다. 삽입 삭제또한 O(n)이다 단, 항목들의 순서를 유지할 필요가 없다면

빠른제거 알고리즘(그냥 맨 뒤의 값을 삭제하는곳에 넣기)을 사용할 수 있다.

---

if문은 프로세서의 분기 예측에 악영향을 미친다. 요즘 프로세서들은 명령을 한번에 하나씩 수행하지 않음..

실제로는 한 번에 많은 명령들을 동시에 수행하고 있다. 프로세서들은 소위 파이프라이닝이라고 불리우는 기능을 사용하는데..

여러 개의 명령들이 하나의 커다란 파이프라인에 들어가며, 그 명령들은 동일한 클럭 주기 동안 각기 다른 단계들에서 동시에 수행된다.

그리고 프로세서들은 파이프라인을 항상 꽉 찬 상태로 유지하려고 한다. 만약에 파이프라인에 조건 명령을 넣은 경우 그 명령의 참/거짓 여부에 따라

이후에 올 명령들이 달라져야 하지만, 프로세서는 그 조건 명령을 평가하지않고 일단 파이프라인을 꽉 채운다. 그럼 프로세서는 파이프라인에 넣을

조건 명령 이후의 명령들을 어떻게 결정할까? 바로 추측을 통해서하는데..프로세서는 분기 예측기라고하는 특별한 유닛을 이용해서 다음번에 파이프라인에 넣을 명령들을 결정한다. 만일 추측이 틀렸다면 파이프라인이 비워져야 하며 프로세서가 잘못된 추측을 한 지점 이후의 모든 것은 무시된다.

---

연결된 목록

게임 프로그래밍을 하다보면 메모리를 좀 더 효율적으로 사용하는 자료구조라던가 자료를 빠르게 삽입 또는 제거할 수 있는 자료구조가 필요해지는 떄가 온다.

노드들은 메모리가 일렬도 늘어서 있지 않다. 어쨌든 시작 끝, 목록 중간에 추가 제거가 상당히 빠름..

단일 연결목록의 장단점

메모리 재할당이 일어나지 않음 , 그러나 목록의 항목들에 직접 접근을 할 수 없다. 처음부터 타고들어가야하지..

단일은 제거가 O(n)인데 이중연결은 O(c)네..

삽입이 O(c)인 이유는 꼬리에 계속 추가되거나 머리에서 계속 추가되니까 그런거다...

연결목록의 치명적인 단점! 게임의 속도가 매우 중요한 경우에는 연결 목록이 발목을 잡을 수 있다. 그 이유는 캐시이다.

캐시는 메모리 블럭 단위로 로드가 되는데..이건 배열과 매우 잘 맞는다..

연결목록의 노드들은 연속적이지도 않고 순서도 임의적이다. 결국 캐쉬 적중률이 떨어지기 마련..

결론은 모든 항목들에 대해 작은 처리들을 반복한다거나 항목들을 빈번하게 추가, 제거해야하는 경우라면 연결된 목록을 사용하지 않는 것이좋다.

예를들어 여러개의 총알들을 목록으로 관리하는건 최악이다..메모리 할당과 해제가 많으면 안되..

---

스택과 대기열은 어떻게 저장되는지가 아니라 어떻게 접근되는지의 문제이다.

그래서 스택의 접근 구조를 만들때도 배열과 연결된 목록 2가지로 구현이 가능하다.

스택은 보통 넣기 뽑기 알고리즘 모두 O(c) 복잡도다 그러나 매번 메모리 할당이 일어나기 때문에..메모리가 연속적이지 않으면 또 캐쉬문제가..(연결된 목록일 경우..) 근데 배열로 만들면? 배열의 크기 변경시 복잡도는 O(n)으로 된다..;

대기열에서 배열로 구현한다면 순환 대기열로(원형)으로 만들어야 한다.

(인큐 (m_count + m_front) % m_size   )

(인덱스 접근시 (p_index +  m_front) % m_size 로 하면..0번은 항상 처음인덱스, 1번은 두번째 인덱스로 된다)

---

해시 테이블

희소자료가 중요한데 이건 식별번호쯤으로 알고 있는게 좋다. 고유한 식별번호!

이 키를 통해서 접근한다고 했을때 배열은?? 낭비가 심하다..만약에 3개만 키가 있다면??

그러면 연결된 목록?? 근데 빠른 접근이 안되잖아...그러면....

이런 문제를 해결하는것이 해시 테이블 자료구조임 ㅋ

1. 키 기반 희소 자료를 적당한 크기의 공간에 빠르게 저장할 수 있다.

2. 특정한 하나의 키가 테이블 안에 존재하는지의 여부를 빠르게 판단할 수 있다.

여기서 핵심은 빠르게 빠르게다!!! 

해시 테이블의 크기는 소수?로 하는게 좋다..저장하고자하는 항목의 개수보다 큰 소수를 선택하는게..좋다라..

(즉 나누는 수가 소수이면 중복되는 경우도 줄고..(충돌이 줄어든다..)..나머진 모르겠음..)

어쨌든 헤시테이블의 검색 알고리즘은 O(c)이다. 빠른속도가 중요한 프로그램에서 매우 유용하다.

근데 해시테이블에서 해결해야할 과제는 충돌!! 충돌이다 키가 충돌된다..

그래서 이 충돌을 피하기 위해서 해시 함수라는 것을 사용한다.

(나머지를 이용한 키 저장은 나쁜 방식이다 그것도 매우 매우임)

//정수가 키인경우

개별 자릿수 더하기 방법

이중 해싱(하나의 함수로 키를 해싱하고 그 결과를 같거나 다른 어떤 함수로 다시해싱)

//문자열인 경우?

문자열 안의 문자가 본질적으로는 정수라는 사실에 기여해서 개별 자릿수 더하기 방법과 마찬가지로 더하는데..그냥 더하면 안되고

각 자리의 색인을 곱해서 더한다..만약에 Hello!라면

H가 72이고 색인이 1이니까 72 * 1 + 101 * 2 ..이런식이 되겠지? 이렇게 안하면? hello와 olleh는 같은 결과가 나온다

!! 그러나 완벽한 해시 함수는 없다 언젠간 충돌만난다!! 따라서 그 충돌이 일어났다면..해결방법이 필요한데..

내부 구조 차원에서 충돌을 처리하는편이 낫다.

방법들..

1. 선형 오버플로우 : 단순히 충돌되면 색인을 증가시키고 빈 색인칸에 키 넣는다. 근데 이건 해시 테이블의 장점 파괴임..

모든 색인을 검색해야하므로. O(c) 알고리즘보다 느린 O(n)알고리즘으로 만들어 버리는것....ㅠ

근데 원래들어가야할 자리에? 충돌을 피하기 위해 들어간 키가 있다면?? 계속 밀린다..나비효과!

2. 2차 오버플로우 : 이거 색인이 1씩 증가가 아니라 제곱을 사용해 증가하면서 빈칸 찾는거임 오히려 1번보다 안좋아

왜냐면..검색하는데 중구난방이거든..

3. 연결된 오버플로우 : linked list와 비슷한 개념임..해시 테이블의 각 칸은 연결된 목록임..

사실 이방법이 충돌을 전혀 걱정할 필요가 없다. 충돌해도 어차ㅣ 자료가 목록의 끝에 추가될 뿐..

키 검색

해시 테이블에서 항목 찾기란 거의 O(c)찾을 수 있다. 근데 최악의 경우로..모든 항목이 동일한 연결 목록이라면..O(n)이겠다..

근데 대부분의 키값이! 문자열인 경우가 많다!!

아니 어쨌든 결론인데..해시 테이블은 현존하는 모든 자료구조 중에서 검색시간이 가장 빠르다.

최악

삽입O(c), 검색O(n), 제거O(n)

최상

삽입O(c), 검색O(c), 제거O(c)

근데 이결과는 연결된 해시 테이블에 대한 결과일뿐...연결된 목록을 배열로? 근데 배열로된 해시를 본적이 업삳고 하네..공간크기를 모르니까..

---

가상함수 테이블

가상함수가 하나라도 존재하면 가상 함수 테이블이 생기는데..본질적으로 호출될 함수를 가리키는 함수 포인터들의 테이블이다.

컴파일러는 그 인스턴스의 가상테이블에서 해당 포인터를 얻고 그 포인터가 가리키는 코드를 수행한다. 결국 포인터의 역참조하는 과정이 필요해서

추가 부담이 생기는것임..

근데 순수가상함수는 코드가 없으므로 포인터도 존재하지 않는다..그런데 어차피 순수가상함수를 가진 클래스는 인스턴스가 만들어질 수 없으므로

가상 함수 포인터 테이블은 항상 유효한 포인터를 가지게 된다.

---

RTTI(Run Time Type Information) 실행 시점 형식 정보..근데 이게 너무 느리다는거야..dynamic_cast지...

RTTI를 사용안한다는건 그냥 C스타일의 강제 캐스팅을 하면됨..A* p = (A*)abc 이런식인데..

어떠한 절차도 없이 그냥 캐스팅해라 이런거지..

---

지금까지 위에서 본것들은 모두 선형 자료구조다!!

시발 하노이탑하고, 피보나치 수열에 대한 재귀는 다시 보낟 이책 끝나고..

---

트리트리~

트리는 연결된 목록처럼 노드에 기반한 구조다..자식이 많다

트리의 구조는 연결된 목록들로 구현된다.

1. 전위운행은 가장 먼저 자신의 것이 처리되고 왼쪽 오른쪽 자식이 처리되는 과정임..그래서 전이 붙는거임

의사코드로는 

Preorder(node)

Process(node)

For each child

Preorder(child)

end for

end Preorder

2. 후위 운행은 자식들을 처리하고 그 후에 현재 노드를 처리하는것

Postorder(node)

For each child

Postorder(child)

end For

Process(node)

end Postorder

이햐 이진트리다!!

위에것은 어떠한 제약도 없는 평범한 트리이고 이번은 이진트리임..

이진트리는 자식이 두개밖에 없다. 그리고 몇가지 특징이 있는데

1. 포화성 : 꽉차있다 아니다라는 개념이 존재

2. 조밀성 : 완전성 또는 좌편성? 이라고 하는데..조밀한 이진트리란 최하위 수준 바로 전까지는 꽉 차있고 모든 말단 노드들이 왼쪽부터 채워져 있는 트리를 이야기한다.(이거 특정한 종류의 이진트리들에서 중요한 특성이다)!!!!!

3. 균형 (균형트리란 트리의 왼쪽과 오른쪽 노드들의 개수가 거의 같은 트리를 이야기하는데..

AVL, 레드 블랙 트리 등 이진 검색 트리 변종들에서 중요함..!!!!!!

저장하는 방식은 2개임

연결된 이진트리 방식과 노드 기반이고 배열로된 방식이다.

근데 배열은 안좋아 왜냐고? 메모리 공간땜시!!!

야 근데 말이야 이진 트리는 중위운행이라고 있어!

자 다시 한번보자 여기서 사용되는 의사코드는 비슷하나 약간 다르다 왜냐? 자식이 2개밖에 없어서..

전위운행

Preorder(node)

Process(node)

Preorder(node.left)

Preorder(node.right)

End Preorder    //왼쪽노드가 먼저 처리된다. 이진트리에서 쓰이는 일반적인 관례다

후위운행

Postorder(node)

Postorder(node.left)

Postorder(node.right)

process(node)

End Postorder

중위운행

Inorder(node)

Inorder(node.left)

process(node)

Inorder(node.right)

End Inorder    //왼쪽 처리하고 다음 현재 처리하고 다음 오른쪽 처리하고..

이진검색트리다!!! BST다!

이건 자료가 어떻게 접근되는가가 아니라 어떻게 정렬되는가가 더 중요한거다!! 정렬에 주안을 둔다.

야 이거 핵심은 자료를 반으로 나눠서 검색 공간을 줄이는게 핵심이다!!

루트뽑고 루트보다 작으면 왼 크면 오른쪽으로 이동하라고!! 그래서 반으로 줄이는거다

검색 알고리즘은 O(logn)이다 근데 이건 최선이고 최악은 시박..O(n)

그리고 중복된 자료 허용안해! ㅓ

근데 이진검색트리가 해시보다 나은게 없어..검색시간이 느리거든..해시보다 느리다는거임..

이진공간분할 트리 라...BSP의 중요한 개념이라는데..

---

우선순위 대기열과 힙이다.

우선순위 대기열은 연결된 목록으로 구현하면 쉽다..근데 느려..그래서 거의 이런방식으로 구현안해 ㅋ

아 힙은 말이야 이진트리의 특별한 형태야..

힙과 우선순위 대기열의 조합이라..

이단 힙은 모든 노드가 자신의 모든 자식들보다 더 크다. 최대힙이네..그래서 우선순위대기열로 쓸수 잇다는..

그래서 힙을 우선순위 대기열로 쓸려면 요구사항이 필요한다.

1. 힙이 조밀성이 중요하다..조밀조밀...조밀하다는게 꽉 찾다는게 아니..다(왼쪽부터 채워지면 되는거다)

2. 그리고 힙은 연결된 이진트리보다 배열로된 이진트리로 구현되는 경우가 많어..왜냐면 조밀해야하니까..??

연결된 이진 트리가 조밀한지의 여부를 판단하는건 복잡하다고 하네..

아아..그리고 어떤 자료가 삽입되었다고해도 힙의 특성을 만족해야해..근데 만약 루트부터 한다? 졸라 느리다 왜냐면..

제대로된 자리에 높이도록 노드들을 교환작업이 많아져......

그래서 올라가기 방식을 ㅏ사용해..

올라가기 방식이란 새 항목을 트리의 제일 아래에 삽입하고 그 항목이 제자리를 찾을 때까지 트리를 따라 올려보낸다

워워..삽입의 알고리즘 복잡은 O(logn)이다..왜냐면 4수준 트리에서 보면 부모가 위로 3개 있잖어.. 5수준은 4번..

음..우선순위 대기열을 연결된 목록 방식으로 구현하면..새 항목이 삽입될 자리를 찾기 위해서 목록의 모든 항목들을 살펴봐야할수도 있는데..

그래서 O(n)인데 힙으로 만들어진 우선순위 대기열은 더 효율적일다!!

힙에서 제거해보자!

1. 루트 제거 할때 

제거후 다시 힙 구조로 정렬되어야해..

1) 트리의 최하위 노드를 루트로 옮기고 그것을 적절한 자리로 내려보내(내려가기 알고리즘)

여기서 최하위 노드란..가장 작은 수를 이야기 하는게 아니라 트리의 마지막 오른쪽 노드를 이야기한다.왜냐면! 조밀조밀해야해서!!

아아..만약 루트가 아니라면? 최하위 노드를 거기에 넣으면 되!! ㅋㅋ 삭제 O(logn)이다

연결된 목록으로 구현된 우선순위보다 늦긴하다 그건..정렬따윈 없으니까 O(c)다 근데 나머진 안좋아 ㅋ

와우 근데 힙은 배열로 된 이진트리로 구현하는게 좋다는데..그냥 덜복잡이지 뭐 엄청 더 빠르고 이런건 아니다

---

그래프다!!

야 그래프는 트리랑 비슷한데..

트리를 융통성있게 만들면 그래프가 된다!! 트리는 각 노드의 자신의 아래 수준의 노드만을 가리키지만,

 그래프는 제한이 없어 어떤 노드든 가리킨다. 노드기반 자료구조야!

결구 그래프에서 수준을 제한하면 트리가 되고 하나의 자식노드로 또 제한하면 연결된 목록이 되는...오오...

양방향, 단방향, 가중 그래프

어쩄든 그래프를 구현하는 가장 일반적인 방식은 연결된 트리 같은 노드 연결방식을 사용하는것임..!!

여기선 그래프 노드들의 배열이나 연결목록..그래프 호들의 배열이나 연결목록으로 나눈다..

그래프 노드는 특정 노드의 자료를 저장하는 역활

그래프 호들은 두개의 포인터를 가진다.

단방향 그래프 : 이것은 연결된 그래프 중 가장 일반적인 형태로, 매우 유연하며 양방향 방법보다 더 빠르다

어떻게 구조를 만들까?

그래프 노드란건 당연히 있고..호는 본질적으로 한 노드에 대한 포인터로 존재한다. 

그리고 그래프의 각 노드는 그러한 호들의 연결 목록을 가진다.

어어..그러니까..각 노드는 다른 노드를 가리키는 호들의 연결된 목록의 가진다..?

여기서 나오는 운행방법이!

깊이 우선 탐색과 ! 너비 우선 탐색이다!!

트리랑 틀린건 어느 노드에서나 시작을 할 수 있다!!

깊이 우선 탐색은 트리의 전위 운행과 비슷하오...

DepthFirst(Node)

Process(Node)

Mark(Node)        //트리의 전위랑 틀린점

For Every Child of Node

If NotMarked(Child)    //트리의 전위랑 틀린점

DepthFirst(Child)

End If

End For

End Function

보통은 스택으로 구현한다고 하네..

각 노드를 처리할때마다 노드를 스택에 넣고 다른 노드로의 연결이 없는 노드를 만나면 스택에서 이전 노드를 뽑고 그 노드에 아직

처리되지 않은 다른 노드들이 있는지 점검해서 남은 노드들을 처리한다.

!!이야 너비 우선탐색이다!

BreadthFirst(Node)

Queue.Enqueue(Node)

Mark(Node) // ? 노드를 대기열에 넣을때 표시를 하는 이유는?

//노드가 대기열에 여러번 들어가는것을 막기 위함이다!

While(Queue.IsNotEmpty)

Process(Queue.Front)

For Each Child of Queue.Front

If NotMarked(Child)

Queue.Enqueue(Child)

Mark(Child)

end If

end FOr

Queue.Dequeue()

End While

End Function

그래프에서 노드를 제거하는게 생각보다 복잡한데 ..그냥 지워버리면? 나가는 호들은 삭제가 될지언정(왜냐면 들고 있으니까..)

제거된 노드를 가리키는 호들은 여전히 존재해서 댕글리 만든다!

그래서 말이다..한 노드를 제거하려면 그 노드를 가리키는 모든 호들을 찾아서 삭제해야한다. 그런 검색 과정으로 인해

노드 제거 알고리즘이 매우 느려지게 된다...!!!읔..그러나 유효성을 위해서 어쩔수 없다!( O(n^2)다 !헉...모든 노드들의 모든 호들을 검색하니까..)

---

유한상태기계다!! 그래프를 이용했슴다!

일단 마지막에 이것도 보는걸로..

---

버블 정렬 O(n^2)

힙정렬..힙이라는 자료구조 자체가 정렬 기능을 가지고 있다.

그래서 이를 정렬에 활용할 수 있는데 간단히 말해서 배열의 항목들을 모두 힙에 넣은 다음 한 번에 하나씩 힙에서 가장 큰 값을 뽑아 다시 배열에

저장하면..이건 정렬이 된거지..내리차순~ 힙은 삭제 삽입 O(logn)임.. 단 공간이 2배로 뿔지요~

오오..이진 검색트리..도 정렬로 쓰일 수 있는데...이진 검색트리에서 중위 운행을 적용하면..오오.......오름차순이..!!

---

야야 진수 변환법이다! 참고해라

이진수 -> 십진수 변환은

1011 -> 1* 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 

이런식으로해서 더하면? 8 2 1 = 11이 다!

십진수 -> 이진수는?

먼저 1 2 4 8 16 32 64 128 256 512 1024 2048 표를 만들어두고

2048	1024	512	256	128	64	32	16	8	4	2	1
0	0	0	0	0	0	0	0	0	0	0	0

이상태에서..주어진 십진수보다 작거나 같은 최대 2의 제곱수를 찾는다

예를 들어 십진수가 512라면 최대 2의 제곱수는 512다 

만약에 십진수 511라면? 최대는 256이다.

그럼 해보자 1996 을 바꿔봐라

2048	1024	512	256	128	64	32	16	8	4	2	1
0	1	1	1	0	0	0	0	0	0	0	0

1024가 먼저 나올테고..1996 - 1024 빼면? 972 

972는 512가 나오고..둘을 빼면 460이 나오고 그럼 256이 나오고

나올때마다 저 위의 표에 1를 적어두고..이짓거리를?? 0이 될떄까지 하면 된다 ㅋ

답은 111, 1100, 1100이다

16진수로 바꾸려면 16으로 나눠주고..

나머지를 거꾸로 쓰면 되겠어요.

16 )  450

16 )   28 ....2

16 )     1 ....12(C)  ↑          나머지를 거꾸로 쓰면 1C2(16) 이렇게 됩니다.

           0 ....1

16진법에서는 10은 A, 11은 B,12는 C,13은 D,14는 E, 15는 F로 씁니다^^

그래서 답은 1C2(16)입니다.

http://dodnet.tistory.com/685 꼭 참고해라!

비트연산에서 말이다..왼쪽 쉬프트는 원본 = 원본 * 2^쉬프트 된 수

오른쪽 쉬프는 원본 = 원본 / 2^쉬프트 된 수 이렇게 표현이 된다.

---

이야 ㅋㅋ 컴퓨터 메모리 구조다 !!

메모리 구역은

코드

전역

스택

자유(힙)

먼저 코드부터c++ 프로그램은 단지 cpp파일에 담긴 텍스트일 뿐이다. 컴퓨터는 그것이 뭔지 모른다..그래서..컴파일러를 통해서 소스 코드를 프로세서가 인식하는 명령들로 변환해야하는데..운영체제가 프로그램을 실행할때 운영체제는 실행 파일의 프로그램 코드를 읽어서 코드 메모리에 넣는다.

전역은..전역변수가 들어가있는곳..data segment라고 하는게 맞음..컴파일러는 실제 실행 파일 안에 그 전역변수들의 자리를 마련한다.

정적변수들 역시 전역 메모리 영역ㄷ에 들어간다..근데 그렇다고 전역변수가 되는건 아니지롱..

그리고 이제 스택 스택메모리는 스택자료구조랑 동일한 작동방식을 갖는다..

지역변수~ 매개변수 ~ (이친구들은 지역변수보다 먼저 스택에 들어감..) 반환값 ~(사실 매개변수나 지역변수들보다도 먼저 스택에 쌓이는..왜냐면 함수가 실행되기전 스택에 놓인다..그 시점에서 반환값은 자리를 미리 차지해두기 위한 것일뿐..실체는 아님!이후 함수가 반환할때 실체가 들어간다)

마지막 히입~힙(이건 힙자료구조랑 작동방식이 전혀 틀리다 ㅋㅋ)

---

단짠단짠 STL 간딴간딴 기본 상식

STL map은 레드 블랙트리로 구현되어있음..

순차컨테이너 vector list deque ㅋㅋ(이건 앞 뒤 삽입이 졸라 빠른 O(c)이다. 백터도 사실 끝에 추가는 O(c)다 그외의 삽입은 O(n)이다, 근데 이건 앞뒤는 빠른데..중간은 역시나 O(n)다 ㅠ)

deque 자료구조는 일방적으로 일련의 연결된 메모리 조각들로 구현된다. deque가 꽉 찬 상태에서 deque 끝에 항목을 추가하면 새로운

메모리 조각이 할당되고 추가된 항목은 메모리 조각의 처음부분에 놓인다...항목을 deque의 제일 앞에 추가하면..역시 새 메모리 조각이 할당되고..

추가된 항목은 새 조각의 끝에 놓인다.. 

새로운 메모리 조각  / 꽉 찬 deque / 새로운 메모리 조각

이 상태에서..연결성을 얻기위해..!!

이런 특징 덕분에 벡터나 배열과는 달리 컨테이너 제일 앞에 새항목을 추가하는 시간이 O(c)이다 그러나 색인으로 특정 항목을 조회하는 시간은

벡터보다 길다..왜냐고? 색인이 가리키는 항목을 조회하려면 먼저 그 메모리 조각부터 찾아야 하거든 ㅋㅋ

아 그리고 deque는 메모리 조각이 비어도 그 메모리 조각을 해제하지 않아.따라서 메모리가 낭비될 수도 있거든..

만약에 뒤에 항목들을 삽입하고 그만큼 항목들을 제거하는일을 반보갛면..개수는 변함없지만..항목들은 점차 다음 메모리 조각으로 밀리고 ㅋㅋ

빈 조각들이 쌓인다 앜 ㅋㅋ

연관컨테이너! 양방향! set multi set map multi map!

컨테이너 어댑터로 stack queue priority_queue가 있엉 ㅋ

아 근데 말이야 이 컨테이너 어댑터의 목적은 서로 다른 컨테이너들을 동일한 인터페이스(여기선 ㄴ스택 큐 이런걸 이야기해 ㅎ 컨테이너 어댑터를 

이야기하지..)에 적응시키는거야...스택이 연결목록이나 배열로도 구현되는거랑 같지요...

그러나! 우선순위큐만은 임의 접근 컨테이너들만 지원해 ㅋㅋ