deque와 list STL 컨테이너의 차이점은 무엇입니까?
둘의 차이점은 무엇입니까? 방법은 모두 동일합니다. 따라서 사용자의 경우 동일하게 작동합니다.
그 맞습니까??
(날짜이지만 여전히 매우 유용함) SGI STL 요약에서 deque:
데크는 벡터와 매우 유사합니다. 벡터와 마찬가지로 요소에 대한 임의 액세스, 시퀀스 끝에서 요소의 일정 시간 삽입 및 제거, 중간 요소의 선형 시간 삽입 및 제거를 지원하는 시퀀스입니다.
deque가 벡터와 다른 주된 방법은 deque가 시퀀스 시작 부분에서 요소의 상수 시간 삽입 및 제거를 지원한다는 것입니다. 또한 deque에는 벡터의 capacity () 및 reserve ()와 유사한 멤버 함수가 없으며 해당 멤버 함수와 관련된 반복기 유효성에 대한 보증을 제공하지 않습니다.
다음 list은 동일한 사이트 의 요약입니다 .
목록은 이중 연결 목록입니다. 즉, 순회 및 역 순회를 모두 지원하는 시퀀스이며 시작 또는 끝 또는 중간에 요소의 (상각) 일정 시간 삽입 및 제거를 지원합니다. 목록에는 삽입 및 스 플라이 싱이 목록 요소에 대한 반복기를 무효화하지 않으며 제거하더라도 제거 된 요소를 가리키는 반복기 만 무효화한다는 중요한 속성이 있습니다. 반복기의 순서는 변경 될 수 있지만 (즉, list :: iterator는 이전과 목록 작업 후 다른 선행 작업 또는 후속 작업을 가질 수 있음), 해당 무효화가 아닌 한 반복기 자체가 무효화되거나 다른 요소를 가리 키도록 만들어지지 않습니다. 또는 돌연변이가 명시 적입니다.
요약하면 컨테이너는 공유 루틴을 가질 수 있지만 이러한 루틴에 대한 시간 보장은 컨테이너마다 다릅니다 . 이는 작업에 사용할 컨테이너를 고려할 때 매우 중요 합니다 . 컨테이너가 가장 자주 사용되는 방식 (예 : 삽입 / 삭제보다 검색에 더 많이 사용)을 고려하면 올바른 컨테이너로 안내하는 데 큰 도움이됩니다. .
차이점을 나열하겠습니다.
- Deque 는 동적 배열로 요소를 관리하고 임의 액세스를 제공 하며 벡터와 거의 동일한 인터페이스를 가지고 있습니다.
- List 는 요소를 이중 연결 목록 으로 관리하며 임의 액세스를 제공하지 않습니다 .
- Deque 는 끝과 시작 모두에서 빠른 삽입 및 삭제를 제공합니다. 공간을 확보하거나 간격을 채우기 위해 양쪽 끝 중 하나까지의 모든 요소를 이동할 수 있기 때문에 중간에 요소를 삽입하고 삭제하는 것이 상대적으로 느립니다.
- 에서는 목록 삽입 및 요소를 제거하는 단계를 포함하여 각각의 양단부 위치에서 빠르다.
- Deque : 시작 또는 끝 부분 이외의 요소 삽입 또는 삭제는 deque의 요소를 참조하는 모든 포인터, 참조 및 반복자를 무효화합니다.
- 목록 : 요소 삽입 및 삭제는 다른 요소에 대한 포인터, 참조 및 반복기를 무효화하지 않습니다.
복잡성
Insert/erase at the beginning in middle at the end
Deque: Amortized constant Linear Amortized constant
List: Constant Constant Constant
std::list 기본적으로 이중 연결 목록입니다.
std::deque반면에는 std::vector. 색인 별 액세스 시간이 일정하고 시작과 끝 부분의 삽입 및 제거가있어 목록과는 매우 다른 성능 특성을 제공합니다.
아니요. deque는 앞뒤에 O (1) 삽입 및 삭제 만 지원합니다. 예를 들어, 랩 어라운드가있는 벡터에서 구현 될 수 있습니다. 또한 O (1) 임의 액세스를 보장하기 때문에 이중 연결 목록을 사용하지 않는지 확인할 수 있습니다.
또 다른 중요한 보장은 각 컨테이너가 데이터를 메모리에 저장하는 방식입니다.
- 벡터는 연속 된 단일 메모리 블록입니다.
- deque는 연결된 메모리 블록의 집합으로, 각 메모리 블록에 둘 이상의 요소가 저장됩니다.
- 목록은 메모리에 분산 된 요소 집합입니다. 즉, 메모리 "블록"당 하나의 요소 만 저장됩니다.
deque는 벡터와 목록의 장점을 각각의 단점없이 균형 을 맞추기 위해 설계되었습니다 . 마이크로 컨트롤러와 같은 메모리 제한 플랫폼에서 특히 흥미로운 컨테이너입니다.
메모리 저장 전략은 종종 간과되지만 특정 애플리케이션에 가장 적합한 컨테이너를 선택하는 가장 중요한 이유 중 하나입니다.
성능 차이는 다른 사람들이 잘 설명했습니다. 객체 지향 소프트웨어를 작성하는 일반적인 방법론의 일부인 객체 지향 프로그래밍에서 유사하거나 동일한 인터페이스가 일반적이라는 점을 추가하고 싶었습니다. 두 클래스가 동일한 인터페이스를 구현하기 때문에 단순히 동일한 방식으로 작동한다고 가정해서는 안됩니다. 둘 다 attack () 및 make_noise ()를 구현하기 때문에 말이 개처럼 작동한다고 가정해야합니다.
'Program Club' 카테고리의 다른 글
| TensorFlow에서 일괄 정규화를 어떻게 사용할 수 있습니까? (0) | 2020.10.13 |
|---|---|
| C #에서 bool 읽기 / 쓰기 원 자성입니다. (0) | 2020.10.13 |
| Selenium WebDriver C #을 사용하여 드롭 다운에서 옵션을 선택하는 방법은 무엇입니까? (0) | 2020.10.13 |
| cntlm 구성 파일에 프록시 정보를 입력하는 방법은 무엇입니까? (0) | 2020.10.13 |
| 내 모든 프로젝트에 대해 맞춤법 검사를 비활성화하는 방법 (0) | 2020.10.13 |