C/C++ Users Journal, January 2006
Last month, we looked at iterators and algorithms, the fundamental abstractions that underlie the Standard Template Library. The TR1 Library doesn't add anything to either of these. It does, however, add several call wrapper types and five new containers. This month, we'll start looking at the new containers with the header<array>, and next month we'll look at the headers <unordered_set> and <unordered_map>.
As you can see from Listing 1, the header <array> defines the template class array. It also defines the usual six comparison functions and a swap function to exchange the contents of two array objects. And, finally, it defines two template functions named get and specializations of the two template classestuple_size and tuple_element.
The details of the template class array are in Listing 2. The template takes two arguments. The first is the type of the elements that the object will hold, and the second is the number of elements. Thus, like a C-style array, an array object holds a fixed-size array of objects. The similarity goes further, though: An array object can be initialized with an aggregate initializer, just like a C-style array [1]. Listing 3 shows this similarity. Note that the initializer for each of the arrays has fewer elements than the array being initialized; if you compile and run this program, you'll see that the extra elements in both arrays are initialized to 0.
Of course, you can also create array objects that hold elements of class types, and use aggregate initialization to construct the individual elements. When you do this, the values in the aggregate initializer are passed to the constructors of the individual elements. This is illustrated in Listing 4.
According to the language definition, aggregate initialization only works for aggregate types. An array or class type is not an aggregate if it has any user-declared constructors, any private or protected nonstatic data members, any base classes, or any virtual functions. For the array template, this means that its only constructors are the two that the compiler generates: the default constructor and the copy constructor. Thus, you cannot, for example, initialize an array object from a sequence designated by a pair of iterators. In addition, since the size of an array object can't be changed, it can't have the commonly used container member functions insert, append, or erase. Despite all that, an array is a proper STL container, provided you apply the right definition of "container."
The most basic form of a container is specified in a table with the title "Container requirements" in the C++ Standard. Every container must meet these requirements, and array does just that. The typedefs listed under the heading "Nested Types" in Listing 2, other than reverse_iterator and const_reverse_ iterator, are the ones required for a container [2]. A container must also have a default constructor, a copy constructor, a destructor that destroys all of its elements, and an assignment operator that copies all of the elements from one object to another. For array, the compiler-generated versions of these functions do just what's needed. A container must also have the member functions begin and end, with each overloaded for const and nonconst containers. As you can see, they're in array. A container must also support all six comparison functions; they're in the header <array>. And finally, a container must provide the member functions swap, size, max_size, and empty [3].
The Standard also has a table with the title "Reversible container requirements" that defines, obviously, a reversible container. A reversible container meets all of the requirements for a container, and it supplies two typedefs, reverse_iterator and const_reverse_iterator, as well as two member functions named rbegin and rend, with each overloaded for const and nonconst containers. As you can see from Listing 2, array meets these requirements, too.
The requirements that array fails to meet are those set out in the table with the title "Sequence requirements." The requirements for a sequence container involve operations that change the size of the container; because an array type has a fixed size, it cannot satisfy these requirements. So it does not have a constructor that takes the desired size and an argument value; it does not have a constructor that takes a sequence designated by a pair of iterators; it doesn't have member functions insert, erase, or clear; and the only assign member function it has takes a single argument that is a reference to the element type, and copies that value into each of the elements.
In short, array is a reversible container, but not a sequence container.
As we've seen, you can initialize an array object with an aggregate initializer, and you can get at individual elements with operator[]. When called on a const array object, this operator returns a const reference to the element at the given index; when called on a nonconst object, it returns a nonconst reference. For a C-style array and for a TR1 array object, using the index operator with an index value that's out of range produces undefined behavior. Just as with vector, though, if you want range-checked access to an array object, you can use the member function at. Of course, you can also do your own range checking, using the member function size, as shown in Listing 5.
The member function assign takes a single argument whose type is a reference to the element type of the array type. It copies that argument into each element of the array object. Listing 6 demonstrates this, along with the swap member function. It also uses the begin and end member functions to get iterators to the beginning and the end of the array object's controlled sequence, and the member function rbegin and rend to get iterators that move through the sequence in reverse order.
Sometimes you need to get a pointer to the contents of an array object. For a C-style array this is easy: In most contexts, the name of an array decays into a pointer to its first element. For a TR1 array object, the member function data gives you a suitable pointer [4]. You can use that pointer in the same way as the address of the first element of a C array, with the same restrictions. In particular, if you pass the pointer into a function that needs to know how many elements are in the array, you also have to pass the element count. Listing 7 illustrates this.
Unlike C-style arrays, array objects can be assigned. Of course, there's a trick to make C-style arrays assignable: Wrap the array inside a struct. That's what the template class array actually does, so being able to assign array objects simply falls out of their definition; see Listing 8.
Finally, the member functions front and back return references to the first and the last elements in the array object, respectively. For a const array object, they return const references.
Most of the things we've looked at so far can be done with array objects and with C-style arrays. The main benefit of using array objects for these things is the simpler syntax. In particular, since the number of elements in an array object is part of the object's type, we don't have to resort to macro tricks or global constants when we need to know how many elements to process. In addition, having the number of elements as part of an array object's type makes it much harder to accidentally intermix array objects with different numbers of elements. That's good if it prevents you from copying a large array object onto a smaller one, but it's bad if you need to write a function that takes arrays of arbitrary sizes. Of course, in the latter case, you can call the member function data() to get the raw array [5].
There's one fairly important thing you can do with C-style arrays that you can't do with array objects. You can't use the initializer alone to set the size of the array. With C-style arrays, you can do this:
int carray[] = { 1, 1, 2, 3, 5 };
and the result will be an array of five ints. With an array object, the size is a template parameter, so you must write it as part of the definition of the object. This makes it a little harder to ensure that an array has the same size as its initializer—when you change the initializer you must also change the size argument.
There are two things you can do with array objects that you can't do with C-style arrays: You can create zero-sized objects, and you can treat them like tuple objects.
Unlike a C-style array, an array object can hold zero elements. You can define an array object that holds zero elements in the obvious way: Just pass 0 as the size argument.
Arrays of zero elements might not sound very useful, but as with loops that execute zero times, it's usually easier to write a single block of code that handles edge cases correctly than to deal with edge cases separately. Of course, code that uses array objects has to be written a bit more carefully if it can be called with a zero-sized object. In particular, indexing won't work (and the member function at will throw an exception whenever it's called), and front and back should not be called because their behavior is undefined. You can still use begin, end, rbegin, and rend to get iterators to the controlled sequence. The STL algorithms that take iterator pairs will work correctly because they're designed to handle empty sequences correctly. And you can call data and pass the returned pointer to a function that takes a size argument and uses it correctly; see Listing 9.
Back in July 2005, we looked at the new TR1 template class tuple, which is a generalization of the Standard Library template class pair. An object of type array<Ty, N> is similar to an object of type tuple<Ty, Ty, ...> with N template arguments of type Ty. To exploit this similarity, TR1 provides specializations of the external accessors for tuple that can be used with array types. To get a reference to the nth element of an array object at compile time, you can use the template function get<n>. To get the type of the nth element of an array object, you can use the template tuple_element, and to get the size of an array object, you can use the template tuple_size. This is shown in Listing 10.
The TR1 template class array holds a fixed-size array of objects of the same type. It can be used wherever a Reversible Container is needed, and it can stand in for a C-style array with simpler syntax and greater safety. There's very little reason to use C-style arrays anymore.
Next time, we'll look at the four new container templates unordered_set, unordered_multiset, unordered_map, and unordered_multimap. They use hash tables to implement the interfaces required for set, multiset, map, and multimap.
CUJ