3
\$\begingroup\$

Follow up to my question here: Constexpr circular queue . I've taken the time to fix the many problems pointed out there and am asking for any tips/corrections for the new version below.

The queue will work with non-trivial types in non-constexpr contexts. For types that are trivially copy assignable and destructible, it works with constexpr contexts.

Code is by me and posted here: https://github.com/SteveZhang1999-SZ/CircularQueue/blob/master/circularQueue.hpp

Changes:

Idxtype must be an integral type so unlike before with enable_if, the new code enforces this with a static_assert.

forConstexprCtor is now an empty class instead of a bool since the former has a no-op construction.

The union Cell will change the active member by either constructing a Cell with the desired active member and assigning it or through placement new.

In the assignment methods, the old active elements are destroyed if either std::is_trivially_copy_assignable::value and std::is_trivially_destructible::value are false, and the only elements in the other queue that are copied are the ones with value as the Cell's active member.

The (Args&&... theList) constructor is no longer preferred over the default empty constructor should a circular queue be constructed with zero arguments.

When inserting elements, users may use the full() method to check if the queue is full.

Changes not made

The Idxtypes are still declared on one line. Personally, I think putting them all in one line is neater and this shouldn't introduce errors since Idxtype will be something simple like shorts or longs.

Direct construction for the member named value remains. This is necessary so I can construct a union with value as the active member initially, then assign it to another union so that the end result is that the assigned-to union has value as the active member now (Which is doable in constexpr contexts).

