Programming: Principles and Practice Using C++ (2014)

---

19.2.4 push_back

When we first think of it, push_back() may appear complicated to implement, but given reserve() it is quite simple:

void vector::push_back(double d)
// increase vector size by one; initialize the new element with d
{
if (space==0)
reserve(8); // start with space for 8 elements
else if (sz==space)
reserve(2*space); // get more space
elem[sz] = d; // add d at end
++sz; // increase the size (sz is the number of elements)
}

In other words, if we have no spare space, we double the size of the allocation. In practice that turns out to be a very good choice for the vast majority of uses of vector, and that’s the strategy used by most implementations of the standard library vector.

19.2.5 Assignment

We could have defined vector assignment in several different ways. For example, we could have decided that assignment was legal only if the two vectors involved had the same number of elements. However, in §18.3.2 we decided that vector assignment should have the most general and arguably the most obvious meaning: after assignment v1=v2, the vector v1 is a copy of v2. Consider:

Obviously, we need to copy the elements, but what about the spare space? Do we “copy” the “free space” at the end? We don’t: the new vector will get a copy of the elements, but since we have no idea how that new vector is going to be used, we don’t bother with extra space at the end:

The simplest implementation of that is:

• Allocate memory for a copy.

• Copy the elements.

• Delete the old allocation.

• Set the sz, elem, and space to the new values.

Like this:

vector& vector::operator=(const vector& a)
// like copy constructor, but we must deal with old elements
{
double* p = new double[a.sz]; // allocate new space
for (int i = 0; i<a.sz; ++i) p[i] = a.elem[i]; // copy elements
delete[] elem; // deallocate old space
space = sz = a.sz; // set new size
elem = p; // set new elements
return *this; // return self-reference
}

By convention, an assignment operator returns a reference to the object assigned to. The notation for that is *this, which is explained in §17.10.

This implementation is correct, but when we look at it a bit we realize that we do a lot of redundant allocation and deallocation. What if the vector we assign to has more elements than the one we assign? What if the vector we assign to has the same number of elements as the vector we assign? In many applications, that last case is very common. In either case, we can just copy the elements into space already available in the target vector:

vector& vector::operator=(const vector& a)
{
if (this==&a) return *this; // self-assignment, no work needed

if (a.sz<=space) { // enough space, no need for new allocation
for (int i = 0; i<a.sz; ++i) elem[i] = a.elem[i]; // copy elements
sz = a.sz;
return *this;
}

double* p = new double[a.sz]; // allocate new space
for (int i = 0; i<a.sz; ++i) p[i] = a.elem[i]; // copy elements
delete[] elem; // deallocate old space
space = sz = a.sz; // set new size
elem = p; // set new elements
return *this; // return a self-reference
}

Here, we first test for self-assignment (e.g., v=v); in that case, we just do nothing. That test is logically redundant but sometimes a significant optimization. It does, however, show a common use of the this pointer checking if the argument a is the same object as the object for which a member function (here, operator=()) was called. Please convince yourself that this code actually works if we remove the this==&a line. The a.sz<=space is also just an optimization. Please convince yourself that this code actually works if we remove the a.sz<=space case.

19.2.6 Our vector so far

Now we have an almost real vector of doubles:

// an almost real vector of doubles:
class vector {
/*
invariant:
if 0<=n<sz, elem[n] is element n
sz<=space;
if sz<space there is space for (space-sz) doubles after elem[sz-1]
*/
int sz; // the size
double* elem; // pointer to the elements (or 0)
int space; // number of elements plus number of free slots
public:
vector() : sz{0}, elem{nullptr}, space{0} { }
explicit vector(int s) :sz{s}, elem{new double[s]}, space{s}
{
for (int i=0; i<sz; ++i) elem[i]=0; // elements are initialized
}

vector(const vector&); // copy constructor
vector& operator=(const vector&); // copy assignment

vector(vector&&); // move constructor
vector& operator=(vector&&); // move assignment

~vector() { delete[] elem; } // destructor

double& operator[ ](int n) { return elem[n]; } // access: return reference
const double& operator[](int n) const { return elem[n]; }

int size() const { return sz; }
int capacity() const { return space; }

void resize(int newsize); // growth
void push_back(double d);
void reserve(int newalloc);
};

Note how it has the essential operations (§18.4): constructor, default constructor, copy operations, destructor. It has an operation for accessing data (subscripting: [ ]) and for providing information about that data (size() and capacity()) and for controlling growth (resize(), push_back(), andreserve()).

19.3 Templates

But we don’t just want vectors of doubles; we want to freely specify the element type for our vectors. For example:

vector<double>
vector<int>
vector<Month>
vector<Window*> // vector of pointers to Windows
vector<vector<Record>> // vector of vectors of Records
vector<char>

