C ++ STL이 "트리"컨테이너를 제공하지 않는 이유는 무엇입니까?

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

  •  03-07-2019
  •  | 
  •  

문제

C ++ STL이 "트리"컨테이너를 제공하지 않는 이유는 무엇이며 대신 사용하기에 가장 좋은 것은 무엇입니까?

트리를 성능 향상으로 사용하기보다는 나무로 객체의 계층 구조를 저장하고 싶습니다 ...

도움이 되었습니까?

해결책

나무를 사용하고 싶은 두 가지 이유가 있습니다.

나무와 같은 구조를 사용하여 문제를 반영하고 싶습니다.
이것을 위해 우리는 가지고 있습니다 그래프 라이브러리 부스트

또는 우리가 가지고있는 액세스 특성과 같은 트리가있는 컨테이너를 원합니다.

기본적 으로이 두 컨테이너의 특성은 실제로 나무를 사용하여 구현되어야합니다 (실제로 요구 사항은 아니지만).

이 질문도 참조하십시오.C 트리 구현

다른 팁

아마도 같은 이유로 부스트에는 트리 용기가 없기 때문일 것입니다. 이러한 컨테이너를 구현하는 방법에는 여러 가지가 있으며, 컨테이너를 사용하는 모든 사람을 만족시키는 좋은 방법은 없습니다.

고려해야 할 몇 가지 문제 :
- 노드 고정 또는 가변의 어린이 수가 있습니까?
- 노드 당 오버 헤드는 얼마입니까? - 즉, 부모 포인터, 형제 포인터 등이 필요합니까?
- 어떤 알고리즘을 제공해야합니까? - 다른 반복자, 검색 알고리즘 등

결국, 문제는 모든 사람에게 충분히 유용한 트리 용기가 너무 헤비급 일 것이기 때문에 그것을 사용하는 대부분의 사람들을 만족시킬 수 없다는 것입니다. 강력한 것을 찾고 있다면 그래프 라이브러리 부스트 본질적으로 트리 라이브러리가 사용될 수있는 슈퍼 세트입니다.

다른 일반 트리 구현은 다음과 같습니다.
- Kasper Peeters 'Tree.hh
- 어도비의 숲
- 핵심 :: 나무

STL의 철학은 컨테이너 구현 방법을 기반으로하지 않고 보증을 기반으로 컨테이너를 선택한다는 것입니다. 예를 들어, 선택한 컨테이너는 빠른 조회가 필요할 수 있습니다. 당신이주의를 기울이면, 컨테이너는 단방향 목록으로 구현 될 수 있습니다. 검색이 매우 빠르면 행복 할 것입니다. 어쨌든 내부를 만지지 않기 때문입니다. 반복자 또는 멤버 기능을 사용하여 액세스 할 수 있습니다. 코드는 컨테이너 구현 방식이 아니라 컨테이너가 얼마나 빨리, 또는 고정 및 정의 순서가 있는지 또는 공간에서 효율적인지 여부 등에 묶여 있습니다.

"나는 개체의 계층 구조를 나무로 저장하고 싶다"

C ++ 11이왔다 갔다했지만 여전히 std::tree, 아이디어가 나타 났지만 (참조 여기). 아마도 그들이 추가하지 않은 이유는 기존 컨테이너 위에 직접 구축하기가 쉽기 때문일 수 있습니다. 예를 들어...

template< typename T >
struct tree_node
   {
   T t;
   std::vector<tree_node> children;
   };

간단한 횡단은 재귀를 사용합니다 ...

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

계층 구조를 유지하려면 그리고 당신은 그것이 함께 일하기를 원합니다 STL 알고리즘, 그러면 상황이 복잡해 질 수 있습니다. 자체 반복자를 구축하고 일부 호환성을 달성 할 수 있지만 많은 알고리즘은 계층 구조에 대해서는 의미가 없습니다 (예 : 범위의 순서를 변경하는 것). 조차 정의 계층 구조 내 범위는 지저분한 사업 일 수 있습니다.

RB-Tree 구현을 찾고 있다면 stl_tree.h 당신에게도 적합 할 수 있습니다.

STD ::지도는 a를 기반으로합니다 빨간 검은 나무. 다른 사람도 사용할 수 있습니다 컨테이너 자신의 유형의 나무를 구현하는 데 도움이됩니다.

어떤면에서 STD ::지도는 트리 (균형 이진 트리와 동일한 성능 특성을 가져야 함)이지만 다른 트리 기능을 노출 시키지는 않습니다. 실제 트리 데이터 구조를 포함하지 않은 이유는 아마도 STL에 모든 것을 포함하지 않는 문제 일 것입니다. STL은 고유 한 알고리즘 및 데이터 구조를 구현하는 데 사용하는 프레임 워크로 볼 수 있습니다.

일반적으로 원하는 기본 라이브러리 기능이 있다면 STL에 있지 않은 경우 수정 사항은 보는 것입니다. 후원.

