队列的实现

Question

我使用C++已经将近一年了，我刚刚实现了这个队列。我已经在许多不同的场景中测试过它，而且它似乎工作得很好。你能告诉我什么可以改进吗？在专业场景中可能和可能不使用什么技术？一般来说，你能不能给我你的意见，以便我可以提高我的技能？

// --- Implementation of an exception class
class E: public std::exception{

    const char * _msg = "Default Exception.";
    E(){};

public:
    E(const char * message) throw() { this->_msg = message; }
    const char * what() const throw(){ return this->_msg; }
};

// --- Implementation of a queue.
template <typename T> class Queue {

    static const int _defaultSize = 10;
    static const int _maxSize = 1000;
    int _size;
    int _currentSize = 0;

    T * _queuePointer;
    int _firstInQueue = -1;                             // Holds the index of the first item in the queue (the item that should be popped).
    int _lastIndex = -1;                                // Holds the index that we have just pushed a new element to. ("last index to have an element being added to")

public:
    // Constructors and Destructors
    Queue(int sz=_defaultSize);                         // Default/Int Constructor Constructor
    Queue(const Queue & other);                         // Copy Constructor
    ~Queue();                                           // Destructor

    // Overloaded Assignment Operator
    Queue & operator = (const Queue rhs);               // To implement the copy-and-swap idiom

    // Utility Functions
    void swap(Queue & rhs);
    T enqueue(const T & node);
    T dequeue();
    bool isFull() const { return (this->getCurrentSize() == this->getSize()); };
    bool isEmpty() const { return (!this->getCurrentSize()); };

    // Getters/Accessors
    int getCurrentSize() const { return this->_currentSize; }
    int getSize() const { return this->_size; }

};

// Implementation of Constructors and Destructors
template <typename T> Queue<T>::Queue(int sz){

    if (sz < 1 || sz > _maxSize){
        // Invalid 'sz' argument value.
        throw E("Queue Exception: Invalid size argument value.");
    }else {
        std::cout << "Created Object (Default/Int Constructor)" << std::endl;
        this->_size = sz;
        this->_queuePointer = new T[this->_size];
    }
}

template <typename T> Queue<T>::Queue(const Queue<T> & other){
    this->_size = other._size;
    this->_currentSize = other._currentSize;
    this->_lastIndex = other._lastIndex;
    this->_queuePointer = new T[this->_size];

    for(int i=0; i < this->_size; i++){
        this->_queuePointer[i] = other._queuePointer[i];
    }
}

template <typename T> Queue<T>::~Queue(){
    delete [] this->_queuePointer;
}

// Implementation Of The Overloaded Assignment Operator
template <typename T> Queue<T> & Queue<T>::operator = (Queue<T> rhs){ // So that I can use the copy-and-swap idiom.
    this->swap(rhs);
    return *this;
}

// Implementation of Utility Functions
template <typename T> void Queue<T>::swap(Queue<T> & rhs){
    std::swap(this->_size, rhs._size);
    std::swap(this->_currentSize, rhs._currentSize);
    std::swap(this->_lastIndex, rhs._lastIndex);

    /*
     As I am assigning, it means that dynamic memory was
     allocated for the lhs object. So, before copying the
     content of the rhs to the lhs object, let's delete
     the allocated memory from the lhs object and allocate
     again based on the new size.
    */
    delete [] this->_queuePointer;
    this->_queuePointer = new T[this->_size];

    for(int i=0; i < this->_size; i++){
        this->_queuePointer[i] = rhs._queuePointer[i];
    }
}

template <typename T> T Queue<T>::enqueue(const T & node){

    if(this->isFull()){

        // The queue is full.
        throw E("Queue Exception: Your queue is full! You can't push anymore until you pop something.");
    }else {
        // The queue is not full.

        if(this->_firstInQueue == -1){
            // If it is the first item being pushed to the queue.
            this->_firstInQueue++; // The first in queue is now index 0.
        }

        // This if statement will just be executed if I push another node, and the last
        // node I added was at the last position of the queue.
        if(this->_lastIndex == (this->getSize() - 1)){
            // If the last index is at the last position of the queue,
            // set the last index to -1 again.
            this->_lastIndex = -1;
        }

        // Increasing index to the index number that we should add the new element.
        this->_lastIndex++;

        // Pushing element here (with respect to/using lastindex)...
        this->_queuePointer[this->_lastIndex] = node;

        // Increasing the current size of the queue.
        this->_currentSize++;
    }
    return (this->_queuePointer[this->_lastIndex]);
}

template <typename T> T Queue<T>::dequeue(){

    if(this->isEmpty()){
        // The queue is empty.
        throw E("Queue Exception: Your queue is empty. There is nothing to pop!");
    }

    // The queue is not empty.
    T value_to_be_returned = this->_queuePointer[this->_firstInQueue];

    if(this->_currentSize == 1){
        // If the queue has just one element and this element is at index 0.

        // Setting the index of the first in the queue to -1, because I am popping the
        // last element of the queue. Now, if I push a new element after popping this last one,
        // the element being pushed will be first in the queue, and its index will be 0.
        this->_firstInQueue = -1; // The first in queue is now back to index -1.

        // Returning the last index to -1, so that when the new item is pushed, the last index will be 0.
        this->_lastIndex = -1;

        // OBS: fiq and the li must ALWAYS go back to their initial values, -1, if all
        // the values are popped from the queue.
    }else {

        // Increasing index.
        // This if statement will just be executed if the first element in the queue
        // is at the last position of the queue. If so, we need to set the first in queue
        // variable to -1 again, and then increase it to 0, so that the next element first
        // in the queue is at index 0.
        if (this->_firstInQueue == (this->getSize() - 1)){
            this->_firstInQueue = -1;
        }

        this->_firstInQueue++;
    }

    // Decreasing queue's current size.
    this->_currentSize--;

    return value_to_be_returned;
}