To do that, we must see how to define templates. We have used templates from day one, but until now we haven’t had a need to define one. The standard library provides what we have needed so far, but we mustn’t believe in magic, so we need to examine how the designers and implementers of the standard library provided facilities such as the vector type and the sort() function (§21.1, §B.5.4). This is not just of theoretical interest, because — as usual — the tools and techniques used for the standard library are among the most useful for our own code. For example, in Chapters 21 and 22, we show how templates can be used for implementing the standard library containers and algorithms. In Chapter 24, we show how to design matrices for scientific computation.

Basically, a template is a mechanism that allows a programmer to use types as parameters for a class or a function. The compiler then generates a specific class or function when we later provide specific types as arguments.

19.3.1 Types as template parameters

We want to make the element type a parameter to vector. So we take our vector and replace double with T where T is a parameter that can be given “values” such as double, int, string, vector<Record>, and Window*. The C++ notation for introducing a type parameter T is thetemplate<typename T> prefix, meaning “for all types T.” For example:

// an almost real vector of Ts:
template<typename T>
class vector { // read “for all types T” (just like in math)
int sz; // the size
T* elem; // a pointer to the elements
int space; // size + free space
public:
vector() : sz{0}, elem{nullptr}, space{0} { }
explicit vector(int s) :sz{s}, elem{new T[s]}, space{s}
{
for (int i=0; i<sz; ++i) elem[i]=0; // elements are initialized
}

vector(const vector&); // copy constructor
vector& operator=(const vector&); // copy assignment

vector(vector&&); // move constructor
vector& operator=(vector&&); // move assignment

~vector() { delete[] elem; } // destructor

T& operator[](int n) { return elem[n]; } // access: return reference
const T& operator[](int n) const { return elem[n]; }

int size() const { return sz; } // the current size
int capacity() const { return space; }

void resize(int newsize); // growth
void push_back(const T& d);
void reserve(int newalloc);
};

That’s just our vector of doubles from §19.2.6 with double replaced by the template parameter T. We can use this class template vector like this:

vector<double> vd; // T is double
vector<int> vi; // T is int
vector<double*> vpd; // T is double*
vector<vector<int>> vvi; // T is vector<int>, in which T is int

One way of thinking about what a compiler does when we use a template is that it generates the class with the actual type (the template argument) in place of the template parameter. For example, when the compiler sees vector<char> in the code, it (somewhere) generates something like this:

class vector_char {
int sz; // the size
char* elem; // a pointer to the elements
int space; // size + free space
public:
vector() : sz{0}, elem{nullptr}, space{0} { }
explicit vector_char(int s) :sz{s}, elem{new char[s]}, space{s}
{
for (int i=0; i<sz; ++i) elem[i]=0; // elements are initialized
}

vector_char(const vector_char&); // copy constructor
vector_char& operator=(const vector_char&); // copy assignment

vector_char(vector_char&&); // move constructor
vector_char& operator=(vector_char&&); // move assignment

~vector_char (); // destructor

char& operator[] (int n) ) { return elem[n]; // access: return reference
const char& operator[] (int n) const ) { return elem[n]; }

int size() const; // the current size
int capacity() const;

void resize(int newsize); // growth
void push_back(const char& d);
void reserve(int newalloc);
};

For vector<double>, the compiler generates roughly the vector (of double) from §19.2.6 (using a suitable internal name meaning vector<double>).

Sometimes, we call a class template a type generator. The process of generating types (classes) from a class template given template arguments is called specialization or template instantiation. For example, vector<char> and vector<Poly_line*> are said to be specializations of vector. In simple cases, such as our vector, instantiation is a pretty simple process. In the most general and advanced cases, template instantiation is horrendously complicated. Fortunately for the user of templates, that complexity is in the domain of the compiler writer, not the template user. Template instantiation (generation of template specializations) takes place at compile time or link time, not at run time.

Naturally, we can use member functions of such a class template. For example:

void fct(vector<string>& v)
{
int n = v.size();
v.push_back("Norah");
// . . .
}

When such a member function of a class template is used, the compiler generates the appropriate function. For example, when the compiler sees v.push_back("Norah"), it generates a function

void vector<string>::push_back(const string& d) { /* . . . */ }

from the template definition

template<typename T> void vector<T>::push_back(const T& d) { /* . . . */ };

That way, there is a function for v.push_back("Norah") to call. In other words, when you need a function for given object and argument types, the compiler will write it for you based on its template.

Instead of writing template<typename T>, you can write template<class T>. The two constructs mean exactly the same thing, but some prefer typename “because it is clearer” and “because nobody gets confused by typename thinking that you can’t use a built-in type, such as int, as a template argument.” We are of the opinion that class already means type, so it makes no difference. Also, class is shorter.

19.3.2 Generic programming

