4
\$\begingroup\$

I have an array wrapper class that I'd like to get reviewed.

There are two differences with other common questions on this site. First, my class needs to be "nullable", where a "null array" has a different meaning than an array of length zero.

Second, I'm trying to test whether small size optimization (like gcc's std::string implementation) can improve performance of my application.

Below is my implementation. I also have another nullable array wrapper class without SSO, but it is pretty similar.

I want to know if my implementation is "correct" assuming up to C++14, but not C++17.

And is using std::numeric_limits::max size value a reasonable approach as a flag for "null array"? I considered using nullptr as the null flag, but allocate(0) may also return nullptr (e.g. on MSVC).

#ifndef SMALL_NULLABLE_ARRAY_H
#define SMALL_NULLABLE_ARRAY_H

#include <algorithm>
#include <type_traits>
#include <cstdlib>
#include <cstring>
#include <limits>

namespace sml {

template<class T, class Allocator = std::allocator<T>, class S = uint32_t, S stack_size = 20>
class SmallNullableArray {
  static_assert(std::is_pod<T>::value, "SmallNullableArray type should be POD");
public:
  typedef T       value_type;
  typedef T*      pointer_type;
  typedef T&      reference_type;
  typedef S       size_type;
  static constexpr size_type nullsize = std::numeric_limits<size_type>::max();
private:
  struct Members : Allocator { // derive from Allocator to use empty base optimization
    pointer_type          _data;
    size_type             _size;
    value_type            _stack[stack_size];
    constexpr pointer_type stack_address() {
      return &(this->_stack[0]);
    }
    inline pointer_type allocate_check_and_copy(value_type const * const data, const size_type size) {
      if(size == nullsize) {
        return this->stack_address();
      } else if(size <= stack_size) {
        pointer_type result = this->stack_address();
        std::copy(data, data + size, result);
        return result;
      } else {
        pointer_type result = this->allocate(size);
        std::copy(data, data + size, result);
        return result;
      }
    }
    inline pointer_type allocate_check(const size_type size) noexcept {
      if((size == nullsize) || (size <= stack_size)) {
        return this->stack_address();
      } else {
        return this->allocate(size);
      }
    }
    inline void deallocate_check() {
      if((this->_size > stack_size) && (this->_size != nullsize)) {
        this->deallocate(this->_data, this->_size);
      }
    }
    Members(value_type const * const data, const size_type size) : _data(this->allocate_check_and_copy(data, size)), _size(size) {}
    Members(const size_type size) : _data(this->allocate_check(size)), _size(size) {}
    Members() : _data(stack_address()), _size(0) {}
  } m;
  friend void swap(SmallNullableArray & first, SmallNullableArray & second) noexcept {
    using std::swap;
    std::swap(first.m._data, second.m._data);
    std::swap(first.m._size, second.m._size);
    std::swap(first.m._stack, second.m._stack);
    if(first.m._size <= stack_size) { first.m._data = first.m.stack_address(); }
    if(second.m._size <= stack_size) { second.m._data = second.m.stack_address(); }
  }
  
public:
  SmallNullableArray() : m() {}
  SmallNullableArray(value_type const * const data, const size_t size) : m(data, size) {}
  SmallNullableArray(const size_t size) : m(size) {}
  // Copy
  SmallNullableArray(SmallNullableArray const & other) : m(other.m._data, other.m._size) {}
  // Move
  SmallNullableArray(SmallNullableArray && other) noexcept : m() { swap(*this, other); }
  // "copy and swap" covers both move and copy assignment https://stackoverflow.com/q/3279543/2723734
  SmallNullableArray & operator=(SmallNullableArray other) {
    swap(*this, other);
    return *this;
  }
  // destructor
  ~SmallNullableArray() { m.deallocate_check(); }
  inline bool is_stack() const { return (m._size <= stack_size) || (m._size == nullsize); }
  inline bool is_null() const { return m._size == nullsize; }
  void nullify() {
    m.deallocate_check();
    m._data = m.stack_address();
    m._size = nullsize;
  }
  // reset and resize are the same, but reset doesn't copy over old data
  // we don't have m._capacity so there is always a re-allocation
  void reset(const size_type size) {
    m.deallocate_check();
    m._data = m.allocate_check(size);
    m._size = size;
  }
  void resize(const size_type size) {
    if(is_null()) {
      m._data = m.allocate_check(size);
      m._size = size;
    } else if(is_stack()) {
      pointer_type new_addr = m.allocate_check(size);
      std::memmove(new_addr, m._data, std::min(size, m._size) * sizeof(value_type)); // need memmove if new size is also stack allocated
      m._data = new_addr;
      m._size = size;
    } else {
      pointer_type new_addr = m.allocate_check(size);
      std::copy(m._data, m._data + std::min(size, m._size), new_addr);
      m.deallocate_check();
      m._data = new_addr;
      m._size = size;
    }
  }
  size_type size() const { return m._size; }
  pointer_type data() const { return m._data; }
  reference_type operator[](size_type idx) const { return *(m._data + idx); }
  pointer_type begin() { return m._data; }
  pointer_type end()   { return m._data + m._size; }
};

} // end namespace

#endif // include guard
\$\endgroup\$
4
\$\begingroup\$

Missing #include <memory>

Since you use std::allocator, you have to #include <memory>, otherwise your code might fail to compile.

Avoid unnecessary use of this->

Your code is full of this->, but in C++ you almost never have to use that, unless you have local variables in a member function that shadow member variables.

Add empty lines to your code to visually separate functions

It would help the readability of your code if you added newlines around functions and in other places where it will make the structure of your code more clear.

Also avoid multiple statements on one line. Just write out small functions like so:

bool is_null() const {
    return m._size == nullsize;
}

Unnecessary use of inline

There is no need to make the member functions of explicitly inline. The compiler should inline them automatically where appropriate.

Use std::size_t for size_type

I would strongly recommend just using std::size_t to store sizes. It will do the right thing. You might not think someone will want to make an array of more than \$2^{32}\$ elements, but that's probably a wrong assumption.

Unnecessary use of stack_address()

You can just write return _stack;. Alternatively, use std::array for the stack:

std::array<value_type, stack_size> stack;

And then you can use stack.data() to get a pointer to the stack.

How to represent a "null" array

Using std::numeric_limits::max is one way, although then you'd have to think about what happens if someone wants to create an array with exactly std::numeric_limits::max elements. But another way would be to use zero is the length, and then use something that is unused when the length is zero to store whether it is an empty array or a "null" array. For example, the first element of stack could be used as a flag in this case.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thank you! Btw, I believe std::allocator<void> is being deprecated not std::allocator in general. \$\endgroup\$
    – thc
    Sep 12 '21 at 18:45
  • \$\begingroup\$ Ah, I missed that. Indeed, then it's fine :) \$\endgroup\$
    – G. Sliepen
    Sep 12 '21 at 19:37

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.