deque的实施

Question

什么可以以不同的方式进行简化、修改或实现？我想知道是否有进一步改进这段代码的方法。

#ifndef _DEQUE_H_
#define _DEQUE_H_
//-------------------------------------------------------------------------
template <typename Type>
class Deque
{
private:
    struct Node
    {
        Type element = {};
        Node* prev = nullptr;
        Node* next = nullptr;
    };
    size_t count;
    Node* head;
    Node* tail;
public:
    //Member functions
    Deque();
    Deque(const Deque & deq);
    Deque(Deque && deq);
    Deque & operator = (const Deque & deq);
    Deque & operator = (Deque && deq);
    ~Deque();

    //Element access
    //const Type & at(Deque pos) const; Not implemented
    //template <typename Type>
    //const Type & operator[](size_type pos) const; Not implemented
    const Type & front() const;
    const Type & back() const;

    //Iterators
    //TODO: Implement in the near future 

    //Capacity
    bool empty() const;
    size_t size() const;
    //size_t max_size() const noexcept; Not implemented

    //Modifiers
    void push_front(const Type & tp);
    void push_back(const Type & tp);

    //void emplace_front(); Not implemented
    //void emplace_back(); Not implemented

    void pop_front();
    void pop_back();

    void clear() noexcept;
    void swap(Deque & deq) noexcept;
};
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque() : count(0), head(nullptr), tail(nullptr)
{
    //Body of the constructor class
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque(const Deque & deq) : count(deq.count), head(nullptr), tail(nullptr)
{
    for (const Node* n_ptr = deq.head; n_ptr != nullptr; n_ptr = n_ptr->next)
    {
        Node* n_ptr_new = new Node;
        n_ptr_new->element = n_ptr->element;
        if (head == nullptr && tail == nullptr)
        {
            head = n_ptr_new;
            tail = head;
        }
        else
        {
            tail->next = n_ptr_new;
            n_ptr_new->prev = tail;
            n_ptr_new->next = nullptr;
            tail = n_ptr_new;
        }
    }
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type>::Deque(Deque && deq) : count(deq.count), head(deq.head), tail(deq.tail)
{
    deq.count = 0;
    deq.head = nullptr;
    deq.tail = nullptr;
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type> & Deque<Type>::operator = (const Deque & deq)
{
    if (this == &deq)
    {
        return *this;
    }

    Deque tmp(deq);
    std::swap(count, tmp.count);
    std::swap(head, tmp.head);
    std::swap(tail, tmp.tail);
    return *this;
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type> & Deque<Type>::operator = (Deque && deq)
{
    if (this == &deq)
    {
        return *this;
    }

    std::swap(count, deq.count);
    std::swap(head, deq.head);
    std::swap(tail, deq.tail);
    return *this;
}
//--------------------------------------------------------------------------
template <typename Type>
Deque<Type>::~Deque()
{
    while (head)
    {
        Node* n_ptr_del = head;
        head = head->next;
        delete n_ptr_del;
    }
    count = 0;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::push_front(const Type & tp)
{
    Node* n_ptr_new = new Node;
    n_ptr_new->element = tp;
    if (head == nullptr && tail == nullptr)
    {
        head = n_ptr_new;
        tail = head;
    }
    else
    {
        n_ptr_new->next = head;
        n_ptr_new->prev = nullptr;
        head->prev = n_ptr_new;
        head = n_ptr_new;
    }
    ++count;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::push_back(const Type & tp)
{
    Node* n_ptr_new = new Node;
    n_ptr_new->element = tp;
    if (head == nullptr && tail == nullptr)
    {
        head = n_ptr_new;
        tail = head;
    }
    else
    {
        tail->next = n_ptr_new;
        n_ptr_new->prev = tail;
        n_ptr_new->next = nullptr;
        tail = n_ptr_new;
    }
    ++count;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::pop_front()
{
    if (empty())
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    if (head == tail)
    {
        delete head;
        --count;
        head = nullptr;
        tail = nullptr;
        return;
    }

    Node* n_ptr_del = head;
    head = head->next;
    head->prev = nullptr;
    --count;
    delete n_ptr_del;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::pop_back()
{
    if (empty())
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    if (head == tail)
    {
        delete head;
        --count;
        head = nullptr;
        tail = nullptr;
        return;
    }

    Node* n_ptr_del = tail;
    tail = tail->prev;
    tail->next = nullptr;
    --count;
    delete n_ptr_del;
}
//--------------------------------------------------------------------------
template <typename Type>
bool Deque<Type>::empty() const
{
    return head == nullptr;
}
//--------------------------------------------------------------------------
template <typename Type>
const Type & Deque<Type>::front() const
{
    if (empty())
    {
        throw std::out_of_range("List<Type>::top: empty stack");
    }
    return head->element;
}
//-------------------------------------------------------------------------------------------------
template <typename Type>
const Type & Deque<Type>::back() const
{
    if (empty())
    {
        throw std::out_of_range("List<Type>::top: empty stack");
    }
    return tail->element;
}
//--------------------------------------------------------------------------
template <typename Type>
size_t Deque<Type>::size() const
{
    return count;
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::clear() noexcept
{
    while (count)
    {
        pop_back();
    }
}
//--------------------------------------------------------------------------
template <typename Type>
void Deque<Type>::swap(Deque & deq) noexcept
{
    Deque temp(deq);
    deq = std::move(*this);
    *this = std::move(temp);
}
//--------------------------------------------------------------------------
#endif // _DEQUE_H_

Answer 1

以下是一些可以帮助您改进代码的东西。

使用适当的#includes

代码指的是一些东西，如std::size_t和std::swap，它们没有对应的#includes。代码应该有以下内容：

#include <cstddef>
#include <utility>
#include <stdexcept>

不定义默认构造函数

Deque的默认构造函数除了初始化成员之外什么也不做。相反，您应该使用类中的成员初始化器，并让编译器像使用Node一样生成构造函数。见CppCoreGuidelines C.45。

不要在名称

中使用前导下划线

带有前导下划线的任何内容都是C++ (和C)中的保留名称。详情请参见这个问题。在这种情况下，它适用于您选择的包含保护名。

简化了代码

push_back和push_front以及许多其他函数的代码可以大大简化。例如，在push_back的情况下，通过使用Node的自动生成构造函数：

template <typename Type>
void Deque<Type>::push_back(const Type & tp)
{
    if (tail) {
        tail = tail->next = new Node{tp, tail, nullptr};
    } else {
        head = tail = new Node{tp, nullptr, nullptr};
    }
    ++count;
}

修复错误消息

有些错误信息似乎与它们发出的信号不太匹配。例如，如果我们试图在空的back()上使用Deque，它会说

throw std::out_of_range("List<Type>::top: empty stack");

这将是一个非常混乱和无益的错误消息！

使用您自己的函数

在某些情况下，代码使用count来确定deque何时为空，在其他情况下，它检查是否为head == nullptr，而在其他情况下则使用empty()。我建议选择一种机制，并专门使用它。同样，如果您使用自己的函数，copy也可以像下面这样简单：

template <typename Type>
Deque<Type>::Deque(const Deque & deq) {
    for (auto curr = deq.head; curr; curr = curr->next) {
        push_back(curr->element);
    }
}

考虑支持列表初始化

目前，这样的建筑没有得到支持：

Deque<std::string> d3{"alpha", "beta", "gamma"};

然而，这很容易做到。我是这样做的：

template <typename Type>
Deque<Type>::Deque(std::initializer_list<Type> list) {
    for (auto& item : list) {
        push_back(item);
    }
}