Templates are the basis for generic programming in C++. In fact, the simplest definition of “generic programming” in C++ is “using templates.” That definition is a bit too simpleminded, though. We should not define fundamental programming concepts in terms of programming language features. Programming language features exist to support programming techniques — not the other way around. As with most popular notions, there are many definitions of “generic programming.” We think that the most useful simple definition is

Generic programming: Writing code that works with a variety of types presented as arguments, as long as those argument types meet specific syntactic and semantic requirements.

For example, the elements of a vector must be of a type that we can copy (by copy construction and copy assignment), and in Chapters 20 and 21 we will see templates that require arithmetic operations on their arguments. When what we parameterize is a class, we get a class template, what is often called a parameterized type or a parameterized class. When what we parameterize is a function, we get a function template, what is often called a parameterized function and sometimes also called an algorithm. Thus, generic programming is sometimes referred to as “algorithm-oriented programming”; the focus of the design is more the algorithms than the data types they use.

Since the notion of parameterized types is so central to programming, let’s explore the somewhat bewildering terminology a bit further. That way we have a chance of not getting too confused when we meet such notions in other contexts.

This form of generic programming relying on explicit template parameters is often called parametric polymorphism. In contrast, the polymorphism you get from using class hierarchies and virtual functions is called ad hoc polymorphism and that style of programming is called object-oriented programming (§14.3-4). The reason that both styles of programming are called polymorphism is that each style relies on the programmer to present many versions of a concept by a single interface. Polymorphism is Greek for “many shapes,” referring to the many different types you can manipulate through a common interface. In the Shape examples from Chapters 16-19 we literally accessed many shapes (such as Text, Circle, and Polygon) through the interface defined by Shape. When we use vectors, we use many vectors (such as vector<int>, vector<double>, andvector<Shape*>) through the interface defined by the vector template.

There are several differences between object-oriented programming (using class hierarchies and virtual functions) and generic programming (using templates). The most obvious is that the choice of function invoked when you use generic programming is determined by the compiler at compile time, whereas for object-oriented programming, it is not determined until run time. For example:

v.push_back(x); // put x into the vector v
s.draw(); // draw the shape s

For v.push_back(x) the compiler will determine the element type for v and use the appropriate push_back(), but for s.draw() the compiler will indirectly call some draw() function (using s’s vtbl; see §14.3.1). This gives object-oriented programming a degree of freedom that generic programming lacks, but leaves run-of-the-mill generic programming more regular, easier to understand, and better performing (hence the “ad hoc” and “parametric” labels).

To sum up:

• Generic programming: supported by templates, relying on compile-time resolution

• Object-oriented programming: supported by class hierarchies and virtual functions, relying on run-time resolution

Combinations of the two are possible and useful. For example:

void draw_all(vector<Shape*>& v)
{
for (int I = 0; i<v.size(); ++i) v[i]->draw();
}

Here we call a virtual function (draw()) on a base class (Shape) using a virtual function — that’s certainly object-oriented programming. However, we also kept Shape*s in a vector, which is a parameterized type, so we also used (simple) generic programming.

So — assuming you have had your fill of philosophy for now — what do people actually use templates for? For unsurpassed flexibility and performance:

• Use templates where performance is essential (e.g., numerics and hard real time; see Chapters 24 and 25).

• Use templates where flexibility in combining information from several types is essential (e.g., the C++ standard library; see Chapters 20-21).

19.3.3 Concepts

Templates have many useful properties, such as great flexibility and near-optimal performance, but unfortunately they are not perfect. As usual, the benefits have corresponding weaknesses. For templates, the main problem is that the flexibility and performance come at the cost of poor separation between the “inside” of a template (its definition) and its interface (its declaration). This manifests itself in poor error diagnostics — often spectacularly poor error messages. Sometimes, these error messages come much later in the compilation process than we would prefer.

When compiling a use of a template, the compiler “looks into” the template and also into the template arguments. It does so to get the information to generate optimal code. To have all that information available, current compilers tend to require that a template must be fully defined wherever it is used. That includes all of its member functions and all template functions called from those. Consequently, template writers tend to place template definitions in header files. This is not actually required by the standard, but until radically improved implementations are widely available, we recommend that you do so for your own templates: place the definition of any template that is to be used in more than one translation unit in a header file.

Initially, write only very simple templates yourself and proceed carefully to gain experience. One useful development technique is to do as we did for vector: First develop and test a class using specific types. Once that works, replace the specific types with template parameters and test with a variety of template arguments. Use template-based libraries, such as the C++ standard library, for generality, type safety, and performance. Chapters 20 and 21 are devoted to the containers and algorithms of the standard library and will give you examples of the use of templates.

C++14 provides a mechanism for vastly improved checking of template interfaces. For example, in C++11 we write

template<typename T> // for all types T
class vector {
// . . .
};