Answer 1

我看到了一些可以帮助您改进代码的东西。

使用所需的#includes

代码使用std::exception、std::cout和std::swap，但是没有列出相应的头。不难推断，但如果代码已经完成，则可以帮助审阅者。代码应该有以下三行：

#include <exception>
#include <iostream>
#include <utility>

修复bug

在operator =实现和好友方面存在一些问题。首先，副本不初始化_firstInQueue成员。由于其默认值是-1，随后对函数(如dequeue )的调用将尝试访问未定义的行为的越界内存。第二，复制指针的循环遍历索引直到this->_size，但是没有考虑到Q1大于Q2的可能性。

不要使用this-> everywhere

在成员函数中，this->是隐含的，因此在任何地方编写它都不必要地扰乱了代码。此代码中的每个this->实例都可以安全地删除。

不使用std::endl如果'\n'要做

使用std::endl会发出一个\n并刷新流。除非您确实需要流刷新，否则可以通过简单地发射'\n'来提高代码的性能，而不是使用可能计算成本更高的std::endl。尽管如此，在这段代码中，我认为应该删除整行代码，因为它看起来只是调试帮助。

return不是函数

因为return是一个关键字，而不是一个函数，所以它不需要对后面的任何参数使用括号。所以，不是这样的：

bool isEmpty() const { return (!getCurrentSize()); };

我会写这个：

bool isEmpty() const { return !getCurrentSize(); }

还请注意，尾随分号是不必要的。

Answer 2

异常类

我不会重复Edward注意到的内容，只是补充说，在return表达式周围添加额外的父母亲总有一天会咬你的，所以现在(自C++17以来)有一个很好的理由而不是风格而不这样做。

class E: public std::exception{

    const char * _msg = "Default Exception.";
    E(){};

public:
    E(const char * message) throw() { this->_msg = message; }
    const char * what() const throw(){ return this->_msg; }
};

普通样式是将指针(或引用)指示符分组到接近类型的位置：

const char* message

在构造函数中，使用初始化列表，而不是正文中的赋值！

您正在让_msg默认初始化，然后使用赋值更改它。

E(const char* message) noexcept :_msg{message} { }

嗯，您没有默认的构造函数，所以永远不会使用"Default Exception."。制作

E() noexcept { }

public (而不是private)现在默认将达到它的目的。

同时，throw()异常规范已经消失！但是，带有空的param列表的throw()将在几年内继续被接受为noexcept的同义词。这是为了轻松地升级旧代码库中的编译器，而不是编写新代码。

基类已经为virtual声明了一个what函数。你可能想要推翻这个，也许你是。也许你不是，如果签名不完全一样的话！这是一个隐秘的bug，所以很高兴我们现在有了override关键字，这表明了您的意图。如果您把签名搞砸了，编译器会告诉您它不匹配。

const char* what() const noexcept  override  { return msg; }

我意识到这是一个简单的原始C-字符串很好的用法，甚至是首选--您希望它不被抛出，所以不想涉及string类。

现在，回到const char*。我同意“老式”的类型在这里是合适的，但你仍然可以用最新的成语来更好地表达它。请参阅⧺F.25 (并查看一般的标准指南！)

所以写

    gsl::zstring _msg = "Default Exception.";

    E (gsl::zstring message) ⋯

Answer 3

队列类

static const int _defaultSize = 10;
static const int _maxSize = 1000;

有人说“constexpr是新的static const”。通常，在可能的地方改变这些。

constexpr int _defaultSize = 10;
constexpr int _maxSize = 1000;

写带有前导下划线的标识符是个坏主意，通常被劝阻为一种风格。注意，如果(并且只有在)下一个字符不是大写字母或其他下划线时，成员名才是合法的。

T * _queuePointer;

见⧺R.20。

unique_ptr<T[]> queuePointer;

然后，在构造函数中：

template <typename T> 
Queue<T>::Queue(int sz) {
    ⋮
    this->_queuePointer = new T[this->_size];

您应该(1)使用成员初始化列表；(2)不要使用裸new (⧺C.149)。

template <typename T> 
Queue<T>::Queue(int sz)
    : size{ensure_range(sz, 1,_maxsize)}, 
      queuePointer{make_unique<T[]>(sz)}
    { }

麻烦的是，在做分配之前，我必须把范围填进去。但是，编写一个单独的ensure_range (value, high, low)函数是通用的和可重用的！

转到复制构造函数。

for(int i=0; i < this->_size; i++){
    this->_queuePointer[i] = other._queuePointer[i];
}

使用std::copy算法代替。(请注意，提供的集合(如vector )甚至更有效，并且复制-构造存在的元素，而不是默认的构造，然后分配。)

破坏者：

通过将指针设置为unique_ptr，这种情况现在完全消失了。不要声明，也不要写！自动生成的更好。

swap成员函数重新分配和复制缓冲区？它似乎也使rhs对象的缓冲区保持不变，而不是将其切换到另一个缓冲区。这是不对的，这些评论“就像我分配给…的那样”让我觉得你的电线交叉了。

有一个nothrow swap函数很重要。它应该切换指针，就像它切换大小和索引一样。

我想你这样做是出于各种原因。但如果你真的想要排队，只需写：

template <typename T, size_t capacity>
using Queue = std::queue<T>;

预先分配的固定容量可以通过使用底层集合中包含该行为。来实现.

template <typename T, size_t capacity>
using Queue = std::queue<T, boost::container::static_vector<T,capacity>>;

不过，表演不错！跟上你的学习步伐！