std :: deque를 어떻게 구현합니까?

Question

지금까지 필자는 std::deque이 구현 된 방법을 배웠고 데이터가 실제로 저장되는 n 바이트 배열에 대한 포인터 배열과 같은 것을 발견했습니다. 이제 나는 deques와 관련된 몇 가지 질문을했습니다.

질문은 다음과 같습니다 : 그것에 대해 내 현재의 지식을 설명

그림 구조의

1. push_front 작업을 수행하고 데이터의 여유 공간은 블록 0이되고 있지 때 새 데이터 블록이 힙에 할당되고이 새로 할당 된 메모리에 대한 포인터가 일반 배열과 마찬가지로 'Map'배열에 삽입됩니다. O (number_of_blocks) 시간에 그렇습니까?

2. 이 동물을 어떻게 분류합니까? 더 잘 상상할 수없는 모든 데이터를 배열에 복사, 정렬 및 다시 넣어. 하지만이 방법은 O (n) 보조 메모리가 필요합니다 ...하지만! std::sort은 std::vector 및 std::deque을 모두 분류 할 수있는 유사한 인터페이스를 제공합니다. 서로 다른 데이터 구조에 대한 서로 다른 알고리즘은 어떻게 구현됩니까? 템플릿 전문화 사용? 그렇다면 을 사용하여 std::list을 (를) 정렬 할 수없는 이유는 무엇입니까? 또는 std::sort은이 컨테이너의 내부 구조를 신경 쓰지 않고 std::vector 및 std::deque (예 : operator[], size() 등)의 두 가지 요소에서 비슷하게 반복기 및 방법을 사용하고 있을까요? "std::sortstd::list을 정렬 할 수없는 이유는 무엇입니까?" 분명해진다.

3. 데이터 블록의 크기는 어떻게 선택됩니까? "구현에 따라 다름"이라고 말하지만 솔루션 구현에 대한 다른 구현 및 동기에 대해 자세히 알려주십시오.

여기에 설명이 필요합니다. 감사합니다. .

Answer 1

첫 번째 질문에 대답하려면 예, 그렇습니다. 이 접근법은 다중 레벨 계층 구조로 확장 될 수 있음을 알 수 있습니다. 그러나 실용적인 구현은 일반적으로 그림에 표시된 것과 같이 2 수준 구조를 유지합니다.

두 번째 질문으로 약 std::sort을 입력하면 std::sort은 실제 컨테이너의 메커니즘에 대해 모르고 작동합니다. if는 다양한 랜덤 액세스 반복자에서 작동합니다. std::deque의 반복자는 임의 접근 반복자이므로 std::sort은 std::deque에 적용 할 수 있습니다. 그리고 실제로 그러한 데이터 구조의 요소에 무작위로 접근하는 것이 효율적이라고 주장 할 수 있습니다. 벡터에서 무작위 액세스만큼 효율적이지는 않지만 std::sort의 컨텍스트에서 이해하는 것이 여전히 효율적입니다.

std::list의 반복자는 임의 액세스 반복자가 아니기 때문에 을 std::list과 함께 사용할 수 없습니다. 원하는 경우 std::list에 대한 임의 액세스 반복기의 자체 (느린) 버전을 구현할 수 있습니다. 이러한 반복자 범위에 std::sort을 적용 할 수 있으므로 std::list을 std::sort으로 정렬 할 수 있습니다. 그러나 명백한 이유 때문에 그것은 비효율적 일 것입니다.

std::deque의 경우 임의 액세스 반복기는 충분히 효율적입니다.

세 번째 질문에 답변 할 준비가되지 않았습니다. 실제로 이러한 크기가 실험을 통해 경험적으로 선택된다는 사실을 알면 놀라지 않을 것입니다. 그리고 물론, "한 가지 크기가 모두 적합합니다"해결책은 없을 것입니다.