一种短矢量优化的动态阵列类型

Question

两年前，我编写了一个简短的向量优化动态数组类型(std::vector)，用于图像分析库。我不认为boost::small_vector当时存在。

用例:这个库中的图像可以有任意数量的维度。但很明显，二维或三维图像将是最常见的。为了存储图像的大小，我想使用简短的向量优化，因为它避免了几乎所有图像的一个malloc，同时仍然没有限制维数。这个库中的许多其他东西都利用了优化，因为每个图像维度通常指定一个值:过滤器大小、坐标等。

这个容器只为POD类型设计。构造函数和析构函数不被调用。

另一个限制是它没有像std::vector那样区分容量和大小。按照它的使用方式，数组可以偶尔由一个元素增长或收缩，没有重复的push_back的用例。大多数情况下，当数组由一个元素增长或缩小时，它仍然是一个“短”数组，因此不需要实际调整大小。

为了进行回顾，我删除了一些实现与此库相关的算法的方法和操作符，只留下了在std::vector中等效的方法。完全实现是在GitHub上进行的.。我试着把其他的东西都留在原处。

当然，我愿意听取任何评论和建议，但我特别想知道，如果我没有满足任何期望，或者做一些经验丰富的C++程序员认为奇怪的事情。

文件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

文件main.cpp:

这显示了一些用于测试的简单用法。用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';

}

Answer 1

/// ...You should only use this container with POD types...

我希望看到这个注释被代码所取代：

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

(也有一个std::is_pod_v<T>类型的特性，至少现在，但我不知道它与这里的约束有什么关系。也许只对is_trivially_destructible_v<T>进行测试是正确的，或者您根本不需要约束，我懒得找出.好吧，好吧，我看你在用realloc。所以你至少需要微不足道的可重定位。trivially_destructible是不够的；trivially_copyable是正确的，但过分了。)

bool empty() const
bool is_dynamic() noexcept

另外，我希望empty()被标记为noexcept，is_dynamic()被标记为const。通常情况下，您似乎没有像STL所标记的那样多地标记noexcept。

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

我对缺少一个移动功能的void push_back(T&& value)和一个完美的转发template<class... Args> void emplace_back(Args&&... args)感到有点惊讶。

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

相反，这是一个非常惊人的过载的push_back！此操作通常拼写为类似于append的单词。

resize看起来很大，很复杂；也许可以寻找一种方法来重构它，使它变得更易于管理。同时，我看到push_back是按照resize实现的，这意味着push_back可能比它可能的效率要低(因为它必须导航resize中不适用于其特殊情况的所有分支)。

将push_back实现为resize，然后是T::operator=(const T&)，而不是reserve，然后是T::T(const T&)，这是一个令人惊讶的决定。这意味着您也需要static_assert(is_trivially_constructible_v<T>, "")，以确保您不会为一个昂贵的零参数构造函数付费。

如果您提供的是rbegin和rend，那么可以考虑提供cbegin、crbegin、cend、crend吗？他们都有点傻。:)

基本上，这看起来像是很好的STL-ish代码。我最大的抱怨是，这个用法评论应该用一个或多个static_assertS来表达；其余的则是nits，它们并不重要，或者说，一旦你限制容器只持有一些可复制的、琐碎的可构造对象，就不会有什么关系了。