Simple table lists choices for different arrays in C and C++ regarding array length and allocation cost on storage. In this context, array means a linear sequential container of element objects of the same type that are next to its neighbors in memory. The array may or may not be resized. The colors are assigned based on the flexibility of array length, speed of allocation on storage, and extra benefits and pitfalls in features.
Storage (auto variable)
|C/C++ array||fixed at compile-time||stack||example: int a;|
|boost::array||fixed at compile-time||stack||container-like support|
|C99 Variable Length Array||fixed after created at run-time||stack||unspecified behavior on error|
|C++ Variable Length Array on stack with alloca()||fixed after created at run-time||stack||See previous post. non-portable alloca().|
|std::vector with fixed_block_allocator<T,N>||Dynamic at run-time, but no larger than N||stack||STL compliant|
|stlsoft::auto_buffer||Dynamic at run-time||stack if size within a static length; heap otherwise||covered in Imperfect C++ (book)|
|boost::auto_buffer||Dynamic at run-time||stack if size within a static length; heap otherwise||more versatile than stlsoft::auto_buffer. Still in boost review process.|
|eastl::fixed_vector||Dynamic at run-time||stack if size within a static length; heap otherwise||EASTL replaces STL for high performance game development mostly on memory allocation. Download|
|rde::fixed_vector||Dynamic at run-time||stack if size within a static length; heap otherwise||RDESTL is similar to EASTL.|
|std::vector (plain)||Dynamic at run-time||heap||explicit elements construction (slow)|
|TR2 dynarray||fixed after created at run-time||heap, but compiler may use stack for auto variable optimization||in fact a std::vector but run-time size is fixed when vector’s variable length is unnecessary.|
|std::valarray||Dynamic at run-time||heap||mostly for mathematic use; no iterator|
|C++0x std::array||fixed at compile-time||stack||see boost::array|
It is quite clear that when high performance is needed, auto_buffers and fixed_vectors are winners, because it provides a fast stack allocation/deallocation when array length is less than the static template parameter, and falls back to heap storage in the worst case.
In fact, the same problem exists on other containers (and string as a special container). EASTL and RDESTL provide fixed_xxxx containers and fixed_string primarily based on stack. STLSOFT has basic_simple_string and basic_static_string for strings.
Leveraging Allocator of STL Containers
Other than std::vector with fixed_block_allocator<T,N> and std::vector, all approaches above are exactly STL containers. Given all the benefits of STL, it would be great to have a STL compliant approach.
STL containers have an allocator template argument for customizing memory allocation for the container. So other than creating new array classes, it is interesting to use the STL container types by using a custom allocator class to get the stack memory for container, for example, for vector.
The C++ allocator for containers is still quite limited with a lot of restrictions (see Effective STL Item 10: Be aware of allocator conventions and restrictions, and Improving Performance with Custom Pool Allocators for STL). For example, an allocator should be able to deallocate memory allocated by another instance of the same allocator class; this is important to implement swap() and list::splice correctly. This would require all allocator types to not have instance data members, but have only class-static data or access global variables. This requirement would make allocator customization a real pain. One can imagine such an allocator is really very restricted.
Fortunately, one can make the operator == of the allocator class to return false when one has instance data in the class. Most STL implementation would know that free swapping is not available for containers with this allocator, and would copy elements one by one. Therefore, by signifying an always unequal allocator, one can get much freedom in designing an allocator.
Even though the standard does not explicitly require the container to have an allocator member variable, it implies so in Allocator requirements. Especially, C++0x enhanced the the allocator model; unlike C++98/03, C++0x explicitly allows one to use an allocator with state (scoped allocator). The container can use meta-programming to take out the allocator member completely if an allocator does not have any data and compact the container’s footprint. If the allocator has state, however, the container has to store it as a data member.
This basically means that it is possible to create upfront an allocator with a big size, for example a fixed length array of T as reserved for container elements. When an instance of the container with a data member of such an allocator type is created on stack, it has that reserved array on stack too.
C++ Programming: Stack Allocators for STL Containers is an example. The fixed_block_allocator<T,N> would house up to N elements. It simply uses max_size() to indicate that fixed length as its memory limit, and trying to size over that would result in std::length_error in container. Because the array member in the allocator is obviously non-static, the allocator uses a false-returning operator ==. Currently it works fine with Visual C++ 10.0 in Release build, but with Debug build the vector has run-time error in the default Visual C++ setting, probably because VC adds debugging bells and rings out-run the buffer.
I think it is possible to extend fixed_block_allocator to use heap as a fall back when more memory is required, such that it does not have the severe limitation of capacity N. This will bring it on par with the auto_buffers and fixed_vectors, but still remain STL compliant.