We cannot precisely state what is expected of an argument type T. The standard says what these requirements are, but only in English, rather than in code that the compiler can understand. We call a set of requirements on a template argument a concept. A template argument must meet the requirements, the concepts, of the template to which it is applied. For example, a vector requires that its elements can be copied or moved, can have their address taken, and be default constructed (if needed). In other words, an element must meet a set of requirements, which we could callElement. In C++14, we can make that explicit:

template<typename T> // for all types T
requires Element<T>() // such that T is an Element
class vector {
// . . .
};

This shows that a concept is really a type predicate, that is, a compile-time-evaluated (constexpr) function that returns true if the type argument (here, T) has the properties required by the concept (here, Element) and false if it does not. This is a bit long-winded, but a shorthand notation brings us to

template<Element T> // for all types T, such that Element<T>() is true
class vector {
// . . .
};

If we don’t have a C++14 compiler that supports concepts, we can specify our requirements in names and in comments:

template<typename Elem> // requires Element<Elem>()
class vector {
// . . .
};

The compiler doesn’t understand our names or read our comments, but being explicit about concepts helps us think about our code, improves our design of generic code, and helps other programmers understand our code. As we go along, we will use some common and useful concepts:

• Element<E>(): E can be an element in a container.

• Container<C>(): C can hold Elements and be accessed as a [begin():end()) sequence.

• Forward_iterator<For>(): For can be used to traverse a sequence [b:e) (like a linked list, a vector, or an array).

• Input_iterator<In>(): In can be used to read a sequence [b:e) once only (like an input stream).

• Output_iterator<Out>(): A sequence can be output using Out.

• Random_access_iterator<Ran>(): Ran can be used to read and write a sequence [b:e) repeatedly and supports subscripting using [ ].

• Allocator<A>(): A can be used to acquire and release memory (like the free store).

• Equal_comparable<T>(): We can compare two Ts for equality using == to get a Boolean result.

• Equal_comparable<T,U>(): We can compare a T to a U for equality using == to get a Boolean result.

• Predicate<P,T>(): We can call P with an argument of type T to get a Boolean result.

• Binary_predicate<P,T>(): We can call P with two arguments of type T to get a Boolean result.

• Binary_predicate<P,T,U>(): We can call P with arguments of types T and U to get a Boolean result.

• Less_comparable<L,T>(): We can use L to compare two Ts for less than using < to get a Boolean result.

• Less_comparable<L,T,U>(): We can use L to compare a T to a U for less than using < to get a Boolean result.

• Binary_operation<B,T,U>(): We can use B to do an operation on two Ts.

• Binary_operation<B,T,U>(): We can use B to do an operation on a T and a U.

• Number<N>(): N behaves like a number, supporting +, -, *, and /.

For standard library containers and algorithms, these concepts (and many more) are specified in excruciating detail. Here, especially in Chapters 20 and 21, we will use them informally to document our containers and algorithms.

A container type and an iterator type, T, have a value type (written as Value_type<T>), which is the element type. Often, that Value_type<T> is a member type T::value_type; see vector and list (§20.5).

19.3.4 Containers and inheritance

There is one kind of combination of object-oriented programming and generic programming that people always try, but it doesn’t work: attempting to use a container of objects of a derived class as a container of objects of a base class. For example:

vector<Shape> vs;
vector<Circle> vc;
vs = vc; // error: vector<Shape> required
void f(vector<Shape>&);
f(vc); // error: vector<Shape> required

But why not? After all, you say, I can convert a Circle to a Shape! Actually, no, you can’t. You can convert a Circle* to a Shape* and a Circle& to a Shape&, but we deliberately disabled assignment of Shapes, so that you wouldn’t have to wonder what would happen if you put a Circle with a radius into a Shape variable that doesn’t have a radius (§14.2.4). What would have happened — had we allowed it — would have been what is called “slicing” and is the class object equivalent of integer truncation (§3.9.2).

So we try again using pointers:

vector<Shape*> vps;
vector<Circle*> vpc;
vps = vpc; // error: vector<Shape*> required
void f(vector<Shape*>&);
f(vpc); // error: vector<Shape*> required

Again, the type system resists; why? Consider what f() might do:

void f(vector<Shape*>& v)
{
v.push_back(new Rectangle{Point{0,0},Point{100,100}});
}

Obviously, we can put a Rectangle* into a vector<Shape*>. However, if that vector<Shape*> was elsewhere considered to be a vector<Circle*>, someone would get a nasty surprise. In particular, had the compiler accepted the example above, what would a Rectangle* be doing in vpc? Inheritance is a powerful and subtle mechanism and templates do not implicitly extend its reach. There are ways of using templates to express inheritance, but they are beyond the scope of this book. Just remember that “D is a B” does not imply “C<D> is a C<B>” for an arbitrary template C— and we should value that as a protection against accidental type violations. See also §25.4.4.

