std::stack이 기본적으로 std::deque를 사용하는 이유는 무엇입니까?

Question

컨테이너를 스택에서 사용하는 데 필요한 유일한 작업은 다음과 같습니다.

• 뒤쪽에()
• push_back()
• 팝백()

기본 컨테이너가 벡터가 아닌 데크인 이유는 무엇입니까?

push_front()가 효율적인 작업이 되도록 재할당을 해제하여 front() 전에 요소 버퍼를 제공하지 않습니까?이러한 요소는 스택의 컨텍스트에서 절대 사용되지 않으므로 낭비되지 않습니까?

벡터 대신 이런 방식으로 deque를 사용하는 데 오버헤드가 없다면 왜 Priority_queue의 기본값이 Deque가 아닌 벡터인가요?(priority_queue에는 front(), push_back() 및 pop_back()이 필요합니다 - 기본적으로 스택과 동일)

---

아래 답변을 기반으로 업데이트되었습니다.

deque가 일반적으로 구현되는 방식은 고정 크기 배열의 가변 크기 배열인 것으로 보입니다.이는 벡터(재할당 및 복사가 필요함)보다 빠르게 성장하므로 요소 추가 및 제거가 전부인 스택과 같은 것의 경우 deque가 더 나은 선택일 가능성이 높습니다.

Priority_queue에는 제거 및 삽입 시마다 pop_heap() 또는 push_heap()을 실행해야 하므로 인덱싱이 많이 필요합니다.어쨌든 요소를 ​​추가하는 것은 여전히 ​​​​상각 상수이기 때문에 이것은 아마도 벡터를 더 나은 선택으로 만들 것입니다.

Answer 1

컨테이너가 커짐에 따라 벡터를 재할당하려면 모든 요소를 ​​새 메모리 블록에 복사해야 합니다.데크를 늘리면 새 블록이 할당되고 이를 블록 목록에 연결하므로 복사본이 필요하지 않습니다.

물론 원하는 경우 다른 지원 컨테이너를 사용하도록 지정할 수도 있습니다.따라서 스택이 많이 성장하지 않을 것으로 예상되는 경우 deque 대신 벡터를 사용하도록 지시하십시오.

Answer 2

Herb Sutter의 글 보기 54주차 전문가 벡터와 데크의 상대적인 장점 중 어느 쪽이든 가능합니다.

Priority_queue와 queue 사이의 불일치는 단순히 다른 사람들이 이를 구현했기 때문이라고 생각합니다.