#ifndef CIRCULARQUEUEHPP
#define CIRCULARQUEUEHPP
#include <cstddef>
#include <new> //For placement new
#include <type_traits>
template<class T, bool B> union Cell;//bool B == std::is_trivially_destructible<T>::value
template<class T>
union Cell<T, true>{
    class emptyClass{} forConstexprCtor;
    T value;
    //Initializes forConstexprCtor because constexpr union constructors must initialize a member
    constexpr Cell() : forConstexprCtor{} {}
    //Initializes value with the provided parameter arguments
    template<typename... Args> 
    constexpr Cell(Args&&... args) : value((args)...) {}
};
template<class T>
union Cell<T, false>{
    class emptyClass{} forConstexprCtor;
    T value;
    constexpr Cell() : forConstexprCtor{} {}
    template<typename... Args> 
    constexpr Cell(Args&&... args) : value((args)...) {}
    ~Cell(){} //Included because Cell<T, false>'s destructor is deleted
};
template<class T, std::size_t N, typename Idxtype>
struct commonQueueFunctions{
    static_assert(std::is_integral<Idxtype>::value, "Idxtype must be an integral type\n");
    constexpr bool full() const noexcept {return theSize == N;} //Check if queue is full
    constexpr bool empty() const noexcept {return !theSize;} //Check if queue is empty
    constexpr Idxtype size() const noexcept {return theSize;} //Returns the queue's current size
    //Returns the max number of elements the queue may hold
    constexpr std::size_t capacity() const noexcept {return N;}
    //Returns the element next to be popped. Undefined behavior if queue is empty
    constexpr const T& front() const {return theArray[head].value;}
    constexpr T& front() {return theArray[head].value;}
    //Returns the element last to be popped. Undefined behavior if queue is empty
    constexpr const T& back() const {return theArray[tail - 1].value;}
    constexpr T& back() {return theArray[tail - 1].value;}
    protected:
        Idxtype head{0}, tail{0}, theSize{0};
        Cell<T, std::is_trivially_destructible<T>::value> theArray[N];
        constexpr void clear(){ //Destroys value in the queue when value is the active member
            if(this->head > this->tail|| (this->head == this->tail && this->theSize == N)){
                for(; this->head < N; ++this->head){
                    this->theArray[this->head].value.~T();
                }
                this->head = 0;
            } 
            for(; this->head < this->tail; ++this->head){
                this->theArray[this->head].value.~T();
            }
        }
        constexpr commonQueueFunctions() = default;
        constexpr commonQueueFunctions(const commonQueueFunctions& other) : head{other.head},
        tail{other.tail}, theSize(other.theSize){ //Copy constructor
            std::size_t originalHead(other.head);
            //If other is full, there's a chance that other.head == other.tail
            if(other.head > other.tail || (other.head == other.tail && other.theSize == N)){
                for(; originalHead < N; ++originalHead){
                    if constexpr(std::is_trivially_copy_assignable<T>::value && 
                                 std::is_trivially_destructible<T>::value){
                        theArray[originalHead] = other.theArray[originalHead];
                    } else {
                        new(&theArray[originalHead].value)T(other.theArray[originalHead].value);
                    }
                }
                originalHead = 0;
            }
            for(; originalHead < other.tail; ++originalHead){
                if constexpr(std::is_trivially_copy_assignable<T>::value && 
                                 std::is_trivially_destructible<T>::value){
                    theArray[originalHead] = other.theArray[originalHead];
                } else {
                    new(&theArray[originalHead].value)T(other.theArray[originalHead].value);
                }
            }
        }
        constexpr commonQueueFunctions(commonQueueFunctions&& other) : head{other.head},
        tail{std::move(other.tail)}, theSize(std::move(other.theSize)){ //Move constructor
            std::size_t originalHead(std::move(other.head));
            if(other.head > other.tail || (other.head == other.tail && other.theSize == N)){
                for(; originalHead < N; ++originalHead){
                    if constexpr(std::is_trivially_copy_assignable<T>::value && 
                                 std::is_trivially_destructible<T>::value){
                        theArray[originalHead] = std::move(other.theArray[originalHead]);
                    } else {
                        new(&theArray[originalHead].value)T(std::move(other.theArray[originalHead].value));
                    }
                }
                originalHead = 0;
            }
            for(; originalHead < other.tail; ++originalHead){
                if constexpr(std::is_trivially_copy_assignable<T>::value && 
                                 std::is_trivially_destructible<T>::value){
                    theArray[originalHead] = std::move(other.theArray[originalHead]);
                } else {
                    new(&theArray[originalHead].value)T(std::move(other.theArray[originalHead].value));
                }
            }
        }
        constexpr commonQueueFunctions& operator=(const commonQueueFunctions& other){//Copy assignment
            std::size_t originalHead(head = other.head);
            if constexpr((std::is_trivially_copy_assignable<T>::value && 
            std::is_trivially_destructible<T>::value) == false){
                clear();
            } 
            if(other.head > other.tail || (other.head == other.tail && other.theSize == N)){
                for(; originalHead < N; ++originalHead){
                    if constexpr(std::is_trivially_copy_assignable<T>::value && 
                                 std::is_trivially_destructible<T>::value){
                        theArray[originalHead] = other.theArray[originalHead];
                    } else {
                        new(&theArray[originalHead].value)T(other.theArray[originalHead].value);
                    }
                }
                originalHead = 0;
            }
            for(; originalHead < other.tail; ++originalHead){
                if constexpr(std::is_trivially_copy_assignable<T>::value && 
                                 std::is_trivially_destructible<T>::value){
                    theArray[originalHead] = other.theArray[originalHead];
                } else {
                    new(&theArray[originalHead].value)T(other.theArray[originalHead].value);
                }
            }
            tail = other.tail;
            theSize = other.theSize;
            return *this;
        }
        constexpr commonQueueFunctions& operator=(commonQueueFunctions&& other){ //Move assignment
            std::size_t originalHead(head = other.head);
            if constexpr((std::is_trivially_copy_assignable<T>::value && 
            std::is_trivially_destructible<T>::value) == false){
                clear();
            }
            if(other.head > other.tail || (other.head == other.tail && other.theSize == N)){
                for(; originalHead < N; ++originalHead){
                    if constexpr(std::is_trivially_copy_assignable<T>::value && 
                                 std::is_trivially_destructible<T>::value){
                        theArray[originalHead] = std::move(other.theArray[originalHead]);
                    } else {
                        new(&theArray[originalHead].value)T(std::move(other.theArray[originalHead].value));
                    }
                }
                originalHead = 0;
            }
            for(; originalHead < other.tail; ++originalHead){
                if constexpr(std::is_trivially_copy_assignable<T>::value && 
                                 std::is_trivially_destructible<T>::value){
                    theArray[originalHead] = std::move(other.theArray[originalHead]);
                } else {
                    new(&theArray[originalHead].value)T(std::move(other.theArray[originalHead].value));
                }
            }
            tail = std::move(other.tail);
            theSize = std::move(other.theSize);
            return *this;
        }
        template<typename... Args> //Constructor which accepts arguments to construct theArray
        constexpr commonQueueFunctions(std::size_t theHead, std::size_t theTail, std::size_t paramSize,
        Args&&... theList) : head(theHead), tail(theTail), theSize(paramSize),theArray{(theList)...}{}
};
template<class T, std::size_t N, bool B, typename Idxtype> struct theQueue;
template<class T, std::size_t N, typename Idxtype>
struct theQueue<T,N, true, Idxtype> : public commonQueueFunctions<T, N, Idxtype>{
    constexpr theQueue() = default; //Default constructor
    //Constructor which accepts arguments to construct theArray
    template<typename... Args, typename = 
    typename std::enable_if<(... && std::is_constructible_v<T,Args>)>::type > 
    explicit constexpr theQueue(Args&&... theList) : commonQueueFunctions<T, N, Idxtype>(0, sizeof...(theList),
    sizeof...(theList),std::forward<Args>(theList)...){}
    constexpr bool push(T theObj){//Pushes the given element value to the end of the queue
        if(this->theSize == N){
            return false;//queue is full
        }
        this->theArray[(this->tail == N ? (this->tail = 0)++ : this->tail++)] = Cell<T,true>(std::move(theObj));
        return ++this->theSize; //++theSize always > 0. Return true
    }
    template<typename ...Args> 
    constexpr bool emplace(Args&&... args){ //Same as push, but the element is constructed in-place
        if(this->theSize == N){
            return false;//queue is full
        }
        this->theArray[(this->tail == N ? (this->tail = 0)++ : this->tail++)] = Cell<T,true>((args)...);
        return ++this->theSize;
    }
    constexpr bool pop() noexcept{ //Removes the element at the queue's front
        if(!this->theSize) return false; //If it's empty, pop fails
        (this->head == N ? this->head = 0 : ++this->head);
        return this->theSize--;//Even if theSize == 1, theSize-- will > 0 so this returns true.
    }
};
template<class T, std::size_t N, typename Idxtype>
struct theQueue<T,N, false, Idxtype>  : public commonQueueFunctions<T, N, Idxtype>{
    constexpr theQueue() = default;
    template<typename... Args, typename = 
    typename std::enable_if<(... && std::is_constructible_v<T,Args>) >::type > 
    explicit constexpr theQueue(Args&&... theList) : commonQueueFunctions<T, N, Idxtype>(0, sizeof...(theList),
    sizeof...(theList),std::forward<Args>(theList)...) {}

