6
\$\begingroup\$

I implemented a queue that holds elements on an array as underlying data type:

#include <cstddef>
#include <cassert>
#include <concepts>
#include <stdexcept>
#include <type_traits>
#include <iostream>

namespace mine {
template <std::semiregular T, std::size_t N> class queue {
public:
  using value_type = std::remove_cv_t<T>;
  using const_value_type = std::add_const_t<value_type>;

  using reference_type = std::add_lvalue_reference_t<value_type>;
  using const_reference_type = std::add_const_t<reference_type>;

  using size_type = std::size_t;
  using const_size_type = std::add_const_t<size_type>;

  void enqueue(const value_type val) {
    if (current_size == N) {
      throw std::overflow_error("queue overflowed.");
    }

    if (current_size == 0) {
      m_head = m_tail = 0;
    }

    m_tail = current_size;
    m_data[current_size++] = val;
  }

  value_type dequeue() {
    if (current_size == 0) {
      m_head = m_tail = 0;
      throw std::underflow_error("queue underflowed.");
    }

    --current_size;

    auto ret = m_data[m_head];
    m_data[m_head] = T{};
    ++m_head;
    return ret;
  }

  [[nodiscard]] reference_type head() { return m_data[m_head]; }
  [[nodiscard]] const_reference_type head() const { return m_data[m_head]; }

  [[nodiscard]] reference_type tail() { return m_data[m_tail]; }
  [[nodiscard]] const_reference_type tail() const { return m_data[m_tail]; }

  [[nodiscard]] bool empty() noexcept { return current_size == 0; }
  [[nodiscard]] const bool empty() const noexcept { return current_size == 0; }

  [[nodiscard]] size_type size() noexcept { return current_size; }
  [[nodiscard]] const size_type size() const noexcept { return current_size; }

private:
  size_type m_head = 0;
  size_type m_tail = 0;
  int current_size = 0;
  value_type m_data[N]{};
};

}

And I wonder about the possible blunders, what is missing and how to make it better in general. Thanks a lot.

\$\endgroup\$
4
\$\begingroup\$

You asked how to make the queue better in general, so I’m going to go in a completely different direction from the other reviews, and answer that question specifically.

Don’t abuse the standard library

The enqueue()/push() function throws std::overflow_error if the queue is full, and dequeue()/pop() throws std::underflow_error if the queue is empty. The problem with this is: that is not what those exceptions mean.

std::overflow_error and std::underflow_error are supposed to signal arithmetic errors—the overflow/underflow of values when doing numeric computations. If I tried to push a value into a queue and got a std::overflow_error thrown in my face, my response would be a flabbergasted: “What the hell? Did this queue just blow past numeric_limits<size_t>::max() while trying to calculate its new size? Does it have some weird internal bug?”

Abusing existing standard exceptions because they just happen to have a name that sorta-kinda works in this case is a terrible idea. Either use the correct standard exceptions for the situation (for example, trying to push when the queue is full might warrant a std::length_error) or, much better, make specific exceptions for the specific errors. You could (and should) derive them from the standard exceptions where possible—in these cases, std::logic_error seems like a logical base:

class queue_is_full : public std::logic_error
{
public:
  queue_is_full() :
    std::logic_error{"failed attempt to push to full queue"}
  {}
};

class queue_is_empty : public std::logic_error
{
public:
  queue_is_empty() :
    std::logic_error{"failed attempt to pop from empty queue"}
  {}
};

Or you could just throw a std::logic_error. This doesn’t really seem like a situation where specialized exceptions are necessary, because it’s not something that should ever happen. It’s trivial to not pop from an empty queue, or not push to a full queue, so it’s not like you should ever expect that to happen in well-written code.

Ease up on the restrictions

You constrain the types that can be put in the queue using the std::semiregular concept. Is that really necessary? Is there a reason I shouldn’t be allowed to store, say, unique_ptr’s in a queue?

What do you really need for types in a queue? Well, as I see it, all you really need is for it to be copyable OR movable, so it can be copied/moved into and out of the queue. And you might not even need that with a slightly different interface. For example, if you had emplace(), then a value could theoretically be enqueued in-place—no copying or moving required at all. And if you had a way to pop that didn’t return the popped value—maybe spelled drop() or ignore()—then you could even dequeue without moving or copying (just destructing).

