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

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

둘 사이의 차이점은 무엇입니까?제 말은 방법이 다 똑같다는 거예요.사용자의 경우 동일하게 작동합니다.

맞습니까?

차이점을 나열해 보겠습니다.

• Deque는 동적 배열로 요소를 관리하고 랜덤 액세스를 제공하며 벡터와 거의 동일한 인터페이스를 가지고 있습니다.
• 목록은 요소를 이중 연결 목록으로 관리하며 임의 액세스를 제공하지 않습니다.

---

• Deque는 끝과 시작 모두에 빠른 삽입 및 삭제 기능을 제공합니다.양쪽 끝까지 모든 요소를 이동하여 공간을 만들거나 공백을 채울 수 있기 때문에 중간에 요소를 삽입하고 삭제하는 속도가 상대적으로 느립니다.
• 목록에서 요소 삽입 및 제거는 양쪽 끝을 포함한 각 위치에서 빠릅니다.

---

• Deque: 시작 또는 끝 이외의 요소를 삽입하거나 삭제하면 deque의 요소를 참조하는 모든 포인터, 참조 및 반복기가 비활성화됩니다.
• 목록: 요소를 삽입하고 삭제해도 다른 요소에 대한 포인터, 참조 및 반복기가 무효화되지 않습니다.

---

복잡성

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

의 SGI STL 요약(날짜는 되었지만 여전히 매우 유용함)에서:

데케는 벡터와 매우 유사합니다. 벡터와 마찬가지로 요소에 대한 무작위 액세스, 시퀀스 끝에 요소의 일정한 시간 삽입 및 제거, 그리고 중간에 요소의 선형 시간 삽입 및 제거를 지원하는 시퀀스입니다.

deque가 벡터와 다른 주요 방법은 deque가 시퀀스 시작 시 요소의 일정한 시간 삽입 및 제거를 지원한다는 것입니다.또한 deque는 벡터의 capacity() 및 reserve()와 유사한 멤버 함수를 가지고 있지 않으며, 이러한 멤버 함수와 관련된 반복기 유효성에 대한 어떠한 보증도 제공하지 않습니다.

다음은 동일한 사이트의 요약입니다.

목록은 이중으로 연결된 목록입니다.즉, 순방향 및 역방향 트래버설을 모두 지원하는 시퀀스이며, 시작 또는 끝 또는 중간에 요소의 (모티브화된) 일정한 시간 삽입 및 제거를 지원합니다.목록에는 삽입 및 스플라이싱을 통해 요소를 나열하는 반복기가 무효화되지 않으며 제거하더라도 제거된 요소를 가리키는 반복기만 무효화된다는 중요한 속성이 있습니다.반복기의 순서는 변경될 수 있지만(즉, 목록:: 반복기는 목록 작업 후 이전과 다른 이전 또는 후속을 가질 수 있습니다), 무효화 또는 변환이 명시적이지 않은 한 반복기 자체는 무효화되거나 다른 요소를 가리키도록 만들어지지 않습니다.

요약하면 컨테이너에는 공유 루틴이 있을 수 있지만 해당 루틴에 대한 시간 보장은 컨테이너마다 다릅니다.이는 작업에 사용할 컨테이너를 고려할 때 매우 중요합니다. 컨테이너가 가장 자주 사용되는 방법(예: 삽입/삭제보다 검색에 더 많은 것)을 고려하면 올바른 컨테이너로 이동하는 데 도움이 됩니다.

std::list 기본적으로 이중으로 연결된 목록입니다.

std::deque반면에, 더 비슷하게 구현됩니다.std::vector인덱스별 액세스 시간이 일정하고 시작과 끝에 삽입 및 제거 기능이 있어 목록과는 성능 특성이 크게 다릅니다.

저는 C++ 수업을 듣는 학생들을 위해 삽화를 만들었습니다.이는 GCC STL 구현(https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_deque.h 및 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_list.h) 의 구현을 기반으로 합니다.

양끝 대기열

컬렉션의 요소는 메모리 블록에 저장됩니다.블록당 요소 수는 요소의 크기에 따라 달라집니다. 요소가 클수록 블록당 요소 수가 적습니다.기본적인 희망은 요소의 유형에 관계없이 블록의 크기가 비슷하다면 대부분의 경우 할당자에게 도움이 될 것이라는 것입니다.

메모리 블록을 나열하는 배열(GCC 구현에서는 맵이라고 함)이 있습니다.시작 부분에 공간이 있을 수 있는 첫 번째 블록과 끝 부분에 공간이 있을 수 있는 마지막 블록을 제외한 모든 메모리 블록이 가득 찼습니다.지도 자체가 중앙에서 바깥쪽으로 채워집니다.은 어떻은게로와 대반것이 입니다.std::vector양쪽 끝의 삽입은 일정한 시간에 수행할 수 있습니다. 유사게하와 std:::vector랜덤 액세스는 일정한 시간에 가능하지만, 하나의 방향 대신 두 개의 방향이 필요합니다.와유게하와 std::vector그리고 반대로std::list데이터 구조의 상당 부분을 재구성해야 하기 때문에 중간에 요소를 제거하거나 삽입하는 데 비용이 많이 듭니다.

이중 링크 리스트

이중으로 연결된 목록이 더 일반적일 수 있습니다.모든 요소는 다른 요소와 독립적으로 할당된 자체 메모리 블록에 저장됩니다.각 블록에는 요소의 값과 이전 요소에 대한 포인터와 다음 요소에 대한 포인터 두 개가 있습니다.목록의 임의 위치에 요소를 삽입하거나 요소의 하위 체인을 한 목록에서 다른 목록으로 이동하는 작업(스플리싱이라고 함)을 매우 쉽게 할 수 있습니다. 삽입 지점의 시작과 끝에서 포인터를 업데이트하기만 하면 됩니다.단점은 인덱스를 사용하여 하나의 요소를 찾으려면 포인터 체인을 걸어야 하기 때문에 랜덤 액세스는 목록의 요소 수에 선형 비용이 든다는 것입니다.

