4
\$\begingroup\$

Below is a constexpr circular queue whose size is fixed. From what I tested the code seems to work exactly as expected of a queue. One advantage is how there's no dynamic allocations, so ignoring the hopefully low chance that there are errors in the logic, are there any suggestions to improve this code's performance?

Code taken from: https://github.com/SteveZhang1999-SZ/CircularQueue/blob/master/circularQueue.hpp

#ifndef CIRCULARQUEUEHPP
#define CIRCULARQUEUEHPP
#include <cstddef>
#include <type_traits>

template<class T ,std::size_t N /*Max capacity*/, 
typename Idxtype = std::size_t /*Integral type to store indices. May change,
like to uint_least16_t, to lower space usage*/,
typename = typename std::enable_if<std::is_integral<Idxtype>::value>::type>
class circularQueue{
    union myUnion{
        bool forConstexprCtor;
        T value;
        constexpr myUnion() : forConstexprCtor{true} {}

        template<class PossibleUnion,typename = typename std::enable_if<std::is_same<PossibleUnion, myUnion>::value >::type>
        constexpr myUnion(PossibleUnion&& other) : value{other.value} {}

        template<typename... Args,typename = typename std::enable_if<std::is_constructible_v<T,Args>...>::type> 
        constexpr myUnion(Args&&... args) : value(std::forward<Args>(args)...) {}

        template<typename AnotherUnion>
        constexpr void operator=(const AnotherUnion&& other){
            value = other.value;
        }
    };
    struct myStruct{
        myUnion theArray[N];
        template<typename... t>
        constexpr myStruct(t&&... theList) : theArray{(theList)...} {}
    } mS;
    //Head == idx of element at the front. Tail == idx of last element + 1. theSize == queue's size
    Idxtype head, tail, theSize;
    
    public:
        constexpr circularQueue() : head{0}, tail{0}, theSize{0} {}
        explicit constexpr circularQueue(const circularQueue<T,N>& other) : mS{other.mS}, head{other.head}, 
        tail{other.tail}, theSize{other.theSize} {}
        
        explicit constexpr circularQueue(circularQueue<T,N>& other) : 
        circularQueue{const_cast<circularQueue<T,N> const&>(other)} {}
        
        template<typename... Args>
        explicit constexpr circularQueue(Args&&... theList) : mS{(theList)...}, head{0},
        tail{sizeof...(theList)}, theSize{sizeof...(theList)}{}
    
        constexpr bool push(const T theObj){
            if(theSize == N){
                return false;//queue is full
            }
            mS.theArray[(tail == N ? (tail = 0)++ : tail++)] = myUnion(std::move(theObj));
            return ++theSize; //++theSize always > 0. Return true
        }
        template<typename ...Args> 
        constexpr bool emplace(Args&&... args){
            if(theSize == N){
                return false;//queue is full
            }
            mS.theArray[(tail == N ? (tail = 0)++ : tail++)] = myUnion(std::forward<Args>(args)...);
            return ++theSize;
        }

        constexpr const T& front() const noexcept{
            return mS.theArray[head].value;
        }

        constexpr bool pop() noexcept{
            if(!theSize) return false; //If it's empty, pop fails
            (head == N ? head = 0 : head++);
            return theSize--;//Even if theSize == 1, theSize-- will > 0 so this returns true.
        }