Now, std::semiregular implies not only copyable, but also default-constructible… which you really shouldn’t need for a queue at all. But we’ll cross that bridge shortly.

At the bare minimum, you should at least allow for noncopyable, move-only types. Because why not, right? You’d only need to change like two lines of code to do moves instead of copies in enqueue() and dequeue(), and use a requires clause instead of a concept directly:

template <typename T, std::size_t N>
requires std::default_initializable<T> and (std::copyable<T> or std::movable<T>)
class queue
{
  // ...

A more honest interface

The biggest issue I’d have with this queue is that it’s dishonest about its state. By that I mean, for example, if I create queue with auto q = mine::queue<T, 10>{};, then when q.empty() returns true… the queue is not really empty. There are actually 10 T’s in it!

Granted, I can’t actually get at those 10 T’s without some skullduggery… but they’re there. If T is some type that registers itself in some registry on construction, or has some static counter counting instances, I’m going to be baffled about where all these extra T objects are.

More honest implementations of empty() and size() might look more like:

constexpr auto empty() const noexcept { return false; }
constexpr auto size() const noexcept { return N; }

Except that’s also somewhat misleading, because q.empty() would be true and q.size() would be 10… but when I do dequeue()/pop()… I get an exception because there’s supposedly nothing there.

I don’t have a solution to this quagmire (other than what I recommend about avoiding unnecessary constructions below). It would probably require additional or differently-named member functions, and probably giving up all hope of conforming to the standard container concepts.

Avoid unnecessary constructions

The real biggest issue with this queue—the cause of the problem above—is that it initializes an array full of default-constructed T’s as an “empty” queue. That’s pretty weird; I’d expect an empty queue to have zero T’s in it… not several that just happen to be hidden from me.

Consider this implementation instead (neither tested, nor particularly well-thought-out; don’t trust it for anything but illustration):

template <typename T, std::size_t N>
class queue
{
  static_assert(N != 0);

  std::array<std::optional<T>, N> m_data = {};
  std::size_t m_head = 0;
  std::size_t m_tail = 0;

public:
  template <typename... Args>
  requires std::constructible_from<T, Args...>
  auto emplace(Args&&... args) -> void
  {
    if (size() == N)
      throw std::logic_error{"queue is full"};

    // Don't update m_tail until the push succeeds, just in case of exception.
    //
    // The tail might be past-the-end (if the head is 0 and the queue is
    // full). To deal with this, we use the modulo operator (saves us a
    // conditional branch).
    auto index = m_tail % N;

    m_data[index].emplace(std::forward<Args>(args)...);

    m_tail = ++index;
  }

  auto push(T const& t) -> void
  {
    emplace(t);
  }

  auto push(T&& t) -> void
  {
    emplace(std::move(t));
  }

  auto pop() -> T
  {
    if (empty())
      throw std::logic_error{"queue is empty"};

    auto result = *std::move(m_data[m_head]);
    m_data[m_head].reset();

    // Advance the head. If it's past-the-end, wrap it around.
    m_head = (++m_head) % N;

    return result;
  }

  auto clear() noexcept -> void
  {
    for (auto&& t : m_data)
      t.reset();

    m_head = 0;
    m_tail = 0;
  }

  constexpr auto empty() const noexcept -> bool
  {
    // If the head and the tail are the same, then the queue is either empty
    // or full. The difference can be detected by seeing if the head optional
    // has a value or not.
    return m_head == (m_tail % N) and not m_data[m_head].has_value();
  }

  constexpr auto size() const noexcept -> std::size_t
  {
    // If the tail is greater than the head, then the size is simply the
    // distance between them.
    //
    // However, if the tail is less than the head, then the size is the
    // number of items between the head and the end of the array, plus the
    // number of items between the start of the array and the tail.
    //
    // (You could rewrite this to avoid the conditional, if you like, but I'd
    // leave that to the compiler.)
    if (m_tail >= m_head)
      return m_tail - m_head;
    else
      return (N - m_head) + m_tail;
  }

