РАИИ-стиль односвязный список


После просмотра Херб Саттер описать односвязный список с точки зрения unique_ptr Я решил реализовать свой собственный. В частности, я хочу знать, если мое движение семантики являются правильными и если все ненужные копии. Он передает мои простые случаи с int и я планирую добавить вставки/удаления позже.

#include <iostream>
#include <memory>
#include <cstddef>
#include <utility>

template<typename Type>
class Node {
public:
  Node(const Type& data) : data {data} {}
  std::unique_ptr<Node<Type>> next = nullptr;
  Type data;
};

template<typename Type>
class LinkedList {
public:
  void push_back(const Type& data) {
    if (!head) {
      head = std::make_unique<Node<Type>>(data);
      return;
    }

    Node<Type>* end = head.get();

    while (end->next) {
      end = end->next.get();
    }

    end->next = std::make_unique<Node<Type>>(data);
  }

  Type pop_back() {
    if (!head) {
      throw;
    }

    Node<Type>* end = head.get();
    Node<Type>* previous = nullptr;

    while (end->next) {
      previous = end;
      end = end->next.get();
    }

    const Type data = end->data;

    if (previous) {
      previous->next = nullptr;
    }

    return data;
  }

  void push_front(const Type& data) {
    if (!head) {
      head = std::make_unique<Node<Type>>(data);
      return;
    }

    std::unique_ptr<Node<Type>> new_head = std::make_unique<Node<Type>>(data);
    new_head->next = std::move(head);
    head = std::move(new_head);
  }

  Type pop_front() {
    if (!head) {
      throw;
    }

    const Type data = head->data;
    head = std::move(head->next);
    return data;
  }

  std::size_t size() const {
    if (!head) {
      return 0;
    }

    std::size_t size = 1;
    Node<Type>* traverse = head.get();

    while (traverse->next) {
      traverse = traverse->next.get();
      size++;
    }

    return size;
  }

  /* iterative destroy to avoid recursive deletes */
  void destroy() {
    if (!head) {
      return;
    }

    while (head->next) {
      head = std::move(head->next);
    }

    head = nullptr;
  }

private:
  std::unique_ptr<Node<Type>> head = nullptr;
};

Редактировать: в ответ Deduplicator я закончил этот код

#include <iostream>
#include <memory>
#include <cstddef>
#include <utility>

template<typename Type>
class Node {
public:
  Node(const Type& data) : data {data} {}
  std::unique_ptr<Node<Type>> next = nullptr;
  Type data;
};

template<typename Type>
class LinkedList {
public:
  void push_back(const Type& data) {
    auto end = &head;

    while (*end) {
      end = &(*end)->next;
    }

    *end = std::make_unique<Node<Type>>(data);
  }

  Type pop_back() {
    auto end = &head;
    auto previous = &head;

    while (*end) {
      previous = end;
      end = &(*end)->next;
    }

    const Type data = (*previous)->data;
    *previous = nullptr;
    return data;
  }

  void push_front(const Type& data) {
    auto new_head = std::make_unique<Node<Type>>(data);
    new_head->next = std::move(head);
    head = std::move(new_head);
  }

  Type pop_front() {
    const Type data = head->data;
    head = std::move(head->next);
    return data;
  }

  ~LinkedList() {
    auto end = &head;

    while (*end) {
      *end = std::move((*end)->next);
    }
  }

private:
  std::unique_ptr<Node<Type>> head = nullptr;
};


248
6
задан 24 февраля 2018 в 05:02 Источник Поделиться
Комментарии
2 ответа

Почти всегда auto. Только напишите конкретный тип, когда вам нужно, это короче, понятнее и с меньшим количеством ошибок.

В настоящее время вы справляетесь пустой список как особый случай. Нет, это ни эффективным, ни элегантной.
Вместо этого, использовать указатель на указатель, и все упрощается. В качестве примера:

void push_back(const Type& data) {
auto p = &head;
while (*p)
p = &(*p)->next;
*p = std::make_unique<Node<Type>>(data);
}

Хороший из вас, чтобы избежать рекурсивного спуска в dtor. Но, вы знаете, что это не прописано destroy()?

3
ответ дан 25 февраля 2018 в 09:02 Источник Поделиться

Хотя это несколько несвязанные, что вы хотите из этого обзора, вот что мне не нравится:

std::size_t size() const {
if (!head) {
return 0;
}

std::size_t size = 1;
Node<Type>* traverse = head.get();

while (traverse->next) {
traverse = traverse->next.get();
size++;
}

return size;
}

В настоящее время данная функция очень сложная, в плане читабельности и производительности. Если клиент имеет цикл, который неоднократно требуется размер связанного списка после изменения его, это замедлит код. Вместо этого, я предлагаю вам держать собственный член переменной size в вашем классе. Каждый раз, когда вы добавляете элемент в список, вы инкремент этой переменной. Кроме того, вы декремента этой переменной, когда вы что-то удалять. Таким образом, эта функция станет О(1):

std::size_t size() const {
return size;
}

Это соответствует поведению стл. Однако добавление такого члена могли наворотить свой класс, как @Фрэнк указал. Если вы хотите действительно следовать STL, тогда я бы снять size функция в целом, как std::forward_list для этих причин.

2
ответ дан 24 февраля 2018 в 05:02 Источник Поделиться