Array (C++)

The array is a wrapper class that provides an STL-like interface to standard fixed-size C arrays. It also overcomes several limitations of standard arrays.

Creation history

In his book Generic Programming and the STL, Matthew H. Austern introduces a wrapper class for ordinary arrays with static size, called block. It is safer and has no worse performance than ordinary arrays. In The C++ Programming Language, 3rd edition, Bjarne Stroustrup introduces a similar class, called c_array, which Nicolai Josuttis presents slightly modified in his book The C++ Standard Library - A Tutorial and Reference, called carray.

Under the name array this class is introduced in boost libraries by Nicolai Josuttis. Later this class was introduced in the C++ Standard Library in TR1.

Motivation

Standard C arrays have several principal limitations:

• They aren't value types. They can not be copied like other objects.
• They do not provide an STL-like interface.

Design

The array template class is defined in header <array> in the C++ standard library and in header <boost/array.hpp> in boost. It can reside in namespaces std:: (in C++0x), std::tr1:: (in C++03 with TR1) or boost::.

The array class template is parametrized with the type of the elements and the number of elements. It can be instantiated with any type that fulfills the CopyConstructible and Assignable requirements. It also itself fulfills CopyConstructible and Assignable requirements.

If array class template is instantiated with a type that fulfills EqualityComparable or LessThanComparable requirements, it fulfills EqualityComparable or LessThanComparable correspondingly.

Class also provides standard iterators and element access functions.

Implementation as aggregate

The array class is implemented as an aggregate class. This allows an array to be initialized with a brace-enclosed, comma-separated list of initializers for the elements of the container, written in increasing subscript order:

array<int, 4> a = { { 1, 2, 3 } };

Note that if there are fewer elements in the initializer list, then each remaining element gets default-initialized. (Thus, it has a defined value.)

However, this approach has its own drawbacks: Passing no initializer list means that the elements have an indeterminate initial value, because the rule says that aggregates may have:

• No user-declared constructors.
• No private or protected non-static data members.
• No base classes.
• No virtual functions.

Note that for standard conforming compilers it is possible to use fewer braces (according to 8.5.1 (11) of the Standard). That is, the array template can be initialized as follows:

array<int, 4> a = { 1, 2, 3 };

Differences from standard array

• The array class is a value type. It satisfies CopyConstructable and Assignable requirements.
• The array class can not be implicitly cast to T * or T const *. However there is member function data() that returns a pointer to the first element.
• The array implementation is not required to do bound check. However the implementation in boost does that for operator[], but not for iterators.

Zero-sized arrays

Unlike standard arrays, the array class can have size zero. The effect of calling front() or back() for a zero-sized array is implementation-defined, but begin() and end() shall return the same unique value. The return value of data() is unspecified for zero-sized arrays.

Differences from standard containers

• The array class does not provide constant-time swap. Instead it provides linear-time swap.
• Because the array class is an aggregate it does not provide fill and range constructors. Its default constructor also does not initialize elements with zeros.
• size() is always constant, based on the second template argument of the type.
• The container provides no allocator support.

Overview of functions

An object of class array can be created using default constructor, copy constructor or initializer list syntax.

expression	description	computational complexity
array<T, N> a	create a array object, elements of that have undetermined values	O(1)
array<T, N> a1(a2)	create a copy of other array object	O(N)
array<T, N> a = {/*...*/}	create a array object initialized with specified values	O(N)

The array class provides a swap function and the assignment operator. The only difference from other containers is that swap takes linear time.

expression	return type	description	computational complexity
swap(a1, a2)	void	swap content of arrays	O(N)
a1 = a2	array &	copy content of a2 to a1	O(N)

Although TR1 define function assign to fill an array with a specified value, C++0x has the function fill for the same purpose. The boost implementation of array supports both functions.

expression	return type	description	computational complexity
a.assign(u)	void	fill a with u (TR1 only)	O(N)
a.fill(u)	void	fill a with u (C++0x only)	O(N)

The array class provides a standard iterator interface.

expression	return type	description	computational complexity
a.begin()	[const_]iterator	returns iterator to first element of array	O(1)
a.end()	[const_]iterator	returns iterator to the one after the last element of array	O(1)
a.rbegin()	[const_]reverse_iterator	returns reverse iterator to first element of array	O(1)
a.rend()	[const_]reverse_iterator	returns reverse iterator to the one after the last element of array	O(1)

The array class provides standard query-capacity functions.

expression	return type	description	computational complexity
a.size()	size_t	returns size of array	O(1)
a.max_size()	size_t	returns size of array	O(1)
a.empty()	bool	a.size() == 0	O(1)

The array class provides a standard set of element access functions.

expression	return type	description	computational complexity
a[i]	T [const] &	returns reference to i-th element	O(1)
a.at(i)	T [const] &	returns reference to i-th element or throws out_of_range exception	O(1)
a.front()	T [const] &	returns reference to first element of array	O(1)
a.back()	T [const] &	returns reference to last element of array	O(1)

The array class has six standard comparison operators.

expression	return type	description	computational complexity
a1 < a2	bool	compare arrays lexicographically	O(N)
a1 == a2	bool	compare arrays lexicographically	O(N)
a1 > a2	bool	compare arrays lexicographically	O(N)
a1 <= a2	bool	compare arrays lexicographically	O(N)
a1 != a2	bool	compare arrays lexicographically	O(N)
a1 >= a2	bool	compare arrays lexicographically	O(N)

Raw data access functions.

expression	return type	description	computational complexity
a.data()	T [const] *	returns pointer to first element of array	O(1)
a.c_array()	T *	returns pointer to first element of array (non-standard, boost-only, no const-overload)	O(1)

The array class provides the standard tuple interface.

expression	return type	description
tuple_size<array>::value	N	returns size of tuple
tuple_element<I, array>::type	T	returns type of tuple element
get<i>(a)	T	returns value of i-th tuple element

The array class provides the standard set of dependent types.

expression	return type
array<T, N>::reference	T &
array<T, N>::const_reference	T const &
array<T, N>::iterator	implementation-defined (T * in boost)
array<T, N>::const_iterator	implementation-defined (T const * in boost)
array<T, N>::size_type	size_t
array<T, N>::difference_type	ptrdiff_t
array<T, N>::value_type	T
array<T, N>::reverse_iterator	reverse_iterator<iterator>
array<T, N>::const_reverse_iterator	reverse_iterator<const_iterator>

External links

• A Proposal to Add a Fixed Size Array Wrapper to the Standard Library Technical Report
• Boost.Array documentation