6
\$\begingroup\$

Two years ago I wrote a short vector optimized dynamic array type (std::vector), for use in an image analysis library. I don't think boost::small_vector existed at the time.

The use case: Images in this library can have any number of dimensions. But obviously images with two or three dimensions are going to be most common by far. To store an image's size, I wanted to use the short vector optimization, as it avoids one malloc for almost all images, while still not putting a limit to the number of dimensions. Many other things in this library take advantage of the optimization, as it is common to specify one value per image dimension: filter sizes, coordinates, etc.

This container is designed for POD types only. Constructors and destructors are not called.

Another limitation is that it doesn't distinguish capacity from size, as std::vector does. The way it's used, arrays can grow or shrink by one element occasionally, there is no use case for repeated push_back. Most of the time, when the array grows or shrinks by one element, it is still a "short" array, and so no actual resizing is necessary.

For the review, I removed some methods and operators that implement algorithms relevant to this library, leaving only the methods that have an equivalent in std::vector. The full implementation is on GitHub. I've tried to leave everything else in place.

I'm of course open to any comments and suggestions, but I'd especially like to hear if I'm not satisfying any expectations or doing something that a seasoned C++ programmer would consider weird.

File dimension_array.h:

#ifndef DIP_DIMENSIONARRAY_H
#define DIP_DIMENSIONARRAY_H

#include <cstdlib>   // std::malloc, std::realloc, std::free, std::size_t
#include <initializer_list>
#include <iterator>
#include <algorithm>
#include <utility>
#include <iostream>

// These two are defined in a header file I'm not including for review.
#define DIP_NO_EXPORT
#define DIP_ASSERT( x )

namespace dip {

/// \brief A dynamic array type optimized for few elements.
///
/// `%dip::DimensionArray` is similar to `std::vector` but optimized for one particular
/// use within the *DIPlib* library: hold one element per image dimension. Most images have
/// only two or three dimensions...
/// ...You should only use this container with POD types...
/// [lengthy documentation cut out for review]
template< typename T >
class DIP_NO_EXPORT DimensionArray {
   public:
      // Types for consistency with STL containers
      using value_type = T;
      using iterator = T*;
      using const_iterator = T const*;
      using reverse_iterator = std::reverse_iterator< iterator >;
      using const_reverse_iterator = std::reverse_iterator< const_iterator >;
      using size_type = std::size_t;

      /// The default-initialized array has zero size.
      DimensionArray() {}

      /// Like `std::vector`, you can initialize with a size and a default value.
      explicit DimensionArray( size_type sz, T newval = T() ) {
         resize( sz, newval );
      }

      /// Like `std::vector`, you can initialize with a set of values in braces.
      DimensionArray( std::initializer_list< T > const init ) {
         resize( init.size() );
         std::copy( init.begin(), init.end(), data_ );
      }

      /// Copy constructor, initializes with a copy of `other`.
      DimensionArray( DimensionArray const& other ) {
         resize( other.size_ );
         std::copy( other.data_, other.data_ + size_, data_ );
      }

      /// \brief Cast constructor, initializes with a copy of `other`.
      /// Casting done as default in C++, not through `dip::clamp_cast`.
      template< typename O >
      explicit DimensionArray( DimensionArray< O > const& other ) {
         resize( other.size() );
         std::transform( other.data(), other.data() + size_, data_, []( O const& v ) { return static_cast< value_type >( v ); } );
      }

      /// Move constructor, initializes by stealing the contents of `other`.
      DimensionArray( DimensionArray&& other ) noexcept {
         steal_data_from( other );
      }

      // Destructor, no need for documentation
      ~DimensionArray() {
         free_array(); // no need to keep status consistent...
      }

      /// Copy assignment, copies over data from `other`.
      DimensionArray& operator=( DimensionArray const& other ) {
         if( this != &other ) {
            resize( other.size_ );
            std::copy( other.data_, other.data_ + size_, data_ );
         }
         return *this;
      }

      /// Move assignment, steals the contents of `other`.
      DimensionArray& operator=( DimensionArray&& other ) noexcept {
         // Self-assignment is not valid for move assignment, not testing for it here.
         free_array();
         steal_data_from( other );
         return *this;
      }

      /// Swaps the contents of two arrays.
      void swap( DimensionArray& other ) {
         using std::swap;
         if( is_dynamic() ) {
            if( other.is_dynamic() ) {
               // both have dynamic memory
               swap( data_, other.data_ );
            } else {
               // *this has dynamic memory, other doesn't
               other.data_ = data_;
               data_ = stat_;
               std::move( other.stat_, other.stat_ + other.size_, stat_ );
            }
         } else {
            if( other.is_dynamic() ) {
               // other has dynamic memory, *this doesn't
               data_ = other.data_;
               other.data_ = other.stat_;
               std::move( stat_, stat_ + size_, other.stat_ );
            } else {
               // both have static memory
               std::swap_ranges( stat_, stat_ + std::max( size_, other.size_ ), other.stat_ );
            }
         }
         swap( size_, other.size_ );
      }

