Реализация списка


Ценю ваши мысли и отзыв на мой простой реализации списка.

У меня есть код на GitHub с список и некоторые googletests здесь (не знаю, почему гитхаб изменений интервал будет настолько большой)

Некоторые моменты, чтобы иметь в виду..

  1. Я выбрал, чтобы иметь две отдельные функции для назначения и движение операторов. Как противостоять одна, которая принимает аргумент по значению.

  2. Лучший курс действий, если моя ясная (функция) бросает? (Деструктор т может быть установлен в noecept(лже)) я должен прекратить исключения из propogating и попробовать продолжить и удалить как можно больше узлов из моего списка? Или это исключение, а не условие для всей программы, и я пусть это повторяйте, даже если это вызывает расторгнуть называться?

  3. Я решил реализовать свой собственный своп на практике, несмотря на, в случай из моего списка, стандартный своп-это вероятно более эффективным.

  4. Я добавлю итераторы, я знаю ее довольно бесполезной список без обход но я хотел получить основы работы в первую очередь.

Список.ч

#ifndef H_UTILS_STORAGE_LIST_H
#define H_UTILS_STORAGE_LIST_H


//  includes
#include <initializer_list>
#include <utility>

namespace utils {
    namespace storage {

        template <typename T>
        class List {

            friend void swap(List<T>& lhs, List<T>& rhs) noexcept
            {
                Node* tempHead(lhs.mHead);
                lhs.mHead = rhs.mHead;
                rhs.mHead = tempHead;

                std::size_t tempSize(lhs.mSize);
                lhs.mSize = rhs.mSize;
                rhs.mSize = tempSize;
            }

        private:
            //  Node
            struct Node {
                T mData;
                Node* mNext = nullptr;
            };

        public:
            List() = default;
            explicit List(const std::size_t size);
            explicit List(const std::initializer_list<T>& il);
            List(const List& rhs);
            List(List&& rhs) noexcept;
            ~List();

            List& operator=(const List& rhs);
            List& operator=(List&& rhs);

            template<typename ...Args>
            void emplace(Args&&... args);

            void insert(const T& t);
            void insert(T&& t);

            void remove(const T& t);
            void clear();

            std::size_t getSize() const { return mSize; }

        private:
            Node* mHead = nullptr;
            std::size_t mSize = 0;
        };

        //  custom constructor - create a list of N size
        template <typename T>
        List<T>::List(const std::size_t size)
        {
            //  empty list?
            if (size == 0) return;

            //  create head
            mHead = new Node{};

            //  create a temporary pointer to the head of the list
            Node* node = mHead;
            for (int i = 0; i < size - 1; ++i) {
                //  this is a valid node
                //  create a new node
                //  link it to the list
                node->mNext = new Node{};

                //  iterate to the next node
                node = node->mNext;
            }

            mSize = size;
        }

        //  custom constructor - create a list populated with data
        template <typename T>
        List<T>::List(const std::initializer_list<T>& il)
        {
            //  empty list?
            if (il.size() == 0) return;

            //  get first element in list and make the head node
            auto it = il.begin();
            mHead = new Node{ (*it), nullptr };
            ++it;

            //  create a temporary pointer to the head of the list
            Node* node = mHead;
            for (; it != il.end(); ++it) {
                //  this is a valid node
                //  create a new node
                //  link it to the list
                node->mNext = new Node{ (*it), nullptr };

                //  iterate to the next node
                node = node->mNext;
            }

            mSize = il.size();
        }

        template <typename T>
        List<T>::List(const List<T>& rhs)
        {
            Node* lhsNode = nullptr;
            Node* rhsNode = rhs.mHead;

            //  create the head node
            if (rhsNode) {                              
                lhsNode = new Node{ rhsNode->mData, nullptr };
                mHead = lhsNode;

                //  iterate to next rhs node
                rhsNode = rhsNode->mNext;
            }

            //  create rest of list
            while (rhsNode && lhsNode) {

                //  create a copy of the rhs node
                //  link it to lhs list
                lhsNode->mNext = new Node{ rhsNode->mData, nullptr };

                //  iterate to next lhs node
                lhsNode = lhsNode->mNext;

                //  iterate to next rhs node
                rhsNode = rhsNode->mNext;
            }

            mSize = rhs.mSize;
        }

