#include <iterator>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vi(10, 0);
ostream_iterator<int> out(cout, " ");
vector<int>::iterator i = vi.begin();
*i = 47;
copy(vi.begin(), vi.end(), out);
cout << endl;
// Force it to move memory (could also just add
// enough objects):
vi.resize(vi.capacity() + 1);
// Now i points to wrong memory:
*i = 48; // Access violation
copy(vi.begin(), vi.end(), out); // No change to vi[0]
} ///:~
This illustrates the concept of iterator invalidation. Certain operations cause internal changes to a container’s underlying data, so any iterators in effect before such changes may no longer be valid afterward. If your program is breaking mysteriously, look for places where you hold onto an iterator while adding more objects to a vector. You’ll need to get a new iterator after adding elements or use operator[ ] instead for element selections. If you combine this observation with the awareness of the potential expense for adding new objects to a vector, you may conclude that the safest way to use one is to fill it up all at once (ideally, knowing first how many objects you’ll need) and then just use it (without adding more objects) elsewhere in the program. This is the way vector has been used in the book up to this point. The standard C++ library documents which container operations invalidate iterators.
You may observe that using vector as the "basic" container in the earlier chapters of this book might not be the best choice in all cases. This is a fundamental issue in containers and in data structures in generaclass="underline" the "best" choice varies according to the way the container is used. The reason vector has been the "best" choice up until now is that it looks a lot like an array and was thus familiar and easy for you to adopt. But from now on it’s also worth thinking about other issues when choosing containers.
Inserting and erasing elements
The vector is most efficient if:
5.You reserve( ) the correct amount of storage at the beginning so the vector never has to reallocate.
6.You only add and remove elements from the back end.
It is possible to insert and erase elements from the middle of a vector using an iterator, but the following program demonstrates what a bad idea this is:
//: C07:VectorInsertAndErase.cpp
// Erasing an element from a vector
//{-bor}
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include "Noisy.h"
using namespace std;
int main() {
vector<Noisy> v;
v.reserve(11);
cout << "11 spaces have been reserved" << endl;
generate_n(back_inserter(v), 10, NoisyGen());
ostream_iterator<Noisy> out(cout, " ");
cout << endl;
copy(v.begin(), v.end(), out);
cout << "Inserting an element:" << endl;
vector<Noisy>::iterator it =
v.begin() + v.size() / 2; // Middle
v.insert(it, Noisy());
cout << endl;
copy(v.begin(), v.end(), out);
cout << "\nErasing an element:" << endl;
// Cannot use the previous value of it:
it = v.begin() + v.size() / 2;
v.erase(it);
cout << endl;
copy(v.begin(), v.end(), out);
cout << endl;
} ///:~
When you run the program, you’ll see that the call to reserve( ) really does only allocate storage—no constructors are called. The generate_n( ) call is busy: each call to NoisyGen::operator( ) results in a construction, a copy-construction (into the vector), and a destruction of the temporary. But when an object is inserted into the vector in the middle, it must shove everything down to maintain the linear array, and, since there is enough space, it does this with the assignment operator. (If the argument of reserve( ) is 10 instead of 11, it would have to reallocate storage.) When an object is erased from the vector, the assignment operator is once again used to move everything up to cover the place that is being erased. (Notice that this requires that the assignment operator properly clean up the lvalue.) Last, the object on the end of the array is deleted.
deque
The deque container is a basic sequence optimized for adding and removing elements from either end. It also allows for reasonably fast random access—it has an operator[ ] like vector. However, it does not have vector’s constraint of keeping everything in a single sequential block of memory. Instead, a typical implementation of deque uses multiple blocks of sequential storage (keeping track of all the blocks and their order in a mapping structure). For this reason, the overhead for a deque to add or remove elements at either end is low. In addition, it never needs to copy and destroy contained objects during a new storage allocation (like vector does), so it is far more efficient than vector if you are adding an unknown quantity of objects at either end. This means that vector is the best choice only if you have a good idea of how many objects you need. In addition, many of the programs shown earlier in this book that use vector and push_back( ) might be more efficient with a deque. The interface to deque is only slightly different from a vector (deque has a push_front( ) and pop_front( ) while vector does not, for example), so converting code from using vector to using deque is almost trivial. Consider StringVector.cpp, which can be changed to use deque by replacing the word "vector" with "deque" everywhere. The following program adds parallel deque operations to the vector operations in StringVector.cpp and performs timing comparisons:
//: C07:StringDeque.cpp
// Converted from StringVector.cpp
#include <cstddef>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
#include "../require.h"
using namespace std;
int main(int argc, char* argv[]) {
char* fname = "StringDeque.cpp";
if(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
vector<string> vstrings;