Collaborator8.2-Blog-CTA-Demo

A Glimpse into C++14: Combine Flexibility and Performance with Dynamic Arrays and Runtime-Sized Arrays

C++14

C99 introduced the notion of variable length arrays: stack allocated built-in arrays whose size is determined at runtime. C++ lacks a similar feature, to the discontent of many a programmer. However, two recent proposals for adding dynamic arrays and runtime-sized arrays to C++14 are closing the gap at last. Learn how to use these new features to imitate C99’s variable length arrays in C++.

Just as you’ve grown used to C++11, a new standard dubbed C+14 is seen on the horizon. Fret not, though, for the new standard doesn’t bring any revolutionary features such as rvalue references or multithreading. C++14 mainly consists of technical fixes and tweaks to the current C++11 standard.

However, C++14 also includes some new features, including a class template that simulates dynamic arrays and a core language feature known as runtime-sized arrays with automatic storage duration. Both of these provide mechanisms for creating array-like objects and arrays whose sizes are determined at runtime, very much like C99’s variable length arrays (VLAs). In this article I explain these new C++14 features and how they differ from traditional Standard Library containers and built-in static arrays, respectively.

Before looking at these exciting new features let’s see why traditional C++ containers don’t fit the bill.

In Quest of Dynamic Arrays

Seemingly, you can stick to std::vector as an alternative to VLAs. In fact, at one time the C++ standards committee considered replacing built-in arrays with vectors all across the board!

Then again, vectors are not arrays. They allocate their objects on the free-store exclusively (whereas arrays’ storage is not restricted to a specific storage class). Second, std::vector defines the member function resize() that can change a vector’s size. resize() violates a crucial array invariant, namely its immutable size. For these reasons, you can’t use std::vector as a VLA substitute.

At this stage, you might consider using std::array. std::array satisfies all of the requirements of a container. As with built-in arrays, it may store its data on the stack or on the free-store. Let’s look at an example of std::array usage:

#include <array>
#include <iostream>
int main()
{
 //allocate on the stack
std::array<int, 10> vals{}; 
for (int count=0; count<vals.size(); ++count)
  vals[count]=count+1;
std::cout<<"the first value is: "    
  <<vals.front()<<std::endl;
std::cout<<"the last value is: "<<vals[(vals.size()-1)]  
  <<std::endl;
std::cout<<"the total number of elements is: " <<vals.size()<<std::endl;
int* alias=vals.data(); 
std::cout<<"the third element is: "<<alias[2]<<std::endl;
}

There is, however, one problem here. std::array supports only static initialization. You can’t specify its size at runtime:

void func(int sz)
{
 std::array <int,sz> arr;//sz isn’t a constant expression
}

std::array may be a reasonable substitute for built-in arrays whose size is known at compile-time. However, if a dynamic array is what you’re after, you need to look elsewhere.

The standard std::valarray container won’t do either. It supports dynamic initialization. However, it also defines resize().

Let’s face it: The C++11 Standard Library doesn’t have a proper substitute for C99’s VLAs. This is why committee members came up with two new proposals. The first proposal introduces a new container class called std::dynarray. The second introduces runtime-sized arrays with automatic storage duration. Both proposals were approved in April 2013 at the Bristol meeting. Let’s look at std::dynarray first.

To Have and to Hold

A container-based approach offers two advantages:

  • Seamless interfacing with standard iterators and algorithms
  • Code safety, particularly with respect to range-checking and copying

The newly-added std::dynarray container provides the familiar interface of a Standard Library container, albeit with two restrictions:

  • Once the container is initialized, its size cannot change throughout the container’s lifetime.
  • The container object shall not be restricted to the free-store. It may as well reside on the stack – at the discretion of the implementation.

The std::dynarray constructor takes a parameter indicating the number of elements in the container. There is no default constructor since there is no accepted default size for a dynarray object. (Note that you cannot instantiate an empty dynarray and populate it later. However, zero-sized dynarray objects are permitted.)

Additionally, std::dynarray supports copy construction. This implies that elements of a dynarray object must also be copy-constructible. The proposal doesn’t mention move semantics, which is no surprise. Moving from a std::dynarray might violate its size invariant.

std::dynarray provides random access iterators and reverse iterators. However, it doesn’t support construction from an initializer_list nor does it provide a constructor from first and last forward iterators. While the last two restrictions might seem limiting, the rationale behind them is as follows: initializer_list necessarily has a static number of elements. In such cases, a built-in array or a std::array are probably more appropriate design choices anyway. With respect to construction from first and last iterators, the technical consideration is that std::distance(first, last) is a constant time operation only for random access iterators. Users can calculate this value manually and pass the result to the std::array constructor.

The proposal introduces a new standard header file called <dynarray> that defines the class template std::dynarray. An instance of dynarray<T> stores elements of type contiguously. Thus, if d is a dynarray<T> then it obeys the identity &a[n] == &a[0] + n for all 0 <= n < N. Note that there is no mechanism for detecting whether a std::dynarray object is allocated on the free-store or on the stack.