        constexpr bool empty() const noexcept{
            return !theSize;
        }
        constexpr Idxtype size() const noexcept{
            return theSize;
        }
        constexpr std::size_t maxCapacity() const noexcept{
            return N;
        }
        //Assignment
        constexpr circularQueue& operator=(const circularQueue<T,N>& other){ 
            std::size_t first{head = other.head};
            tail = other.tail;
            theSize = other.theSize;
            if(other.tail < other.head){ //Only need to copy elements from other.head to other.tail
                for(; first < N; ++first){
                    mS.theArray[first] = other.mS.theArray[first];
                }
                for(first = 0; first < tail; ++first){
                    mS.theArray[first] = other.mS.theArray[first];
                }
            }
            else{
                for(; first < other.tail; ++first) mS.theArray[first] = other.mS.theArray[first];
            }
            return *this;
        }
        constexpr circularQueue& operator=(const circularQueue<T,N>&& other){ 
            std::size_t first{head = std::move(other.head)};
            tail = std::move(other.tail);
            theSize = std::move(other.theSize);
            if(other.tail < other.head){ //Only need to copy elements from other.head to other.tail
                for(; first < N; ++first){
                    mS.theArray[first] = std::move(other.mS.theArray[first]);
                }
                for(first = 0; first < tail; ++first){
                    mS.theArray[first] = std::move(other.mS.theArray[first]);
                }
            }
            else{
                for(; first < other.tail; ++first) mS.theArray[first] = std::move(other.mS.theArray[first]);
            }
            return *this;
        }
};
#endif //CIRCULARQUEUEHPP
\$\endgroup\$
3
\$\begingroup\$

I’m afraid you have some very serious, game-breaking bugs in this class, mostly to do with your use of a union. But I’ll do the review from top to bottom to keep everything in order.

Before I begin: In my opinion, the biggest problem with this code—the problem that would first make me reject it out of hand before even bothering to try reading it—is the near-complete lack of useful comments. There are one or two comments that are useful, but there are many more things in the code that just make no sense at all at first glance, and with no comments to explain your thinking, I have no idea whether I’m looking at the most ingenious piece of software engineering ever committed, or an incoherent mess. Why are you using a union? Why is the array inside a struct? Why are some special member functions defined while others are not? 🤷🏼 All mysteries. Some I can (somewhat) guess at. Others are just ciphers.

One major thing that isn’t explained anywhere (that comes up as an issue over and over in the review) is whether this queue is intended to be used with non-trivial types (like std::string). That makes a huge difference in the complexity of the problem. If I saw a comment explaining that only trivial types should be used (or even better, a static_assert), then fine. But without that, I have to assume the intention is to use non-trivial types. And that’s going to make things a lot more complicated, and the review a lot more brutal.

template<class T ,std::size_t N /*Max capacity*/, 
typename Idxtype = std::size_t /*Integral type to store indices. May change,
like to uint_least16_t, to lower space usage*/,
typename = typename std::enable_if<std::is_integral<Idxtype>::value>::type>

I’m not sure enable_if is what you want to use here.

enable_if/SFINAE is the mechanism to use when you want to disable particular template instantiations while leaving other options available. In other words, if your intention was that the class you’ve written will only work for integral indexes… but there is another class that will work for non-integral indexes… then SFINAE would be the way go.

But I don’t think that’s your intention. I think you just want to ban non-integral indexes, and that’s that. For that, it’s simpler just to use static_assert:

