0
\$\begingroup\$

I've implemented a dynamic queue with a random-access iterator.

iterator:

#pragma once
#include <iterator>

namespace con {
template <class T> class rnd_iterator {
  T *m_Ptr;

public:
  /*
   * type aliases
   */
  using value_type = T;
  using iterator_type = rnd_iterator<value_type>;
  using iterator_category = std::random_access_iterator_tag;
  using pointer = value_type *;
  using const_pointer = const pointer;
  using difference_type = std::ptrdiff_t;
  using reference = value_type &;
  using const_reference = const value_type &;
  /*
   * constructors
   */
  rnd_iterator(const rnd_iterator<T> &other) noexcept : m_Ptr(other.m_Ptr) {}
  rnd_iterator(T *p) noexcept : m_Ptr(p) {}
  /*
   * access operators
   */
  reference operator*() { return *m_Ptr; }
  reference operator[](std::size_t idx) { return m_Ptr[idx]; }
  pointer operator->() { return m_Ptr; }
  /*
   * increment/decrement and assign operators
   */
  rnd_iterator &operator=(pointer oth) {
    m_Ptr = oth;
    return *this;
  }
  rnd_iterator &operator+=(pointer oth) {
    m_Ptr += oth;
    return *this;
  }
  rnd_iterator &operator-=(pointer oth) {
    m_Ptr -= oth;
    return *this;
  }
  iterator_type &operator=(const iterator_type &rhs) {
    m_Ptr = rhs.m_Ptr;
    return *this;
  }
  friend iterator_type &operator+=(const iterator_type &lhs,
                                   const iterator_type &rhs) {
    lhs.m_Ptr += rhs.m_Ptr;
    return lhs;
  }
  friend iterator_type &operator-=(const iterator_type &lhs,
                                   const iterator_type &rhs) {
    lhs.m_Ptr -= rhs.m_Ptr;
    return lhs;
  }
  rnd_iterator operator++() {
    ++m_Ptr;
    return *this;
  }
  rnd_iterator operator++(int) {
    auto temp = *this;
    m_Ptr++;
    return temp;
  }
  rnd_iterator &operator--() {
    --m_Ptr;
    return *this;
  }
  rnd_iterator operator--(int) {
    auto temp = *this;
    m_Ptr--;
    return temp;
  }
  /*
   * comparison operators
   */
  friend bool operator!=(const iterator_type &lhs, const iterator_type &rhs) {
    return lhs.m_Ptr != rhs.m_Ptr;
  }
  friend bool operator!=(const iterator_type &lhs, pointer rhs) {
    return lhs.m_Ptr != rhs;
  }
  friend bool operator==(const iterator_type &lhs, const iterator_type &rhs) {
    return lhs.m_Ptr == rhs.m_Ptr;
  }
  friend bool operator==(const iterator_type &lhs, pointer rhs) {
    return lhs.m_Ptr == rhs;
  }
  friend bool operator<(const iterator_type &lhs, const iterator_type &rhs) {
    return lhs.m_Ptr < rhs.m_Ptr;
  }
  friend bool operator<(const iterator_type &lhs, pointer rhs) {
    return lhs.m_Ptr < rhs;
  }
  friend bool operator<=(const iterator_type &lhs, const iterator_type &rhs) {
    return lhs.m_Ptr <= rhs.m_Ptr;
  }
  friend bool operator<=(const iterator_type &lhs, pointer rhs) {
    return lhs.m_Ptr <= rhs;
  }
  friend bool operator>(const iterator_type &lhs, const iterator_type &rhs) {
    return lhs.m_Ptr > rhs.m_Ptr;
  }
  friend bool operator>(const iterator_type &lhs, pointer rhs) {
    return lhs.m_Ptr > rhs;
  }
  friend bool operator>=(const iterator_type &lhs, const iterator_type &rhs) {
    return lhs.m_Ptr >= rhs.m_Ptr;
  }
  friend bool operator>=(const iterator_type &lhs, pointer rhs) {
    return lhs.m_Ptr >= rhs;
  }
  friend difference_type operator+(const iterator_type &lhs,
                                   const iterator_type &rhs) {
    return lhs.m_Ptr + rhs.m_Ptr;
  }
  friend difference_type operator+(const iterator_type &lhs, pointer rhs) {
    return lhs.m_Ptr + rhs;
  }
  friend iterator_type operator+(const iterator_type &lhs,
                                 difference_type rhs) {
    return lhs.m_Ptr + rhs;
  }
  friend difference_type operator-(const iterator_type &lhs,
                                   const iterator_type &rhs) {
    return lhs.m_Ptr - rhs.m_Ptr;
  }
  friend iterator_type operator-(const iterator_type &lhs,
                                 difference_type rhs) {
    return lhs.m_Ptr - rhs;
  }
  friend difference_type operator-(const iterator_type &lhs, pointer rhs) {
    return lhs.m_Ptr - rhs;
  }
};
}

queue:

#pragma once
#include "iterator.hpp"
#include <algorithm>
#include <cassert>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>