Putting std::dynarray to Work

The following function creates a loop that traverses a std::dynarray object and prints its elements. Next, the function copy-constructs a new std::dynarray, sorts it, accumulates its elements’ values and finally, accesses the std::dynarray elements using data(), at() and the [] operator:

#include <dynarray> //C++14
#include <iostream>
#include <algorithm>
void show(const std::dynarray <int>& vals )
{
  std::dynarray<int>::const_iterator cit=vals.begin();
  for (; cit != vals.end(); cit++)
    std::cout << " " << *cit;
  std::cout << std::endl;
    //runtime initialization of a new dynarray
  std::dynarray <int> target (vals);
    //algorithms, iterators, data(), & rev iterators
  std::sort(target.begin(), target.end());
  for (int n=0, *p=target.data(); n<target.size(); n++ )
    std::cout << " " << p[n]<<std::endl;
  int res=
     std::accumulate(target.rbegin(),target.rend(),0);

  for (int j=0; j<target.size(); j++) {
    //subscript access and at()
   target.at(j)=j*2;
   std::cout<<" "<<target[j] <<std::endl;
  }
  std::cout<<"total: "<<res<<std::endl;
}

Notice how similar the interfaces of std::dynarray and std::vector are – so much so that you may replace every occurrence of std::dynarray in the listing above with std::vector without breaking the code or changing its semantics. The only crucial difference between std::dynarray and std::vector in this context is that once you instantiate a std::dynarray object, you cannot change its size.

Runtime-Sized Arrays

Runtime-sized arrays offer the same syntax and performance of C99’s VLAs. The std::dynarray facility, on the other hand, offers the robustness of a first class Standard Library container. Additional differences between these two features include:

  • Runtime-sized arrays do not allow zero-sized arrays; std::dynarray does.
  • One can use initializer lists with runtime-sized arrays. These aren’t currently supported with std::dynarray.
  • There are subtle differences with respect to the exceptions that each feature might throw. I won’t get into the details here but remember always to check the exception specification of each core feature and library class you use.

The following code uses a runtime-sized array. Any C++14 compliant compiler should accept it:

//C++14 only
#include <algorithm>
void f(std::size_t n)
{
  int arr[n]; //runtime-sized array
  for (std::size_t i=0; i< n; ++i)
    arr[i] = i*2;
  std::sort(arr, arr+n);
  for (std::size_t i=0; i< n; ++i)
    std::cout<<" "<<arr[i]<<std::endl;
}

Bear in mind that runtime-sized arrays aren’t precisely the same as C99’s VLAs. The C++14 feature is more restrained, which is just as well. Specifically, the following properties are excluded:

  • Runtime-sized multidimensional arrays
  • Modifications to the function declarator syntax
  • sizeof(a) being a runtime-evaluated expression returning the size of a
  • typedef int a[n]; evaluating n and passing it through the typedef

Examples:

void f(std::size_t n)
{
  int a[n]; //C++14
  unsigned int x=sizeof(a);             //ill-formed
  const std::type_info& ti = typeid(a); //ill-formed
  typedef int t[n];                     //ill-formed
}

In Conclusion

Runtime-sized arrays with automatic storage are to std::dynarray as ordinary, statically-sized arrays are to std::array. If you want a low-level, efficient core language arrays whose size is determined at runtime, use them. If however you need a full-blown container that simulates runtime-sized arrays, use std::dynarray instead.

With respect to compiler support of runtime-sized arrays, gcc, Intel C++, and Clang already implement this feature. At present I am not aware of any implementation that supports std::dynarray. However, after its recent approval, vendors should support it soon.

Danny Kalev is a certified system analyst and software engineer specializing in C++. Kalev has written several C++ textbooks and contributes C++ content regularly on various software developers’ sites. He was a member of the C++ standards committee and has a master’s degree in general linguistics. He’s now pursuing a PhD in linguistics. Follow Danny on Twitter.

See also:


Comments

  1. std::sort(a, a+n); is ill-formed.
    1) You probably meant arr, not a
    2) You’ll probably need arr+0 instead of a.

    • Danny Kalev says:

      mgaunard, You’re absolutely right. I’ve asked my eds to fix it.
      Thanks,
      Danny Kalev,

    • mindlessgeek says:

      You don’t need “+0″ to pass arr as an iterator.

      • std::sort expects both types to be the same.

        • Danny Kalev says:

          Aren’t arr and arr+n the same (both decay into pointers, which are treated as forward iterators)? I’ve never seen any compiler complaining about the use of arr as a sort argument instead of arr+0.
          Am I missing something here?
          Thanks,

  2. Great overview, thanks!

  3. >>std::array vals;//10 int’s initialized to 0

    It’s a mistake, I think. std::array is an aggregate just as built-in array – its elements are default-initialized and you need {} to zero them
    And std::dynarray will behave similarly too (at least according to N3690)
    Thanks

Speak Your Mind

*