template<class T ,std::size_t N /*Max capacity*/, 
typename Idxtype = std::size_t /*Integral type to store indices. May change,
like to uint_least16_t, to lower space usage*/>
class circularQueue
{
    static_assert(std::is_integral_v<Idxtype>);

(Also, you’re using enable_if wrong. What you want is to have an undefined (or static_assert-ed) primary template with the selection parameter defaulted, and then use enable_if in the real template, like so:

// Primary template is undefined so it will trigger a compile error.
// You could also define it with a static_assert to get a clearer
// error message.
template <
    class T,
    std::size_t N,
    typename Idxtype = std::size_t,
    typename = void>
class circularQueue;

template <
    class T,
    std::size_t N,
    typename Idxtype>
class circularQueue<T, N, Idxtype, typename std::enable_if<std::is_integral<Idxtype>::value>::type>
{
   // ...

The way you’re using enable_if, I could use a non-integral type as the index by doing this:

// A std::string index!
circularQueue<T, std::size_t, std::string, void>

The two-step dance shown above—with the empty primary template—is how you prevent such abuses.)

union myUnion{
    bool forConstexprCtor;
    T value;
    constexpr myUnion() : forConstexprCtor{true} {}

    template<class PossibleUnion,typename = typename std::enable_if<std::is_same<PossibleUnion, myUnion>::value >::type>
    constexpr myUnion(PossibleUnion&& other) : value{other.value} {}

    template<typename... Args,typename = typename std::enable_if<std::is_constructible_v<T,Args>...>::type> 
    constexpr myUnion(Args&&... args) : value(std::forward<Args>(args)...) {}

    template<typename AnotherUnion>
    constexpr void operator=(const AnotherUnion&& other){
        value = other.value;
    }
};

This is a clever way to have correctly sized and aligned storage for an uninitialized T while still being constexpr, but there are lot of problems… so many, in fact, that I don’t know if you could reasonably fix them in C++17.

First, you shouldn’t use bool for the “alternate” object. bool is not necessarily 1 byte, nor is its alignment necessarily 1. It’s entirely possible and legal for bool to be 4 bytes (and that actually was the case in older versions of Visual C++). You could end up with a situation where you’ve created a circular buffer for 10 chars, and it turns out to be 40 bytes in size.

You can use any flavour of char (signed, unsigned, or not), or std::byte. But a better solution is to use an empty class. Why? Because:

   bool forConstexprCtor; // or use char
   constexpr myUnion() : forConstexprCtor{true /* or '\0' for char */} {}

is not a no-op default construction, because it has to set forConstexprCtor to true (or zero). But this is a no-op:

   // struct empty_t {};
   empty_t forConstexprCtor;
   constexpr myUnion() : forConstexprCtor{} {}

If you made a circular buffer with 100 elements, the constructor has to initializer 100 bools to true. With an empty type, it has to theoretically initialize those 100 objects… but since initialization is zero-cost, that means nothing actually needs to be done in practice.

template<class PossibleUnion,typename = typename std::enable_if<std::is_same<PossibleUnion, myUnion>::value >::type>
constexpr myUnion(PossibleUnion&& other) : value{other.value} {}

Okay, so what I think you’re trying to do here is write both your move and copy constructors in a single function. That’s… not a great idea on any given day. But it’s especially bad here because of the surrounding context.

Let’s start with asking why you even need to define the move and copy constructors. I can think of two reasons:

  1. You want to use non-trivial Ts. A non-trivial T will probably cause the move and copy constructors to be deleted.
  2. The following constructor template “swallows” the move/copy operations, so you need to reclaim them.

So let’s assume you need to rewrite the move and copy constructors. What’s wrong with doing it this way? Well, a lot of things.

To start with, the code above turns the copy and move constructors into two copy constructors. You lose move ops: myUnion’s move constructor invokes value’s copy constructor… not its move constructor. You can “fix” this problem by using std::forward(), I suppose.

But there’s other problems. Move ops should always be noexcept whenever possible. And most types are noexcept moveable. But if we put one of those types in this union, then it won’t be anymore. You could probably fix this with type traits.

But you also lose triviality. This, too, might be able to be “fixed”… but certainly not easily.

My advice is to forget trying to be clever. You’re only shooting yourself in the foot, not to mention making it more difficult for others to understand and maintain the class. You want copy and move constructors? Write copy and move constructors. Individually, as the good Bjarne intended.

But that brings us to the biggest problem here: you impement the copy/move by assuming that value is the active object in the union. Why would you assume that? It certainly won’t be true for a default-constructed circular queue:

auto cq1 = circularQueue<std::string, 32>{};
// cq1 internally has an array of 32 myUnion objects, all with active
// object set to "forConstexprCtor"... not "value".

auto cq2 = cq1;
// This calls the copy constructor of myUnion 32 times, which copies 32
// nonexistent "value" objects, triggering UB (and, likely, a
// spectacular crash the first time you try to do anything with any of
// those strings).

You can’t fix this within the union. You need an external discriminator of some sort, to keep track of which myUnion objects have forConstexprCtor active, and which have value active. And then you need to write the copy constructor in circularQueuenot myUnion… to properly move/copy each myUnion object according to its active member.

What a complicated mess, eh?

template<typename... Args,typename = typename std::enable_if<std::is_constructible_v<T,Args>...>::type> 
constexpr myUnion(Args&&... args) : value(std::forward<Args>(args)...) {}

This seems like a simple and obvious implementation, but… consider what happens if T is a vector<int>, and you do this:

auto v1 = std::vector<int>{4, 4};
std::cout << v1.size(); // prints 2

auto v2 = circularQueue<std::vector<int>, N>::myUnion{4, 4};
std::cout << v2.value.size(); // what do you think this prints?

The problem here is that you don’t support initializer lists with myUnion. Perhaps that’s not a problem. Perhaps you’re okay with preventing in-place construction with initializer lists. But it’s something you should think about.

Aside from that, I think implementing a direct-construction constructor for value like this is a terrible idea. Of the many headaches it introduces, the fact that it “swallows” the copy and move constructors is just the tip of the iceberg.

If you really want a function like this (and, I can’t imagine why you think you need it), you really should use a tagged constructor instead:

struct value_construct_tag_t {} value_construct_tag;

template<typename... Args,typename = typename std::enable_if<std::is_constructible_v<T,Args>...>::type> 
constexpr myUnion(value_construct_tag_t, Args&&... args) : value(std::forward<Args>(args)...) {}

// used as:
myUnion(value_construct_tag, args...);

Next up is the copy/move assignment dual-purpose function, which basically has all the same problems as the copy/move constructor chimera.

Okay, so myUnion is just riddled with problems. In my opinion, all of them are due to you trying to be too clever, and trying to make myUnion a “perfect”, self-contained, self-aware type. My advice? Throw it all out. myUnion should be nothing more than a union of T and some dummy, empty type (along with dummy operations if necessary to make it work with non-trivial Ts). Don’t try to make myUnion a container in its own right. It’s nothing more than an internal storage type; an implementation detail. All the real work should be done by circularQueue.

struct myStruct{
    myUnion theArray[N];
    template<typename... t>
    constexpr myStruct(t&&... theList) : theArray{(theList)...} {}
} mS;

I honestly don’t see the purpose of this internal struct. Am I missing something? It looks it all you need it for is that constructor, but that constructor is trivial to write in place where you need it (and you only need it in one place).

Idxtype head, tail, theSize;

Declaring all your variables on one line like this is terrible practice in general. You should never do it.

And in this case, it’s actually self-defeating. If you gave myUnion a default constructor that activated forConstexprCtor, and defined your member variables like this:

myUnion theArray[N] = {};
Idxtype head = {};
Idxtype tail = {};
Idxtype theSize = {};

then your default constructor could be defaulted:

constexpr circularQueue() noexcept = default;

Next up is the copy constructor, and this (along with the move constructor, which you don’t have but should) is where the rubber really hits the road.

When you are coping a circularQueue, none, some, or all of the elements in other will be present. You need to correctly handle all cases. You need to do this->theArray[i].value = other.theArray[i].value; for all elements that are present, and this->theArray[i].forConstexprCtor = {}; for all elements that are not.

Figuring out how to do that correctly is the real trick of writing this type.

As an aside… why is your copy constructor explicit? What do you think that is accomplishing?

And I am completely baffled as to why you have a constructor that copies from a non-const circularQueue. Is this because the following template constructor swallowed the copy/move ops? If so, there is an easier fix.

template<typename... Args>
explicit constexpr circularQueue(Args&&... theList) : mS{(theList)...}, head{0},
tail{sizeof...(theList)}, theSize{sizeof...(theList)}{}

I’m guessing the intention here is to be able to write code like:

auto c = circularQueue<int, 4>{1, 2, 3, 4};
// c is a queue with 1,2,3,4 in it.

That’s cool, but as you may or may not have noticed, this function swallows your default constructor, and your copy and move constructors. I’m blindly guessing that’s why you implemented a non-const lvalue reference copy constructor. If that’s the case, there’s a better way.

First, note that it doesn’t make sense to have zero args. That would be the default constructor. So you only need to consider cases with one or more args. So you can do this:

template <typename T, typename... Args>
circularQueue(T&& t, Args&&... theList)

Now the default constructor is safe. (It was anyway, but bear with me.)

Next up you want to rescue the copy and move constructors. That’s easy: that’s the case where T&& is circularQueue with or without const and either an lvalue or rvalue reference, and args is empty. No problem (using concepts… to do this with enable_if, you’re on your own—perhaps use a non-type template parameter?):

template <typename T, typename... Args>
requires requires(sizeof...(Args) > 0 or not std::is_same_v<circularQueue, std::remove_cv_ref_t<T>>)
circularQueue(T&& t, Args&&... theList)

Now this constructor will not step on the toes of either the default constructor, or the copy or move constructor.

constexpr bool push(const T theObj)

I’m not a fan of interfaces that let you just ignore errors. If you fail you push an object to the queue, that’s not just an “oh, well, doesn’t matter” kind of thing. That’s a critical error! You’ve lost data. You really want to know when that happens.

At the very least, you should mark the return value here as [[nodiscard]]. But honestly, this seems like something that warrants an exception.

Also… why is theObj const? There doesn’t seem to be any point. Worse, making it const means it’s impossible to move it. So this line:

mS.theArray[(tail == N ? (tail = 0)++ : tail++)] = myUnion(std::move(theObj));

doesn’t do what you apparently think it does. The std::move() in there does absolutely nothing.

(And I’m not even talking about the gastly ternary op going on in there. That indexing operation is one of the most important parts of your whole class! It’s what makes your circular queue circular! It even gets repeated in both push() and emplace()! It shouldn’t be buried in a mess of operations like that! That should be its own function.)

constexpr const T& front() const noexcept

This shouldn’t be a noexcept function, because noexcept means a function cannot fail. But this function can fail; it can fail if the queue is empty. You don’t necessarily need to throw an exception here (or you could throw one in debug mode, and just do UB in release mode). But you do need to not give the impression the function can’t fail.

constexpr std::size_t maxCapacity() const noexcept

Unless you have a reason not to, you should follow the conventions of the standard library. In the standard library, this function would be called capacity(). (Plus “max capacity” is redundant. A thing’s “capacity” is the maximum it can hold, by definition.)

constexpr circularQueue& operator=(const circularQueue<T,N>& other)

The copy/move assignment operations have all the complexity of the copy/move constructors… and then some, because you also have to handle the existing elements in this, all while giving the strong exception guarantee (if possible).

As it stands, you have the same serious bugs in the assignment ops as in the constructors, plus more. The comment in the function says “[o]nly need to copy elements from other.head to other.tail”… except that’s wrong. Yes, you do only need to copy the active elements and not the inactive ones… but you also need to deactivate the inactive ones in this.

constexpr circularQueue& operator=(const circularQueue<T,N>&& other)

Why is this taking a const rvalue reference? That breaks moving; it’s no long a move assignment, and all the std::move()s in there do nothing.

Finally, this class doesn’t have a destructor, but it needs one, because you need to manually call the T destructors for active elements, and the dummy destructors for the inactive ones.

Overall, I think the biggest source of bugs here is the fact that you’re not keeping track of which elements are active in your unions. Even when you’re dealing with trivial types, you can’t do that. It is UB to access the non-active member of a union (though it is usually silent UB, meaning your program is broken, but you’ll never know because everything appears to “work”). And when it’s a non-trivial type, you’re pretty much cruising for a crash.

Normally you’d use a flag to keep track of which part of the union is active—that’s what std::variant does. But you can actually get away without a flag, because you can tell which elements are active and which aren’t by whether they’re in the live part of the queue or not.

But there’s still the complexity of handling non-trivial types. It may be necessary to have two different union types: one for trivial types, and one for non-trivial types—that’s how I’ve seen it done for implementations of variant anyway.

| improve this answer | |
\$\endgroup\$

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.