또 다른 중요한 보증은 각 컨테이너가 데이터를 메모리에 저장하는 방식입니다.

• 벡터는 연속된 단일 메모리 블록입니다.
• deque는 연결된 메모리 블록 집합으로, 각 메모리 블록에 두 개 이상의 요소가 저장됩니다.
• 목록은 메모리에 분산된 요소들의 집합입니다. 즉, 메모리 "블록"당 하나의 요소만 저장됩니다.

deque는 벡터와 목록의 장점을 각각의 단점 없이 균형 있게 조정하기 위해 설계되었습니다.메모리 제한 플랫폼(예: 마이크로컨트롤러)에서 특히 흥미로운 컨테이너입니다.

메모리 저장 전략은 종종 간과되지만 특정 애플리케이션에 가장 적합한 컨테이너를 선택해야 하는 가장 중요한 이유 중 하나입니다.

아니요. 앞뒷면만 O(1)삽입 및 삭제를 지원하는 데데크입니다.예를 들어, 그것은 랩어라운드와 함께 벡터로 구현될 수 있습니다.또한 O(1) 랜덤 액세스를 보장하므로 이중으로 연결된 목록을 (단순히) 사용하지 않을 수 있습니다.

사이의 현저한 차이점 중에서.deque그리고.list

• 위해서deque:

  나란히 보관된 항목;

  양면(전면, 후면)에서 데이터를 추가하는 데 최적화됨.

  숫자(정수)로 인덱싱된 요소입니다.

  반복자 및 요소의 인덱스를 사용하여 검색할 수 있습니다.

  데이터에 대한 시간 액세스가 더 빠릅니다.

• 위해서list

  메모리에 "임의로" 저장된 항목;

  반복자만 검색할 수 있습니다.

  중간에 삽입 및 제거할 수 있도록 최적화되었습니다.

  공간적 위치가 매우 열악하기 때문에 데이터에 대한 시간 액세스가 더 느리고 반복이 더 느립니다.

  대형 요소를 매우 잘 처리합니다.

두 STL 용기 간의 성능을 비교하는 다음 링크도 확인할 수 있습니다(std::vector 포함).

유용한 정보를 공유했으면 좋겠습니다.

성능 차이는 다른 사람들에 의해 잘 설명되었습니다.저는 객체 지향 프로그래밍에서 유사하거나 심지어 동일한 인터페이스가 흔하다는 것을 덧붙이고 싶었습니다. 객체 지향 소프트웨어를 작성하는 일반적인 방법론의 일부입니다.두 클래스가 동일한 인터페이스를 구현한다는 이유만으로 동일한 방식으로 작동한다고 가정해서는 안 되며, 두 클래스 모두 공격()과 make_noise()를 구현하기 때문에 말이 개처럼 작동한다고 가정해야 하는 것과 마찬가지입니다.

다음은 O(1) 조회 및 O(1) 정확한 LRU 유지관리를 제공하는 정렬되지 않은 맵인 목록의 개념 증명 코드 사용입니다.지우기 작업에서 살아남으려면 (삭제되지 않은) 반복기가 필요합니다.GPU 메모리의 CPU 포인터를 위해 O(1) 임의로 큰 소프트웨어 관리 캐시에서 사용할 계획입니다.Linux O(1) 스케줄러에 노드를 지정합니다(LRU <-> 프로세서당 대기열 실행).unordered_map은 해시 테이블을 통해 일정한 시간 액세스를 제공합니다.

#include <iostream> 
#include <list> 
#include <unordered_map>  
using namespace std; 

struct MapEntry {
  list<uint64_t>::iterator LRU_entry;
  uint64_t CpuPtr;
};
typedef unordered_map<uint64_t,MapEntry> Table;
typedef list<uint64_t> FIFO;
FIFO  LRU;        // LRU list at a given priority 
Table DeviceBuffer; // Table of device buffers

void Print(void){
  for (FIFO::iterator l = LRU.begin(); l != LRU.end(); l++) {
    std::cout<< "LRU    entry "<< *l << "   :    " ;
    std::cout<< "Buffer entry "<< DeviceBuffer[*l].CpuPtr <<endl;
  }  
}
int main() 
{ 

  LRU.push_back(0);
  LRU.push_back(1);
  LRU.push_back(2);
  LRU.push_back(3);
  LRU.push_back(4);

  for (FIFO::iterator i = LRU.begin(); i != LRU.end(); i++) {
    MapEntry ME = { i, *i}; 
    DeviceBuffer[*i] = ME;
  }

  std::cout<< "************ Initial set of CpuPtrs" <<endl;
  Print();

  {
    // Suppose evict an entry - find it via "key - memory address uin64_t" and remove from 
    // cache "tag" table AND LRU list with O(1) operations
    uint64_t key=2;
    LRU.erase(DeviceBuffer[2].LRU_entry);
    DeviceBuffer.erase(2);
  }

  std::cout<< "************ Remove item 2 " <<endl;
  Print();

  { 
    // Insert a new allocation in both tag table, and LRU ordering wiith O(1) operations
    uint64_t key=9;
    LRU.push_front(key); 
    MapEntry ME = { LRU.begin(), key };
    DeviceBuffer[key]=ME;
  }

  std::cout<< "************ Add item 9  " <<endl;
  Print();

  std::cout << "Victim "<<LRU.back()<<endl;
} 

언급URL : https://stackoverflow.com/questions/1436020/whats-the-difference-between-deque-and-list-stl-containers