가장 빠른 대기열 컨테이너 (C++)

Question

대기열 및 우선 순위 대기열을 사용하여 많은 양의 데이터를 아주 빨리 펌프 할 계획입니다.

따라서 q, pq가 더하기 및 빼기에 응답해야합니다.

기본 컨테이너로 벡터, 목록 또는 양털을 사용하면 어떤 장점이 있습니까?

업데이트

: 글을 쓰는 시점에서 , 마이크 시모어 스티브 타운센드의 답변 모두 아래 읽을 가치가있다. 둘 다 고마워!

Answer 1

예상되는 사용 사례와 유사한 상황에서 선택 효과 성능을 측정하는 것이 유일한 방법입니다.

std::queue의 경우 : 그것은 여기에 몇 가지 관찰하고, 말했다

• std::deque은 일반적으로 최선의 선택이; 그것은 필요한 모든 작업을 일정한 시간에 지원하고, 메모리가 커질 때 청크로 할당합니다.
• std::list도 필요한 작업을 지원하지만 더 많은 메모리 할당으로 인해 느려질 수 있습니다. 특수한 상황에서는 전용 객체 풀에서 할당하여 좋은 결과를 얻을 수 있지만 완전히 간단하지는 않습니다.
• std::vector은 pop_front() 작업이 없으므로 사용할 수 없습니다. 그러한 작업은 나머지 요소를 모두 옮겨야하므로 느릴 수 있습니다. 잠재적으로 더 빠르게

하지만 덜 유연한 대안은 고정 크기 어레이 (예컨대 std::array, 또는 조정되지 않은 std::vector) 위에 원형 버퍼를 구현하는 것이다. 오류를보고하거나 더 큰 버퍼를 할당하고 모든 데이터를 복사하여 오류가 가득 찬 경우를 처리해야합니다. std::priority_queue를 들어

:

• std::vector은 일반적으로 최선의 선택; 기하 급수적으로 (메모리 할당 횟수를 줄임) 커지고, 액세스가 매우 빠른 간단한 데이터 구조입니다. 이터레이터는 단순히 포인터를 감싸는 래퍼로 구현할 수 있습니다.
• std::deque은 일반적으로 선형 적으로 커짐에 따라 느려질 수 있으며 (더 많은 메모리 할당이 필요함) 액세스는 벡터보다 복잡합니다.
• std::list은 임의 액세스를 제공하지 않으므로 사용할 수 없습니다.

요약하면 일반적으로 기본값이 가장 적합하지만 속도가 중요한 경우 대안을 측정하십시오.

Answer 2

deque의 래퍼 인 (적어도 기본적으로) 기본 대기열에 std::queue을 사용합니다. 그것이 당신을 위해 작동하지 않는 경우에 더 특별한 목적을하십시오.

std::priority_queue은 (기본적으로 vector 이상)를 존재하지만 추가 의미가 더 가능성이 당신이 특정 액세스 패턴 관찰 퍼포 레이션에 따라, 여기에 자신의 롤 할 수 있다고합니다.

vector에는 저장 특성이있어 데이터 집합의 전면에서 제거하는 것이 적합하지 않습니다. 당신이 할 때마다 매번 내려지기 위해서 많이 걸어 다니. pop_front. 간단한 대기열의 경우이를 피하십시오.

list은 계약을 통해 필요없는 기능을 제공해야하므로 고가의 대기열에 비해 비용이 많이 든다. 우선 순위 대기열로 사용할 수 있지만 내 본능은 항상 STL을 신뢰하는 것입니다.

Answer 3

vector은 빠른 삽입이 끝에 있고 빠른 제거도 끝에 있으므로 스택을 구현합니다. FIFO 대기열을 원하면 vector이 잘못된 구현입니다.

deque 또는 list은 둘 다 일정 시간 삽입을 제공합니다. list은 중간에서 빠르게 요소를 이동하려는 LRU 캐시에 유용하며 반복 정도에 상관없이 반복기를 유효하게 유지하려는 곳에 적합합니다. deque은 일반적으로 삽입 및 삭제가 끝에있을 때 사용됩니다.

귀하의 컬렉션에 대해 물어볼 필요가있는 주요 사항은 여러 스레드에 의해 액세스되는지 여부입니다. 나는 그들이 일종의 가정이라고 생각합니다.이 경우 주된 목표 중 하나는 잠금을 줄이는 것입니다. 이것은 적어도 multi_push 및 multi_get 기능이있어 잠금없이 한 번에 둘 이상의 요소를 넣을 수 있으면 가장 좋습니다.

잠금 해제 컨테이너 또는 반 잠금 해제 컨테이너가 있습니다.

작업이 모두 일정 시간 동안 이루어지는 경우 컬렉션의 성능보다 잠금 전략이 더 중요하다는 것을 알 수 있습니다.