Реализация нейтрального элемента в связанном списке - PullRequest
Новая
       32

Реализация нейтрального элемента в связанном списке

0 голосов
/ 03 мая 2018

Я сделал двунаправленный и двухмерный связанный список. Мои узлы называются chunk s, и они содержат указатель на chunks слева, справа, снизу и сверху. 

class chunk;
typedef std::shared_ptr<chunk> chunk_ptr;
typedef std::weak_ptr<chunk> chunk_wptr;

class chunk
{
public:
    chunk(wanted_id) : id(wanted_id) {}

    chunk_ptr left() const { return _left.lock(); }
    chunk_ptr right() const { return _right.lock(); }
    chunk_ptr top() const { return _top.lock(); }
    chunk_ptr bottom() const { return _bottom.lock(); }

    void left(const chunk_ptr set) { _left = set; }
    void right(const chunk_ptr set) { _right = set; }
    void top(const chunk_ptr set) { _top = set; }
    void bottom(const chunk_ptr set) { _bottom = set; }

    int id() const { return _id; }

private:
    chunk_wptr _left, _right, _top, _bottom;
    int _id;
    void id(const int id) { _id = id; }
};

Теперь давайте представим, что я построил следующую структуру:

enter image description here

Если я хочу перейти с 1 на 4, я мог бы использовать следующую строку кода: 

id4 = id1->right()->right()->bottom();

Теперь давайте представим, что кусок 3 был удален, например, id2->right == id4->top == nullptr: enter image description here

Если я хочу получить доступ к id4, то для выполнения какой-либо операции с ним произойдет ошибка во время выполнения. Чтобы не выполнять проверку на каждом шаге, я хотел бы ввести нейтральный элемент чанка: 

auto null_chunk = std::make_shared<chunk>(-1); // Let's define its id as -1
null_chunk->left(null_chunk);
null_chunk->right(null_chunk);
null_chunk->top(null_chunk);
null_chunk->bottom(null_chunk);

Таким образом, следующее утверждение будет успешно выполнено: 

id4 = id1->right()->right()->bottom();

А потом id4 == null_chunk.

Однако я не совсем уверен, как интегрировать такой элемент в мой код.

Я мог бы использовать статическую переменную : 

// This is a public static method
chunk_ptr chunk::null_chunk()
{
    static auto ptr = instanciate_null_chunk();
    return ptr;
}
// This is a private static method
chunk_ptr chunk::instanciate_null_chunk()
{
    auto ptr = std::make_shared<chunk>(-1);
    ptr->left(ptr);
    ptr->right(ptr);
    ptr->top(ptr);
    ptr->bottom(ptr);
    return ptr;
}

Теперь я хотел бы инициализировать left, right, top и bottom с помощью null_chunk в моем конструкторе: 

chunk(wanted_id) : id(wanted_id) 
{
    this->left(null_chunk());
    this->right(null_chunk());
    this->top(null_chunk());
    this->bottom(null_chunk());
}

Это приводит к переполнению стека рекурсии (null_chunk вызывает конструктор, вызывающий null_chunk и т. Д ...).

Это вынуждает меня определить конкретный частный конструктор для null_chunk(), но поскольку я использую общие указатели, мой конструктор должен быть общедоступным, чтобы использовать make_shared ...

Таким образом, существует поток проектирования. Как лучше всего реализовать такую ​​функцию?

1 Ответ

0 голосов
/ 04 мая 2018

Одним из возможных решений для реализации нулевого узла является использование статического члена. Этот элемент инициализируется один раз с использованием другой статической функции, которая создает общий указатель с пустым чанком и перенаправляет все исходящие соединения на сам чанк.

При построении любого другого чанка все исходящие соединения также указывают на нулевой чанк.

Как упомянуто в комментариях выше, не допускайте утечки памяти из-за циклических ссылок.

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

class chunk { 
public: 
  using chunk_ptr = std::shared_ptr<chunk>; 
  using chunk_wptr = std::weak_ptr<chunk>;

private:
  int _id; 
  chunk_wptr _left, _right, _top, _bottom; 
  static chunk_ptr nullchunk;
  struct pctor {};

  static chunk_ptr gennull() {
    chunk_ptr pnullchunk {std::make_shared<chunk>(pctor{})};
    pnullchunk->_left = pnullchunk;
    pnullchunk->_right = pnullchunk;
    pnullchunk->_top = pnullchunk;
    pnullchunk->_bottom = pnullchunk;
    return pnullchunk;
  }

public:
  chunk(pctor) : _id(-1) {}
  chunk(int id) :   _id(id), 
                    _left(chunk::nullchunk),
                    _right(chunk::nullchunk),
                    _top(chunk::nullchunk),
                    _bottom(chunk::nullchunk) {}

  bool isNullNode() const 
  { return this == chunk::nullchunk.get(); } 

  //
  // Further functions omitted
  //
}; 

chunk::chunk_ptr chunk::nullchunk {chunk::gennull()};
...