STL 목록, 벡터 및 집합의 기본 데이터 구조는 무엇입니까?

STL 목록, 벡터 및 집합의 기본 데이터 구조는 무엇입니까?STL 목록, 벡터 및 집합의 기본 데이터 구조는 무엇입니까?

내 용액 :

벡터 (동적 할당) 배열
목록 :
세트 : 힙 (또는 가능한 한 채있는 모든 리프 노드와 이진 트리와 상단에 최소/최대 요소를 유지)

오른쪽?

2011-10-26 user1002288

구현이 정의되었지만 일반적으로'std :: vector'는 동적으로 할당 된 배열입니다. 'std :: list'는 이중 링크리스트입니다 (C++ 11은 단독 링크리스트 인'std :: forward_list'를 도입했습니다). 그리고'set'은 일반적으로 [red-black trees] (http : /en.wikipedia.org/wiki/Red%E2%80%93black_tree) 표준에서 정의 된 인터페이스의 상각 된 복잡성 및 동작 요구 사항에 맞는 것은 모두 수용 가능한 구현입니다. – birryree

명확히 코멘트에 기초하여, 다음은 가장 일반적인 선택이 있지만, 원하는 복잡성 및 기타 요인에 따라, 이러한 구현의 지원은 다를 수

Vector = 동적 배열을

목록 리사이징 = Doubly Linked List

설정 = Red/Black Tree (균형 이진 검색 트리)

나는 당신이 가능 힙과 BST를을 혼합 것 같아요. 힙은 트리로 시각화되지만 실제로는 인덱스 가능한 목록 구조 (예 : 배열 또는 벡터) 위에 만들어집니다. C++은 STL의 algorithm header을 통해 힙 기능을 제공합니다. BST는 효율적인 조회 (일반적으로 집합에 대해 원하는 것)에 사용되는 키/값 기반 구조에 가깝습니다.

출처

2011-10-26 15:25:15

목록이 이중 연결 목록입니다. – Praetorian

일반적으로 이는 사실이지만이 옵션이 구현에만 의존하는 것은 아닙니다. – avakar

@sgusc, 맵은 빨강 - 검정 트리이며, 요소가 정렬되지 않았기 때문에 설정되지 않습니다. 목록과 연결된 목록 간의 차이점은 무엇입니까? "연결된 목록"의 데이터 구조 란 무엇입니까? 목록? – user1002288

표준은 어떤 데이터 구조가 사용되는지에 대한 보증을 제공하지 않으며 단지 복잡성 만 보장되므로 구현시이를 충족하는 구조를 선택할 수 있습니다.

는 std::list 아마 doubly-linked list하고 std::set 가장 자주 self-balancing binary tree의 일종이며, std::vector는 일반적으로 dynamic array입니다 말했다.

출처

2011-10-26 15:31:33 Fanael

STL 목록, 벡터 및 집합의 기본 데이터 구조는 무엇입니까?

답변

관련 문제