3. vector源码

缺点：

因为每次扩容空间翻倍，而很多空间没有利用上，空间利用率不如固定扩容。

在实际应用中，一般采用空间换时间的策略。

3、resize()和reserve()

resize()：改变当前容器内含有元素的数量(size())，而不是容器的容量

1. 当resize(len)中len>v.capacity()，则数组中的size和capacity均设置为len;
2. 当resize(len)中len<=v.capacity()，则数组中的size设置为len，而capacity不变;

reserve()：改变当前容器的最大容量（capacity）

1. 如果reserve(len)的值 > 当前的capacity()，那么会重新分配一块能存len个对象的空间，然后把之前的对象通

过copy construtor复制过来，销毁之前的内存;

1. 当reserve(len)中len<=当前的capacity()，则数组中的capacity不变，size不变，即不对容器做任何改变。

3. vector源码

templeta<class T,class Alloc=alloc> class vector {

public:

typedef T value_type;

typedef value_type *pointer;

typedef value_type &reference;

typedef value_type *iterator;

typedef size_t size_type;

typedef ptrdiff_t difference_type //嵌套类型定义，也可以是关联类型定义

protected:

typedef simple_alloc <value_type, Alloc> data_alloctor //空间配置器（分配器）

iterator start;

iterator finish;

iterator end_of_storage;

//这3个就是vector里的数据，所以一个vector就是包含3个指针12byte,下面有图介绍

void insert_aux(iterator position, const T &x);

//这个就是vector的自动扩充函数，在下面章节我会拿出来分析 void deallocate() {

if (start)

data_allocator::deallocate(start, end_of_storage);

}

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支持随机访问

vector() : start(0), end(0), end_of_storage(0) {};

vector(size_type n, const T &value)(fill_initialize(n, value););

vector(long n, const T &value)(fill_initialize(n, value););

vector(int n, const T &value)(fill_initialize(n, value););

explicit vector(size_type n) { fill_initialize(n, T()); };

//重载构造函数 ~vector() {

destory(start, finish);//全局函数，析构对象 deallocate();//成员函数，释放空间

} //接下来就是一些功能函数

reference front() { return *begin(); };

reference back() { return *(end() - 1); };

void push_back(const T &x) { if (finsih != end_of_storage) {

construct(finish, x);

++finish;

} else insert_aux(end(), x);

//先扩充在添加 }

void pop_back() { --finish;

iterator erase(iterator position) { if (position + 1 != end())

copy(position + 1, finish, position);

--finish;

destory(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);//全局函数 }

}

vector迭代器：由于vector维护的是一个线性区间，所以普通指针具备作为vector迭代器的所有条件，就不需要重载operator+，operator*之类的东⻄

template <class T, class Alloc = alloc> class vector {

public:

typedef T value_type;

typedef value_type* iterator; //vector的迭代器是原生指针 // ...

};

vector的数据结构：线性空间。为了降低配置空间的成本，我们必须让其容量大于其大小。

vector的构造以及内存管理：当我们使用push_back插入元素在尾端的时候，我们首先检查是否还有备用空间也就是说end是否等于end_of_storage，如果有直接插入，如果没有就扩充空间

template<class T, class Alloc> void vector<T, Alloc>::insert_aux(iterator position, const T &x) {

if (finish != end_of_storage) {//有备用空间

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;

//vector中如果没有元素就配置一个元素，如果有就配置2倍元素。

iterator new_start = data_allocator::allocate(len);

iterator new_finish = new_start;

try { //拷贝插入点之前的元素

new_finish = uninitialized_copy(start, position, new_start);

construct(new_finish, x);

++new_finish;

//拷贝插入点之后的元素 new_finish = uninitialized_copy(position, finish, new_finish);

} catch () {

destroy(new_start, new_finish);

data_allocator::deallocate(new_start, len);

throw;

} //析构并释放原vector

destory(begin(), end());

deallocate();

//调整迭代器指向新的vector start = new_start;

finish = new_finish;

end_of_storage = new_start + len;

} }

整个分为3个部分，配置新空间，转移元素，释放原来的元素与空间,因此一旦引起空间配置指向以前vector的所有迭代器都要失效。

vector的部分元素操作：pop_back,erase,clear,insert

void pop_back() { --finish;

destory(finish);

}

//erase版本一：清除范围元素

iterator erase(iterator first, iterator last) { interator i = copy(last, finish, first);

destory(i, finish);

finish = finish - (last - first);

return first;

}

//版本二：清除某个位置上的元素 iterator erase(iterator position) {

if (position + 1 != finish) { copy(position + 1, finish, position);

--finish;

distory(finish);

return position;

} }

void clear() { erase(begin(), end()) };

template<class T, class Alloc> void vector<T, Alloc>::insert(iterator position, size_type n, const T &x) {

if (n != 0) { if (size_type(end_of_strage - finish) > n) {

//备用空间大于插入的元素数量 T x_copy = x;

if (elems_after > n) { //插入点之后的元素个数大于要插入的元素个数

uninitialiazed_copy(finish - n, finish, finish);

finish += n;//将vector的尾端标记后移 copy_backward(position, old_finish - n, old_finish);

fill(position, old_finish, x_copy);//从插入点之后开始插入新值 } else {

//插入点之后的元素个数小于要插入的元素个数 uninitialiazed_fill_n(finish, n - elems_after, finish);

finish += n - elems_after;

uninitialiazed_copy(position, old_finish, finish);

finish += elems_after;

fill(position, old_finish, x_copy);

} else {

//备用空间小于要插入元素的个数 //首先决定新长度，原长度的两倍，或者老长度+新的元素个数

const size_type old_size = size();

const size_type len = old_size + max(old_size, n);

//以下配置新的空间 iterator new_start = data_allocator::allocate(len);

iterator new_finish = new_start;

_STL_TRY { //拷贝插入点之前的元素

new_finish = uninitialized_copy(start, position, new_start);

//把新增元素（初值皆为n)传入新空间 new_finish=uninitialized_fill_n

//拷贝插入点之后的元素 new_finish=uninitialized_copy(position, finish, new_finish);

//这一段有利于理解上面的insert_aux函数 }

#ifdef _STL_USE_EXCEPTIONS catch(){

//如果有异常发生 destroy(new_start,new_finish);

data_allocator::deallocate(new_start,len);

throw;

} #endif/* _STL_USE_EXCEPTIONS*/

//析构并释放原vector destory(begin(), end());

deallocate();

//调整迭代器指向新的vector start = new_start;

finish = new_finish;