deque에 벡터 사용을 선호하는 이유
이후
- 둘 다 인접한 메모리 컨테이너입니다.
- 기능면에서 deque는 벡터가 가진 거의 모든 것을 가지고 있습니다. 앞쪽에 삽입하는 것이 더 효율적이기 때문입니다.
왜 whould 사람을 선호 std::vector하는 std::deque?
A의 요소 deque입니다 하지 메모리에 연속; vector요소가 보장됩니다. 따라서 연속 배열이 필요한 일반 C 라이브러리와 상호 작용해야하거나 공간 지역성에 대해 (많이) 신경 쓰는 경우 vector. 또한 추가 부기가 있으므로 다른 작업은 동등한 vector작업 보다 (약간) 더 비쌉니다 . 반면에 많은 / 대규모 인스턴스를 사용 vector하면 불필요한 힙 조각화 가 발생할 수 있습니다 (에 대한 호출 속도 저하 new).
또한 StackOverflow의 다른 곳에서 지적했듯이 http://www.gotw.ca/gotw/054.htm 에서 더 좋은 토론이 있습니다 .
차이점을 알기 위해서는 deque일반적으로 구현되는 방법을 알아야합니다 . 메모리는 동일한 크기의 블록으로 할당되며 함께 연결됩니다 (배열 또는 가능한 벡터로).
따라서 n 번째 요소를 찾으려면 적절한 블록을 찾은 다음 그 안의 요소에 액세스합니다. 이것은 항상 정확히 2 회 조회이기 때문에 일정한 시간이지만 여전히 벡터보다 많습니다.
vector또한 C API이거나 포인터와 길이를 사용할 수 있다는 점에서 더 다양하기 때문에 연속 버퍼를 원하는 API 와도 잘 작동합니다. (따라서 아래에 벡터 또는 일반 배열을 가질 수 있으며 메모리 블록에서 API를 호출 할 수 있습니다).
어디 deque가 그것의 가장 큰 장점은 다음과 같습니다
- 양쪽 끝에서 컬렉션을 늘리거나 줄일 때
- 매우 큰 컬렉션 크기를 다룰 때.
- bool을 다룰 때 bitset보다는 bool을 원합니다.
두 번째는 덜 알려져 있지만 매우 큰 컬렉션 크기의 경우 :
- 재 할당 비용이 큽니다.
- 연속적인 메모리 블록을 찾아야하는 오버 헤드는 제한적이므로 메모리가 더 빨리 부족할 수 있습니다.
과거에 대규모 컬렉션을 처리하고 연속 모델에서 블록 모델로 이동할 때 32 비트 시스템에서 메모리가 부족해지기 전에 컬렉션의 약 5 배를 저장할 수있었습니다. 이는 부분적으로 재 할당 할 때 요소를 복사하기 전에 이전 블록과 새 블록을 실제로 저장해야하기 때문입니다.
이 모든 것을 말했듯이 std::deque"낙관적"메모리 할당을 사용하는 시스템에서 문제가 발생할 수 있습니다 . a의 재 할당을 위해 큰 버퍼 크기를 요청하려는 시도는를 사용하여 vector어느 시점에서 거부 될 수 있지만 bad_alloc, 할당 자의 낙관적 특성은 항상 a가 요청한 더 작은 버퍼에 대한 요청을 허용 할 deque가능성이 높으며 메모리를 확보하기 위해 프로세스를 종료하는 운영 체제. 어느 쪽을 선택하든 너무 즐겁지 않을 수 있습니다.
이러한 경우의 해결 방법은 시스템 수준 플래그를 설정하여 낙관적 할당을 재정의하거나 (항상 가능한 것은 아님) 메모리 사용량을 확인하는 자체 할당자를 사용하거나 이와 유사한 것을 사용하여 메모리를 다소 수동으로 관리하는 것입니다. 분명히 이상적이지 않습니다. (벡터 선호에 대한 귀하의 질문에 답할 수 있습니다 ...)
벡터와 deque를 여러 번 구현했습니다. deque는 구현 관점에서 훨씬 더 복잡합니다. 이러한 복잡성은 더 많은 코드와 더 복잡한 코드로 이어집니다. 따라서 벡터보다 deque를 선택하면 일반적으로 코드 크기가 표시됩니다. 또한 코드가 벡터가 뛰어난 기능 (예 : push_back) 만 사용하는 경우 약간의 속도 저하를 경험할 수 있습니다.
양단 대기열이 필요한 경우 deque가 확실한 승자입니다. 그러나 대부분의 삽입과 지우기를 뒤쪽에서 수행한다면 벡터가 확실한 승자가 될 것입니다. 확실하지 않은 경우 typedef로 컨테이너를 선언하고 (앞뒤로 쉽게 전환 할 수 있도록) 측정합니다.
std::deque지속적인 메모리를 보장하지 않으며 인덱스 액세스의 경우 다소 느립니다. 데크는 일반적으로 "벡터 목록"으로 구현됩니다.
http://www.cplusplus.com/reference/stl/deque/ 에 따르면 , "벡터와 달리 deque는 연속 된 저장 위치에 모든 요소가 있다고 보장되지 않으므로 포인터 산술을 통한 안전한 액세스 가능성을 제거합니다."
Deques는 부분적으로 연속적인 메모리 레이아웃을 가질 필요가 없기 때문에 조금 더 복잡합니다. 해당 기능이 필요한 경우 데크를 사용하지 마십시오.
(이전에 내 대답은 표준화의 부족을 가져 왔지만 (위와 동일한 소스에서 "데크는 특정 라이브러리에 의해 다른 방식으로 구현 될 수 있습니다") 실제로 거의 모든 표준 라이브러리 데이터 유형에 적용됩니다.)
deque는 요소에 대한 임의 액세스를 허용하는 시퀀스 컨테이너이지만 연속 저장소가 있다고 보장되지는 않습니다.
각 케이스의 성능 테스트를하는 것이 좋은 생각이라고 생각합니다. 그리고이 테스트에 의존하여 결정을 내립니다.
대부분의 경우 std::deque보다 선호합니다 std::vector.
이러한 테스트 결과 (소스 포함)에 따라 deque보다 벡터를 선호하지 않습니다 .
Of course, you should test in your app/environment, but in summary:
- push_back is basically the same for all
- insert, erase in deque are much faster than list and marginally faster than vector
Some more musings, and a note to consider circular_buffer.
On the one hand, vector is quite frequently just plain faster than deque. If you don't actually need all of the features of deque, use a vector.
On the other hand, sometimes you do need features which vector does not give you, in which case you must use a deque. For example, I challenge anyone to attempt to rewrite this code, without using a deque, and without enormously altering the algorithm.
참고URL : https://stackoverflow.com/questions/5345152/why-would-i-prefer-using-vector-to-deque
'Program Tip' 카테고리의 다른 글
| JavaScript를 통해 도메인 이름을 얻는 방법은 무엇입니까? (0) | 2020.10.18 |
|---|---|
| session.connection ()은 Hibernate에서 더 이상 사용되지 않습니까? (0) | 2020.10.18 |
| awk에서 탭으로 구분 된 값 (0) | 2020.10.18 |
| Java : 문자열 (IP를 나타내는)을 InetAddress로 변환 (0) | 2020.10.18 |
| 사용자 정의보기가있는 UIBarButtonItem이 왼쪽 또는 오른쪽 탐색 모음 항목으로 사용될 때 iOS 7에서 제대로 정렬되지 않음 (0) | 2020.10.18 |