namespace con {
template <class T, class Allocator = std::allocator<T>> class queue {
  Allocator m_Alloc;
  std::size_t m_Size, m_Capacity;
  std::allocator_traits<Allocator> m_AllocTraits;
  T *m_RawData;
  void m_ReallocAnyway(std::size_t t_NewCapacity) {
    std::size_t f_old = m_Capacity;
    T *f_temp = m_Alloc.allocate(sizeof(T) * t_NewCapacity);
    try {
      for (std::size_t i = 0; i < m_Size; i++) {
        new (&f_temp[i]) T(std::move_if_noexcept(m_RawData[i]));
        m_AllocTraits.destroy(m_Alloc, std::addressof(m_RawData[i]));
      }
      m_Alloc.deallocate(m_RawData, f_old);
      m_RawData = f_temp;
    } catch (const std::exception &exc) {
      m_Alloc.deallocate(f_temp, sizeof(T) * t_NewCapacity);
      throw std::move(exc);
    }
  }
  void m_Realloc(std::size_t t_NewCapacity) {
    if (t_NewCapacity > m_Capacity) {
      m_ReallocAnyway(t_NewCapacity);
    } else {
      return;
    }
  }
  void m_ShiftToLeft() {
    for (std::size_t i = 0; i < m_Size; i++) {
      new (&m_RawData[i]) T(std::move_if_noexcept(m_RawData[i + 1]));
    }
  }
  template <class F>
  void m_ShiftFromTo(std::size_t from, std::size_t to, F &&func) {
    for (; from < to; from++) {
      new (&m_RawData[from])
          T(std::move_if_noexcept(m_RawData[func(from, to)]));
    }
  }
  template <class It> void m_ShiftRangeFromTo(It from, It to) {
    for (; from != to; from++) {
      new (std::addressof(*from))
          T(std::move_if_noexcept(*(from + (to - from))));
    }
  }
  template <class Iter> void m_DestroyRange(Iter beg, Iter end) {
    for (; beg != end; beg++) {
      m_AllocTraits.destroy(m_Alloc, std::addressof(*beg));
    }
  }
  void m_CheckOrAlloc(std::size_t t_Size) {
    if (t_Size >= m_Capacity) {
      m_Realloc(m_Capacity * 2);
    }
  }

public:
  using value_type = T;
  using allocator_type = Allocator;
  using size_type = decltype(m_Size);
  using difference_type = std::ptrdiff_t;
  using reference = value_type &;
  using const_reference = const value_type &;
  using pointer = typename std::allocator_traits<Allocator>::pointer;
  using const_pointer =
      typename std::allocator_traits<Allocator>::const_pointer;
  using iterator = con::rnd_iterator<value_type>;
  using const_iterator = const iterator;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  explicit queue(size_type cap = (sizeof(value_type) * 5),
                 const Allocator &alloc = Allocator{}) noexcept
      : m_Alloc(alloc), m_Size(0), m_Capacity(cap),
        m_RawData(m_Alloc.allocate(m_Capacity)) {}
  explicit queue(const std::initializer_list<T> &init,
                 const Allocator &alloc = Allocator{}) noexcept
      : m_Alloc(alloc), m_Size(init.size()), m_Capacity(sizeof(value_type) * 5),
        m_RawData(m_Alloc.allocate(m_Capacity)) {
    m_Size = init.size();
    m_CheckOrAlloc(m_Size);
    std::uninitialized_copy(init.begin(), init.end(), m_RawData);
  }
  explicit queue(const queue<value_type> &oth) : queue() {
    if (std::is_destructible<value_type>::value)
      clear();
    m_Size = oth.size();
    m_CheckOrAlloc(m_Size);
    std::uninitialized_copy(oth.begin(), oth.end(), m_RawData);
  }
  explicit queue(queue<value_type> &&oth) noexcept : queue() {
    if (std::is_destructible<value_type>::value)
      clear();
    m_Size = oth.size();
    m_CheckOrAlloc(m_Size);
    std::uninitialized_move(oth.begin(), oth.end(), m_RawData);
  }
  template <class It> queue(It begin, It end) noexcept : queue() {
    assert(begin <= end);
    size_type f_size = std::distance(begin, end);
    m_CheckOrAlloc(f_size);
    m_Size = f_size;
    std::uninitialized_copy(begin, end, m_RawData);
  }
  explicit queue(const queue<value_type> &&oth) = delete;
  iterator begin() noexcept { return iterator(m_RawData); }
  iterator end() noexcept { return iterator(m_RawData + size()); }
  reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
  reverse_iterator rend() noexcept { return reverse_iterator(begin()); }

  const_iterator begin() const noexcept { return const_iterator(m_RawData); }
  const_iterator end() const noexcept {
    return const_iterator(m_RawData + size());
  }
  const_reverse_iterator rbegin() const noexcept {
    return const_reverse_iterator(m_RawData + size());
  }
  const_reverse_iterator rend() const noexcept {
    return const_reverse_iterator(m_RawData);
  }

  const_iterator cbegin() const noexcept { return const_iterator(m_RawData); }
  const_iterator cend() const noexcept {
    return const_iterator(m_RawData + size());
  }
  const_reverse_iterator crbegin() const noexcept { return rbegin(); }
  const_reverse_iterator crend() const noexcept { rend(); }

  bool empty() const noexcept { return size() == 0; }
  size_type size() const noexcept { return m_Size; }
  size_type capacity() const noexcept { return m_Capacity; }
  size_type max_capacity() const noexcept {
    return std::numeric_limits<size_type>::max();
  }
  const_pointer data() const { return m_RawData; }
  void clear() requires(std::is_destructible<value_type>::value) {
    for (size_type i = 0; i < size(); i++) {
      m_AllocTraits.destroy(m_Alloc, std::addressof(m_RawData[i]));
    }
    m_Size = 0;
  }
  void reserve(size_type cp) { m_CheckOrAlloc(cp); }
  void resize(size_type sz) {
    m_Size = sz;
    m_CheckOrAlloc(sz);
  }
  void erase(iterator val) {
    if (val != end()) {
      difference_type x = val - begin();
      pointer p = m_RawData + x;
      m_AllocTraits.destroy(m_Alloc, std::addressof(*val));
      m_ShiftFromTo(std::distance(begin(), iterator(p)), size(),
                    [](auto l, [[maybe_unused]] auto _) { return l + 1; });
      m_Size--;
    } else {
      return;
    }
  }
  void erase(iterator first, iterator last) {
    assert(first <= last && "queue::erase invalid range");
    m_DestroyRange(first, last);
    m_ShiftRangeFromTo(first, last);
    m_Size -= std::distance(first, last);
  }
  void erase(reverse_iterator first, reverse_iterator last) {
    assert(first <= last && "queue::erase invalid range");
    m_DestroyRange(first, last);
    m_ShiftRangeFromTo(first, last);
    m_Size -= std::distance(first, last);
  }
  void erase(reverse_iterator val) {
    if (val != rend()) {
      m_AllocTraits.destroy(m_Alloc, std::addressof(*val));
      m_ShiftFromTo(std::distance(val, rend()) - 1, size(),
                    [](auto l, [[maybe_unused]] auto _) { return l + 1; });
      m_Size--;
    } else {
      return;
    }
  }
  void erase(const value_type &obj) { erase(std::find(begin(), end(), obj)); }
  void rerase(const value_type &obj) {
    erase(std::find(rbegin(), rend(), obj));
  }
  iterator find(const value_type &obj) {
    return std::find(begin(), end(), obj);
  }
  reverse_iterator rfind(const value_type &obj) {
    return std::find(rbegin(), rend(), obj);
  }
  const_iterator find(const_reference obj) const {
    return std::find(begin(), end(), obj);
  }
  const_reverse_iterator rfind(const value_type &obj) const {
    return std::find(rbegin(), rend(), obj);
  }

  void enqueue(const value_type &oth) requires(
      std::is_copy_constructible<value_type>::value) {
    m_CheckOrAlloc(size());
    new (&m_RawData[m_Size++]) value_type(oth);
  }
  void enqueue(value_type &&oth) requires(
      std::is_move_constructible<value_type>::value) {
    m_CheckOrAlloc(size());
    new (&m_RawData[m_Size++]) value_type(std::move(oth));
  }
  [[nodiscard]] value_type
  dequeue() requires(std::is_destructible<value_type>::value) {
    --m_Size;
    value_type temp = m_RawData[0];
    m_AllocTraits.destory(m_Alloc, std::addressof(m_RawData[0]));
    m_ShiftToLeft();
    return temp;
  }
  template <class... Args> void emplace(Args &&...args) {
    enqueue(value_type(std::forward<Args>(args)...));
  }
  value_type at(size_type index) const {
    if (index >= size()) {
      throw std::range_error("out of bounds queue"); // yes helpful error
    } else {
      return m_RawData[index];
    }
  }
  reference at(size_type index) {
    if (index >= size()) {
      throw std::range_error("out of bounds queue"); // yes helpful error
    } else {
      return m_RawData[index];
    }
  }
  value_type operator[](size_type index) const { return m_RawData[index]; }
  reference operator[](size_type index) { return m_RawData[index]; }

  queue<value_type> &operator=(const queue<value_type> &oth) {
    if (&oth != this) {
      clear();
      m_Size = oth.size();
      m_CheckOrAlloc(m_Size);
      std::uninitialized_copy(oth.begin(), oth.end(), m_RawData);
    }
    return *this;
  }
  queue<value_type> &operator=(queue<value_type> &&oth) {
    if (&oth != this) {
      clear();
      m_Size = oth.size();
      m_CheckOrAlloc(m_Size);
      std::uninitialized_move(oth.begin(), oth.end(), m_RawData);
      oth.~queue();
    }
    return *this;
  }
  queue<value_type> &operator=(const queue<value_type> &&oth) = delete;
  ~queue() {
    m_Alloc.deallocate(m_RawData, m_Capacity);
    std::exchange(m_RawData, nullptr);
    std::exchange(m_Size, 0);
  }
  ~queue() requires(std::is_destructible<value_type>::value) {
    clear();
    m_Alloc.deallocate(m_RawData, m_Capacity);
    std::exchange(m_RawData, nullptr);
    std::exchange(m_Size, 0);
  }
};
}
```
\$\endgroup\$
4
\$\begingroup\$

Despite the many criticisms in my review, I think this is an OUTSTANDING effort.

Design review

Iterators are part of range interfaces

The first issue that strikes me about your design is that you have separated the iterator from the container. That’s nonsense. Iterators can’t exist independently from a container. There is no such thing as a “general-purpose random-access iterator”.

Iterators are a part of a range. We talk about them as independent “things”, but they are not. In fact, you can’t even create an iterator without a range to create it from. By attempting to separate the iterator from the range, you’ve actually created numerous problems. It is possible (even dangerously easy) to create broken rnd_iterators (rnd_iterators that don’t actually reference a legitimate range).

What you’ve actually created with rnd_iterator is not really a random-access iterator. It looks like one, and it will work for some containers—it will work for std::vector, but not std::deque, for example—but it will crash with most random-access containers (like std::deque). It’s actually an iterator type that will work with contiguous ranges (std::vector is a contiguous range, and so is con::queue)… not random-access ranges… but it will work worse than the range’s own iterator type.

In fact, rnd_iterator is really nothing more than an alias for T*… except it’s more limited, less efficient, and lacks the well-understood semantics.

Dangerous conversions

rnd_iterator has a serious problem with dangerous conversions from raw pointers. That’s not a good thing; that’s very, very bad. There are NO situations, any time, ever, where you’d want client code to be able to freely convert raw pointers to queue iterators. And especially to have those conversions happen silently, by default.

The problem here is that because the iterator is separate from the container, you need a way to convert the container’s internal pointers to iterators. But by making that public, you’ve allowed random user code to be able to do the same thing. I can take any random pair of raw pointers, and create a pair of iterators… even if those pointers are not pointing to the same array. And in fact, even worse, random pointers will be automatically and silently converted to iterators, so at the slightest typo, suddenly I have what looks like a valid range. Hello, bugs. For example:

auto i = 0;
auto ptr = &i;

auto q = con::queue<int>{};

find(q.begin(), ptr, 42); // compiles without a warning, and probably crashes

You need for con::queue to be able to construct iterators from raw pointers… but that should only be an internal function. It should not be available to outside code. You could do this by friendship, I suppose, but however you do it, con::queue should be able to turn its internal pointers into iterators, but nothing else.

Incidentally, this also implies you should remove all the other operations with raw pointers:

  // all these are bad

  rnd_iterator &operator=(pointer oth);
  rnd_iterator &operator+=(pointer oth);
  rnd_iterator &operator-=(pointer oth);

  friend bool operator!=(const iterator_type &lhs, pointer rhs);
  friend bool operator==(const iterator_type &lhs, pointer rhs);
  friend bool operator<(const iterator_type &lhs, pointer rhs);
  friend bool operator<=(const iterator_type &lhs, pointer rhs);
  friend bool operator>(const iterator_type &lhs, pointer rhs);
  friend bool operator>=(const iterator_type &lhs, pointer rhs);
  friend difference_type operator+(const iterator_type &lhs, pointer rhs);

There is NO situation where it would be a good thing to do comparisons or other operations between iterators and raw pointers. (And if you ever create a situation where you need to do that: 1) you should rewrite your algorithm; and 2) you could do it anyway, it would just be much more verbose, but that’s a good thing.)

Overblown interface

Now, you’re making a queue, which, by definition, exists to take elements in on one end, and pop them off from the other. Does the existing interface make sense for that?

Like, what is the purpose of being able to iterate through the queue… backwards? Seems a bit silly. I mean, one might ask why you need to iterate through the queue at all even, including forwards, because… that’s not how you use queues. You push, and you pop; those are the only operations a queue needs. But okay, having range access isn’t a bad thing because it can allow some massive optimizations (like rather than repeatedly popping items off the queue until it’s empty, you could iterate through the queue doing some operation, then clear the whole queue in a single step). But… backwards? Really?

And let’s be clear, if your queue can support reverse iteration, I’m not saying you should prevent it. But you don’t need to make it part of the public interface. You could remove rbegin()/rend() etc. and still have reverse iteration:

std::for_each(std::reverse_iterator{q.begin()}, std::reverse_iterator{q.end()}, func);

// or:

std::for_each(std::ranges::rbegin(q), std::ranges::rend(q), func);

// or:

for (auto&& element : q | std::views::reverse)
    func(element);

All of the above work with just begin() and end(), and do the exact same thing, just as efficiently. So there’s no need to add more cruft to the queue’s interface, especially stuff that doesn’t directly relate to what a queue actually is.

Similar logic goes for the element access functions. Does it really make sense to provide random access to the middle of a queue? I don’t see why. If I want efficient random-access to a sequential data structure… well, that’s what std::vector is for (or std::deque for that matter). Again, even if you remove operator[size_type] and at(), it’s still possible to get efficient access to random elements in the queue (because the queue iterators are random-access iterators). So you’re not losing functionality by removing those functions. You’re just sending the message “that’s not how I intend for this type to be used (because it’s a queue)”.

A good interface should be:

  1. Complete. It should be possible to do every operation necessary for the type with maximal efficiency.
  2. Minimal. The more crap you add to an interface, the more unwieldy the class becomes both for maintainers and users (because now users have learn and memorize more functions).
  3. Logical. The interface should have all the operations that make semantic sense for what the type means… and no more than that (with exceptions made for the sake usability and efficiency).

A queue’s basic interface should be nothing more than construction, destruction, moving, copying, pushing, and popping, and maybe peeking at the front of the queue, and maybe-maybe peeking at the back of the queue… and that… is… it. If you add ANYTHING ELSE, you need to seriously justify why it’s NECESSARY, either for usability or efficiency… because every single little thing you add to a class makes it that much more brittle, that much less maintainable, and that much more annoying to learn and use.

So I would suggest trimming down this interface quite a bit. I would suggest removing:

  • reverse_iterator and const_reverse_iterator.
  • rbegin(), rend(), crbegin(), crend().
  • max_capacity(), because it is not a standard container function; max_size() is.
  • All the element access functions. You can get at elements just as easily and efficiently with iterators.
  • All the erase functions that don’t take iterator.
  • All the find functions.

I would also suggest adding a few functions:

  • Definitely shrink_to_fit().
  • At least front(), and maybe back() as well.
  • A dequeue_and_discard() function for when you want to pop but don’t care what you’re popping.
  • Maybe assign(), where you can assign from an iterator pair or initializer list.
  • Maybe a resize() (and perhaps assign()) overload that takes a source to copy for any new elements.
  • get_allocator() and max_size(), for container requirements.

Unbalanced efficiency

The standard library has a queue—std::queue. It’s actually a container adapter: you supply a container, and it makes it act like a queue. The reason I’m mentioning all this is because the default container for a std::queue is std::deque… not std::vector.

Why is that relevant? Because your queue—con::queue—is actually built on an implementation that is basically std::vector.

Here’s why that’s an issue. When you are pushing to your queue, you get maximal efficiency. Let’s imagine you start with a queue that has capacity = 2, and is full, and you want to push a total of 8 elements:

  1. Push element 3.
    • Allocate 4 spaces.
    • Move element 1 to new memory.
    • Move element 2 to new memory.
    • Push element 3 into new memory.
    • (Queue now has size = 3, capacity = 4)
  2. Push element 4.
    • Push element 4 into existing capacity
    • (Queue now has size = 4, capacity = 4)
  3. Push element 5.
    • Allocate 8 spaces.
    • Move element 1 to new memory.
    • Move element 2 to new memory.
    • Move element 3 to new memory.
    • Move element 4 to new memory.
    • Push element 5 into new memory.
    • (Queue now has size = 5, capacity = 8)
  4. Push element 6.
    • Push element 6 into existing capacity
    • (Queue now has size = 6, capacity = 8)
  5. Push element 7.
    • Push element 7 into existing capacity
    • (Queue now has size = 7, capacity = 8)
  6. Push element 8.
    • Push element 8 into existing capacity
    • (Queue now has size = 8, capacity = 8)

That’s not bad! That’s actually highly efficient. There are two allocations during the process, but that’s not really avoidable (unless you reserve, of course), and during those two allocations, there are a bunch of extra moves… but for fully half of the pushes, it’s doing the absolute minimum work possible: just adding the element directly into the queue. (And if you actually reserved the required capacity up front, you’d really get the minimum work possible.)

But now look what happens when you try to pop those 6 elements back off:

  1. Pop element.
    • Move element 1 to return slot.
    • Move element 2 to position 1.
    • Move element 3 to position 2.
    • Move element 4 to position 3.
    • Move element 5 to position 4.
    • Move element 6 to position 5.
    • Move element 7 to position 6.
    • Move element 8 to position 7.
  2. Pop element.
    • Move element 1 to return slot.
    • Move element 2 to position 1.
    • Move element 3 to position 2.
    • Move element 4 to position 3.
    • Move element 5 to position 4.
    • Move element 6 to position 5.
    • Move element 7 to position 6.
  3. Pop element
    • Move element 1 to return slot.
    • Move element 2 to position 1.
    • Move element 3 to position 2.
    • Move element 4 to position 3.
    • Move element 5 to position 4.
    • Move element 6 to position 5.
  4. Pop element.
    • Move element 1 to return slot.
    • Move element 2 to position 1.
    • Move element 3 to position 2.
    • Move element 4 to position 3.
    • Move element 5 to position 4.
  5. Pop element.
    • Move element 1 to return slot.
    • Move element 2 to position 1.
    • Move element 3 to position 2.
    • Move element 4 to position 3.
  6. Pop element.
    • Move element 1 to return slot.
    • Move element 2 to position 1.
    • Move element 3 to position 2.

Yikes. That’s not a problem with your implementation. In fact, if you used std::vector with std::queue you’d get the same behaviour. That’s why std::vector is not the default container to use with std::queue. Every time you pop an element off of a queue built on a vector-like container with N, you trigger a chain of N − 1 moves. If your queue has a million elements, popping an item off triggers 9,999,999 moves. Not great.

Here is what would happen with a std::queue using std::deque:

  1. Pop element.
    • Move element 1 to return slot.
  2. Pop element.
    • Move element 1 to return slot.
  3. Pop element
    • Move element 1 to return slot.
  4. Pop element.
    • Move element 1 to return slot.
  5. Pop element.
    • Move element 1 to return slot.
  6. Pop element.
    • Move element 1 to return slot.

Wow, big difference, eh?

Now I am NOT saying you should make your queue with a re-implementation of std::deque internally. In fact, I think you could do much better. Your implementation is already half-way there. The only thing I think you need to do differently is not adjusting the entire internal array when you pop from the front.

Here’s one way you could do it:

  • Store the currently allocated block address.
  • Store a pointer to the head of the queue (in the currently allocated block).
  • Store the queue size.

Currently you store only m_RawPtr as BOTH the current block address AND the head of the queue… and that is where your problems arise. I recommend splitting them into two. That way, when you pop from the queue, you don’t need to move all the elements one position over… you just move the pointer to the queue head.

Here’s how that might look. Suppose you have a queue with size 6, capacity 8:

         +---+---+---+---+---+---+---+---+
         | A | B | C | D | E | F | _ | _ |
         +---+---+---+---+---+---+---+---+
         ^
         |
m_block -+
         |
m_head --/

m_size     = 6

m_capacity = 8

With your current design, when you pop, you get this:

         +---+---+---+---+---+---+---+---+
         | B | C | D | E | F | _ | _ | _ |
         +---+---+---+---+---+---+---+---+
         ^
         |
m_block -+
         |
m_head --/

m_size     = 5

m_capacity = 8

(Except of course, instead of m_block and m_head, you just have the one m_RawPtr.)

What I’m suggesting is that when you pop, you destroy the head element, and then just advance the head pointer:

         +---+---+---+---+---+---+---+---+
         | _ | B | C | D | E | F | _ | _ |
         +---+---+---+---+---+---+---+---+
         ^   ^
         |   |
m_block -/   |
             |
m_head ------/

m_size     = 5

m_capacity = 7

The pro of this design is that popping now becomes MUCH faster, and there is no more chance of failure (which might happen if you have elements that are not nothrow-movable). The con is that you don’t recover capacity by popping. So if your use pattern is one-push-one-pop over and over… you’ll need to reallocate eventually. (With std::deque as the underlying container, that can be avoided because a deque is a bunch of chunks: if necessary, the deque can just move empty chunks around to avoid needing to reallocate at one end or the other.) HOWEVER, if your use pattern is to basically pump the queue empty every so often, then this design could be very efficient, because every time you empty the queue, you can just reset the head pointer to the beginning of the block, and recover all the capacity. Or, if the space at the beginning is larger than the size, you can safely copy the whole queue back to the beginning of the block. (And if the elements are nothrow-movable, you can do that safely any time, so you can always recover the capacity when you need it.)

Anyway, whatever design you choose, I just wanted to point out that you have an unbalanced efficiency issue: pushing is fast, popping is slow. If that’s what you want, well then fine; there’s nothing wrong with having fast pushes and slow pops. It’s a little surprising, but if you document that that’s the point, then that’s cool. That pattern does have real-world usage potential.

Indestructible elements?

Several functions in the queue class have a bizarre requirement: requires(std::is_destructible<value_type>::value). Now, for starters, it would probably make more sense to use the destructible concept: requires std::destructible<T>. But aside from that… what do you think it means for a type to not be destructible?

If a type cannot be destroyed, then how the hell are you are supposed to pop elements from the queue? How the hell are you supposed to destroy the queue itself? (No, your answer— simply ignoring the destruction of the elements and deallocating their memory out from under them—is absolutely NOT the right answer. That’s a one-way ticket to UB-land, with bonus leakage along the way.)

If a type cannot be destroyed, it cannot be constructed. (At least, not without significant chicanery that’s not worth serious consideration.) If a type cannot be constructed… how the hell is it supposed to get into the queue? The only way to put things into the queue is either to move construct, copy construct, or otherwise directly (via emplace()) construct them in the queue. If you can’t destruct, you can’t construct, so none of those things should be possible (conceptually). So never mind getting things out of the queue; you can’t even put things into the queue.

So if a type is indestructible, you can’t put it into the queue, and even if you could, you couldn’t then take it out of the queue, or even destroy the queue itself.

So what do you think it means to have a queue full of indestructible objects? Do you have any actual use-cases for this?

From where I’m sitting, it looks like complete nonsense, but maybe I’m missing something.

Code review

rnd_iterator

To start, let me reiterate that what you’ve basically done is re-implemented T*… except not as efficiently. That being said, let’s dive in to the actual code.

#pragma once

#pragma once is non-standard, and it has serious problems that while rare, are nightmarish to deal with (which is why it’s never been standardized). Use include guards instead.

T *m_Ptr;

In C++, the convention is to put the pointer asterisk or reference ampersand with the type, not with the variable name. That’s because types matter more in C++… it’s more important to think of m_Ptr as a T* than it is to think of it as a pointer to a T.

  • T *m_ptr is C style.
  • T* m_ptr is C++ style.

This is true for references as well.

using value_type = T;

If you want this template to be used for both iterator and const_iterator, then you will need to remove the const here. This is as easy as using value_type = std::remove_cv_t<T>;.

using pointer = value_type *;
// ... [snip] ...
using difference_type = std::ptrdiff_t;
using reference = value_type &;

You have a problem where con::queue<T>::iterator::pointer may not be the same as con::queue<T>::pointer, because the former is typename std::allocator_traits<Allocator>::pointer while the latter is just T*. This is just one of a number of problems that arise because you have separated the iterator from the container.

using iterator_type = rnd_iterator<value_type>;

I don’t see the point of this type alias. It’s actually longer than just using rnd_iterator.

using const_pointer = const pointer;
// ...
using const_reference = const value_type &;

These two type aliases make no sense. They make sense in the context of the container… but not in the context of the iterator. iterator::const_reference makes no sense; what you’d really want is const_iterator::reference.

In any case, you have defined const_pointer incorrectly (although const_reference is correct).

rnd_iterator(const rnd_iterator<T> &other) noexcept : m_Ptr(other.m_Ptr) {}

There is no reason to write this constructor, because it’s not doing anything differently from the default, implicitly generated copy constructor. And, in fact, by writing it out, you have actually crippled the efficiency. See the the rule of 3/5/0.

rnd_iterator(T *p) noexcept : m_Ptr(p) {}

All single-argument constructors should, by default, be declared explicit.

But as mentioned in the design overview, this constructor should also be private (if it even exists at all).

reference operator[](std::size_t idx) { return m_Ptr[idx]; }

This should actually be using the container’s size_type, not std::size_t. Again, this is why iterators should be defined with their containers. They don’t make sense independently.

Also, all of the access operators should be const. None of them change the iterator. You could use the returned pointer/reference to change whatever is pointed-to or referenced… but the iterator itself isn’t being changed.

  rnd_iterator &operator=(pointer oth)
  rnd_iterator &operator+=(pointer oth)
  rnd_iterator &operator-=(pointer oth)

All of these operations should be deleted.

Also… what sense does adding two pointers make? What do you think will happen if you add a pointer to a pointer?

  iterator_type &operator=(const iterator_type &rhs)

Like the copy constructor, this shouldn’t be explicitly defined.

  friend iterator_type &operator+=(const iterator_type &lhs,
                                   const iterator_type &rhs)

Adding pointers, or iterators, makes no sense.

  friend iterator_type &operator-=(const iterator_type &lhs,
                                   const iterator_type &rhs)

Subtracting iterators does make sense… but the result will be a difference_type… not an iterator. So operator-= with an iterator on the right-hand side makes no sense.

  rnd_iterator operator++()

You have a bug; you forgot the & on the return type.

  friend bool operator!=(const iterator_type &lhs, const iterator_type &rhs)
  friend bool operator!=(const iterator_type &lhs, pointer rhs)
  friend bool operator==(const iterator_type &lhs, const iterator_type &rhs)
  friend bool operator==(const iterator_type &lhs, pointer rhs)
  friend bool operator<(const iterator_type &lhs, const iterator_type &rhs)
  friend bool operator<(const iterator_type &lhs, pointer rhs)
  friend bool operator<=(const iterator_type &lhs, const iterator_type &rhs)
  friend bool operator<=(const iterator_type &lhs, pointer rhs)
  friend bool operator>(const iterator_type &lhs, const iterator_type &rhs)
  friend bool operator>(const iterator_type &lhs, pointer rhs)
  friend bool operator>=(const iterator_type &lhs, const iterator_type &rhs)
  friend bool operator>=(const iterator_type &lhs, pointer rhs)

Okay, first, all of the operations that take raw pointers should be removed.

That leaves you with only the operations between two iterators. But you’re using C++20, so all of the above can be reduced to one line:

    constexpr auto operator<=>(iterator const&) const noexcept = default;

(I’ve added constexpr, though you don’t have it anywhere else. You could, though.)

  friend difference_type operator+(const iterator_type &lhs,
                                   const iterator_type &rhs)
  friend difference_type operator+(const iterator_type &lhs, pointer rhs)

Adding iterators makes no sense. Adding a pointer to an iterator makes even less sense.

  friend iterator_type operator-(const iterator_type &lhs, difference_type rhs)
  friend difference_type operator-(const iterator_type &lhs, pointer rhs)

The operation with a raw pointer should be removed, but you have also forgotten all the addition operations. You can’t add two iterators… but you can add an iterator and a difference_type in either order.

A big problem that you will probably run into is that you haven’t given any thought to the relationship between rnd_iterator<T> and rnd_iterator<const T>. The former should be implicitly convertible to the latter… but the latter should not be convertible to the former. This will really become an issue when you try to use it as iterator and const_iterator for the container.

One more thing worth mentioning: you explicitly said you want a random-access iterator, and yeah, that’s what you have. However, you could have a contiguous iterator, if you wanted.

queue<T, Allocator>

  Allocator m_Alloc;
  std::size_t m_Size, m_Capacity;
  std::allocator_traits<Allocator> m_AllocTraits;
  T *m_RawData;

There are a couple issues with the way you’ve laid out your class.

First, when you are ordering a class’s data members, you should try to put the most important data members first. Why? Because the address of the very first member in a class is (usually!) the same as this, which means the moment you access this, you already have the first data member right there. Later data members might not be in cache yet, and may require a separate load.

In this case, the data member you probably want right up front is m_rawData. So that should be first. Next most important is maybe m_Size, followed by m_Capacity, with m_Alloc being the least important.

The second problem comes from the fact that allocators are often stateless, which means they have zero size. However, when you write an allocator data member like that, it has to take up at least 1 byte. And, unfortunately, the next type is std::size_t, which is usually 8 bytes, and has to be aligned on an 8-byte boundary… so m_Alloc will have to be padded with 7 extra bytes just to make things line up.

To fix that, you can use [[no_unique_address]], so if m_Allocator really is zero-sized, it will take up zero space in the class.

Never do this:

std::size_t m_Size, m_Capacity;

Each declaration should be on its own line.

And, finally, there is no need for m_AllocTraits. std::allocator_traits is a traits class. It is zero-sized by definition, and it is meant to be used statically. You’re never supposed to create an allocator_traits object, let alone store one in a class. m_AllocTraits.destroy(...) is just plain wrong. destroy() is not a non-static member function, it is a static member function. You have to call it like this: decltype(m_AllocTraits)::destroy(...). But of course, that makes no sense when you can just do std::allocator_traits<Allocator>::destroy(...).

So your data members should probably look more like this:

  T* m_RawData = nulltpr;
  std::size_t m_Size = 0;
  std::size_t m_Capacity = 0;
  [[no_unique_address]] Allocator m_Alloc = {};

Note I added initializers, which is probably a good idea, too.

  void m_ReallocAnyway(std::size_t t_NewCapacity)

This is a very good attempt at writing what is actually an EXTREMELY complicated operation.

You correctly use std::allocator_traits elsewhere in the code, but not here, which is a shame. Instead of calling m_Alloc.allocate(...) directly, you should do:

auto f_temp = std::allocator_traits<Allocator>::allocate(m_Alloc, t_NewCapacity);

Note also that it’s just t_NewCapacity… not sizeof(T) * t_NewCapacity. The allocator already knows about sizeof(T) (as well as alignof(T)).

Also, using std::addressof() is a little ridiculous. You know m_RawData is a T*. It doesn’t make sense to dereference the pointer, then use addressof() to get it back. Just do m_RawData + i.

Alright, now comes the really tricky part:

      for (std::size_t i = 0; i < m_Size; i++) {
        new (&f_temp[i]) T(std::move_if_noexcept(m_RawData[i]));
        // ...
      }

First, rather than a raw placement-new, you should be using std::allocator_traits<Allocator>::construct(m_Alloc, f_temp + i, std::move_if_noexcept(m_RawData[i])).

But now here comes the critical issue. Let’s say m_Size is 10; there are 10 elements in queue. So you start the loop, and successfully copy-construct 5 elements… then, catastrophe, an exception is thrown copying the 6th element. What happens now?

Well, you bubble up to the catch block, deallocate f_temp, and then propagate the exception…

… but… hang on… you’ve missed something.

5 objects were constructed. Those 5 objects need to be destructed before you can deallocate the memory out from under them.

So what you actually need to do is something more like:

// allocate the memory
auto const f_temp = std::allocator_traits<Allocator>::allocate(m_Alloc, t_NewCapacity);

auto num_constructed = std::size_t{0};
try
{
    // construct the objects in that memory
    for (; num_constructed != m_Size; ++num_constructed)
    {
        std::allocator_traits<Allocator>::construct(
            m_Alloc,
            f_temp + num_constructed,
            std::move_if_noexcept(m_RawData[num_constructed])
        );
    }
}
catch (...)
{
    // destroy objects in reverse order
    for (auto i = num_constructed; i != 0; --i)
    {
        std::allocator_traits<Allocator>::destroy(m_Alloc, f_temp + (i - 1));
    }

    // deallocate the memory
    std::allocator_traits<Allocator>::deallocate(m_Alloc, f_temp, t_NewCapacity);

    throw;
}

Now, your catch block is also wrong. You should never rethrow an exception the way you do, because while you catch a std::exception const&, the actual exception might not be an actual std::exception. It might be std::bad_alloc or some other type that derives from std::exception. So when you do throw exc; (or throw std::move(exc);, which is pointless, because exc is a const reference… you can’t move from a const object, it’s going to turn into a copy anyway) you might actually be slicing the actual exception object. That’s bad.

Never rethrow an exception like throw exc;. Just do throw;.

Also, there is no reason you need to limit the exceptions you catch to types that derive from std::exception. If some T constructor throws some other exception type, you want to catch and rethrow that, too. So don’t limit the catch to std::exception const&. Catch everything with catch (...). Rethrow anything with throw;.

Finally, you’re asking for trouble interleaving the construction of the new elements with the destruction of the old ones. Consider the same scenario as before, where you’ve copied 5 out of 10 elements, and then there’s an exception. If you’ve been destroying the source elements as you go along… well, now you’re screwed. You have an array where the first 5 elements are invalid.

Instead, what you should aim to do is get all the dangerous stuff out of the way first, and then do cleanup. Allocating the new array and copy-constructing the new elements are the dangerous steps. Once those are done, destroying the old elements and deallocating the old array should be safe. So do those last. Something like:

    void m_ReallocAnyway(std::size_t new_capacity)
    {
        using alloc_traits = std::allocator_traits<Allocator>;

        // this might throw, but if it does, meh, we haven't done anything yet
        auto const new_data = alloc_traits::allocate(m_Alloc, new_capacity);

        auto num_constructed = std::size_t{0};
        try
        {
            // any of these copy-constructions might fail
            //
            // if they do, the catch block will clean up everything done so far
            for (; num_constructed != m_Size; ++num_constructed)
            {
                alloc_traits::construct(
                    m_Alloc,
                    new_data + num_constructed,
                    std::move_if_noexcept(m_RawData[num_constructed])
                );
            }
        }
        catch (...)
        {
            // all the clean-up from the potentially dangerous stuff goes here

            for (auto i = num_constructed; i != 0; --i)
            {
                alloc_traits::destroy(m_Alloc, new_data + (i - 1));
            }

            alloc_traits::deallocate(m_Alloc, new_data, new_capacity);

            throw;
        }

        // now new_data contains all the stuff from m_RawData
        //
        // from this point on, all we need to do is clean up the old stuff,
        // which should be no-fail

        // destroy old objects in reverse order
        for (auto i = m_Size; ; i != 0; --i)
        {
            // shouldn't fail
            alloc_traits::destroy(m_Alloc, m_RawData + (i - 1));
        }

        // deallocate old memory; shouldn't fail
        alloc_traits::deallocate(m_Alloc, m_RawData, m_Capacity);

        // and finally, set the class data members to the new values
        //
        // these also can't fail
        m_RawData = new_data;
        m_Capacity = new_capacity;
    }

As an optimization to the above, you could put the entire try-catch block in an if constexpr block, so that you only need it when you don’t have no-fail moving. If moving is no-fail (as it is for most types), then there’s no need to worry about anything in that first loop failing, so there’s no need for any cleanup.

  void m_Realloc(std::size_t t_NewCapacity) {
    if (t_NewCapacity > m_Capacity) {
      m_ReallocAnyway(t_NewCapacity);
    } else {
      return;
    }
  }

I mean, you don’t really need the else { return; } here. But I suppose that’s just a matter of personal style.

  void m_ShiftToLeft() {
    for (std::size_t i = 0; i < m_Size; i++) {
      new (&m_RawData[i]) T(std::move_if_noexcept(m_RawData[i + 1]));
    }
  }

This is really wrong.

First, placement new constructs a new object in raw memory. You should never do that overtop of an existing object. If an object is already constructed, you need to destroy it before you can construct a new object over it. If you want to replace an existing object with another existing object… as you’re doing here… you have two options:

  1. The hard way:
    1. Destroy object 1
    2. Use placement new to copy/move construct from object 2 over the old location of object 1
  2. The easy way:
    1. Just copy/move assign object 2 to object 1

The catch of option 2 is that it requires the type to be copy/move assignable, whereas option 1 only requires the type to be copy/move constructible (which you need anyway).

(By the way, I get that the only time this function is ever used, you’ve already destroyed the first object in the queue. So the first iteration of the loop is correct… though every subsequent iteration is still wrong. In any case, the whole plan is still terrible. But we’ll get to that later.)

If you actually want to shift everything in the queue to the left, the safest way to do it would be to use move_if_no_except() to copy/move-assign every item to the previous one. If moving really is no-fail, then this will be perfectly safe. If it’s not… well, then there’s really no way to make this operation safe. (Well, there is one! But we’ll get to it later.)

Also, note that in your code, you have a bug. You loop from 0 to m_Size, which is fine, but then you access m_RawData[i + 1], which is one-past-the-end.

  template <class F>
  void m_ShiftFromTo(std::size_t from, std::size_t to, F &&func)

This whole function really doesn’t make any sense. All you ever use it for is to shift elements to the start N positions over starting at position I (and N is always 1, though it doesn’t need to be, conceivably). m_ShiftRangeFromTo() already covers that. There’s no need for all the extra complexity of a function object. Keep things simple, and you’ll have fewer bugs and less maintenance headache.

  void m_CheckOrAlloc(std::size_t t_Size) {
    if (t_Size >= m_Capacity) {
      m_Realloc(m_Capacity * 2);
    }
  }

Are you sure this is what you want? If your capacity is 10, and someone wants to put 10 elements in the queue… you really want to reallocate to a capacity of 20 rather than just put the 10 elements in the existing capacity?

  using iterator = con::rnd_iterator<value_type>;
  using const_iterator = const iterator;

const_iterator is incorrect. It should be con::rnd_iterator<value_type const> (assuming rnd_iterator correctly handles const value types… which it doesn’t, but should).

  explicit queue(size_type cap = (sizeof(value_type) * 5),
                 const Allocator &alloc = Allocator{}) noexcept
      : m_Alloc(alloc), m_Size(0), m_Capacity(cap),
        m_RawData(m_Alloc.allocate(m_Capacity)) {}

This is your default constructor… among other things (which is not good!)… and you want it to be noexcept, which is a good idea… however, it can’t be, because you’ve crammed too much work into it. How can it possibly be noexcept when you’re allocating?

The first thing I would recommend is to not use default parameters. I think they’re a terrible idea in general, and it’s an especially bad idea here. At the very least, even if you insist on using default parameters, you’re going to need more constructors than this, because it should be possible to construct a queue with just an allocator, like so: auto q = queue<int>(alloc);.

So you need at least two constructors:

explicit queue(const Allocator& alloc = {}) noexcept;
explicit queue(size_type cap, const Allocator& alloc = {});

But this is still a wacky interface, because when I do auto q = queue<int>(5);, I expect that means to create a queue with 5 default-constructed elements in it. That’s what it means for every container in the standard library, after all. But, no, here I get an empty queue… with a capacity of 5. That’s just weird.

My advice is to just forget the constructor with the capacity. You don’t need it. This:

auto q = queue<int>{};
q.reserve(5);

… is clearer than:

auto q = queue<int>(5);

… and there’s no reason it couldn’t be just as efficient.

So that leaves you with just the default constructor (with optional allocator). But it’s still not noexcept so long as it’s allocating. So if you really want a noexcept default constructor (and you should!), you need to not do any allocating. How is that possible?

Well, one option is to say that a default-constructed queue has a size of 0 and a capacity of 0, and thus m_RawData is nullptr:

template <typename T, typename Allocator = std::allocator<T>>
class queue
{
    T* m_RawData = nullptr;
    std::size_t m_Size = 0;
    std::size_t m_Capacity = 0;
    [[no_unique_address]] Allocator m_alloc = {};

    // ... [snip] ...

public:
    constexpr explicit queue(Allocator const& alloc = {}) noexcept :
        m_Alloc{alloc}
    {}

    // ...

Of course, since you now have a “null state”, you have to be careful in some of your member functions to account for it… but not that many actually. (Mostly just the destructor and the functions that might do destruction in one form or another (like reserve()).

But having this no-fail default construction is enormously important, because it allows for no-fail moving as well, and thus, swapping. And you really, really want no-fail moving and no-fail swapping. You could do:

    static constexpr auto _swap_data_with_equal_allocators(queue& to, queue&& from) noexcept
    {
        std::ranges::swap(to.m_RawData,     from.m_RawData);
        std::ranges::swap(to.m_Size,        from.m_Size);
        std::ranges::swap(to.m_Capacity,    from.m_Capacity);
    }

    static constexpr auto _move_data_with_equal_allocators(queue& to, queue&& from) noexcept
    {
        return _swap_data_with_equal_allocators(to, std::move(from));
    }

    constexpr queue() noexcept = default;

    constexpr explicit queue(Allocator const& alloc) noexcept :
        m_Alloc{alloc}
    {}

    constexpr queue(queue&& other) noexcept :
        m_Alloc{std::move(other.m_Alloc)}
    {
        _move_data_with_equal_allocators(*this, std::move(other));
    }

    constexpr queue(queue&& other, Allocator const& alloc)
            noexcept(std::allocator_traits<Allocator>::is_always_equal) :
        m_Alloc{alloc}
    {
        if constexpr (std::allocator_traits<Allocator>::is_always_equal)
        {
            _move_data_with_equal_allocators(*this, std::move(other));
        }
        else
        {
            if (m_Alloc == other.m_Alloc)
            {
                _move_data_with_equal_allocators(*this, std::move(other));
            }
            else
            {
                // need to allocate memory, then MOVE-CONSTRUCT elements
                // from other
                //
                // afterwards, other should have its original size and
                // capacity... but all the elements should be moved-from
            }
        }
    }

    constexpr auto operator=(queue&& other)
            noexcept(std::allocator_traits<Allocator>::propagate_on_container_move_assignment
                or std::allocator_traits<Allocator>::is_always_equal)
        -> queue&
    {
        if constexpr (std::allocator_traits<Allocator>::propagate_on_container_move_assignment)
        {
            // this is safe, because copying allocators is guaranteed to be
            // noexcept, and of course moving a queue's data is noexcept
            clear();

            m_alloc = other.m_alloc;

            _move_data_with_equal_allocators(*this, std::move(other));
        }
        else
        {
            if constexpr (std::allocator_traits<Allocator>::is_always_equal)
            {
                _move_data_with_equal_allocators(*this, std::move(other));
            }
            else
            {
                if (m_alloc == other.m_alloc)
                {
                    _move_data_with_equal_allocators(*this, std::move(other));
                }
                else
                {
                    // need to make sure this has enough capacity, then
                    // MOVE-ASSIGN the elements from other into this
                    //
                    // take into account whether moving/copying is noexcept;
                    // if not, then maybe you need to use a temporary buffer
                    // to keep the strong exception guarantee
                    //
                    // afterwards, other should have its original size and
                    // capacity... but all the elements should be moved-from
                }
            }
        }

        return *this;
    }

    constexpr auto swap(queue& other)
            noexcept(std::allocator_traits<Allocator>::propagate_on_container_swap
                or std::allocator_traits<Allocator>::is_always_equal)
        -> void
    {
        if constexpr (std::allocator_traits<Allocator>::is_always_equal)
        {
            if constexpr (std::allocator_traits<Allocator>::propagate_on_container_swap)
                std::ranges::swap(m_alloc, other.m_alloc);

            _swap_data_with_equal_allocators(*this, std::move(other));
        }
        else
        {
            if (m_Alloc == other.m_Alloc)
            {
                _swap_data_with_equal_allocators(*this, std::move(other));
            }
            else
            {
                // ??? you're on your own here
                //
                // this is UB for all standard containers, so maybe make it UB
                // for yours, too, and throw or terminate
            }
        }
    }

With the above, moving and swapping is guaranteed no-fail whenever possible, and even when it’s not possible to guarantee, it’s no-fail whenever possible.

But let’s get back to your constructor:

  explicit queue(size_type cap = (sizeof(value_type) * 5),
                 const Allocator &alloc = Allocator{}) noexcept

Now you seem confused about what “capacity” means, and sizing in general. In the standard containers, a capacity of 5 means it can hold 5 Ts without reallocating… no matter what size the Ts are. Same goes for the size, basically: a size of 8 means it has 8 objects… not that it’s 8 bytes large.

So when you do… cap = (sizeof(value_type) * 5), you’re saying that the default capacity for a queue depends on the size of the objects its holding. If it’s a queue<std::byte>, then it has a capacity to hold 5 objects, so the total size in memory is 5 bytes… but if it's a queue<std::array<std::byte, 1000>>, then it has a capacity to hold 5,000 objects… so the total size in memory is 5,000,000 bytes. Clearly something has gone awry.

What you really want, I think, is just cap = 5. That means the default capacity is 5 objects, regardless of what those objects are.

Also, once again, don’t intialize multiple things on a single line. It makes your code damn near illegible.

  explicit queue(const std::initializer_list<T> &init,
                 const Allocator &alloc = Allocator{}) noexcept
      : m_Alloc(alloc), m_Size(init.size()), m_Capacity(sizeof(value_type) * 5),
        m_RawData(m_Alloc.allocate(m_Capacity))

First, you should never take initializer lists by const&. They are made to be passed around by value.

Second, this constructor obviously can’t be noexcept, because it’s allocating.

Third, I don’t see the sense of allocating a capacity of 5 (or sizeof(T) * 5 even) when you know already how many objects are in the initializer list. If it’s greater, then you’ll need to throw away what you’ve just allocated and reallocate… which is silly. If it’s less, then you’ve got wasted capacity that you may never need, because if someone gave you an initializer list, that often means they already know all the data they need in the queue.

In fact, you might as well just delegate this constructor over to the iterator constructor:

    constexpr queue(std::initializer_list<T> init, Allocator const& alloc = {}) :
        queue(init.begin(), init.end(), alloc)
    {}

Assuming you write the iterator constructor well, there will be no performance loss from doing this.

  explicit queue(const queue<value_type> &oth) : queue() {
    if (std::is_destructible<value_type>::value)
      clear();
    m_Size = oth.size();
    m_CheckOrAlloc(m_Size);
    std::uninitialized_copy(oth.begin(), oth.end(), m_RawData);
  }

First, let’s get the obvious issue out of the way: you are clearing a queue that you know has to be empty… because it’s just been constructed and nothing’s been put in it. I don’t think you thought this through.

But the real issue here is the test for is_destructible. As mentioned in the design section… this is gibberish.

Okay, that weirdness aside, you have an efficiency issue when you delegate to the default constructor, which allocates a default capacity, and then possibly reallocate with a new size. As with the initializer list constructor, it’s easier just to delegate to the iterator constructor:

    constexpr queue(queue const& other) :
        queue(other.begin(), other.end())
    {}

    constexpr queue(queue const& other, Allocator const& alloc) :
        queue(other.begin(), other.end(), alloc)
    {}

Once again, assuming the iterator constructor is properly written, this should cause no performance penalty.

  explicit queue(queue<value_type> &&oth) noexcept : queue() {
    if (std::is_destructible<value_type>::value)
      clear();
    m_Size = oth.size();
    m_CheckOrAlloc(m_Size);
    std::uninitialized_move(oth.begin(), oth.end(), m_RawData);
  }

Yikes, no, this is not how you move containers. You absolutely do not allocate a whole new buffer and then move construct a whole new set of objects there. I’ve already shown how to do a proper noexcept move constructor above.

  template <class It> queue(It begin, It end) noexcept : queue() {
    assert(begin <= end);
    size_type f_size = std::distance(begin, end);
    m_CheckOrAlloc(f_size);
    m_Size = f_size;
    std::uninitialized_copy(begin, end, m_RawData);
  }

Now this is an important constructor to get right, because if it’s done well, so many other operations can be built on top of it.

The first problem here is that you don’t seem to understand iterator categories. assert(begin <= end); will only work for random-access or better iterators… and, frankly, it’s a pointless test anyway. But the real sneaky issue is that call to std::distance(). Because you use that, you are restricting the iterator category to forward iterators or better… meaning you can’t fill a queue with data from a file like this:

auto file = std::ifstream{"/path/to/data"};

auto q = queue<int>{std::istream_iterator<int>{file}, std::istream_iterator<int>{}};
// q now has all the ints that were in the data file

If you try the code above, it will compile and run… but the queue will be empty. That’s because istream_iterators are input iterators, which means you get only one pass. You blow through that one pass with std::distance(). Which means that by the time you get to std::uninitialized_copy()… there’s no more data. Your queue is now broken, because it says it has a certain size… but there will be nothing in it but uninitialized gibberish.

What you need to do is check the iterator category. If it’s forward or better, you can use std::distance() to preallocate the buffer. But if it’s just input iterator, then the best you can do is add elements one at a time, reallocating as you go:

    template <std::input_iterator It, std::sentinel_for<It> Sen>
    constexpr queue(It first, Sen last, Allocator const& alloc = {}) :
        m_Alloc{alloc}
    {
        while (first != last)
            push_back(*first++);
    }

    template <std::forward_iterator It, std::sentinel_for<It> Sen>
    constexpr queue(It first, Sen last, Allocator const& alloc = {}) :
        m_Alloc{alloc}
    {
        reserve(std::distance(begin, end));
        std::ranges::uninitialized_copy(first, last, m_RawData, m_RawData + m_Capacity);
        m_Size = m_Capacity;
    }

Note that I’m using iterator/sentinel pairs, rather than iterator/iterator pairs. That’s the C++20 way. Also note that I haven’t included any error handling. Let’s call than an exercise for the reader.

  explicit queue(const queue<value_type> &&oth) = delete;

? 🤨

  const_iterator cbegin() const noexcept { return const_iterator(m_RawData); }
  const_iterator cend() const noexcept {
    return const_iterator(m_RawData + size());
  }

These can both just return begin() and end() respectively.

  const_reverse_iterator crend() const noexcept { rend(); }

Missing return.

  size_type max_capacity() const noexcept {
    return std::numeric_limits<size_type>::max();
  }

Standard containers don’t have max_capacity()… but they do have max_size(), which you don’t.

Also, assuming you can hold the max value of size_type seems optimistic. A better estimate would probably be std::numeric_limits<size_type>::max() / sizeof(T). But meh, I’ve never seen anyone actually use max_size().

const_pointer data() const { return m_RawData; }

If you’re providing this, you might as well provide the non-const overload.

  void clear() requires(std::is_destructible<value_type>::value) {
    for (size_type i = 0; i < size(); i++) {
      m_AllocTraits.destroy(m_Alloc, std::addressof(m_RawData[i]));
    }
    m_Size = 0;
  }

The constraint makes no sense, as discussed earlier.

The function should be noexcept (especially since it needs to be used in the destructor).

You are not using allocator traits correctly, as discussed earlier.

The addressof() is pointless.

void reserve(size_type cp) { m_CheckOrAlloc(cp); }

It’s good that you’re willing to delegate to helper functions, but…

  1. m_CheckOrAlloc() checks whether the new capacity is larger, and if so delegates to m_Realloc().
  2. m_Realloc() checks whether the new capacity is larger, and if so delegates to m_ReallocAnyway().
  3. m_ReallocAnyway() finally just reallocates unconditionally.

Is all that dancing really necessary?

  1. m_ReallocAnyway() is ONLY ever called from m_Realloc().
  2. m_Realloc() is ONLY ever called from m_CheckOrAlloc().
  3. m_CheckOrAlloc() is called from multiple places (good!)… but… it’s really just reserve().

I think AT MOST all you need is reserve(), and then maybe an internal, unconditional reallocation function. Keep it simple.

  void resize(size_type sz) {
    m_Size = sz;
    m_CheckOrAlloc(sz);
  }

This is just completely wrong. You allocate enough capacity, but you never actually construct or destruct any objects. You just set the size. You’re either going to truncate your queue with a bunch of inaccessible objects past the end, or the last few elements in your queue are going to be empty garbage.

  void erase(iterator val)
  void erase(iterator first, iterator last)

erase() is perhaps the trickiest function in std::vector to properly implement, and your queue is basically std::vector. In the std::vector version of erase() there are basically 2 paths:

  1. erase(p, q), where q is equal to end().
  2. erase(p, q), where q is not equal to end().

And the single-argument form of erase() just delegates to those two paths:

  1. erase(p) where p is end()… just return.
  2. erase(p) where p is end() - 1… go to path 1 above as erase(end() - 1, end()).
  3. erase(p) where p is not end() - 1… go to path 2 above as erase(p, p + 1).

So the single argument version is easy:

    void erase(const_iterator p)
    {
        if (p != end())
            erase(p, p + 1);
    }

Now, in the 2-argument version, if last is end(), you just destroy everything from first to end(). No biggie:

    void erase(const_iterator first, const_iterator last)
    {
        if (last == end())
        {
            for (; first != end(); ++first)
                // use allocator traits to destroy each element

            // set m_Size
        }
        else
        {
            // ...
        }
    }

Simple.

If last is not end(), now you need to do the shifting. Something like:

    void erase(const_iterator first, const_iterator last)
    {
        if (last == end())
        {
            // ...
        }
        else
        {
            std::ranges::move(last, end(), first);

            for (; last != end(); ++last)
                // use allocator traits to destroy each element

            // set m_Size
        }
    }

You can simplify this, but when you do, you will find that it is the opposite of your implementation: first it does the shift, then it does the destroying. Why? Exception safety. If you destroy all the elements in the middle first, then you try to start the shifting, what happens if an exception is thrown midway through shifting? Now you have a hole of uninitialized memory in the middle of your queue.

  void erase(reverse_iterator first, reverse_iterator last)
  void erase(reverse_iterator val)

These functions just seem ridiculous. Who’s seriously going to want to erase elements from the queue… backwards? And if they don’t really want to erase elements backwards, but it’s just that they have reverse iterators and want to erase some stuff (but don’t really care about the order), then they can just do:

q.erase(rev_first.base(), rev_last.base());

Don’t put crap in your interface you don’t need. The more you over-complicate the plumbing, the easier it is to clog up the drain.

    void erase(const value_type &obj) { erase(std::find(begin(), end(), obj)); }

Notice how the entirety of this function is implementable from the public interface, just as efficiently? Thus you don’t need it.

  void rerase(const value_type &obj)

The Scooby-Doo version of erase(), I presume.

  iterator find(const value_type &obj)
  reverse_iterator rfind(const value_type &obj)
  const_iterator find(const_reference obj) const
  const_reverse_iterator rfind(const value_type &obj) const

All of these functions are pointless, because you can do the exact same job from the rest of the public interface, with no loss of efficiency. In fact, you can do MORE from the public interface. For example:

auto q1 = queue<std::string>{};

std::ranges::find(q1, "foo"sv); // can search with a string view,
                                // without having to construct a string

// could also use projections

auto q2 = queue<int>{};

std::find(std::unseq, q2.begin(), q2.end(), 42); // vectorized find

You see, adding more functions to an interface doesn’t make it better. Making it easier to use existing algorithms is what really makes it better. And for that, all you really need are basics: begin(), end(), size() maybe, and so on. Less is more.

  void enqueue(const value_type &oth) requires(
      std::is_copy_constructible<value_type>::value) {
    m_CheckOrAlloc(size());
    new (&m_RawData[m_Size++]) value_type(oth);
  }
  void enqueue(value_type &&oth) requires(
      std::is_move_constructible<value_type>::value) {
    m_CheckOrAlloc(size());
    new (&m_RawData[m_Size++]) value_type(std::move(oth));
  }

You’ve actually introduced a subtle bug by being clever here. By incrementing m_Size in the same expression, if the copy/move construction fails, now the queue has the wrong size; the last element will be random garbage.

You shouldn’t increment m_Size until after the creation of the new element succeeds.

A word about using concepts: concepts are still very new technology, and we haven’t really established a good set of rules for when to use them or how. But one idea that seems to be taking root is that you shouldn’t treat concepts as simply assertions on operations. In other words, you shouldn’t say, “well, I’m move-constructing the element here… therefore I should add a move_constructible concept”. When you do that, you are limiting your options. As a somewhat silly example, let’s say that someone has a non-move-constructible type… but that type is noexcept default constructible, and noexcept move-assignable. In that case, you could still implement enqueue(value_type&&)… except if you already blocked it by requiring move construction, now you’re screwed.

That example may have been silly, but there’s actually a real case of it in your code here. Your enqueue(value_type&&) says that it requires move construction… except that it will still work without move construction. If I have a type that is copy constructible, but not move constructible, then move construction will fall back on copy construction. So enqueue(value_type&&) still works fine with types that are not move constructible. Your requires clause prevents perfectly good code from working.

The bottom line is: don’t use concepts unless you know you need them. You don’t need them here. They don’t actually improve anything. Even without the concepts, the functions will fail to compile for types that won’t work.

  [[nodiscard]] value_type
  dequeue() requires(std::is_destructible<value_type>::value) {
    --m_Size;
    value_type temp = m_RawData[0];
    m_AllocTraits.destory(m_Alloc, std::addressof(m_RawData[0]));
    m_ShiftToLeft();
    return temp;
  }

Now this requires clause is obviously unnecessary, as discussed earlier.

I’m also not keen on the [[nodiscard]] here. It’s not hard to image usage scenarios where I want to pop something off the front of the queue, but I don’t really care what it is. Forcing me to care about what I’m taking off the queue seems unnecessarily dictatorial. You should use [[nodiscard]] in situations where ignoring the return value is probably an error. I don’t see that that’s the case here.

You also have some exception safety issues. What happens if the copy construction to temp fails? You’ve already decremented m_Size… which means you’ve “lost” the last element of the queue. Seems safer to not change the size until after you’ve done the dangerous stuff.

(Also, you misspelled “destroy”.)

  template <class... Args> void emplace(Args &&...args) {
    enqueue(value_type(std::forward<Args>(args)...));
  }

Ah, you’ve kinda missed the point of emplacing. The point of emplacing is to construct the new object in place. (Hence, “emplace”.) Not to just construct it somewhere random and then copy it in. Rather than writing emplace() in terms of enqueue(), it would make more sense to do the opposite.

  value_type at(size_type index) const
  value_type operator[](size_type index) const

These should return a const_reference, not a value_type.

  queue<value_type> &operator=(const queue<value_type> &oth) {
    if (&oth != this) {
      clear();
      m_Size = oth.size();
      m_CheckOrAlloc(m_Size);
      std::uninitialized_copy(oth.begin(), oth.end(), m_RawData);
    }
    return *this;
  }

This is a dangerous way to do copy assignment. If any of the copying at the end fails, you’ve lost the original data. A better way is to use the “copy and swap” idiom.

  queue<value_type> &operator=(queue<value_type> &&oth) {
    if (&oth != this) {
      clear();
      m_Size = oth.size();
      m_CheckOrAlloc(m_Size);
      std::uninitialized_move(oth.begin(), oth.end(), m_RawData);
      oth.~queue();
    }
    return *this;
  }

It’s usually possible, and much easier, to implement moving in terms of swapping.

But in any case, explicitly calling the destructor of oth is definitely wrong. Except in very rare, special-case situations, you should never manually call destructors.

  queue<value_type> &operator=(const queue<value_type> &&oth) = delete;

Again, what is the purpose of this?

  ~queue() {
    m_Alloc.deallocate(m_RawData, m_Capacity);
    std::exchange(m_RawData, nullptr);
    std::exchange(m_Size, 0);
  }
  ~queue() requires(std::is_destructible<value_type>::value) {
    clear();
    m_Alloc.deallocate(m_RawData, m_Capacity);
    std::exchange(m_RawData, nullptr);
    std::exchange(m_Size, 0);
  }

So, let’s set aside the whole is_destructible thing; only the second destructor is correct (sorta).

However, there’s no point in zeroing the data members at the end (and even less point in using std::exchange() to do it). It doesn’t matter if m_RawData is still pointing to now deallocated memory, because m_RawData is about to cease existing anyway.

\$\endgroup\$
2
  • \$\begingroup\$ I appreciate your effort, I'm confused about the move assignment/ctor, why having noexcept depending on the allocator stats and also the swap when is_always_equal is true otherwise just allocate enough capacity, why it does and why is it important ? \$\endgroup\$ – dammi Mar 16 at 15:12
  • \$\begingroup\$ Answering that would take far more space than comments allow, and the answer above is already full, so I'll add another answer with the explanation. \$\endgroup\$ – indi Mar 18 at 21:09
0
\$\begingroup\$

Answers to questions

Allocator equality

The first piece of the puzzle is understanding what it means when two allocators are equal. If two allocators are equal, then any memory allocated with one can be deallocated with the other.

For example:

auto a1 = std::allocator<int>{};
auto a2 = std::allocator<int>{};

std::cout << std::boolalpha << (a1 == a2); // will print "true"

auto p = a1.allocate(1);

// this is okay:
a2.deallocate(p);

If two allocators are not equal, then you cannot deallocate memory from one with the other:

auto mr1 = std::pmr::unsynchronized_pool_resource{};
auto mr2 = std::pmr::unsynchronized_pool_resource{};

auto a1_a = std::pmr::polymorphic_allocator<int>{&mr1};
auto a1_b = std::pmr::polymorphic_allocator<int>{&mr1};

std::cout << std::boolalpha << (a1_a == a1_b) << '\n'; // will print "true"

auto a2 = std::pmr::polymorphic_allocator<int>{&mr2};

std::cout << std::boolalpha << (a2 == a1_a) << '\n'; // will print "false"
std::cout << std::boolalpha << (a2 == a1_b) << '\n'; // will print "false"

auto p1 = a1_a.allocate(1);
auto p2 = a1_a.allocate(1);

// this is okay:
a1_b.deallocate(p1);

// this is *NOT* okay:
a2.deallocate(p2);

Some types of allocators are always equal. For example, std::allocator just uses new and delete, so it doesn’t matter which std::allocator instance you use (in theory, you could even mix std::allocator with raw new and delete… but I do not recommend that).

Which allocator gets used?

The next piece of the puzzle is knowing which allocator gets used with different methods of construction, assignment, and swapping. I’ll use std::vector as a guide (since your queue is basically a std::vector under the hood):

  • vector() noexcept(noexcept(Allocator()))
    • Default-constructed allocator.
  • explicit vector(Allocator const& alloc) noexcept
    • Uses alloc. (It can be noexcept because allocators must be noexcept copyable, and it’s not doing any allocating.)
  • vector(vector const& other)
    • Uses std::allocator_traits<Allocator>::select_on_container_copy_construction(other.get_allocator()). Usually just copies the allocator.
  • vector(vector const& other, Allocator const& alloc)
    • Uses alloc.
  • vector(vector&& other) noexcept
    • Uses an allocator move-constructed from other.get_allocator().
  • vector(vector&& other, Allocator const& alloc)
    • Uses alloc.
  • auto operator=(vector const& other) -> vector&
    • If std::allocator_traits<Allocator>::propagate_on_container_copy_assignment::value is true:
      • Uses a copy of other’s allocator.
    • Else:
      • Keeps its own allocator.
  • auto operator=(vector&& other) noexcept(/* !!! */) -> vector&
    • If std::allocator_traits<Allocator>::propagate_on_container_move_assignment::value is true:
      • Uses a copy of other’s allocator.
    • Else:
      • Keeps its own allocator.
  • auto swap(vector& a, vector& b) noexcept (/* !!! */) -> void
    • If std::allocator_traits<Allocator>::propagate_on_container_swap::value is true:
      • a and b swap allocators along with their data.
    • Else:
      • a and b keep their own allocators.

Most of those are pretty trivial. The move-plus-allocator constructor, the move-assignment, and the swap are the really interesting cases.

vector(vector&& other, Allocator const& alloc)

Okay, so other has a bunch of elements allocated with its own allocator. You want to move them into this… but there’s a catch. The elements were allocated with other.get_allocator()… if you move them into this, then they will be deallocated with alloc.

If alloc == other.get_allocator(), then there’s no problem. Just move the pointer and you’re good.

But if alloc != other.get_allocator(), then you can’t simply transfer the memory over. You need to allocate all new memory, and then move the elements from the old memory into the new memory. This, of course, might fail and throw an exception.

So that’s this:

constexpr queue(queue&& other, Allocator const& alloc) :
    m_Alloc{alloc}
{
    if (m_Alloc == other.m_Alloc)
    {
        // just move the pointer; cannot fail
    }
    else
    {
        // need to allocate memory, then MOVE-CONSTRUCT elements
        // from other
        //
        // afterwards, other should have its original size and
        // capacity... but all the elements should be moved-from
    }
}

But there’s an optimization we can make. If the allocators are always equal, then this constructor can never fail. So:

constexpr queue(queue&& other, Allocator const& alloc)
        noexcept(std::allocator_traits<Allocator>::is_always_equal) :
    m_Alloc{alloc}
{
    if constexpr (std::allocator_traits<Allocator>::is_always_equal)
    {
        // just move the pointer; cannot fail
    }
    else
    {
        if (m_Alloc == other.m_Alloc)
        {
            // just move the pointer; cannot fail
        }
        else
        {
            // need to allocate memory, then MOVE-CONSTRUCT elements
            // from other
            //
            // afterwards, other should have its original size and
            // capacity... but all the elements should be moved-from
        }
    }
}

auto operator=(vector&& other) noexcept(/* !!! */) -> vector&

Okay, now this has a bunch of elements, allocated with this->get_allocator(), and other has a different bunch of elements, allocated with other.get_allocator().

The first question to ask is whether the allocator gets moved, too, or whether this keeps its own allocator. For that we use std::allocator_traits<Allocator>::propagate_on_container_move_assignment::value.

If the allocator does get moved, then things are pretty easy. The allocator is actually just copied, and copying allocators cannot fail. The same time we take other’s allocator, we can just steal its data pointer, too. And of course, clearing the data that was previously in this also cannot fail. (Though, in practice, for efficiency, the data usually isn’t cleared, it’s just moved over to this, where it will presumably be destroyed or assigned-over shortly anyway.) So it’s all simple, and no-fail.

If the allocator doesn’t get moved, then things get more complicated. Let’s deal with that in a moment, and for now, take a look at what we have:

constexpr auto operator=(queue&& other)
        noexcept(std::allocator_traits<Allocator>::propagate_on_container_move_assignment /* ??? */)
    -> queue&
{
    if constexpr (std::allocator_traits<Allocator>::propagate_on_container_move_assignment)
    {
        // basically do `this->clear()`, but in practice, the pointer to
        // `this`'s data is usually just moved over to `other`

        // move `other`'s allocator and data pointer over to `this`
    }
    else
    {
        // ...
    }

    return *this;
}

Okay, if the allocator doesn’t propagate, then we need to check if the two allocators are equal.

If they are equal, then there’s no problem. We can simply swap the data pointers around, because it doesn’t matter which allocated them, or which will deallocate. And swapping pointers cannot fail.

If they are not equal, then we can’t simply swap the pointers. We actually need to make sure this has enough capacity, then move everything over from other one element at a time. Of course this could fail.

So:

constexpr auto operator=(queue&& other)
        noexcept(std::allocator_traits<Allocator>::propagate_on_container_move_assignment /* ??? */)
    -> queue&
{
    if constexpr (std::allocator_traits<Allocator>::propagate_on_container_move_assignment)
    {
        // basically do `this->clear()`, but in practice, the pointer to
        // `this`'s data is usually just moved over to `other`

        // move `other`'s allocator and data pointer over to `this`
    }
    else
    {
        if (m_alloc == other.m_alloc)
        {
            // basically do `this->clear()`, but in practice, the pointer to
            // `this`'s data is usually just moved over to `other`

            // move `other`'s data pointer over to `this`
        }
        else
        {
            // need to make sure this has enough capacity, then
            // MOVE-ASSIGN the elements from other into this
            //
            // take into account whether moving/copying is noexcept;
            // if not, then maybe you need to use a temporary buffer
            // to keep the strong exception guarantee
            //
            // afterwards, other should have its original size and
            // capacity... but all the elements should be moved-from
        }
    }

    return *this;
}

Now, in that else clause, we can use the same optimization we used before. If the allocators are always equal, then there’s no need to waste time doing the comparison, plus we know that the whole move will never fail.

Which gives us:

constexpr auto operator=(queue&& other)
        noexcept(std::allocator_traits<Allocator>::propagate_on_container_move_assignment
                or std::allocator_traits<Allocator>::is_always_equal)
    -> queue&
{
    if constexpr (std::allocator_traits<Allocator>::propagate_on_container_move_assignment)
    {
        // basically do `this->clear()`, but in practice, the pointer to
        // `this`'s data is usually just moved over to `other`

        // move `other`'s allocator and data pointer over to `this`
    }
    else
    {
        if constexpr (std::allocator_traits<Allocator>::is_always_equal)
        {
            // basically do `this->clear()`, but in practice, the pointer to
            // `this`'s data is usually just moved over to `other`

            // move `other`'s data pointer over to `this`
        }
        else
        {
            if (m_alloc == other.m_alloc)
            {
                // basically do `this->clear()`, but in practice, the pointer to
                // `this`'s data is usually just moved over to `other`

                // move `other`'s data pointer over to `this`
            }
            else
            {
                // need to make sure this has enough capacity, then
                // MOVE-ASSIGN the elements from other into this
                //
                // take into account whether moving/copying is noexcept;
                // if not, then maybe you need to use a temporary buffer
                // to keep the strong exception guarantee
                //
                // afterwards, other should have its original size and
                // capacity... but all the elements should be moved-from
            }
        }
    }

    return *this;
}

The noexcept clause basically says: “if the allocator is being moved (in which case, we can no-fail move the data pointer along with it; this case is the first comment block in the function above) OR if it is always okay to allocate and deallocate with different allocator instances (this case is the second comment block above)”. If it is only sometimes okay to allocate and deallocate with different allocator instances (that is, if allocators aren’t always equal; the third and fourth comment blocks), then we cannot guarantee no-fail.

auto swap(vector& a, vector& b) noexcept (/* !!! */) -> void

This case is pretty similar to the case above, with only minor tweaks (like replacing propagate_on_container_move_assignment with propagate_on_container_swap). So we can start with this:

constexpr auto swap(queue& other)
        noexcept(std::allocator_traits<Allocator>::propagate_on_container_swap
            or std::allocator_traits<Allocator>::is_always_equal)
    -> void
{
    if constexpr (std::allocator_traits<Allocator>::propagate_on_container_swap)
    {
        // just swap the pointers and allocators
    }
    else
    {
        if constexpr (std::allocator_traits<Allocator>::is_always_equal)
        {
            // just swap the pointers
        }
        else
        {
            if (m_alloc == other.m_alloc)
            {
                // just swap the pointers
            }
            else
            {
                // ???
            }
        }
    }

    return *this;
}

The complexity comes when you ask what happens in that last block (the one marked with the “???” comment). I’m not going to work through the logic here, because it’s just long and tedious, with many, many different cases to consider (are the sizes equal? if not, does the smaller one have enough capacity for all the elements in the larger? etc. etc.). I’ll just tell you the punch line: it turns out there is no way, in general, to swap elements from one allocator’s arena into another’s. (You can do things that look kinda like swapping when the dust settles, like move-constructing a’s elements into memory allocated by b and move-constructing b’s elements into memory allocated by a, but that’s not actually swapping since the elements in both queues are now totally newly-constructed… not simply swapped over.)

That’s why std::vector doesn’t even bother to handle that case; it’s just undefined behaviour.

\$\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.