Реализация c++ стек с связанного списка


Это, оказывается, трудно найти реализаций стека с связанный список, и я пытаюсь выяснить, если моя реализация-это правильно/не хватает чего-то очевидного.

template <class T>
class Stack {
private:
  struct node {
    T data;
    node* next = nullptr;
    node(T data, node* next) : data(data), next(next) {};
  };
  node* top_ = nullptr;
public:
  Stack() {}
  Stack(T seed[], size_t len) {
    for(size_t i = 0; i < len; ++i) {
      Push(seed[i]);
    }
  }
  void Push(T value) {
    node* ele = new node { value, top_ };
    top_ = ele;
  }
  bool IsEmpty() {
    return top_ == nullptr;
  }
  T Peek() {
    if (IsEmpty())
      throw std::runtime_error("Stack is empty");
    return top_->data;
  }
  T Pop() {
    if (IsEmpty())
      throw std::runtime_error("Stack is empty");
    node* popped = top_;
    T result = popped->data;
    top_ = popped->next;
    delete popped;
    return result;
  }
};

Мои тесты (образец основных из них ниже) показывают рабочую функцию, поэтому его очень просто моя структура кода/процедуры меня беспокоит

int seed[3] { 5,4,3 };
Stack<int> stack { seed, 3 };
REQUIRE( stack.Pop() == 3 );
REQUIRE( stack.Pop() == 4 );
REQUIRE( stack.Pop() == 5 );
REQUIRE_THROWS_WITH( stack.Pop(), "Stack is empty" );
REQUIRE_NOTHROW( stack.Push(9) );
REQUIRE_NOTHROW( stack.Push(3) );
REQUIRE( stack.Peek() == 3 );
REQUIRE( stack.Pop() == 3 );


Комментарии
2 ответа

Это архаичная форма декларации шаблон:

template <class T>

Более современные формы-это:

template<typename T>

Технически нет разницы, но class подразумевает определенный пользователем тип А typename подразумевает любого типа. Большинство современных библиотек будут использовать новую версию. Там тоже одного глухого угла шаблоны шаблон случае это имеет значение.

Вам не нужно определить конструктор для node.

  struct node {
T data;
node* next = nullptr;
node(T data, node* next) : data(data), next(next) {};
};

Список инициализатора договор будет иметь тот же эффект.

  struct node {
T data;
node* next;
};
...
new node {data, top};

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

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

Теперь у вас есть деструктор:

Вы не соблюдаете правило 3 или 5 (кто-то еще упомянул Правило 7, но я не знаю, что это такое, если кто-то хотелось бы уточнить в комментариях?).

Правило 3: Если вы определите деструктор, конструктор копирования и присваивания копий, то вы, вероятно, нужно все три.

Правило 5: Правило 3 + 2-х операторов перемещения. Позволяет определять перемещения операторов для Ваш объект так, чтобы он двигаться совместимы.

Альтернатива с использованием правила 3/5 заключается в том, чтобы использовать правило 0. Это в основном означает node объект очищает себя. Это потребует использования std::unique_ptr. В top в свой список и next в узле должны использовать этот тип.

Лично я не думаю, что это подходит для формирования списков рассылки (но это, безусловно, вариант, и другие люди рекомендую его).

Вы передаете по значению здесь:

  void Push(T value)

Это хорошо для простых видах T. Но если T дорого скопировать тогда скопировать его в Push метод. Потом снова скопировать его при создании объекта.

Попробуйте нажимать на ссылку и подвижные ссылка.

 void Push(T const& value);  // Pass value by reference.
void Push(T&& value); // Pass by r-value ref allowing a move.

Эта функция не изменяет состояние объекта.

  bool IsEmpty() {
return top_ == nullptr;
}

Вы, вероятно, следует пометить его как const. Это позволяет пройти стека const reference и еще проверить состояние объекта.

Сухой вам код.
Следующий код повторяется в двух местах

    if (IsEmpty())
throw std::runtime_error("Stack is empty");

Это означает, что он является кандидатом, чтобы быть введены в собственную функцию.

Вы можете не реализовать Pop() что возвращает значение в исключение безопасным способом. В качестве такого стандартного стека использует два разных метода top() которая возвращает ссылку на верхний значение и pop() что возвращает void но удаляет верхний элемент из стека.

Вы, вероятно, должны следовать этой конвенции.

Эти две функции возвращают значение.

  T Peek()
T Pop()

Это означает, что вы сделать копию значения. Это хорошо для простых типов, таких как целое число, но для сложных классов это потенциально дорого. Еще одна причина, чтобы использовать top() и void pop(). Но здесь, по крайней мере Peek() возвращает ссылку, чтобы избежать копирования.

4
ответ дан 14 марта 2018 в 05:03 Источник Поделиться

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

45:45: error: taking address of temporary array
Stack<int> stack { (int []){ 5,4,3 }, 3 };

Ваша программа также утечки памяти. Запустить его через Valgrind и проверить на герметичность.
Механическая память управление через new это почти всегда плохая идея. Использовать смарт-указатели, чтобы избежать этих проблем.
Почему вы предоставляете пустой конструктор по умолчанию?

Обеспечить публичную часть вашего интерфейса в первую очередь.
Когда люди смотрят на вашу библиотеку, они не хотят, чтобы прочитать все данные-члены, просто чтобы посмотреть, какие методы вы выставляете. Имена методов обычно хранятся в нижнем регистре.

Как вы инициализировать вещи тоже выглядит странно. Можно использовать тремя различными способами (прямые, списки и конструктор). Переработать код и придерживаться списка инициализации.

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

Я думаю, что дизайн может быть чище. Интерфейс и реализация, вероятно, может быть менее связанная, но может кто-то еще есть лучшее объяснение здесь.

3
ответ дан 14 марта 2018 в 02:03 Источник Поделиться