Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
B.Eckel - Thinking in C++, Vol.2, 2nd edition.pdf
Скачиваний:
50
Добавлен:
08.05.2013
Размер:
2.09 Mб
Скачать

The basicOps( ) function tests everything else (and in turn calls print( )), including a variety of constructors: default, copy-constructor, quantity and initial value, and beginning and ending iterators. There’s an assignment operator= and two kinds of assign( ) member functions, one which takes a quantity and initial value and the other which take a beginning and ending iterator.

All the basic sequence containers are reversible containers, as shown by the use of the rbegin( ) and rend( ) member functions. A sequence container can be resized, and the entire contents of the container can be removed with clear( ).

Using an iterator to indicate where you want to start inserting into any sequence container, you can insert( ) a single element, a number of elements that all have the same value, and a group of elements from another container using the beginning and ending iterators of that group.

To erase( ) a single element from the middle, use an iterator; to erase( ) a range of elements, use a pair of iterators. Notice that since a list only supports bidirectional iterators, all the iterator motion must be performed with increments and decrements (if the containers were limited to vector and deque, which produce random-access iterators, then operator+ and operator- could have been used to move the iterators in big jumps).

Although both list and deque support push_front( ) and pop_front( only member functions that work with all three are push_back( ) and

), vector does not, so the pop_back( ).

The naming of the member function swap( ) is a little confusing, since there’s also a nonmember swap( ) algorithm that switches two elements of a container. The member swap( ), however, swaps everything in one container for another (if the containers hold the same type), effectively swapping the containers themselves. There’s also a non-member version of this function.

The following sections on the sequence containers discuss the particulars of each type of container.

vector

The vector is intentionally made to look like a souped-up array, since it has array-style indexing but also can expand dynamically. vector is so fundamentally useful that it was introduced in a very primitive way early in this book, and used quite regularly in previous examples. This section will give a more in-depth look at vector.

To achieve maximally-fast indexing and iteration, the vector maintains its storage as a single contiguous array of objects. This is a critical point to observe in understanding the behavior of vector. It means that indexing and iteration are lighting-fast, being basically the same as indexing and iterating over an array of objects. But it also means that inserting an object anywhere but at the end (that is, appending) is not really an acceptable operation for a vector. It also means that when a vector runs out of pre-allocated storage, in order to maintain its

Chapter 15: Multiple Inheritance

172

contiguous array it must allocate a whole new (larger) chunk of storage elsewhere and copy the objects to the new storage. This has a number of unpleasant side effects.

Cost of overflowing allocated storage

A vector starts by grabbing a block of storage, as if it’s taking a guess at how many objects you plan to put in it. As long as you don’t try to put in more objects than can be held in the initial block of storage, everything is very rapid and efficient (note that if you do know how many objects to expect, you can pre-allocate storage using reserve( )). But eventually you will put in one too many objects and, unbeknownst to you, the vector responds by:

1.Allocating a new, bigger piece of storage

2.Copying all the objects from the old storage to the new (using the copy-constructor)

3.Destroying all the old objects (the destructor is called for each one)

4.Releasing the old memory

For complex objects, this copy-construction and destruction can end up being very expensive if you overfill your vector a lot. To see what happens when you’re filling a vector, here is a class that prints out information about its creations, destructions, assignments and copyconstructions:

//: C04:Noisy.h

// A class to track various object activities #ifndef NOISY_H

#define NOISY_H #include <iostream>

class Noisy {

static long create, assign, copycons, destroy; long id;

public:

Noisy() : id(create++) { std::cout << "d[" << id << "]";

}

Noisy(const Noisy& rv) : id(rv.id) { std::cout << "c[" << id << "]"; copycons++;

}

Noisy& operator=(const Noisy& rv) { std::cout << "(" << id << ")=[" <<

rv.id << "]"; id = rv.id; assign++;

Chapter 15: Multiple Inheritance

173

return *this;

}

friend bool

operator<(const Noisy& lv, const Noisy& rv) { return lv.id < rv.id;

}

friend bool

operator==(const Noisy& lv, const Noisy& rv) { return lv.id == rv.id;

}

~Noisy() {

std::cout << "~[" << id << "]"; destroy++;

}

friend std::ostream&

operator<<(std::ostream& os, const Noisy& n) { return os << n.id;

}

friend class NoisyReport;

};

struct NoisyGen {

Noisy operator()() { return Noisy(); }

};

//A singleton. Will automatically report the

//statistics as the program terminates: class NoisyReport {

static NoisyReport nr;

NoisyReport() {} // Private constructor public:

~NoisyReport() {

std::cout << "\n-------------------\n"

<<"Noisy creations: " << Noisy::create

<<"\nCopy-Constructions: "

<<Noisy::copycons

<<"\nAssignments: " << Noisy::assign

<<"\nDestructions: " << Noisy::destroy

<<std::endl;

}

};

// Because of these this file can only be used

Chapter 15: Multiple Inheritance

174

//in simple test situations. Move them to a

