Реализация очереди в C++


При рассмотрении моего кода, пожалуйста, рассмотрите эти вопросы:

  1. Любой способ, чтобы избежать использования новых/удалить? Или структур данных, как правило, а также не сможете использовать смарт-указатели? Я думал использовать общие указатели или уникальные указатели, но они, кажется странным использовать в этом случае.

  2. Рекурсия в конструктор? Хорошо или плохо?

  3. Конструктор копирования должен быть удален для узла? Потому что вы копируете указатель на следующий иначе. Копия узлы надо делать по очереди, а?

очереди.ч

#ifndef H_UTILS_QUEUE_H
#define H_UTILS_QUEUE_H

#include <stdexcept>


namespace Utils {

template<class T>
class Queue {

private:

    //  Node
    class Node {
    public:
        explicit Node(const T& data, Node* next);
        explicit Node(T&& data, Node* next);
        Node(const Node& other);
        Node(Node&& other) noexcept;

        Node& operator=(Node other) noexcept;

    private:
        void swap(Node& other) noexcept;

    public:
        T mData;
        Node* mNext;

    };  //  Node

public:
    Queue();
    Queue(const Queue<T>& other);
    Queue(Queue<T>&& other) noexcept;

    Queue<T>& operator=(Queue<T> other) noexcept;