        template <typename T>
        List<T>::List(List<T>&& rhs) noexcept
        {
            using std::swap;
            swap(*this, rhs);
        }

        template <typename T>
        List<T>::~List()
        {
            try {
                clear();
            } catch (...) {
                //  T's destructor could be set to noexcept(false) and throw during the delete call
                //  do not allow any exceptions to propogate from a destructor
            }
        }

        template <typename T>
        List<T>& List<T>::operator=(const List<T>& rhs)
        {
            //  check for self assignment
            if (this != &rhs) {

                //  make a copy of rhs
                List<T> rhsCopy(rhs);

                //  swap
                using std::swap;
                swap(*this, rhsCopy);
            }

            return *this;
        }

        template <typename T>
        List<T>& List<T>::operator=(List<T>&& rhs)
        {
            //  check for self move
            if (this != &rhs) {

                //  swap
                using std::swap;
                swap(*this, rhs);
            }

            return *this;
        }

        template<typename T>
        template<typename ...Args>
        void List<T>::emplace(Args&&... args)
        {
            //  forward to the relevant insert
            insert(std::forward<Args>(args)...);
        }

        template <typename T>
        void List<T>::insert(const T& t)
        {
            Node* tail = mHead;

            //  find the tail of the list
            while (tail && tail->mNext) {
                tail = tail->mNext;
            }

            if (tail) {
                //  list has a tail
                //  append this node to the end of the list
                tail->mNext = new Node{ t, nullptr };
            } else {
                //  empty list
                //  append to head
                mHead = new Node{ t, nullptr };
            }

            ++mSize;
        }

        template <typename T>
        void List<T>::insert(T&& t)
        {
            Node* tail = mHead;

            //  find the tail of the list
            while (tail && tail->mNext) {
                tail = tail->mNext;
            }

            if (tail) {
                //  list has a tail
                //  append this node to the end of the list
                tail->mNext = new Node{ std::move(t), nullptr };
            } else {
                //  empty list
                //  append to head
                mHead = new Node{ std::move(t), nullptr };
            }

            ++mSize;
        }

        template <typename T>
        void List<T>::remove(const T& t)
        {
            Node* node = mHead;
            Node* prev = nullptr;

            while (node) {
                //  found?
                if (node->mData == t) {
                    if (prev) {
                        //  unlink from list, delete and decrease size of list
                        Node* next = node->mNext;
                        delete node;
                        node = nullptr;
                        prev->mNext = next;                     
                        --mSize;
                    } else {
                        //  remove head
                        //  decrease size of list
                        delete node;
                        node = nullptr;
                        mHead = nullptr;
                        --mSize;
                    }
                } else {
                    //  data not found
                    //  iterate to next node
                    prev = node;
                    node = node->mNext;
                }
            }
        }

        template<typename T>
        void List<T>::clear()
        {
            Node* node = mHead;
            while (node) {
                //  store the pointer to the next node
                Node* next = node->mNext;

                //  delete current node
                delete node;

                //  T's destructor could be set to noexcept(false) and throw
                //  could wrap "delete node" in a try/catch to suppress any exceptions
                //  and continue deleting the rest of the nodes else there could be leaked memory
                //

                //  iterate to next node
                node = next;
            }

            mHead = nullptr;
            mSize = 0;
        }
    }
}

#endif


184
3
задан 10 апреля 2018 в 01:04 Источник Поделиться
Комментарии
2 ответа

Комментарий

В целом очень хороший кусок кода.

Я заметил только один баг (удаление из головы).
На мой взгляд код может быть сухой уложил в пару мест, а преждевременная оптимизация в назначении ненужно (но ничего не нарушить).

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

А не:

 Node<T>* next = mHead;