      /// \brief Resizes the array, making it either larger or smaller. Initializes
      /// new elements with `newval`.
      void resize( size_type newsz, T newval = T() ) {
         if( newsz == size_ ) { return; } // NOP
         if( newsz > static_size_ ) {
            if( is_dynamic() ) {
               // expand or contract heap data
               T* tmp = static_cast< T* >( std::realloc( data_, newsz * sizeof( T )));
               //std::cout << "   DimensionArray realloc\n";
               if( tmp == nullptr ) {
                  throw std::bad_alloc();
               }
               data_ = tmp;
               if( newsz > size_ ) {
                  std::fill( data_ + size_, data_ + newsz, newval );
               }
               size_ = newsz;
            } else {
               // move from static to heap data
               // We use malloc because we want to be able to use realloc; new cannot do this.
               T* tmp = static_cast< T* >( std::malloc( newsz * sizeof( T )));
               //std::cout << "   DimensionArray malloc\n";
               if( tmp == nullptr ) {
                  throw std::bad_alloc();
               }
               std::move( stat_, stat_ + size_, tmp );
               data_ = tmp;
               std::fill( data_ + size_, data_ + newsz, newval );
               size_ = newsz;
            }
         } else {
            if( is_dynamic() ) {
               // move from heap to static data
               if( newsz > 0 ) {
                  std::move( data_, data_ + newsz, stat_ );
               }
               free_array();
               size_ = newsz;
               data_ = stat_;
            } else {
               // expand or contract static data
               if( newsz > size_ ) {
                  std::fill( stat_ + size_, stat_ + newsz, newval );
               }
               size_ = newsz;
            }
         }
      }

      /// Clears the contents of the array, set its length to 0.
      void clear() { resize( 0 ); }

      /// Checks whether the array is empty (size is 0).
      bool empty() const { return size_ == 0; }

      /// Returns the size of the array.
      size_type size() const { return size_; }

      /// Accesses an element of the array
      T& operator[]( size_type index ) { return *( data_ + index ); }
      /// Accesses an element of the array
      T const& operator[]( size_type index ) const { return *( data_ + index ); }

      /// Accesses the first element of the array
      T& front() { return *data_; }
      /// Accesses the first element of the array
      T const& front() const { return *data_; }

      /// Accesses the last element of the array
      T& back() { return *( data_ + size_ - 1 ); }
      /// Accesses the last element of the array
      T const& back() const { return *( data_ + size_ - 1 ); }

      /// Returns a pointer to the underlying data
      T* data() { return data_; };
      /// Returns a pointer to the underlying data
      T const* data() const { return data_; };

      /// Returns an iterator to the beginning
      iterator begin() { return data_; }
      /// Returns an iterator to the beginning
      const_iterator begin() const { return data_; }
      /// Returns an iterator to the end
      iterator end() { return data_ + size_; }
      /// Returns an iterator to the end
      const_iterator end() const { return data_ + size_; }
      /// Returns a reverse iterator to the beginning
      reverse_iterator rbegin() { return reverse_iterator( end() ); }
      /// Returns a reverse iterator to the beginning
      const_reverse_iterator rbegin() const { return const_reverse_iterator( end() ); }
      /// Returns a reverse iterator to the end
      reverse_iterator rend() { return reverse_iterator( begin() ); }
      /// Returns a reverse iterator to the end
      const_reverse_iterator rend() const { return const_reverse_iterator( begin() ); }

      /// \brief Adds a value at the given location, moving the current value at that
      /// location and subsequent values forward by one.
      void insert( size_type index, T const& value ) {
         DIP_ASSERT( index <= size_ );
         resize( size_ + 1 );
         if( index < size_ - 1 ) {
            std::move_backward( data_ + index, data_ + size_ - 1, data_ + size_ );
         }
         *( data_ + index ) = value;
      }

      /// Adds a value to the back.
      void push_back( T const& value ) {
         resize( size_ + 1 );
         back() = value;
      }

      /// Adds all values in source array to the back.
      void push_back( DimensionArray const& values ) {
         size_type index = size_;
         resize( size_ + values.size_ );
         for( size_type ii = 0; ii < values.size_; ++ii ) {
            data_[ index + ii ] = values.data_[ ii ];
         }
      }

      /// Removes the value at the given location, moving subsequent values forward by one.
      void erase( size_type index ) {
         DIP_ASSERT( index < size_ );
         if( index < size_ - 1 ) {
            std::move( data_ + index + 1, data_ + size_, data_ + index );
         }
         resize( size_ - 1 );
      }

      /// Removes the value at the back.
      void pop_back() {
         DIP_ASSERT( size_ > 0 );
         resize( size_ - 1 );
      }

   private:
      constexpr static size_type static_size_ = 4;
      size_type size_ = 0;
      T* data_ = stat_;
      T stat_[ static_size_ ];
      // The alternate implementation, where data_ and stat_ are in a union
      // to reduce the amount of memory used, requires a test for every data
      // access. Data access is most frequent, it's worth using a little bit
      // more memory to avoid that test.

