Древовидная структура данных со списком в C++

Я реализовал древовидную структуру на C++, обращаясь к чужим кодам. Код ниже, который я сделал, наверняка был скомпилирован и, похоже, хорошо работает. Но подозреваю, что есть способы получше. Например, безопасен ли этот код в точке утечки памяти? Есть ли способ более простой и более эффективный в вычислительном отношении?

В частности, я сомневаюсь в необходимости «std :: list lst_nodes». Функция expand_node в классе Tree присоединяет новый узел к родительскому узлу, значение которого наиболее близко к значению нового узла. Этот процесс требует итерации по всем существующим узлам для доступа к их значениям. Для этой итерации я определил переменную-член с именем "std :: list lst_nodes" в классе Tree. И я подозреваю, что существует отличный способ сделать то же самое без определения lst_nodes.

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

class Node{
  public:/*functions*/
    Node(const double& val_, Node* parent_=nullptr)
      :val(val_), parent(parent_)
    {
      if (parent){
        parent->children.push_back(this);
      }
    }
  public:/*variables*/
    Node* parent;
    std::list<Node*> children;
    double val;
};

class Tree{
  public:/*function*/
    Tree(double x_init);
    void extend_node();

  public:/*variables*/
    list<Node*> lst_nodes;
    double x_init;
};

Tree::Tree(double x_init_)
  :x_init(x_init_)
{
  Node* n=new Node(x_init);
  lst_nodes.push_back(n);
}

void Tree::extend_node(){
  double val_new = rand();
  auto it=lst_nodes.begin();
  double minval = abs((**it).val-val_new);
  Node* node_parent;
  for(;it!=lst_nodes.end(); it++){
    if (minval>abs((**it).val-val_new)){
      minval = abs((**it).val-val_new);
      node_parent = *it;
    }
  }
  Node* n_new = new Node(val_new, node_parent);
  node_parent->children.push_back(n_new);
  lst_nodes.push_back(n_new);
}

int main(){
  Tree t(0);
  for(int i=0; i<100; i++){
    t.extend_node();
  }
}

Большое спасибо.

Вы также можете размещать сообщения на Обмен стеком для проверки кода

Richard 04.07.2018 01:19

@Richard: ваша ссылка отображается не так, как вы планировали, потому что вы пропустили "https: //"

Beta 04.07.2018 01:20
безопасен ли этот код в точке утечки памяти? - delete не обращается ни разу, поэтому код полон утечек памяти.
PaulMcKenzie 04.07.2018 01:21

@Beta исправлено спасибо

Richard 04.07.2018 01:21

Вы правы, lst_nodes там быть не должно. Вы создаете и список узлов, и дерево. Вместо этого сделайте его деревом поиска, чтобы вы могли таким образом находить узлы.

DrC 04.07.2018 01:25
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
5
945
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

В современном C++ вы можете использовать unique_pointer<T> вместо необработанных указателей T*, когда объект, на который указывает указатель, принадлежит объекту, имеющему указатель. Таким образом, вам не нужно явно указывать объект delete, это будет сделано в деструкторе unique_ptr.

В дереве (то есть связном графе без циклов) право собственности четко определено: каждый узел владеет своими дочерними элементами, поэтому вы можете использовать list<unique_ptr<Node>> для Node::children.

Другие вопросы по теме