19.3.5 Integers as template parameters

Obviously, it is useful to parameterize classes with types. How about parameterizing classes with “other things,” such as integer values and string values? Basically, any kind of argument can be useful, but we’ll consider only type and integer parameters. Other kinds of parameters are less frequently useful, and C++’s support for other kinds of parameters is such that their use requires quite detailed knowledge of language features.

Consider an example of the most common use of an integer value as a template argument, a container where the number of elements is known at compile time:

template<typename T, int N> struct array {
T elem[N]; // hold elements in member array

// rely on the default constructors, destructor, and assignment

T& operator[] (int n); // access: return reference
const T& operator[] (int n) const;

T* data() { return elem; } // conversion to T*
const T* data() const { return elem; }

int size() const { return N; }
};

We can use array (see also §20.7) like this:

array<int,256> gb; // 256 integers
array<double,6> ad = { 0.0, 1.1, 2.2, 3.3, 4.4, 5.5 };
const int max = 1024;

void some_fct(int n)
{
array<char,max> loc;
array<char,n> oops; // error: the value of n not known to compiler
// . . .
array<char,max> loc2 = loc; // make backup copy
// . . .
loc = loc2; // restore
// . . .
}

Clearly, array is very simple — much simpler and less powerful than vector — so why would anyone want to use an array rather than a vector? One answer is “efficiency.” We know the size of an array at compile time, so the compiler can allocate static memory (for global objects, such as gb) and stack memory (for local objects, such as loc) rather than using the free store. When we do range checking, the checks can be against constants (the size parameter N). For most programs the efficiency improvement is insignificant, but if you are writing a crucial system component, such as a network driver, even a small difference can matter. More importantly, some programs simply can’t be allowed to use the free store. Such programs are typically embedded systems programs and/or safety-critical programs (see Chapter 25). In such programs, array gives us many of the advantages of vector without violating a critical restriction (no free-store use).

Let’s ask the opposite question: not “Why can’t we just use vector?” but “Why not just use built-in arrays?” As we saw in §18.6, arrays can be rather ill behaved: they don’t know their own size, they convert to pointers at the slightest provocation, they don’t copy properly; like vector,array doesn’t have those problems. For example:

double* p = ad; // error: no implicit conversion to pointer
double* q = ad.data(); // OK: explicit conversion

template<typename C> void printout(const C& c) // function template
{
for (int i = 0; i<c.size(); ++i) cout << c[i] <<'\n';
}

This printout() can be called by an array as well as a vector:

printout(ad); // call with array
vector<int> vi;
// . . .
printout(vi); // call with vector

This is a simple example of generic programming applied to data access. It works because the interface used for array and vector (size() and subscripting) is the same. Chapters 20 and 21 will explore this style of programming in some detail.

19.3.6 Template argument deduction

For a class template, you specify the template arguments when you create an object of some specific class. For example:

array<char,1024> buf; // for buf, T is char and N is 1024
array<double,10> b2; // for b2, T is double and N is 10

For a function template, the compiler usually deduces the template arguments from the function arguments. For example:

template<class T, int N> void fill(array<T,N>& b, const T& val)
{
for (int i = 0; i<N; ++i) b[i] = val;
}

void f()
{
fill(buf,'x'); // for fill(), T is char and N is 1024
// because that’s what buf has
fill(b2,0.0); // for fill(), T is double and N is 10
// because that’s what b2 has
}

Technically, fill(buf,'x') is shorthand for fill<char,1024>(buf,'x'), and fill(b2,0) is shorthand for fill<double,10>(b2,0), but fortunately we don’t often have to be that specific. The compiler figures it out for us.

19.3.7 Generalizing vector

When we generalized vector from a class “vector of double” to a template “vector of T,” we didn’t review the definitions of push_back(), resize(), and reserve(). We must do that now because as they are defined in §19.2.2 and §19.2.3 they make assumptions that are true for doubles, but not true for all types that we’d like to use as vector element types:

• How do we handle a vector<X> where X doesn’t have a default value?

• How do we ensure that elements are destroyed when we are finished with them?

Must we solve those problems? We could say, “Don’t try to make vectors of types without default values” and “Don’t use vectors for types with destructors in ways that cause problems.” For a facility that is aimed at “general use,” such restrictions are annoying to users and give the impression that the designer hasn’t thought the problem through or doesn’t really care about users. Often, such suspicions are correct, but the designers of the standard library didn’t leave these warts in place. To mirror the standard library vector, we must solve these two problems.

We can handle types without a default by giving the user the option to specify the value to be used when we need a “default value”:

template<typename T> void vector<T>::resize(int newsize, T def = T());

That is, use T() as the default value unless the user says otherwise. For example:

vector<double> v1;
v1.resize(100); // add 100 copies of double(), that is, 0.0
v1.resize(200, 0.0); // add 100 copies of 0.0 — mentioning 0.0 is redundant
v1.resize(300, 1.0); // add 100 copies of 1.0

struct No_default {
No_default(int); // the only constructor for No_default
// . . .
};

vector<No_default> v2(10); // error: tries to make 10 No_default()s
vector<No_default> v3;
v3.resize(100, No_default(2)); // add 100 copies of No_default(2)
v3.resize(200); // error: tries to add 100 No_default()s

The destructor problem is harder to address. Basically, we need to deal with something really awkward: a data structure consisting of some initialized data and some uninitialized data. So far, we have gone a long way to avoid uninitialized data and the programming errors that usually accompany it. Now — as implementers of vector — we have to face that problem so that we — as users of vector — don’t have to in our applications.

First, we need to find a way of getting and manipulating uninitialized storage. Fortunately, the standard library provides a class allocator, which provides uninitialized memory. A slightly simplified version looks like this:

template<typename T> class allocator {
public:
// . . .
T* allocate(int n); // allocate space for n objects of type T
void deallocate(T* p, int n); // deallocate n objects of type T starting at p

void construct(T* p, const T& v); // construct a T with the value v in p
void destroy(T* p); // destroy the T in p
};

Should you need the full story, have a look in The C++ Programming Language, <memory> (§B.1.1), or the standard. However, what is presented here shows the four fundamental operations that allow us to

• Allocate memory of a size suitable to hold an object of type T without initializing

• Construct an object of type T in uninitialized space

• Destroy an object of type T, thus returning its space to the uninitialized state

• Deallocate uninitialized space of a size suitable for an object of type T

Unsurprisingly, an allocator is exactly what we need for implementing vector<T>::reserve(). We start by giving vector an allocator parameter:

template<typename T, typename A = allocator<T>> class vector {
A alloc; // use allocate to handle memory for elements
// . . .
};

Except for providing an allocator — and using the standard one by default instead of using new — all is as before. As users of vector, we can ignore allocators until we find ourselves needing a vector that manages memory for its elements in some unusual way. As implementers of vector and as students trying to understand fundamental problems and learn fundamental techniques, we must see how a vector can deal with uninitialized memory and present properly constructed objects to its users. The only code affected is vector member functions that directly deal with memory, such as vector<T>::reserve():

template<typename T, typename A>
void vector<T,A>::reserve(int newalloc)
{
if (newalloc<=space) return; // never decrease allocation
T* p = alloc.allocate(newalloc); // allocate new space
for (int i=0; i<sz; ++i) alloc.construct(&p[i],elem[i]); // copy
for (int i=0; i<sz; ++i) alloc.destroy(&elem[i]); // destroy
alloc.deallocate(elem,space); // deallocate old space
elem = p;
space = newalloc;
}

We move an element to the new space by constructing a copy in uninitialized space and then destroying the original. We can’t use assignment because for types such as string, assignment assumes that the target area has been initialized.

Given reserve(), vector<T,A>::push_back() is simple to write:

template<typename T, typename A>
void vector<T,A>::push_back(const T& val)
{
if (space==0) reserve(8); // start with space for 8 elements
else if (sz==space) reserve(2*space); // get more space
alloc.construct(&elem[sz],val); // add val at end
++sz; // increase the size
}

Similarly, vector<T,A>::resize() is not too difficult:

template<typename T, typename A>
void vector<T,A>::resize(int newsize, T val = T())
{
reserve(newsize);
for (int i=sz; i<newsize; ++i) alloc.construct(&elem[i],val); // construct
for (int i = newsize; i<sz; ++i) alloc.destroy(&elem[i]); // destroy
sz = newsize;
}

Note that because some types do not have a default constructor, we again provide the option to supply a value to be used as an initial value for new elements.

The other new thing here is the destruction of “surplus elements” in the case where we are resizing to a smaller vector. Think of the destructor as turning a typed object into “raw memory.”

“Messing with allocators” is pretty advanced stuff, and tricky. Leave it alone until you are ready to become an expert.

19.4 Range checking and exceptions

We look at our vector so far and find (with horror?) that access isn’t range checked. The implementation of operator[] is simply

template<typename T, typename A> T& vector<T,A>::operator[](int n)
{
return elem[n];
}

So, consider:

vector<int> v(100);
v[-200] = v[200]; // oops!
int i;
cin>>i;
v[i] = 999; // maul an arbitrary memory location

This code compiles and runs, accessing memory not owned by our vector. This could mean big trouble! In a real program, such code is unacceptable. Let’s try to improve our vector to deal with this problem. The simplest approach would be to add a checked access operation, called at():

struct out_of_range { /* . . . */ }; // class used to report range access errors

template<typename T, typename A = allocator<T>> class vector {
// . . .
T& at(int n); // checked access
const T& at(int n) const; // checked access

T& operator[](int n); // unchecked access
const T& operator[](int n) const; // unchecked access
// . . .
};