    constexpr bool push(T theObj){
        if(this->theSize == N){
            return false;//queue is full
        }
        new(&this->theArray[(this->tail == N ? (this->tail = 0)++ : this->tail++)].value)T(std::move(theObj));
        return ++this->theSize; //++theSize always > 0. Return true
    }
    template<typename ...Args> 
    constexpr bool emplace(Args&&... args){
        if(this->theSize == N){
            return false;//queue is full
        }
        new(&this->theArray[(this->tail == N ? (this->tail = 0)++ : this->tail++)].value)T((args)...);
        return ++this->theSize;
    }
    constexpr bool pop(){
        if(!this->theSize) return false; //If it's empty, pop fails
        this->theArray[(this->head == N ? this->head = 0 : this->head++)].value.~T();
        return this->theSize--;
    }
    ~theQueue(){ //Destroys every Cell's value where value is the active member
        this->clear();
    }
};
template<class T, std::size_t N, typename Idxtype = std::size_t>
using circularQueue = 
theQueue<T,N,std::is_trivially_destructible<T>::value && std::is_trivially_copy_assignable<T>::value, Idxtype>;
#endif //CIRCULARQUEUEHPP
```
\$\endgroup\$
1
\$\begingroup\$

Add empty lines and whitespace

You hardly use empty lines and sometimes omit spaces around operators, leading to very dense code. This makes it very hard to see the structure in your code. I recommended these rules of thumb:

  • Add empty lines between functions and classes.
  • Add an empty line before and after every if-then-else-block.
  • Add whitespace around binary operators, except:
  • Add whitespace after a comma, but not before.
  • Add whitespace after a semicolon if another statement or a comment follows.

Also just avoid having multiple statements on one line. That includes things like:

if(!this->theSize) return false;

That should become:

if(!this->theSize) {
    return false;
}

Don't write this-> unnecessarily

In C++ it is usually not necessary to explicitly write this-> inside member functions. However, there are a few cases where it is necessary, such as:

  1. When you have a local variable in a member function that shadows a member variable. To be able to access the member variable you need to specify this->.
  2. When you to pass a pointer or reference to the current object.
  3. When you are referring to a member function or variable of a templated base class.

The reason for the latter is explained in this question.

It might be tempting to write this-> everywhere, but it does hurt readability. So try to only do it where necessary.

Split up complex expressions

Similar to the whitespace issue, very complex one-line expressions can be hard to follow. Take for example:

this->theArray[(this->tail == N ? (this->tail = 0)++ : this->tail++)] = Cell<T,true>(std::move(theObj));

Part of the complexity is from all the thises, but also because of the ternary expression and the combined assignment and post-increment of tail. You cannot get rid of this-> inside theQueue when referring to members of the base class commonQueueFunctions, however you can minimize it by creating a helper function in the base class to update the tail pointer and return a reference to the next free element in the array for you:

template<class T, std::size_t N, typename Idxtype>
struct commonQueueFunctions {
    ...
    constexpr auto &nextFreeElement() {
        if (tail == N)
            tail == 0;
        return theArray[tail++];
    }
};

Then inside push() for trivial types, you can write:

this->nextFreeElement() = Cell<T, true>(std::move(theObj));

Inside the variant for non-trivial types, you can write:

new(&this->nextFreeElement().value) T(std::move(theObj));

You can do something similar for pop(). You can also consider moving the updating of this->theSize into the base class itself. Basically, move as much as possible into the base class, and only handle the actual differences in the derived class.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Regarding the this->, I noticed that the clear() method didn't need the this-> to refer the variables since it's part of commonQueueFunctions, so I cleaned that up. For the variables in the theQueue<class T, std::size_t N, bool B, typename Idxtype> methods, I think the this-> is mandatory since those variables are inherited from commonQueueFunctions. In my previous submission, everything was in one class, so I knew I didn't need to refer to the variables with this->. \$\endgroup\$ – Steve Zhang Jul 1 at 22:23
  • \$\begingroup\$ You don't need this-> to refer to inherited variables or functions either. \$\endgroup\$ – G. Sliepen Jul 2 at 4:45
  • 1
    \$\begingroup\$ In a push() method, I replaced one of the this>theSize with theSize, but I got an error saying "use of undeclared identifier 'theSize'". In case it's important, this is on Visual Studio Code. \$\endgroup\$ – Steve Zhang Jul 2 at 15:31
  • \$\begingroup\$ You're correct, it is actually necessary in the derived class, but not in the base class. I've updated the answer with a short explaination, and a link to another question which has a much more detailed answer about why this-> is necessary in the derived class. \$\endgroup\$ – G. Sliepen Jul 2 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.