확장 클래스와 인스턴스

Question

의 우리가이 개 클래스로 구성 RedBlack 트리 구현이 있다고 가정하자

• Tree은 - 트리의 Node *root에 대한 포인터를 보유하고 트리를 통해 모든 작업을 정의 (Insert, Delete 등)
• Node - Node *parent, , Node *right 노드 및 std::string key에 대한 포인터를 보유하는 데이터 저장소입니다. 이제 작업을

  void Tree::Insert(const std::string &key) 
  { 
      Node *z = new Node(key); 
      // adding node logic 
  } 
  

  :

Tree::Insert()는 다음 구현이있는 모든 노드는 창조의 시간을 저장한다.

제한 사항 : 기본 트리 구현은 가능한 한 적게 수정해야하며 특정 확장자에 대한 세부 정보를 포함해야합니다. 따라서 생성 시간 속성에 대해 알 필요가 없습니다.

내 생각 : NodeWithTime : Node을 확장하고 unsigned int creation_time 속성을 추가하십시오.

나는 막혔다 : 지금 노드를 어떻게 인스턴스화 할까?

모든 제안?

추 신 : 그것은 숙제가 아니며 직무도 아닙니다. 저는 C++과 데이터 구조를 배우고 있습니다.

Answer 1

비교적 간단합니다. 첫째, 노드 구조체 :

template<typename T> struct Node { 
    Node(T t) : value(std::move(t)), time(RightNow()) {} 
    T value; 
    TimeType time; 
    std::unique_ptr<Node> left; 
    std::unique_ptr<Node> right; 
}; 

빠른 도우미 make_unique :

template<typename T, typename... Args> std::unique_ptr<T> make_unique(Args&&... args) { 
    return std::unique_ptr<T>(new T(std::forward<Args>(args...))); 
} 
template<typename T> void Tree<T>::Insert(T key) { 
    auto z = make_unique<Node<T>>(std::move(key)); 
    // insert 
} 

첫째, 당신의 엉터리 고정 new 및 delete와 스마트 포인터로 대체. 그런 다음 하나의 유형 만 수행 할 수있는 트리가 필요하기 때문에 트리를 템플릿으로 만들었습니까? 그런 다음 const T&을 T으로 바꾸어 이동 전용 유형으로 사용할 수 있도록했습니다.

그러면 시간 필드를 추가하고 생성자에 RightNow()를 호출했습니다. 사용하는 정확한 TimeType 및 RightNow()는 필요에 따라 달라지며 "작성 시간"이 정확히 무엇인지 의미합니다. 2013 년 7 월 6 일에 대해 이야기하고 있습니까? 아니면 매우 높은 해상도의 클럭? 어쨌든 이러한 "생성 시간"세부 정보는 트리에 영향을주지 않습니다.

편집 : 잠깐만, 노드 중 일부에서만 생성 시간을 알고있는 트리 유형 하나를 갖고 싶습니까? 또는 단지 나무를 변경하여 모두 노드가 생성 시간을 알고 있습니까? 나는 # 2를했지만, # 1에서는 실제로 노드를 상속받을 수있었습니다. 위트로,

template<typename T> struct Node { 
    Node(T t) : value(std::move(t)) {} 
    T value; 
    std::unique_ptr<Node> left; 
    std::unique_ptr<Node> right; 
}; 
template<typename T> struct NodeWithTime : Node<T> { 
    TimeType time; 
    NodeWithTime(T t) : Node(std::move(t)), time(RightNow()) {} 
}; 
template<typename T> void Tree<T>::insert(T t) { 
    std::unique_ptr<Node> nodeptr; 
    if (IWantToStoreCreationTime) 
     nodeptr = make_unique<NodeWithTime<T>>(std::move(t)); 
    else 
     nodeptr = make_unique<Node>(std::move(t)); 
    // insert 
}