while(next->mNext != nullptr) {
next = next->mNext;
}
next->mNext = new Node(t);

Я бы разделил эту функцию и написать:

 Node<T>* next = getTailNode();
next->mNext = new Node(t);

Цель кода теперь становится понятно.

Основной Обзор

Почему бы не использовать std::swap() для замены членов?

            friend void swap(List<T>& lhs, List<T>& rhs) noexcept
{
Node* tempHead(lhs.mHead);
lhs.mHead = rhs.mHead;
rhs.mHead = tempHead;

std::size_t tempSize(lhs.mSize);
lhs.mSize = rhs.mSize;
rhs.mSize = tempSize;
}

Я бы написал так:

            friend void swap(List<T>& lhs, List<T>& rhs) noexcept
{
using std::swap;
swap(lhs.mHead, rhs.mHead);
swap(lhs.mSize, rhs.mSize);
}

Когда вы создаете список набор размер:

        //  custom constructor - create a list of N size
template <typename T>
List<T>::List(const std::size_t size)

Что в списке? В настоящее время вы можете только поддержать видах T которые стручка или по умолчанию под застройку. Но если они под они находятся в неопределенном состоянии и читая их, УБ. Лично, вместе с размером я хотел определить значение по умолчанию в каждый член (элемент по умолчанию можно использовать значения по умолчанию).

        template <typename T>
List<T>::List(const std::size_t size, T const& defaultValue = T())

В этот инициализатор (используя список)

        //  custom constructor - create a list populated with data
template <typename T>
List<T>::List(const std::initializer_list<T>& il)

Там, кажется, большое сходство с первым конструктором. Вы можете высушить код немного?

То же самое касается и конструктор копирования. Также некоторые из них являются лишними. Вам не надо комментировать каждую строчку. Комментарии должны быть использованы, чтобы описать , почему код делает что-то (или описание и ссылку на алгоритм). Пусть код описать как.

        template <typename T>
List<T>::List(const List<T>& rhs)

Это копия работы. Но я не вижу необходимости для проверки самостоятельная работа. Копия и идиома своп является безопасным для использования в присутствии самостоятельная работа.

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

        template <typename T>
List<T>& List<T>::operator=(const List<T>& rhs)
{
// check for self assignment
if (this != &rhs) {

// make a copy of rhs
List<T> rhsCopy(rhs);

// swap
using std::swap;
swap(*this, rhsCopy);
}

return *this;
}

Аналогичное замечание по ходу. Своп-это самостоятельная работа безопасная. Пессимизации самый распространенный случай для того, что случается исчезающе редко. Это гораздо хуже, благо тест исчезающе мала (как самостоятельного передвижения не так уж дорого, будучи своп).

        template <typename T>
List<T>& List<T>::operator=(List<T>&& rhs)
{
// check for self move
if (this != &rhs) {

// swap
using std::swap;
swap(*this, rhs);
}

return *this;
}

Вы теряете преимущества разместить здесь.

        template<typename T>
template<typename ...Args>
void List<T>::emplace(Args&&... args)
{
// forward to the relevant insert
insert(std::forward<Args>(args)...);
}

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

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

        template<typename ...Args>
void List<T>::emplace(Args&&... args)
{
// forward to the relevant insert
doInsert(new Node(std::forward<Args>(args)...)); // Need a new node constructor
}

void List<T>::insert(T const& val)
{
doInsert(new Node(val));
}

void List<T>::insert(T&& val)
{
doInsert(new Node(std::move(val))); // Need another node constructor.
}

void doInsert(Node<T>* ptr)
{
if (!mHead) {
mHead = ptr;
}
else {
Node<T>* tail = getTail();
tail->mNext = ptr;
}
}

ОК. Это remove() может быть значительно упрощена. Также есть определенная ошибка в удалении элемента Head, как вы всегда назначают nullptr для mHead.

        template <typename T>