그렇지 않으면 a가 있습니다 다발 의 도서관 밖으로 거기, 나무의 요구에 따라.

모든 STL 컨테이너는 하나의 반복 메커니즘을 갖는 "시퀀스"로 표현됩니다. 나무는이 관용구를 따르지 않습니다.

STL은 "모든 것"라이브러리가 아니기 때문입니다. 그것은 본질적으로 물건을 만드는 데 필요한 최소 구조를 포함합니다.

이것은 유망한 것처럼 보이고 당신이 찾고있는 것 같습니다.http://tree.phi-sci.com/

IMO, 누락. 그러나 나는 STL에 트리 구조를 포함시키지 않아야할만한 충분한 이유가 있다고 생각합니다. 나무를 유지하는 데 많은 논리가 있으며 멤버는 기본으로 기능합니다 TreeNode 물체. 언제 TreeNode STL 헤더에 싸여있어 단지 지저분 해집니다.

예를 들어:

template <typename T>
struct TreeNode
{
  T* DATA ; // data of type T to be stored at this TreeNode

  vector< TreeNode<T>* > children ;

  // insertion logic for if an insert is asked of me.
  // may append to children, or may pass off to one of the child nodes
  void insert( T* newData ) ;

} ;

template <typename T>
struct Tree
{
  TreeNode<T>* root;

  // TREE LEVEL functions
  void clear() { delete root ; root=0; }

  void insert( T* data ) { if(root)root->insert(data); } 
} ;

STL 나무가없는 몇 가지 이유가 있다고 생각합니다. 주로 나무는 컨테이너 (목록, 벡터, 세트)와 같은 재귀 적 데이터 구조의 한 형태로, 올바른 선택을 까다로운 미세 구조를 가지고 있습니다. 또한 STL을 사용하여 기본 형태로 구성하기가 매우 쉽습니다.

유한 한 뿌리 나무는 클래스 A의 인스턴스와 뿌리가 떨어지는 (서브) 나무의 컬렉션을 나타내는 값 또는 페이로드를 갖는 컨테이너로 생각할 수 있습니다. 하위 트리를 비우는 나무는 잎과 함께 있습니다. 

template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};

template<class A>
struct b_tree : std::vector<b_tree>, A
{};

template<class A>
struct planar_tree : std::list<planar_tree>, A
{};

하나는 반복자 설계 등에 대해 조금 생각해야하며 어떤 제품 및 공동 제품 작업이 트리 사이에서 정의하고 효율적이어야하는지, 원래 STL을 잘 작성해야하므로 빈 세트, 벡터 또는 목록 컨테이너가 기본 케이스의 페이로드가 실제로 비어 있습니다.

나무는 많은 수학적 구조에서 필수적인 역할을합니다 (정육점, Grossman 및 Larsen의 고전 논문, 또한 결합 할 수있는 예와 열거에 사용되는 방법에 대한 Connes와 Kiemer의 논문 참조). 그들의 역할이 단순히 특정 다른 운영을 촉진하는 것이라고 생각하는 것은 옳지 않습니다. 오히려 그들은 데이터 구조로서의 근본적인 역할 때문에 이러한 작업을 촉진합니다.

그러나 나무 외에도 "공동 트리"도 있습니다. 무엇보다도 나무에는 뿌리를 삭제하면 모든 것을 삭제하는 속성이 있습니다.

트리의 반복자를 고려하십시오. 아마도 반복자의 간단한 스택, 노드 및 부모에게 뿌리까지 실현 될 것입니다. 

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

그러나 원하는만큼 많은 것을 가질 수 있습니다. 종합적으로 그들은 "나무"를 형성하지만 모든 화살표가 뿌리를 향한 방향으로 흐르는 경우,이 공동 트리는 반복적으로 반복적 인 반복적 인 반복자와 뿌리를 향해 반복 할 수 있습니다. 그러나 모든 인스턴스를 추적하는 것을 제외하고는 반복자의 앙상블을 삭제할 수 없으며 (다른 반복자는 알려지지 않았습니다).

나무는 엄청나게 유용하고 구조가 많기 때문에 확실히 올바른 접근 방식을 얻는 것이 심각한 도전입니다. 제 생각에 이것이 STL에서 구현되지 않은 이유입니다. 더욱이 과거에는 사람들이 종교를 얻는 것을 보았고 자체 유형의 인스턴스를 포함하는 컨테이너 유형에 대한 아이디어를 찾았습니다. 아마도 (작은) 나무의 빈 컬렉션. 현재 언어는 기본 생성자를 제공하는 도전없이이를 허용합니다. container<B> 힙 (또는 다른 곳)에 공간을 할당하지 않습니다. B, 등.

이것이 좋은 형태로 표준으로 들어가면 기뻐할 것입니다.

모든 STL 컨테이너는 반복자와 함께 사용할 수 있습니다. ``하나의 오른쪽 ''방식이 없기 때문에 반복자에게 나무를 가질 수 없습니다.

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