    T& front();
    void pop_front() noexcept;
    void push_front(const T& data);
    void push_back(const T& data);
    void push_back(T&& data);

private:
    void swap(Queue<T>& other) noexcept;
    Node* deepCopy(Node* node);

private:
    Node* mHead;

};  //  Queue


//  Node
template<class T>
Queue<T>::Node::Node(const T& data, typename Queue<T>::Node* next)
    : mData(data)
    , mNext(next)
{

}

template<class T>
Queue<T>::Node::Node(T&& data, typename Queue<T>::Node* next)
    : mData(std::move(data))
    , mNext(next)
{

}

template<class T>
Queue<T>::Node::Node(typename const Queue<T>::Node& other)
    : mData()
    , mNext(nullptr)
{
    mData = other.mData;
    mNext = other.mNext;
}

template<class T>
Queue<T>::Node::Node(typename Queue<T>::Node&& other) noexcept
    : mData()
    , mNext(nullptr)
{
    swap(other);
}

template<class T>
typename Queue<T>::Node& Queue<T>::Node::operator=(typename Queue<T>::Node other) noexcept
{
    if (this != &other) {
        swap(node);
    }

    return *this
}

template<class T>
void Queue<T>::Node::swap(typename Queue<T>::Node& other) noexcept
{
    using std::swap;
    swap(mData, other.mData);
    swap(mNext, other.mNext);
}


//  Queue
template<class T>
Queue<T>::Queue()
    : mHead(nullptr)
{

}

template<class T>
Queue<T>::Queue(const Queue<T>& other)
    : mHead(nullptr)
{
    if (other.mHead) {
        mHead = deepCopy(other.mHead);
    }
}

template<class T>
Queue<T>::Queue(Queue<T>&& other) noexcept
    : mHead(nullptr)
{
    swap(other);
}

template<class T>
Queue<T>& Queue<T>::operator=(Queue<T> other) noexcept
{
    if (this != &other) {
        swap(other);
    }

    return *this;
}

template<class T>
void Queue<T>::swap(Queue<T>& other) noexcept
{
    using std::swap;
    swap(mHead, other.mHead);
}

template<class T>
typename Queue<T>::Node* Queue<T>::deepCopy(typename Queue<T>::Node* node)
{
    if (node->mNext == nullptr) {
        //  at tail

        //  if an exception is thrown here allow it to progate out of this function
        //  to be handled by the calling code
        //  no memory will be leaked
        return new Node(node->mData, nullptr);
    }

    Node* next = deepCopy(node->mNext);
    Node* current = nullptr;

    try {
        current = new Node(node->mData, next);
    } catch (...) {
        //  something went wrong
        //  recursively deallocate any nodes that have been allocated up to this point
        Node* i = next;
        while (i) {
            Node* copy = i->mNext;
            delete i;
            i = copy;
        }
    }

    return current;
}

template<class T>
T& Queue<T>::front()
{
    if (mHead) {
        return mHead->mData;
    } else {
        throw std::logic_error("trying to get front of empty queue");
    }
}

template<class T>
void Queue<T>::pop_front() noexcept
{
    if (mHead) {
        Node* newHead = mHead->mNext;
        Node* oldHead = mHead;
        mHead = newHead;
        delete oldHead;
    } 
}

template<class T>
void Queue<T>::push_front(const T& data)
{   
    try {
        Node* prevHead = mHead;
        Node* newHead = new Node(data, prevHead);
        //  only once we successfully get to this stage do we set the head pointer
        mHead = newHead;
    } catch (...) {
        //  something went wrong
        //  queue still in same state it was before call to push_back

        //  let the caller handle the exception
        throw;
    }
}

template<class T>
void Queue<T>::push_back(const T& data)
{
    //  find the tail
    Node* tail = mHead;
    while (tail) {
        if (tail->mNext == nullptr) break;

        tail = tail->mNext;
    }

    if (tail) {
        Node* newHead = nullptr;

        try {
            newHead = new Node(data, nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        tail->mNext = newHead;
    } else {
        Node* newHead = nullptr;

        try {
            newHead = new Node(data, nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        mHead = newHead;
    }

}

template<class T>
void Queue<T>::push_back(T&& data)
{
    //  find the tail
    Node* tail = mHead;
    while (tail) {
        if (tail->mNext == nullptr) break;

        tail = tail->mNext;
    }

    if (tail) {
        Node* newHead = nullptr;

        try {
            newHead = new Node(std::move(data), nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        tail->mNext = newHead;
    }
    else {
        Node* newHead = nullptr;

        try {
            newHead = new Node(std::move(data), nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        mHead = newHead;
    }

}



}  //  Utils


#endif  //  UTILS_QUEUE

main.cpp

#include <iostream>
#include "queue.h"

using Utils::Queue;

int main()
{
    {
        Queue<char> charQueue;

        charQueue.push_back('a');
        char b = 'b';
        charQueue.push_back(b);
        charQueue.push_back('c');
        charQueue.push_back('d');
        charQueue.push_back('e');
        charQueue.push_back('f');
        charQueue.push_back('g');
        charQueue.push_back('h');
        charQueue.push_back('i');
        charQueue.push_back('j');
        charQueue.push_back('k');
        charQueue.push_back('l');
        charQueue.push_back('m');

        for (std::size_t i = 0; i < 13; ++i) {
            std::cout << charQueue.front() << "\n";
            charQueue.pop_front();
        }
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b(a);
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b(std::move(a));
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b;

        b = a;
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b;

        b = std::move(a);
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        try {
            for (std::size_t i = 0; i < 10; ++i) {
                a.front();
                a.pop_front();
            }       
        } catch (std::exception& e) {
            std::cout << "Caught Exception " << e.what() << "\n";
        }
    }


    std::cin.get();

}


207
5
задан 23 марта 2018 в 08:03 Источник Поделиться
Комментарии
2 ответа

Что касается вашего прямого вопроса:


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

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

  3. Вообще, я бы не пытался изо всех сил OOifying вспомогательных классов. Помните, что это ограничивает использование кода делать полезные вещи, делает их неестественными и витиевато, и, как правило, приводит к раздутости.
    Оптимальное определение для узла-класса имхо:

    struct node { node* next; T data; };

    Использование агрегатной инициализации для создания узлов.

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

    Единственное, что нужно рассмотреть, является ли вы хотите использовать std::unique_ptr<node> за следующим.


И сейчас, пересматривая все еще не упоминалось:


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

  2. Если поток один-символьной строки, рассмотрим вместо потокового характера. Это может быть немного более эффективным.

  3. Node должны быть либо совокупности без какой-либо настройки, или не поддержка копирования/перемещения - конструкция, назначение и, конечно, .swap().
    В любом случае вы посмотрите на нее, объявив операции, которые вы сделали noexcept безусловно это ошибка, а не все T'ы поддержки, гарантия.

  4. Если вы настаиваете на член-функцию .swap(other)по крайней мере сделать его публичным. Хотя было бы гораздо полезнее просто определить friend void swap(a, b) вместо этого, как будет подобран общий код.

  5. Вы действительно нужно только сделать глубокий-копия в копию-конструктор, который только и делает, что. Как таковой, извлекая, что в собственную функцию Не покупайте вы ничего. Фактически, это означает, что вы должны дублировать очистки-код уже в dtor.

  6. Вы должны определить template<class... X> void emplace_back(X&&... x) и определяют два пуш-вариантов с точки зрения того, что то же самое для emplace_front(). Что позволяет удалить больше кода-дублирование и получает вам более эффективный и гибкий интерфейс.

  7. Не предохранитель против самостоятельного назначения. Помимо того, что это тривиально, чтобы доказать, что this и &other различны как other был передан по значению, копия-и-своп уже работает корректно и pessimizing общем случае это плохая идея.

  8. Не ловить исключения только для передачи их. Это может выглядеть как компилятор должен уметь оптимизировать его, но это не всегда так.

  9. Старайтесь избегать особых случаях. Двойной косвенности не ракетостроение.
    Например, вставка нового узла в конец:

    auto p = &head;
    while (*p)
    p = &p->next;
    *p = new Node{...};

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

Прежде всего, давайте ответим на ваши вопросы:


  1. Ну, вы могли бы сделать эту работу, используя std::unique_ptr. Однако, поскольку вы реализуете достаточно низкоуровневую структуру памяти, я не уверен, я бы предложил его здесь. В общем, смарт-указатель использование предпочтительнее сырые указатели; однако, в таком случае, где вы должны манипулировать указателями на себя много (в отличие от данных, на которые они указывают), смарт-указатели, как правило, несколько неуклюжий и плохо оборудованная. Однако, вы должны обязательно убедиться, что вы делаете правильно управление памятью (используя статический анализ, а также выполнения анализаторов, таких как Valgrind и, Асан, msan и т. д.).

  2. Нет ничего изначально плохого использования рекурсии в конструктор.

  3. Существует два различных подхода к проблеме копирования. Один-лечить Node как стремно, структура-как класс, который не намного больше, чем сочетание кусок данных с указателем на следующий узел. В этом случае, это прекрасно, чтобы копировать узлы правильно отвечает Queue.

    Другой подход заключается в лечении Nodeбольше похоже на "умные" объекты, которые имеют некоторые укоренившиеся поведения, в случае копирования должны быть определены через Node класс.

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


Вы стоите в очереди-это почти бесполезно

Резкие слова. Почему я говорю что-то вроде этого?

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

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

Кроме того, вы должны добавить некоторые определения типа в соответствии с требованиями контейнер стандартной библиотеки.

Некоторые другие вещи


  1. Исправьте включает в себя. Сейчас. Вам нужно #include <utility> для обоих std::move и std::swapиначе ваш код может не компилироваться.

  2. Придерживаться правила пяти. Queue определяет копирования и конструктор перемещения, а также копию оператор присваивания, поэтому он должен определять двигаться оператор присваивания и деструктор, а также. То же самое верно для Nodeесли вы хотите последовать моему предложению на вопрос 3. Если нет, вы должны полностью удалить специальные функции-члены.

  3. Относится к пункту 2: так как вы не определить деструктор, вы утечку памяти повсюду. Немедленно исправить это.

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

  5. Вместо того чтобы вручную писать конструктор по умолчанию для Queueвы должны добавить члена инициализатор для mHead (т. е. Node* mHead = nullptr;) и просто = default конструктор по умолчанию.

  6. При написании одного символа в std::coutиспользуйте 'c' вместо "c" (в частности, это относится к использованию "\n"). Последний, вероятно, привести к снижению производительности.

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