boost :: mutable_queue를 반복하는 방법

Question

우선 순위 키를 늘리거나 줄일 수있는 우선 순위 큐가 필요합니다. 그래서 boost :: mutable_queue는 문서의 부족에도 불구하고 완벽 해 보였다.

문제는 큐의 모든 요소에 대해 어느 정도 반복해야한다는 것입니다. 어떻게해야합니까?

또는 (부스트가 바람직 함) 작동하는 데이터 구조가 있습니까?

Answer 1

대기열은 반복 할 수 없습니다. 대기열의 요점은 대기열 앞에있는 요소 만 볼 수 있다는 것입니다.

반복하려는 경우 바로 주문한 std::set을 사용하는 것이 좋습니다. 요소를 수정하려면 요소를 제거한 다음 새 키로 다시 삽입해야합니다. mySet.begin() (iterator를 반환)을 사용하여 가장 높은 우선 순위 요소를 가져올 수 있습니다.

이상적으로는 힙을 사용하는 것이 좋습니다. STL은 힙을 만들기위한 함수를 제공하며, 이것은 std::priority_queue이 사용하는 것입니다. 그러나 인터페이스가 없기 때문에 힙의 키를 수정할 수 없습니다.

힙을 직접 관리 할 수 ​​있습니다. 그러나 문서화되지 않은 함수를 <heap.h>에서 사용해야합니다. 이 기능이 왜 this interview with Alexander Stepanov (STL의 발명가)에 문서화되어 있지 않은지에 대한 모든 내용을 읽을 수 있습니다. 분명히 STL이 너무 커서 원래의 표준에서 해시 맵에 일어난 일이기 때문에 "제거"되어야했습니다.

Answer 2

문제는 큐의 모든 요소에 대해 어느 정도 반복해야한다는 것입니다. 어떻게해야합니까?

mutable_queue은 단지 어댑터 일뿐입니다. 적절한 기본 컨테이너에 전달하십시오. 어댑터 사용으로 인해 사용 가능한 인터페이스가 수정됩니다. 기본적으로 큐는 반복을 허용하지 않습니다. 그렇다면이 어댑터를 가질 필요가 없습니다. this 제한에 대한 SGI STL 설명서를 참조하십시오.

또는 (부스트가 바람직 함) 작동하는 데이터 구조가 있습니까?

용도에 따라 다른 데이터 구조를 사용해야 할 수도 있습니다. 적절한 선택은 데이터 저장 및 액세스 방법에 따라 다릅니다. std::deque 컨테이너를 살펴볼 수 있습니다. 그러나 포함 된 객체의 상태의 일부로 우선 순위를 인코딩해야합니다.