Chapter 4. The array Class Template
Even Solomon in all his glory was not arrayed like one of these.
— The Gospel According to Saint Matthew, 6:29
C-style arrays are tricky to use with STL algorithms. The size of the array is not part of its type, and the name of the array in almost all contexts decays into a pointer to its first element. So code that creates iterators into C-style arrays has to deal directly with the size of the array.
Example 4.1. C-style Arrays and the STL (contarray/carray.cpp)
#include <algorithm>
#include <iostream>
using std::cout; using std::sort;
void do_sort (int *values, int count)
{ // sort contents of array
sort (values, values + count);
}
int main ()
{ // demonstrate use of C-style array as STL sequence
const int ELEMS = 6;
int values [ELEMS] = { 3, 1, 4, 2, 9, 8 };
for (int i = 0; i < ELEMS; ++i)
cout << values[i] << ' ';
cout << '
';
do_sort (values, ELEMS);
for (int i = 0; i < ELEMS ; ++i)
cout << values[i] << ' ';
cout << '
';
return 0;
}
The class template array<Ty, N> holds an array of N elements of type Ty. Its advantage over an ordinary array is that it directly supports some of the operations required for a sequence container.
Example 4.2. Class Template array and the STL (contarray/array.cpp)
#include <array>
#include <algorithm>
#include <iostream>
using std::cout; using std::sort;
using std::tr1::array;
template <class Container>
void do_sort (Container& values)
{ // sort contents of array
sort (values.begin(), values.end());
}
int main()
{ // demonstrate use C-style array as STL sequence
const int ELEMS = 6;
array<int, ELEMS> values = { 3, 1, 4, 2, 9, 8 };
for (int i = 0; i < ELEMS ; ++i)
cout << values [i] << ' ';
cout << '
';
do_sort(values);
for (int i = 0; i < ELEMS; ++i)
cout << values[i] << ' ';
cout << '
';
return 0;
}
The class template itself, as well as several function templates that round out the support for the sequence container requirements and for a tuple-like interface, is defined in the header <array>.
namespace std {
namespace tr1 {
template<class Ty, size_t N>
class array;
// FUNCTION TEMPLATES
template<class Ty, size_t N>
bool operator==(
const array<Ty, N>& left,
const array<Ty, N>& right);
template<class Ty, size_t N>
bool operator!=(
const array<Ty, N>& left,
const array<Ty, N>& right);
template<class Ty, size_t N>
bool operator<(
const array<Ty, N>& left,
const array<Ty, N>& right);
template<class Ty, size_t N>
bool operator<=(
const array<Ty, N>& left,
const array<Ty, N>& right);
template<class Ty, size_t N>
bool operator>(
const array<Ty, N>& left,
const array<Ty, N>& right);
template<class Ty, size_t N>
bool operator>=(
const array<Ty, N>& left,
const array<Ty, N>& right);
template<class Ty, size_t N>
void swap(
array<Ty, N>& left,
array<Ty, N>& right);
// tuple-LIKE INTERFACE
template<int Idx, class Ty, size_t N>
Ty& get(array<Ty, N>& arr);
template<int Idx, class Ty, size_t N>
const Ty& get(const array<Ty, N>& arr);
template<class Ty, size_t N>
class tuple_element<array<Ty, N> >;
template<class Ty, size_t N>
class tuple_size<array<Ty, N> >;
} }
4.1. Class Template array
template<class Ty, size_t N>
class array {
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef Ty& reference;
typedef const Ty& const_reference;
typedef Ty *pointer;
typedef const Ty *const_pointer;
typedef T0 iterator;
typedef T1 const_iterator;
typedef Ty value_type;
typedef reverse_iterator<iterator>reverse_iterator;
typedef reverse_iterator<const_iterator>
const_reverse_iterator;
void assign(const Ty& val);
void swap(array& right);
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
size_type size() const;
size_type max_size() const;
bool empty() const;
reference operator[](size_type off);
const_reference operator[](size_type off) const;
reference at(size_type off);
const_reference at(size_type off) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
T *data();
const T *data() const;
};
An object of type array<Ty, N> holds N objects of type Ty in contiguous storage.[1]
Each specialization of the class template array is an aggregate, using only the compiler-generated default constructor, copy constructor, copy assignment operator, and destructor.
An object of type array<Ty, N> can be constructed either with the default constructor, which uses the default constructor for Ty to initialize each of the stored elements, or with an aggregate initializer, which is an opening curly brace followed by zero to N comma-separated values, each of which must be convertible to the type Ty, followed by a closing curly brace. The compiler will use each of the initializer values to construct the corresponding element in the array object. If there are fewer than N initializers, the remaining elements are value-initialized.[2]
Example 4.3. Construct an array Object (contarray/constructing.cpp)
#include <array>
#include <algorithm>
#include <iterator>
#include <ostream>
#include <iostream>
using std::tr1::array;
using std::basic_ostream; using std::cout;
using std::copy; using std::ostream_iterator;
class Elt
{ // class with non-trivial default constructor
public:
Elt() : i (1) {}
Elt(int ii) : i(ii) {}
private:
template<class Elem, class Traits> friend
basic_ostream<Elem, Traits>& operator<<(
basic_ostream<Elem, Traits>&, const Elt&);
int i;
};
template<class Elem, class Traits>
basic_ostream<Elem, Traits>& operator <<(
basic_ostream<Elem, Traits>& out, const Elt& elt)
{ // show object contents
return out << elt .i;
}
int main()
{ // demonstrate default constructor and aggregate initialization
array<Elt, 6> arr0;
copy(arr0.begin(), arr0.end(),
ostream_iterator <Elt>(cout, " "));
cout << '
';
array<Elt, 6> arr1 = { 1, 2, 3, 4 };
copy(arr1.begin(), arr1.end(),
ostream_iterator <Elt >(cout, " "));
cout << '
';
array<int, 6> arr2 = { 1, 2, 3, 4 };
copy(arr2.begin(), arr2.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
array<int, 6> arr3;
copy(arr3.begin(), arr3.end(),
ostream_iterator <int>(cout, " "));
cout << '
';
array<int, 6> arr4 = {};
copy(arr4.begin(), arr4.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
return 0;
}
An object of type array<Ty, N> can also be used to initialize another object of the same type, and an object of type array<Ty, N> can be assigned to another object of the same type.
Example 4.4. Copy an array Object (contarray/copying.cpp)
#include <array>
#include <algorithm>
#include <iterator>
#include <ostream>
#include <iostream>
using std::tr1::array;
using std::basic_ostream; using std::cout;
using std::copy; using std::ostream_iterator;
int main()
{ // demonstrate copying
cout << "Original array: ";
array<int, 6> arr0 = { 1, 1, 2, 3, 5, 8 };
copy(arr0.begin(), arr0.end(),
ostream_iterator<int>(cout, " "));
cout << "
Copied array: ";
array<int, 6> arr1 = arr0;
copy(arr1.begin(), arr1.end(),
ostream_iterator<int>(cout, " "));
cout << "
New array: ";
array<int, 6> arr2 = {};
copy(arr2.begin(), arr2.end(),
ostream_iterator<int>(cout, " "));
cout << "
After copy: ";
arr2 = arr0;
copy(arr2.begin(), arr2.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
return 0;
}
4.2. Queries
All containers have three member functions that provide information about the size of their controlled sequence. For array objects, these functions are very simple, because the size never changes.
size_type array<Ty, N>::size() const;
The member function returns N, the number of elements in the controlled sequence.
The member function returns N, the maximum possible number of elements in the controlled sequence.
bool array<Ty, N>::empty() const;
The member function returns N == 0.
4.3. Access
reference array<Ty, N>::operator[](size_type off);
const_reference
array<Ty, N>::operator[](size_type off) const;
The member functions return a reference to the element of the controlled sequence at position off. If the position is invalid, the behavior is undefined.
These functions provide the usual indexed access to elements of an array. Note that the implementation is not required to check the index value against the bounds of the array. If there is a possibility of getting an index value that is out of bounds, the calling code should check the value before calling these operators.
Example 4.5. Checking Index Values (contarray/indexing.cpp)
#include <array>
#include <iostream>
using std::tr1::array;
using std::cin; using std::cout;
const int ELEMS = 10;
array<int, ELEMS> squares = { 0, 1, 4, 9, 16,
25, 36, 49, 64, 81 };
int main()
{ // demonstrate array indexing
int idx = -1;
while (idx <0 || ELEMS <= idx)
{ // check index value before using
cout << "Value to square: ";
cin >> idx;
}
cout << idx << " squared is "
<< squares [idx] << "
";
// no check needed:
for (idx = 0; idx < ELEMS; ++idx)
cout << idx << " squared is "
<< squares[idx] << '
';
return 0;
}
reference array<Ty, N>::at(size_type off);
const_reference array<Ty, N>::at(size_type off) const;
The member functions return a reference to the element of the controlled sequence at position off. If the position is invalid, the function throws an object of class std::out_of_range.
These functions provide indexed access to elements of an array. The index value is checked against the bounds of the array; if the value is out of bounds, the function throws an exception. It’s tempting to use this function to avoid validating input, but it’s usually better to make the range check explicit. Exceptions should be reserved for truly exceptional situations and not used for control flow.
Example 4.6. Implicit Checking of Index Values (contarray/at.cpp)
#include <array>
#include <iostream>
#include <stdexcept>
using std::tr1::array;
using std::cin; using std::cout; using std::out_of_range;
const int ELEMS = 10;
array<int, ELEMS> squares = { 0, 1, 4, 9, 16,
25, 36, 49, 64, 81 };
int main()
{ // demonstrate index checking with array::at
int idx = -1;
for (;;)
{ // don't do this:
try { // show the value
cout << idx << " squared is "
<< squares .at(idx) << '
';
break;
}
catch(const out_of_range&)
{ // prompt for new index value
cout << "Value to square: ";
cin >> idx;
}
}
return 0;
}
reference array<Ty, N>::front();
const_reference array<Ty, N>::front() const;
The member functions return a reference to the first element of the controlled sequence. If the controlled sequence is empty, the behavior is implementation-defined.
reference array<Ty, N>::back();
const_reference array<Ty, N>::back() const;
The member functions return a reference to the last element of the controlled sequence. If the controlled sequence is empty, the behavior is implementation-defined.
T *array<Ty, N>::data();
const T *array<Ty, N>::data() const;
The member functions return a pointer to the first element of the controlled sequence or, for an empty sequence, a non-null pointer that cannot be dereferenced.
As mentioned earlier, the elements of an array object are contiguous. As a result, the pointer returned by data() is a pointer to a C-style array of N objects of type Ty.
Example 4.7. C-Style Array of Objects (contarray/data.cpp)
#include <array>
#include <stdlib.h>
#include <iostream>
using std::tr1::array;
using std::cout;
int lt(const void *left, const void *right)
{ // compare int values pointed to by left and right
int il = *(int*)left;
int ir = *(int*)right;
return il < ir ? -1 : il == ir ? 0 : 1;
}
const int ELEMS = 6;
int main()
{ // demonstrate use of array::data() as C-style pointer
array<int, ELEMS> values = { 3, 1, 4, 2, 9, 8 };
for (int i = 0; i < ELEMS; ++i)
cout << values [i] << ' ';
cout << '
';
qsort(values.data(), ELEMS, sizeof(int), lt);
for (int i = 0; i < ELEMS; ++i)
cout << values[i] << ' ';
cout << '
';
return 0;
}
4.4. Modification
Individual elements of a non-const array object can be modified through the reference returned by operator[] or the member function at. Multiple elements can be modified by calling assign or swap.
void array<Ty, N>::assign(const Ty& val);
The member function replaces the controlled sequence with a repetition of N elements of value val.
This function simply assigns the value val to all the elements in the array object. Be careful, though, when you use array objects in generic code: The signature of this function is not the same as the signature of the member function assign for sequence containers. That function takes an element count as its first argument and creates a new sequence with the specified number of elements. Since the number of elements in an array object is fixed, passing this argument to the member function would be pointless.
void array<Ty, N>::swap(array& right);
The member function swaps the controlled sequences between *this and right in linear time.
template <class Ty, size_t N>
void swap(array<Ty, N>& left, array<Ty, N>& right);
The function template calls left.swap(right).
The swap functions exchange the contents of two array objects of the same type. However, the time they take is proportional to the size of the array objects, so they do not meet the sequence container requirement that swap run in constant time.
4.5. Iteration
iterator array<Ty, N>::begin();
const_iterator array<Ty, N>::begin() const;
The member functions return a random-access iterator that points to the first element of the controlled sequence or just beyond the end of an empty sequence.
iterator array<Ty, N>::end();
const_iterator array<Ty, N>::end() const;
The member functions return a random-access iterator that points just beyond the end of the controlled sequence.
The member functions begin and end return a pair of iterators that designate the beginning and the end of the controlled sequence.
Example 4.8. Calling an Algorithm (contarray/beginend.cpp)
#include <array>
#include <algorithm>
#include <iostream>
#include <iterator>
using std::tr1::array;
using std::sort;
using std::cout; using std::copy;
using std::ostream_iterator;
const int ELEMS = 6;
int main()
{ // demonstrate use of begin and end to designate range
array<int, ELEMS> values = { 3, 1, 4, 2, 9, 8 };
copy(values.begin(), values.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
sort(values.begin(), values.end());
copy(values.begin(), values.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
return 0;
}
reverse_iterator array<Ty, N>::rbegin();
const_reverse_iterator array<Ty, N>::rbegin() const;
The member functions return a random-access iterator that points just beyond the end of the controlled sequence. Hence, it designates the beginning of the reverse sequence.
reverse_iterator array<Ty, N>::rend();
const_reverse_iterator array<Ty, N>::rend() const;
The member functions return a random-access iterator that points to the first element of the controlled sequence or just beyond the end of an empty sequence. Hence, it designates the end of the reverse sequence.
The member functions rbegin and rend return a pair of iterators that designate the beginning and the end of the controlled sequence in reverse.
Example 4.9. Reversing an Algorithm (contarray/rbeginrend.cpp)
#include <array>
#include <algorithm>
#include <iostream>
#include <iterator>
using std::tr1::array;
using std::sort;
using std::cout; using std::copy;
using std::ostream_iterator;
const int ELEMS = 6;
int main()
{ // demonstrate use of rbegin and rend to designate range
array<int, ELEMS> values = { 3, 1, 4, 2, 9, 8 };
copy(values.begin(), values.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
sort(values.rbegin(), values.rend());
copy(values.begin(), values.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
return 0;
}
4.6. Nested Type Names
The class template array provides all the nested type names required for sequence containers in the standard C++ library.
typedef size_t array<Ty, N>::size_type;
The unsigned integer type describes an object that can represent the length of any controlled sequence. It is required to be a synonym for the type size_t.
typedef ptrdiff_t array<Ty, N>::difference_type;
The signed integer type describes an object that can represent the difference between the addresses of any two elements in the controlled sequence. It is required to be a synonym for the type ptrdiff_t.
typedef Ty& array<Ty, N>::reference;
The type describes an object that can serve as a reference to an element of the controlled sequence. It is required to be a synonym for the type Ty&.
typedef const Ty& array<Ty, N>::const_reference;
The type describes an object that can serve as a reference to an element of the controlled sequence. The reference type does not permit modification of the referenced element. It is required to be a synonym for the type const Ty&.
typedef Ty *array<Ty, N>::pointer;
The type describes an object that can serve as a pointer to an element of the controlled sequence. It is required to be a synonym for the type Ty*.
TR1 doesn’t actually require the nested type pointer, but that seems to be an oversight.
typedef const Ty *array<Ty, N>::const_pointer;
The type describes an object that can serve as a pointer to an element of the controlled sequence. The pointer type does not permit modification of the element it points to. It is required to be a synonym for the type const Ty*.
TR1 doesn’t actually require the nested type const_pointer, but that seems to be an oversight.
typedef T0 array<Ty, N>::iterator;
The type describes an object that can serve as a random-access iterator for the controlled sequence. It is described here as a synonym for the implementation-defined type T0.
Just as with std::vector, the type of an iterator is not required to be a pointer to the contained type. When you write code that stores iterators explicitly—which you should do only rarely, if at all—use the nested type name:
typedef array<int, 10> data;
data values;
data::iterator iter =
values.begin(); // if you insist
int *pointer = values.begin(); // wrong, but might compile
typedef T1 array<Ty, N>::const_iterator;
The type describes an object that can serve as a random-access iterator for the controlled sequence. The iterator type does not permit modification of the element it points to. It is described here as a synonym for the implementation-defined type T1.
typedef Ty array<Ty, N>::value_type;
The type is a synonym for the template parameter Ty.
typedef reverse_iterator<iterator>
array<Ty, N>::reverse_iterator;
The type describes an object that can serve as a reverse iterator for the controlled sequence.
The type describes an object that can serve as a reverse iterator for the controlled sequence. The iterator type does not permit modification of the element it points to.
4.7. Comparisons
template<class Ty, size_t N>
bool operator==(
const array<Ty, N>& left,
const array<Ty, N>& right);
The function template overloads operator== to compare two objects of class template array. The function returns equal(left.begin(), left. end(), right.begin()).
This is the usual definition of equality: Two containers are equal if their corresponding elements are equal.
template<class Ty, size_t N>
bool operator!=(
const array<Ty, N>& left,
const array<Ty, N>& right);
The function template overloads operator!= to compare two objects of class template array. The function returns !(left == right).
template<class Ty, size_t N>
bool operator<(
const array<Ty, N>& left,
const array<Ty, N>& right);
The function template overloads operator< to compare two objects of class template array. The function returns lexicographical_compare (left.begin(), left.end(), right.begin()).
This is the usual definition of less-than: One container is less than another if, in the first pair of unequal elements, the element from the first container is less than the element from the second container.
template<class Ty, size_t N>
bool operator<=(
const array<Ty, N>& left,
const array<Ty, N>& right);
The function template overloads operator<= to compare two objects of class template array. The function returns !(right < left).
template<class Ty, size_t N>
bool operator>(
const array<Ty, N>& left,
const array<Ty, N>& right);
The function template overloads operator> to compare two objects of class template array. The function returns right < left.
template<class Ty, size_t N>
bool operator>=(
const array<Ty, N>& left,
const array<Ty, N>& right);
The function template overloads operator>= to compare two objects of class template array. The function returns !(left < right).
4.8. The tuple-like Interface
The type array<Ty, N> is similar to the type tuple<Ty, Ty, …, Ty> with N arguments of type Ty, so the TR1 library provides a set of overloaded function templates that can be applied to array objects in the same way that they can be applied to tuple objects.
template<int Idx, class Ty, size_t N>
Ty& get(array<Ty, N>& arr);
template<int Idx, class Ty, size_t N>
const Ty& get(const array<Ty, N>& arr);
The function templates return a reference to arr[Idx]. If Idx < 0 or N <= Idx, the program is ill formed.
template<class Ty, size_t N>
class tuple_element<array<Ty, N> >;
The class template holds a nested type named type that is a synonym for the template parameter Ty.
template<class Ty, size_t N>
class tuple_size<array<Ty, N> >;
The class template holds a compile-time constant named value of an unspecified integral type whose value is the template parameter N.
[0, N), &arr[n] == &arr[0] + n.
Exercises
Exercise 1
For each of the following errors, write a simple test case containing the error, and try to compile it. In the error messages, look for the key words that relate to the error in the code.
1. Attempting aggregate initialization of an array object with more initializers than the number of elements it holds
2. Attempting default construction of an array object holding elements whose type does not have a default constructor
3. Attempting aggregate initialization with a type that cannot be converted to the type of elements the array type holds
4. Attempting copy construction from an array object of a different type
5. Attempting to call get with an index value that is out of bounds
Exercise 2
Write a struct named elt that holds a value of type unsigned char but doesn’t initialize it. Create an object of type std::tr1::array<elt, 6> with no initializer, and show the stored values. Now write a new struct, elt1, that holds a value of type unsigned char and has a default constructor that sets the stored value to 1. Create an object of type std::tr1::array <elt1, 6> with no initializer, and show the stored values.
Exercise 3
Repeat the preceding exercise, but when you create each array object, use an aggregate initializer that initializes some but not all of the stored objects. (You’ll have to add another constructor to elt1. It should take a value of type unsigned char and copy it to the stored value.)
Exercise 4
Create an object of type array<int, 6> that initially holds all 0s. Change all its stored values to 1. Create an object of type array<int, 6> that initially holds all 1s. Change all its stored values to 0.
Exercise 5
Create two objects of type array<int, 6>. The first one should contain the values 1 through 6 in ascending order. The second one should contain the value 1, 2, 3, 3, 9000, and 9001, in that order. Which of the two is less than the other? Write a test program to verify your answer.
Exercise 6
Repeat Exercise 5 from Chapter 1 with array instances instead of tuple instances.