  constexpr auto max_size() const noexcept -> std::size_t { return N; }
};

When this queue is constructed, even though its size is statically-determined and there is no dynamic allocation, it’s still “empty” in that there are no T objects in it… just N value-less std::optional’s. As you push stuff, those optionals will contain those values… as you pop stuff, they become value-less again.

You could also do it better, with less wasted memory, and entirely constexpr†, by using an array of uninitialized memory, and std::aligned_storage or the equivalent, and std::construct_at()/std::destruct_at(). This would be much more complicated to do, but would probably be worth it. You’d need the current_size member again, but that’s one extra std::size_t in the queue class versus an extra bool for every element of the queue, so you’ll almost certainly save a lot of space for large queues. The cppreference page on std::aligned_storage has a sample implementation of a static vector you could use as a base for this (though you should use std::construct_at()/std::destruct_at() rather than placement new and so on).

† (Presumably C++23? will have a fully-constexpr std::optional. But for now, you’d have to roll your own.)

\$\endgroup\$
8
\$\begingroup\$

Avoid unnecessary copies

enqueue() takes its parameter by value, which means the caller has to make a copy. Then it has to store that value in the array, making another copy. You can avoid copies by replacing the function that takes a value with two overloads, one for const references and one for rvalue references:

void enqueue(const_reference_type val) {
    // same as before
    ...
}

void enqueue(value_type &&val) {
    // mostly the same
    ...
    // but now we move:
    data[current_size++] = std::move(val);
}

The first version will make just one copy, the second one will use move assignment, which might avoid an expensive copy.

Similarly, dequeue() makes a copy. You can avoid this by splitting this function in two; one that returns a reference to the head element so the caller can read it without having to copy it, and another function that just removes the head element. You already have a head(), so then just modify dequeue() to be:

void dequeue() {
    // mostly the same as before, except without returning anything
    ...
}

This is also why std::queue provides a separate front() and pop() function. Also, doing it this way makes the requirements for T less strict; it now only requires it to be std::default_constructible and std::movable.

Make it look like std::queue

Programming is much easier if everything has a similar interface. Consider renaming your member functions to match that of std::queue:

  • enqueue() -> push()
  • dequeue() -> pop()
  • head() -> front()
  • tail() -> back()

You could also add emplace() and swap() to make it almost a drop-in replacement.

\$\endgroup\$
2
  • \$\begingroup\$ Any tip on how to implement swap()? Because I need to swap the private variables as well. Maybe I could write a getter for the m_data, (like the data() on std::vector) to access but it would probably be nonsensical to have accessors for m_head and m_tail which are just a index values. \$\endgroup\$
    – user201793
    Nov 23 '20 at 23:15
  • 2
    \$\begingroup\$ If you make it a member function it has access to private variables, if you make it an out-of-class function you should make it a friend of your class queue. See this question for more details. \$\endgroup\$
    – G. Sliepen
    Nov 24 '20 at 7:26
7
\$\begingroup\$

Make your typedefs more similar to Standard Library types

There is no need for const_size_type or const_value_type; if the user wanted them they could simply use const mine::queue::value_type or the like—as, in fact, you do.

The standard library containers use reference and const_reference, not reference_type and const_reference_type. I would use the former set for consistency.

I wouldn't do using value_type = std::remove_cv_t<T>;. T cannot have top-level const, since then it wouldn't fulfil the requirements for semiregular. The only purpose then is to strip top-level volatile, which is of dubious benefit for the additional semantic burden.

Don't define a non-const size() or empty() overload

The idea that calling queue.size() on a mutable queue potentially modifies it is... worrying. I would remove this overload entirely: remember that const member functions can be called on non-const objects, though not the other way around.

For the const overload you should return size_type, not const size_type. Although there is no functional difference in this case, returning by const value is typically discouraged, as for class types it can inhibit moving. (The fact that there is no functional difference for primitive types is probably a case for avoiding the const in const size_type in and of itself, too.)

All of the above applies to empty() as well.

Make the type of current_size consistent

Currently your current_size variable is of type int, but everywhere you use it where you would otherwise expect to be using size_type. This is problematic, because signed types (like int) and unsigned types (like std::size_t) have different behaviour and can cause some odd issues when mixed.

In addition, on many systems sizeof(std::size_t) > sizeof(int). This means that if the size of the array grows too large your current_size value will overflow, causing undefined behaviour.

As you are using std::size_t/size_type everywhere else here, you should make current_size size_type as well.

Include (only) what you use

Your class does not appear to use anything from <cassert> or <iostream>. As such, you should remove those headers, to potentially improve compile times.

\$\endgroup\$

Your Answer

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