void List<T>::remove(const T& t)
{
Node* node = mHead;
Node* prev = nullptr;

while (node) {
// found?
if (node->mData == t) {
if (prev) {
// unlink from list, delete and decrease size of list
Node* next = node->mNext;
delete node;
node = nullptr;
prev->mNext = next;
--mSize;
} else {
// remove head
// decrease size of list
delete node;
node = nullptr;
mHead = nullptr;
--mSize;
}
} else {
// data not found
// iterate to next node
prev = node;
node = node->mNext;
}
}
}

Итерационный упрощения:

        void List<T>::remove(const T& t)
{
Node<T>* prev = nullptr;
for(Node<T>* loop = mHead; loop != nullptr; prev = loop, loop = loop->mNext) {
if (loop->mData == t) {
if (prev == nullptr) {
mHead = loop->mNext;
}
else {
prev->next = loop->mNext;
}
delete loop;
return;
}
}
}

Но мне не нравится это. Его все еще очень густое. Это одна из причин, мне нравится использовать Сентинел значение. Если вы используете часовой значение кода будет существенно упрощается, так как у вас нет специального голове и все эти тесты для nullptr просто исчезнут.

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

            void List<T>::remove(const T& t)
{
mHead = doRemove(mHead, t);
}
void List<T>::doRemove(Node<T>* current, const T& t)
{
if (current == nullptr) {
return nullptr;
}

if (current->mData == t) {
Node<T>* result = current->mNext;
delete current;
return result;
}

current->mNext = doRemove(current->mNext, t);
return current;
}

Как я обычно реализовать своп

 class MyClass
{
public:
void swap(MyClass& rhs) noexcept {
using std::swap;
// call swap on each member.
}
friend void swap(MyClass& lhs, MyClass& rhs) noexcept {
lhs.swap(rhs);
}
};

5
ответ дан 10 апреля 2018 в 03:04 Источник Поделиться

Во-первых, о ваших пунктах:


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

  2. Потенциально бросая dtor находится почти во всех случаях патологическим. Пытаясь справиться с ней в любой удобный способ-это в высшей степени неприятно, упражнение в тщетности.

  3. Ну, std::swap() использует командлет Move-конструктор, назначения перемещения, и dtor. Как ваш переезд-ctor является правильно реализована с swap(a, b)что вы ожидаете произойдет, если вы не реализуете свой собственный swap(a, b)? (Как в стороне, using std::swap; есть не очень разумные, и кольца большой тревоги для любого читателя.)

    Или вы имеете в виду не использовать using std::swap; swap(x, y); в реализации ваших пользовательских swap()? В таком случае, мне действительно нужно превозносить значение лаконичность и используя соответствующие абстракции, при всех остальных равных условиях.


  4. Приятно слышать, что вы добавить итератор-поддержка. В любом случае, что приведет к полному ре-дизайн: копирования-конструктор, initializer_list-конструктор, и .remove().

Теперь другие вещи:


  1. В определении шаблона класса List<T>вы можете обратиться к текущий шаблон-экземпляр без указания шаблона-аргумент простой List.

  2. Объятия auto. Нет проверки, обязаны ли вы вспомнили, чтобы использовать правильный тип, или отремонтировать его в сотни мест, когда вы решили поменять его по любой причине.

  3. Лично я всегда ставлю указатели перед тем, как данные-члены, но это может быть просто меня.

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

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


  5. Это любопытно для реализации dtor точки зрения .clear()вместо того, чтобы наоборот. Что может привести к не менее эффективным за счет в пользу последних, что является меньше, чем идеал...

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

  7. Не тест для самостоятельного перемещения-назначения. Почти такой же, как для самостоятельного копирования и присваивания применяется, хотя и самостоятельного передвижения-задание-это патология, и вы, возможно, захотите наклеить assert(this != &rhs); там.

  8. .emplace() надо построить значение в месте, взорвать его. Вот что он говорит на олово.
    Кроме того, два .insert()ы должны делегировать один .emplace() на все работы, а не наоборот, для уменьшения ненужного кода-дублирование.

1
ответ дан 12 апреля 2018 в 10:04 Источник Поделиться