向量vector
1.vector概述
vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变；vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。
vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector旧有空间满载，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓扩充空间（不论多大），一如稍早说，是“配置新空间 / 数据移动 / 释还旧空间”的大工程，时间成本很高，应该加入某种未雨绸缪的考虑。稍后我们便可以看到SGI vector的空间配置策略。
2.定义：
以下是vetor定义的源代码摘录。虽然STL规定，欲使用vector必须先包括<vector>，但SGI STL将vector实现吾更底层的<stl_vector.h>
// alloc是SGI STL的空间配置器
template <class T, class Alloc = alloc>
class vector {
public:
// vector 的嵌套类型定义
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
// 以下，simple_alloc 是SGI STL 的空间配置器
typedef simple_alloc<value_type, Alloc> data_allocator;
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
void insert_aux(iterator position, const T& x);
void deallocate() {
if (start)
data_allocator::deallocate(start, end_of_storage - start);
}
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_type size() const { return size_type(end() - begin()); }
size_type capacity() const {
return size_type(end_of_storage - begin());
}
bool empty() const { return begin() == end(); }
reference operator[](size_type n) { return *(begin() + n); }
vector() : start(0), finish(0), end_of_storage(0) {}
vector(size_type n, const T& value) { fill_initialize(n, value); }
vector(int n, const T& value) { fill_initialize(n, value); }
vector(long n, const T& value) { fill_initialize(n, value); }
explicit vector(size_type n) { fill_initialize(n, T()); }
~vector()
destroy(start, finish); // 全局函数
deallocate(); // 这是 vector 的一个 member function
}
reference front() { return *begin(); } // 第一个元素
reference back() { return *(end() - 1); } // 最后一个元素
void push_back(const T& x) { // 将元素插入到尾端
if (finish != end_of_storage) {
construct(finish, x); // 全局函数
++finish;
}
else
insert_aux(end(), x); // 这是 vector 的一个 member function
}
void pop_back() { // 将最尾端元素取出
--finish;
destroy(finish); // 全局函数
}
iterator erase(iterator position) { // 清除某位置上的元素
if (position + 1 != end())
copy(position + 1, finish, position); // 后续元素往前移动
--finish;
destroy(finish); // 全局函数
return position;
}
void resize(size_type new_size, const T& x) {
if (new_size < size())
erase(begin() + new_size, end());
else
insert(end(), new_size - size(), x);
}
void resize(size_type new_size) { resize(new_size, T()); }
void clear() { erase(begin(), end()); }
protected:
// 配置空间并填满内容
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n);
uninitialized_fill_n(result, n, x); // 全局函数
return result;
}
3.vector的迭代器
vector维护的是一个连续线性空间，所以不论其元素类型为何，普通指针都可以作为vector的迭代器而满足所有必要条件，因为vector迭代器所需要的操作行为，如operator*,operator->operator++,operator--,operator+,operator-,operator+=,operator-=，普通指针天生就具备。vector支持随机存取，而普通指针正有着这样的能力。所以，vector提供的是Random Access Itrerators。
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator; // vector 的迭代器是普通指针
...
};
根据上术定义，如果客户端写出这样的代码：
vector<int>::iterator ivite; vector<Shape>::iterator svite;
ivite的类型其实就是int*，svite的类别其实就是Shape*。
4.vector的数据结构
vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端：
template <class T, class Alloc = alloc>
class vector {
...
protected:
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
...
};
运用start,finish,end_of_storage三个迭代器，便可轻易地提供首尾标示、大小、容量、空容器判断、注标([ ])运算子、最前端元素值、最后端元素值...等机能；
template <class T, class Alloc = alloc>
class vector {
...
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_type size() const { return size_type(end() - begin()); }
size_type capacity() const {
return size_type(end_of_storage - begin());
}
bool empty() const { return begin() == end(); }
reference operator[](size_type n) { return *(begin() + n); }
reference front() { return *begin(); }
reference back() { return *(end() - 1); }
...
};
5.vector的构造与管理：constructor,push_back
千头万绪该如何说起？以客户端 程序代码为引导，观察其所得结果并实证原代码，是一个良好的学习路径。不面是一个小小的测试程序，观察重点在构造的方式、元素的添加，以及大小、容量的变化：
// filename : 4vector-test.cpp
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int i;
// vector<int> ivec; // size=0 capacity=0
vector<int> iv(2, 9);
cout << "size=" << iv.size() << endl; // size=2
cout << "capacity=" << iv.capacity() << endl; // capacity=2
iv.push_back(1);
cout << "size=" << iv.size() << endl; // size=3
cout << "capacity=" << iv.capacity() << endl; // capacity=4
iv.push_back(2);
cout << "size=" << iv.size() << endl; // size=4
cout << "capacity=" << iv.capacity() << endl; // capacity=4
iv.push_back(3);
cout << "size=" << iv.size() << endl; // size=5
cout << "capacity=" << iv.capacity() << endl; // capacity=8
iv.push_back(4);
cout << "size=" << iv.size() << endl; // size=6
cout << "capacity=" << iv.capacity() << endl; // capacity=8
for (i = 0; i<iv.size(); ++i)
cout << iv[i] << ' '; // 9 9 1 2 3 4
cout << endl;
iv.push_back(5);
cout << "size=" << iv.size() << endl; // size=7
cout << "capacity=" << iv.capacity() << endl; // capacity=8
for (i = 0; i<iv.size(); ++i)
cout << iv[i] << ' '; // 9 9 1 2 3 4 5
cout << endl;
iv.pop_back();
iv.pop_back();
cout << "size=" << iv.size() << endl; // size=5
cout << "capacity=" << iv.capacity() << endl; // capacity=8
iv.pop_back();
cout << "size=" << iv.size() << endl; // size=4
cout << "capacity=" << iv.capacity() << endl; // capacity=8
vector<int>::iterator ivite = find(iv.begin(), iv.end(), 1);
if (ivite) iv.erase(ivite);
cout << "size=" << iv.size() << endl; // size=3
cout << "capacity=" << iv.capacity() << endl; // capacity=8
for (i = 0; i<iv.size(); ++i)
cout << iv[i] << ' '; // 9 9 2
cout << endl;
ite = find(ivec.begin(), ivec.end(), 2);
if (ite) ivec.insert(ite, 3, 7);
cout << "size=" << iv.size() << endl; // size=6
cout << "capacity=" << iv.capacity() << endl; // capacity=8
for (int i = 0; i<ivec.size(); ++i)
cout << ivec[i] << ' '; // 9 9 7 7 7 2
cout << endl;
iv.clear();
cout << "size=" << iv.size() << endl; // size=0
cout << "capacity=" << iv.capacity() << endl; // capacity=8
}
vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位：
template <class T, class Alloc = alloc>
class vector {
protected:
// simple_alloc<>
typedef simple_alloc<value_type, Alloc> data_allocator;
...
};
于是，data_allocator::allocatore(n)表示配置n个元素空间。
vector提供许多constructors，其中一个允许我们指定空间大小及初值：
// 构造函数，允许指定 vector 大小 n 和初值 value
vector(size_type n, const T& value) { fill_initialize(n, value); }
// 充填并予以初始化
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
// 配置而后填充
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n); // 配置n 个元素空间
uninitialized_fill_n(result, n, x); // 全局函数
return result;
}
uninitialized_fill_n()会根据第一参数的类型特性（type traits）决定使用算法fill_n()或反复调用construct()来完成任务。
当我们以push_back()将元素插入于vector尾端时，该函数产生检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器finish，使vector变大。如果没有备用空间了，就扩大空间（重新配置、移动数据、释放空间）：
template <class T, class Alloc = alloc>
class vector {
protected:
// simple_alloc<>
typedef simple_alloc<value_type, Alloc> data_allocator;
...
};
于是，data_allocator::allocate(n) 表示配置n 个元素空间。
vector 提供许多 constructors，其中一个允许我们指定空间大小及初值：
// 构造函数，允许指定 vector 大小 n 和初值 value
vector(size_type n, const T& value) { fill_initialize(n, value); }
// 充填并予以初始化
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
// 配置而后填充
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n); // 配置n 个元素空间
uninitialized_fill_n(result, n, x); // 全局函数
return result;
}
void push_back(const T& x) {
if (finish != end_of_storage) { // 还有备用空间
construct(finish, x); // 全局函数
++finish; // 调整水位高度
}
else // 已无备用空间
insert_aux(end(), x); // vector member function，见以下列表
}
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
if (finish != end_of_storage) { // 还有备用空間
// 在务用空间起始下构造一个元素，并以vector 最后一个元素值为其初值。
construct(finish, *(finish - 1));
// 调整水位。
++finish;
T x_copy = x;
copy_backward(position, finish - 2, finish - 1);
*position = x_copy;
}
else { // 已无备用空间
const size_type old_size = size();
const size_type len = old_size != 0 ? 2 * old_size : 1;
// 以上配置原则：如果原大小为0，并配置 1（个元素大小）；
// 如果原大小不为0，则配置原大小的两倍，
// 前半段用来放置原数据，后半段准备用来放置新资料。
iterator new_start = data_allocator::allocate(len); // 實際配置
iterator new_finish = new_start;
try {
// 将原vector 的內容拷贝到新 vector。
new_finish = uninitialized_copy(start, position, new_start);
// 为新元素设定初值x
construct(new_finish, x);
// 调整水位。
++new_finish;
// 将原vector 的备用空间中的內容也忠实拷贝过来（侯捷疑惑：啥用途？）
new_finish = uninitialized_copy(position, finish, new_finish);
}
catch (...) {
// "commit or rollback" semantics.
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
// 析构并释放原 vector
destroy(begin(), end());
deallocate();
// 调整迭代器，指向新vector
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
注意，所谓动态增加大小，并不是在原空间之后接续新的空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。这是程序员易犯的一个错误，务需小心。