Section 9.1. Defining a Sequential Container

9.1. Defining a Sequential Container

We already know a fair bit about how to use the sequential containers based on what we covered in Section 3.3 (p. 90). To define a container object, we must include its associated header file, which is one of

      #include <vector>      #include <list>      #include <deque> 

Each of the containers is a class template (Section 3.3, p. 90). To define a particular kind of container, we name the container followed by angle brackets that enclose the type of the elements the container will hold:

      vector<string>    svec;       // empty vector that can hold strings      list<int>         ilist;      // empty list that can hold ints      deque<Sales_item> items;      // empty deque that holds Sales_items 

Each container defines a default constructor that creates an empty container of the speicfied type. Recall that a default constructor takes no arguments.

For reasons that shall become clear shortly, the most commonly used container constructor is the default constructor. In most programs, using the default constructor gives the best run-time performance and makes using the container easier.

9.1.1. Initializing Container Elements

In addition to defining a default constructor, each container type also supports constructors that allow us to specify initial element values.

Table 9.2. Container Constructors

C<T> c;	Create an empty container named c. C is a container name, such as vector, and T is the element type, such as int or string. Valid for all containers.
C c(c2);	Create c as a copy of container c2; c and c2 must be the same container type and hold values of the same type. Valid for all containers.
C c(b, e);	Create c with a copy of the elements from the range denoted by iterators b and e. Valid for all containers.
C c(n, t);	Create c with n elements, each with value t, which must be a value of the element type of C or a type convertible to that type. Sequential containers only.
C c(n);	Create c with n value-initialized (Section 3.3.1, p. 92) elements. Sequential containers only.

Intializing a Container as a Copy of Another Container

When we initialize a sequential container using any constructor other than the default constructor, we must indicate how many elements the container will have. We must also supply initial values for those elements. One way to specify both the size and element values is to initialize a new container as a copy of an existing container of the same type:

      vector<int> ivec;      vector<int> ivec2(ivec);   // ok: ivec is vector<int>      list<int>   ilist(ivec);   // error: ivec is not list<int>      vector<double> dvec(ivec); // error: ivec holds int not double 

When we copy one container into another, the types must match exactly: The container type and element type must be the same.

Initializing as a Copy of a Range of Elements

Although we cannot copy the elements from one kind of container to another directly, we can do so indirectly by passing a pair of iterators (Section 3.4, p. 95). When we use iterators, there is no requirement that the container types be identical. The element types in the containers can differ as long as they are compatible. It must be possible to convert the element we copy into the type held by the container we are constructing.

The iterators denote a range of elements that we want to copy. These elements are used to initialize the elements of the new container. The iterators mark the first and one past the last element to be copied. We can use this form of initialization to copy a container that we could not copy directly. More importantly, we can use it to copy only a subsequence of the other container:

      // initialize slist with copy of each element of svec      list<string> slist(svec.begin(), svec.end());      // find midpoint in the vector      vector<string>::iterator mid = svec.begin() + svec.size()/2;      // initialize front with first half of svec: The elements up to but not including *mid      deque<string> front(svec.begin(), mid);      // initialize back with second half of svec: The elements *mid through end of svec      deque<string> back(mid, svec.end()); 

Recall that pointers are iterators, so it should not be surprising that we can initialize a container from a pair of pointers into a built-in array:

      char *words[] = {"stately", "plump", "buck", "mulligan"};      // calculate how many elements in words      size_t words_size = sizeof(words)/sizeof(char *);      // use entire array to initialize words2      list<string> words2(words, words + words_size); 

Here we use sizeof (Section 5.8, p. 167) to calculate the size of the array. We add that size to a pointer to the first element to get a pointer to a location one past the end of the array. The initializers for words2 are a pointer to the first element in words and a second pointer one past the last element in that array. The second pointer serves as a stopping condition; the location it addresses is not included in the elements to be copied.

Allocating and Initializing a Specified Number of Elements

When creating a sequential container, we may specify an explicit size and an (optional) initializer to use for the elements. The size can be either a constant or non-constant expression. The element initializer must be a valid value that can be used to initialize an object of the element type:

      const list<int>::size_type list_size = 64;      list<string> slist(list_size, "eh?"); // 64 strings, each is eh? 

