Deque와 List STL 컨테이너의 차이점은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1436020

  •  07-07-2019
  •  | 
  •  

문제

둘의 차이점은 무엇입니까? 나는 방법이 모두 동일하다는 것을 의미합니다. 따라서 사용자의 경우 동일하게 작동합니다.

그 맞습니까??

도움이 되었습니까?

해결책

(날짜이지만 여전히 매우 유용함)에서 SGI STL 요약 deque:

Deque는 벡터와 매우 흡사합니다. 벡터와 마찬가지로 요소에 대한 임의의 액세스, 시퀀스 끝에서 요소의 일정한 시간 삽입 및 제거 및 중간에 요소의 선형 시간 삽입 및 제거를 지원하는 시퀀스입니다.

Deque가 벡터와 다른 주된 방법은 Deque가 서열의 시작시 원소의 일정한 시간 삽입 및 제거를 지원한다는 것입니다. 또한 Deque에는 벡터의 용량 () 및 Reserve ()과 유사한 멤버 기능이 없으며 해당 멤버 기능과 관련된 반복자 유효성에 대한 보증을 제공하지 않습니다.

다음은 요약입니다 list 같은 사이트에서 :

목록은 이중 링크 된 목록입니다. 즉, 전방 및 후진 트래버스를 모두 지원하고 (상각) 일정한 시간 삽입 및 시작 또는 끝 또는 중간에 요소의 제거를 지원하는 시퀀스입니다. 목록은 삽입 및 스 플라이 싱이 반복자를 무효화하여 요소를 나열하지 않으며 제거 된 요소를 가리키는 반복자 만 무효화하는 중요한 속성을 가지고 있습니다. 반복자의 순서는 변경 될 수 있습니다 (즉, 목록 :: 반복자는 이전과 목록 작업 후에 다른 전임자 또는 후임자가있을 수 있지만 반복자 자체는 무효화되지 않으면 무효화되거나 다른 요소를 가리 키지 않습니다. 또는 돌연변이가 명시 적입니다.

요약하면 컨테이너는 공유 루틴을 가지고있을 수 있지만 해당 루틴의 시간 보증은 컨테이너마다 다릅니다.. 작업에 사용할 컨테이너를 고려할 때 매우 중요합니다. 어떻게 컨테이너는 가장 자주 사용됩니다 (예 : 삽입/삭제보다 검색을위한 더 많은)는 올바른 컨테이너로 안내하는 데 먼 길을갑니다.

다른 팁

차이점을 나열하겠습니다.

  • Deque 요소를 a동적 배열, 제공 무작위 액세스, 벡터와 거의 동일한 인터페이스를 가지고 있습니다.
  • 목록 요소를 a로 관리합니다이중 링크 된 목록 제공하지 않습니다 무작위 액세스.
  • 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 ()를 구현하기 때문에 말이 개처럼 작동한다고 가정해야합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top