//.cpp file for more complex programs:

long Noisy::create = 0, Noisy::assign = 0, Noisy::copycons = 0, Noisy::destroy = 0;

NoisyReport NoisyReport::nr; #endif // NOISY_H ///:~

Each Noisy object has its own identifier, and there are static variables to keep track of all the creations, assignments (using operator=), copy-constructions and destructions. The id is initialized using the create counter inside the default constructor; the copy-constructor and assignment operator take their id values from the rvalue. Of course, with operator= the lvalue is already an initialized object so the old value of id is printed before it is overwritten with the id from the rvalue.

In order to support certain operations like sorting and searching (which are used implicitly by some of the containers), Noisy must have an operator< and operator==. These simply compare the id values. The operator<< for ostream follows the standard form and simply prints the id.

NoisyGen produces a function object (since it has an operator( )) that is used to automatically generate Noisy objects during testing.

NoisyReport is a type of class called a singleton, which is a “design pattern” (these are covered more fully in Chapter XX). Here, the goal is to make sure there is one and only one NoisyReport object, because it is responsible for printing out the results at program termination. It has a private constructor so no one else can make a NoisyReport object, and a single static instance of NoisyReport called nr. The only executable statements are in the destructor, which is called as the program exits and the static destructors are called; this destructor prints out the statistics captured by the static variables in Noisy.

The one snag to this header file is the inclusion of the definitions for the statics at the end. If you include this header in more than one place in your project, you’ll get multiple-definition errors at link time. Of course, you can put the static definitions in a separate cpp file and link it in, but that is less convenient, and since Noisy is just intended for quick-and-dirty experiments the header file should be reasonable for most situations.

Using Noisy.h, the following program will show the behaviors that occur when a vector overflows its currently allocated storage:

//: C04:VectorOverflow.cpp

//Shows the copy-construction and destruction

//That occurs when a vector must reallocate

//(It maintains a linear array of elements) #include "Noisy.h"

#include "../require.h" #include <vector> #include <iostream>

Chapter 15: Multiple Inheritance

175

#include <string> #include <cstdlib> using namespace std;

int main(int argc, char* argv[]) { requireArgs(argc, 1);

int size = 1000;

if(argc >= 2) size = atoi(argv[1]); vector<Noisy> vn;

Noisy n;

for(int i = 0; i < size; i++) vn.push_back(n);

cout << "\n cleaning up \n"; } ///:~

You can either use the default value of 1000, or use your own value by putting it on the command-line.

When you run this program, you’ll see a single default constructor call (for n), then a lot of copy-constructor calls, then some destructor calls, then some more copy-constructor calls, and so on. When the vector runs out of space in the linear array of bytes it has allocated, it must (to maintain all the objects in a linear array, which is an essential part of its job) get a bigger piece of storage and move everything over, copying first and then destroying the old objects. You can imagine that if you store a lot of large and complex objects, this process could rapidly become prohibitive.

There are two solutions to this problem. The nicest one requires that you know beforehand how many objects you’re going to make. In that case you can use reserve( ) to tell the vector how much storage to pre-allocate, thus eliminating all the copies and destructions and making everything very fast (especially random access to the objects with operator[ ]). Note that the use of reserve( ) is different from using the vector constructor with an integral first argument; the latter initializes each element using the default copy-constructor.

However, in the more general case you won’t know how many objects you’ll need. If vector reallocations are slowing things down, you can change sequence containers. You could use a list, but as you’ll see, the deque allows speedy insertions at either end of the sequence, and never needs to copy or destroy objects as it expands its storage. The deque also allows random access with operator[ ], but it’s not quite as fast as vector’s operator[ ]. So in the case where you’re creating all your objects in one part of the program and randomly accessing them in another, you may find yourself filling a deque, then creating a vector from the deque and using the vector for rapid indexing. Of course, you don’t want to program this way habitually, just be aware of these issues (avoid premature optimization).

There is a darker side to vector’s reallocation of memory, however. Because vector keeps its objects in a nice, neat array (allowing, for one thing, maximally-fast random access), the iterators used by vector are generally just pointers. This is a good thing – of all the sequence containers, these pointers allow the fastest selection and manipulation. However, consider

Chapter 15: Multiple Inheritance

176

Соседние файлы в предмете Численные методы
  • #
    08.05.20133.99 Mб22A.Menezes, P.van Oorschot,S.Vanstone - HANDBOOK OF APPLIED CRYPTOGRAPHY.djvu
  • #
  • #
    08.05.20135.91 Mб24B.Eckel - Thinking in Java, 3rd edition (beta).pdf
  • #
  • #
    08.05.20136.09 Mб17D.MacKay - Information Theory, Inference, and Learning Algorithms.djvu
  • #
    08.05.20133.85 Mб15DIGITAL Visual Fortran ver.5.0 - Programmers Guide to Fortran.djvu
  • #
    08.05.20131.84 Mб12E.A.Lee, P.Varaiya - Structure and Interpretation of Signals and Systems.djvu