This code initializes slist to have 64 elements, each with the value eh?.

As an alternative to specifying the number of elements and an element initializer, we can also specify only the size:

 list<int> ilist(list_size); // 64 elements, each initialized to 0 // svec has as many elements as the return value from get_word_count extern unsigned get_word_count(const string &file_name); vector<string> svec(get_word_count("Chimera")); 

When we do not supply an element initializer, the library generates a value-initialized (Section 3.3.1, p. 92) one for us. To use this form of initialization, the element type must either be a built-in or compound type or be a class type that has a default constructor. If the element type does not have a default constructor, then an explicit element initializer must be specified.

The constructors that take a size are valid only for sequential containers; they are not supported for the associative containers,

9.1.2. Constraints on Types that a Container Can Hold

While most types can be used as the element type of a container, there are two constraints that element types must meet:

• The element type must support assignment.

• We must be able to copy objects of the element type.

There are additional constraints on the types used as the key in an associative container, which we'll cover in Chapter 10.

Most types meet these minimal element type requirements. All of the built-in or compound types, with the exception of references, can be used as the element type. References do not support assignment in its ordinary meaning, so we cannot have containers of references.

Exercises Section 9.1.1

Exercise 9.1:	Explain the following initializations. Indicate if any are in error, and if so, why. int ia[7] = { 0, 1, 1, 2, 3, 5, 8 }; string sa[6] = { "Fort Sumter", "Manassas", "Perryville", "Vicksburg", "Meridian", "Chancellorsville" }; (a) vector<string> svec(sa, sa+6); (b) list<int> ilist( ia+4, ia+6); (c) vector<int> ivec(ia, ia+8); (d) list<string> slist(sa+6, sa);
Exercise 9.2:	Show an example of each of the four ways to create and initialize a vector. Explain what values each vector contains.
Exercise 9.3:	Explain the differences between the constructor that takes a container to copy and the constructor that takes two iterators.

With the exception of the IO library types (and the auto_ptr type, which we cover in Section 17.1.9 (p. 702)), all the library types are valid container element types. In particular, containers themselves satisfy these requirements. We can define containers with elements that are themselves containers. Our Sales_item type also satisifes these requirements.

The IO library types do not support copy or assignment. Therefore, we cannot have a container that holds objects of the IO types.

Container Operations May Impose Additional Requirements

The requirement to support copy and assignment is the minimal requirement on element types. In addition, some container operations impose additional requirements on the element type. If the element type doesn't support the additional requirement, then we cannot perform that operation: We can define a container of that type but may not use that particular operation.

One example of an operation that imposes a type constraint is the constructors that take a single initializer that specifies the size of the container. If our container holds objects of a class type, then we can use this constructor only if the element type has a default constructor. Most types do have a default constructor, although there are some classes that do not. As an example, assume that Foo is a class that does not define a default constructor but that does have a constructor that takes an int argument. Now, consider the following declarations:

      vector<Foo> empty;     // ok: no need for element default constructor      vector<Foo> bad(10);   // error: no default constructor for Foo      vector<Foo> ok(10, 1); // ok: each element initialized to 1 

We can define an empty container to hold Foo objects, but we can define one of a given size only if we also specify an initializer for each element.

As we describe the container operations, we'll note the constraints, if any, that each container operation places on the element type.

Containers of Containers

Because the containers meet the constraints on element types, we can define a container whose element type is itself a container type. For example, we might define lines as a vector whose elements are a vector of strings:

      // note spacing: use ">>" not ">>" when specifying a container element type      vector< vector<string> > lines; // vector of vectors 

Note the spacing used when specifying a container element type as a container:

      vector< vector<string> > lines; // ok: space required between close >      vector< vector<string>> lines; // error: >> treated as shift operator 

We must separate the two closing > symbols with a space to indicate that these two characters represent two symbols. Without the space, >> is treated as a single symbol, the right shift operator, and results in a compile-time error.

Exercises Section 9.1.2

Exercise 9.4:	Define a list that holds elements that are deques that hold ints.
Exercise 9.5:	Why can we not have containers that hold iostream objects?
Exercise 9.6:	Given a class type named Foo that does not define a default constructor but does define a constructor that takes int values, define a list of Foo that holds 10 elements.