      bool is_dynamic() noexcept {
         return data_ != stat_;
      }

      void free_array() noexcept {
         if( is_dynamic() ) {
            std::free( data_ );
            //std::cout << "   DimensionArray free\n";
         }
      }

      void steal_data_from( DimensionArray& other ) noexcept {
         if( other.is_dynamic() ) {
            size_ = other.size_;
            data_ = other.data_;       // move pointer
            other.size_ = 0;           // so other won't deallocate the memory space
            other.data_ = other.stat_; // make sure other is consistent
         } else {
            size_ = other.size_;
            data_ = stat_;
            std::move( other.data_, other.data_ + size_, data_ );
         }
      }
};


//
// Other operators and convenience functions
//

/// \brief Writes the array to a stream
template< typename T >
inline std::ostream& operator<<(
      std::ostream& os,
      DimensionArray< T > const& array
) {
   os << "{";
   auto it = array.begin();
   if( it != array.end() ) {
      os << *it;
      while( ++it != array.end() ) {
         os << ", " << *it;
      };
   }
   os << "}";
   return os;
}

template< typename T >
inline void swap( DimensionArray< T >& v1, DimensionArray< T >& v2 ) {
   v1.swap( v2 );
}

} // namespace dip

#endif // DIP_DIMENSIONARRAY_H

File main.cpp:

This shows some simple usage for testing. Compile with g++ -std=c++14 -Wall -Wextra -pedantic main.cpp -o test.

#include <iostream>
#include "dimension_array.h"

int main() {

   dip::DimensionArray< int > a{ 1, 2, 4, 8, 16, 32 };
   std::cout << "a, initial = " << a << '\n';

   dip::DimensionArray< int > b( 3, 1 );
   std::cout << "b, initial = " << b << '\n';
   b.resize( 5, 2 );
   std::cout << "b, after resize = " << b << '\n';

   a.swap( b );
   std::cout << "a, after swap = " << a << '\n';
   std::cout << "b, after swap = " << b << '\n';

   a.push_back( 3 );
   std::cout << "a, after push_back = " << a << '\n';
   a.pop_back();
   a.pop_back();
   std::cout << "a, after 2x pop_back = " << a << '\n';
   std::cout << "a.front() = " << a.front() << ", a.back() = " << a.back() << '\n';

   b.insert( 0, 100 );
   std::cout << "b, after insert = " << b << '\n';
   b.erase( 0 );
   b.erase( 1 );
   std::cout << "b, after 2x erase = " << b << '\n';
   b.clear();
   std::cout << "b, after clear = " << b << '\n';

}
\$\endgroup\$
8
\$\begingroup\$
/// ...You should only use this container with POD types...

I'd expect to see this comment replaced with code:

static_assert(std::is_trivially_copyable_v<T>, "");

(There is also a std::is_pod_v<T> type trait, at least for now, but I don't see what POD has to do with your constraints here. It might even be correct to test only for is_trivially_destructible_v<T>, or maybe you don't need the constraint at all, I'm too lazy to find out... well, okay, I see you're using realloc. So you need trivially relocatable at least. trivially_destructible would be insufficient; trivially_copyable is correct but overkill.)


bool empty() const
bool is_dynamic() noexcept

I would additionally expect empty() to be marked noexcept, and is_dynamic() to be marked const. In general it looks like you're not marking as many things noexcept as the STL would have marked.


/// Adds a value to the back.
void push_back( T const& value ) {
   resize( size_ + 1 );
   back() = value;
}

I am mildly surprised by the lack of a move-enabled void push_back(T&& value) and a perfect-forwarding template<class... Args> void emplace_back(Args&&... args).

/// Adds all values in source array to the back.
void push_back( DimensionArray const& values )

Contrariwise, this is a very surprising overload of push_back! This operation would normally be spelled something like append.


resize looks very big and complicated; maybe look for a way to refactor it so that it becomes more manageable. At the same time, I see that push_back is implemented in terms of resize, which means that push_back is probably less efficient than it could be (because it has to navigate all those branches in resize that don't apply to its special case).

Implementing push_back as a resize followed by T::operator=(const T&), rather than as a reserve followed by T::T(const T&), is a surprising decision. This suggests that you'll want to static_assert(is_trivially_constructible_v<T>, "") as well, to make sure you're not paying for an expensive zero-argument constructor.


If you're providing rbegin and rend, maybe consider providing cbegin, crbegin, cend, crend as well? They're all kind of dumb. :)


Basically, though, this looks like good STL-ish code. The biggest complaint I've got is that that usage comment should be expressed as one or more static_asserts; the rest is nits that don't really matter, or won't matter once you constrain the container to hold only trivially copyable, trivially constructible objects.

\$\endgroup\$
  • \$\begingroup\$ Many thanks for your comments! The static_assert is a really good suggestion! The push_back implementation (no move, no perfect-forwarding, no reserve) really is because I presume T is a numeric type, or not much more complicate than that. You make a good point about the additional default construction though. \$\endgroup\$ – Cris Luengo Apr 26 '18 at 13:10

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.