template<typename T, typename A > T& vector<T,A>::at(int n)
{
if (n<0 || sz<=n) throw out_of_range();
return elem[n];
}

template<typename T, typename A > T& vector<T,A>::operator[](int n)
// as before
{
return elem[n];
}

Given that, we could write

void print_some(vector<int>& v)
{
int i = -1;
while(cin>>i && i!=-1)
try {
cout << "v[" << i << "]==" << v.at(i) << "\n";
}
catch(out_of_range) {
cout << "bad index: " << i << "\n";
}
}

Here, we use at() to get range-checked access, and we catch out_of_range in case of an illegal access.

The general idea is to use subscripting with [ ] when we know that we have a valid index and at() when we might have an out-of-range index.

19.4.1 An aside: design considerations

So far, so good, but why didn’t we just add the range check to operator[]()? Well, the standard library vector provides checked at() and unchecked operator[]() as shown here. Let’s try to explain how that makes some sense. There are basically four arguments:

1. Compatibility: People have been using unchecked subscripting since long before C++ had exceptions.

2. Efficiency: You can build a checked-access operator on top of an optimally fast unchecked-access operator, but you cannot build an optimally fast access operator on top of a checked-access operator.

3. Constraints: In some environments, exceptions are unacceptable.

4. Optional checking: The standard doesn’t actually say that you can’t range check vector, so if you want checking, use an implementation that checks.

19.4.1.1 Compatibility

People really, really don’t like to have their old code break. For example, if you have a million lines of code, it could be a very costly affair to rework it all to use exceptions correctly. We can argue that the code would be better for the extra work, but then we are not the ones who have to pay (in time or money). Furthermore, maintainers of existing code usually argue that unchecked code may be unsafe in principle, but their particular code has been tested and used for years and all the bugs have already been found. We can be skeptical about that argument, but again nobody who hasn’t had to make such decisions about real code should be too judgmental. Naturally, there was no code using the standard library vector before it was introduced into the C++ standard, but there were many millions of lines of code that used very similar vectors that (being pre-standard) didn’t use exceptions. Much of that code was later modified to use the standard.

19.4.1.2 Efficiency

Yes, range checking can be a burden in extreme cases, such as buffers for network interfaces and matrices in high-performance scientific computations. However, the cost of range checking is rarely a concern in the kind of “ordinary computing” that most of us spend most of our time on. Thus, we recommend and use a range-checked implementation of vector whenever we can.

19.4.1.3 Constraints

Again, the argument holds for some programmers and some applications. In fact, it holds for a whole lot of programmers and shouldn’t be lightly ignored. However, if you are starting a new program in an environment that doesn’t involve hard real time (see §25.2.1), prefer exception-based error handling and range-checked vectors.

19.4.1.4 Optional checking

The ISO C++ standard simply states that out-of-range vector access is not guaranteed to have any specific semantics, and that such access should be avoided. It is perfectly standards-conforming to throw an exception when a program tries an out-of-range access. So, if you like vector to throw and don’t need to be concerned by the first three reasons for a particular application, use a range-checked implementation of vector. That’s what we are doing for this book.

The long and the short of this is that real-world design can be messier than we would prefer, but there are ways of coping.

19.4.2 A confession: macros

Like our vector, most implementations of the standard library vector don’t guarantee to range check the subscript operator ([ ]) but provide at() that checks. So where did those std::out_of_range exceptions in our programs come from? Basically, we chose “option 4” from §19.4.1: a vectorimplementation is not obliged to range check [ ], but it is not prohibited from doing so either, so we arranged for checking to be done. What you might have been using is our debug version, called Vector, which does check [ ]. That’s what we use when we develop code. It cuts down on errors and debug time at little cost to performance:

struct Range_error : out_of_range { // enhanced vector range error reporting
int index;
Range_error(int i) :out_of_range("Range error"), index(i) { }
};

template<typename T> struct Vector : public std::vector<T> {
using size_type = typename std::vector<T>::size_type;
using vector<T>::vector; // use vector<T>’s constructors (§20.5)

T& operator[](size_type i) // rather than return at(i);
{
if (i<0||this->size()<=i) throw Range_error(i);
return std::vector<T>::operator[](i);
}
const T& operator[](size_type i) const
{

if (i<0||this->size()<=i) throw Range_error(i);
return std::vector<T>::operator[](i);
}
};

We use Range_error to make the offending index available for debugging. Deriving from std::vector gives us all of vector’s member functions for Vector. The first using introduces a convenient synonym for std::vector’s size_type; see §20.5. The second using gives us all of vector’s constructors for Vector.

This Vector has been useful in debugging nontrivial programs. The alternative is to use a systematically checked implementation of the complete standard library vector — in fact, that may indeed be what you have been using; we have no way of knowing exactly what degree of checking your compiler and library provide (beyond what the standard guarantees).

In std_lib_facilities.h, we use the nasty trick (a macro substitution) of redefining vector to mean Vector:

// disgusting macro hack to get a range-checked vector:
#define vector Vector

That means that whenever you wrote vector, the compiler saw Vector. This trick is nasty because what you see looking at the code is not what the compiler sees. In real-world code, macros are a significant source of obscure errors (§27.8, §A.17.2).

We did the same to provide range-checked access for string.

Unfortunately, there is no standard, portable, and clean way of getting range checking from an implementation of vector’s [ ]. It is, however, possible to do a much cleaner and more complete job of a range-checked vector (and string) than we did. However, that usually involves replacement of a vendor’s standard library implementation, adjusting installation options, or messing with standard library source code. None of those options is appropriate for a beginner’s first week of programming — and we used string in Chapter 2.

19.5 Resources and exceptions

So, vector can throw exceptions, and we recommend that when a function cannot perform its required action, it throws an exception to tell that to its callers (Chapter 5). Now is the time to consider what to do when we write code that must deal with exceptions thrown by vector operations and other functions that we call. The naive answer — “Use a try-block to catch the exception, write an error message, and then terminate the program” — is too crude for most nontrivial systems.

One of the fundamental principles of programming is that if we acquire a resource, we must — somehow, directly or indirectly — return it to whatever part of the system manages that resource. Examples of resources are

• Memory

• Locks

• File handles

• Thread handles

• Sockets

• Windows

Basically, we define a resource as something that is acquired and must be given back (released) or reclaimed by some “resource manager.” The simplest example is free-store memory that we acquire using new and return to the free store using delete. For example:

void suspicious(int s, int x)
{
int* p = new int[s]; // acquire memory
// . . .
delete[] p; // release memory
}

As we saw in §17.4.6, we have to remember to release the memory, and that’s not always easy to do. When we add exceptions to the picture, resource leaks can become common; all it takes is ignorance or some lack of care. In particular, we view code, such as suspicious(), that explicitly usesnew and assigns the resulting pointer to a local variable with great suspicion.

We call an object, such as a vector, that is responsible for releasing a resource the owner or a handle of the resource for which it is responsible.

19.5.1 Potential resource management problems

One reason for suspicion of apparently innocuous pointer assignments such as

int* p = new int[s]; // acquire memory

is that it can be hard to verify that the new has a corresponding delete. At least suspicious() has a delete[] p; statement that might release the memory, but let’s imagine a few things that might cause that release not to happen. What could we put in the . . . part to cause a memory leak? The problematic examples we find should give you cause for thought and make you suspicious of such code. They should also make you appreciate the simple and powerful alternative to such code.

Maybe p no longer points to the object when we get to the delete:

void suspicious(int s, int x)
{
int* p = new int[s]; // acquire memory
// . . .
if (x) p = q; // make p point to another object
// . . .
delete[] p; // release memory
}

We put that if (x) there to be sure that you couldn’t know whether we had changed the value of p. Maybe we never get to the delete:

void suspicious(int s, int x)
{
int* p = new int[s]; // acquire memory
// . . .
if (x) return;
// . . .
delete[] p; // release memory
}

Maybe we never get to the delete because we threw an exception:

void suspicious(int s, int x)
{
int* p = new int[s]; // acquire memory
vector<int> v;
// . . .
if (x) p[x] = v.at(x);
// . . .
delete[] p; // release memory
}

It is this last possibility that concerns us most here. When people first encounter this problem, they tend to consider it a problem with exceptions rather than a resource management problem. Having misclassified the root cause, they come up with a solution that involves catching the exception:

void suspicious(int s, int x) // messy code
{
int* p = new int[s]; // acquire memory
vector<int> v;
// . . .
try {
if (x) p[x] = v.at(x);
// . . .
} catch (. . .) { // catch every exception
delete[] p; // release memory
throw; // re-throw the exception
}
// . . .
delete[] p; // release memory
}

This solves the problem at the cost of some added code and a duplication of the resource release code (here, delete[] p;). In other words, this solution is ugly; worse, it doesn’t generalize well. Consider acquiring more resources:

void suspicious(vector<int>& v, int s)
{
int* p = new int[s];
vector<int>v1;
// . . .
int* q = new int[s];
vector<double> v2;
// . . .
delete[] p;
delete[] q;
}

Note that if new fails to find free-store memory to allocate, it will throw the standard library exception bad_alloc. The try . . . catch technique works for this example also, but you’ll need several try-blocks, and the code is repetitive and ugly. We don’t like repetitive and ugly code because “repetitive” translates into code that is a maintenance hazard, and “ugly” translates into code that is hard to get right, hard to read, and a maintenance hazard.