再探Vector

@[toc]

今晚复习的时候，有一股很强烈的感觉，要重新进入STL看一下。曾几何时，我好像做过这样的事情，所以看到vector的那些知识点的时候有种莫名的亲切，又感觉我现在写到vector的博客里面零零散散的版块，好像是从以前某一篇里面拆出来的，可惜后面那篇被我删了。

后来我才知道，不要觉得某些点简单就删了，可能那时候是“高光时刻”，所以才会觉得简单吧。

---

灵魂拷问

先写个vector遍历删除的代码

void del_vec_foreach(vector<int>& vec,int target) {
	for (vector<int>::iterator it = vec.begin(); it != vec.end();) {
		if (*it == target) {
			it = vec.erase(it);
		}
		else {
			++it;
		}
	}
}

---

vector<T> vi1 = vi2 的时候发生了什么？

调用了拷贝构造函数。

1、vector使用的是深拷贝。
2、选择合适的拷贝算法。
/3、拷贝两类：
（一）对于POD类型直接采用memcpy进行拷贝;
（二）对于非POD类型需要采用for循环加new定位表达式;
4、切记拷贝完成之后释放掉原来的旧空间

源码之前，了无秘密

// 本实作中默认构造出的vector不分配内存空间
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(const vector<T, Alloc>& x){
    start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
    finish = start + (x.end() - x.begin());
    end_of_storage = finish;
}

这个跟主题关系不大，不过我乐意放这儿

//维护了vector的三个迭代器，调用了allocate_and_fill函数
void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}


protected:
	//typedef simple_alloc<value_type, Alloc> data_allocator;
    //vector给SGISTL的空间配置器设置了一个别名
    iterator allocate_and_fill(size_type n, const T& x) {
        iterator result = data_allocator::allocate(n);
        
        /* __STL_TRY...__STL_UNWIND类似异常处理的try...catch语句块
		 * 这段代码的大意就是,初始化allocate分配的未初始化空间
		 * 如果失败了,则将分配的内存回收,防止内存泄露
=		 */
        __STL_TRY {
        	//调用初始化uninitialized_fill_n未初始化的空间
            uninitialized_fill_n(result, n, x);
            return result;
        }
        __STL_UNWIND(data_allocator::deallocate(result, n));
    }

再往下：allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());

//allocate_and_copy整体和allocate_and_fill类似，只是他们初始化未初始化空间调用的函数不同
#ifdef __STL_MEMBER_TEMPLATES
  template <class ForwardIterator>
  iterator allocate_and_copy(size_type n,
                             ForwardIterator first, ForwardIterator last) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_copy(first, last, result);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }
#else /* __STL_MEMBER_TEMPLATES */
  iterator allocate_and_copy(size_type n,
                             const_iterator first, const_iterator last) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_copy(first, last, result);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }

接下来还有个 range_initialize:

//根据迭代器的不同版本，重载了不同版本
 template <class InputIterator>
  void range_initialize(InputIterator first, InputIterator last,
                        input_iterator_tag) {
    for ( ; first != last; ++first)
      push_back(*first);
  }

  // This function is only called by the constructor.  We have to worry
  //  about resource leaks, but not about maintaining invariants.
  template <class ForwardIterator>
  void range_initialize(ForwardIterator first, ForwardIterator last,
                        forward_iterator_tag) {
    size_type n = 0;
    distance(first, last, n);
    start = allocate_and_copy(n, first, last);
    finish = start + n;
    end_of_storage = finish;
  }

再往下，还没完。这里面出现了两个关键函数（或者说一个）：

//调用初始化uninitialized_fill_n未初始化的空间
            uninitialized_fill_n(result, n, x);

//allocate_and_copy整体和allocate_and_fill类似，只是他们初始化未初始化空间调用的函数不同
 uninitialized_copy(first, last, result);

再往下：

template <class InputIterator, class ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result){
		__uninitialized_copy(first, last, result, value_type(result));
		__uninitialized_copy_aux(first, last, result, is_POD());
}

主要便是uninitialized_copy()调用__uninitialized_copy() 最后一个参数是value_type(result)
value_type(result)的作用是将 ForwardIterator result 转化为指针类型T
__uninitialized_copy() 中调用__uninitialized_copy_aux() 则是判断 T是否为POD type

template <class InputIterator, class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,ForwardIterator result,__true_type) {
	return copy(first, last, result);
}

template <class InputIterator, class ForwardIterator>
ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,ForwardIterator result,__false_type) {
	ForwardIterator cur = result;
	__STL_TRY {
		for ( ; first != last; ++first, ++cur)
			construct(&*cur, *first);
		return cur;
	}
	__STL_UNWIND(destroy(result, cur));
}

如何判断是否是POD type？

typedef typename __type_traits<T>::is_POD_type is_POD;

所有的基本类型都有如下定义

struct __type_traits<char> {
	typedef __true_type is_POD_type;
};

struct __type_traits<signed char> {
	typedef __true_type is_POD_type;
};

struct __type_traits<int> {
	typedef __true_type is_POD_type;
};

而非基本类型则会对应到以下模板代码

template <class type>
struct __type_traits {
	typedef __false_type is_POD_type;
};

所以当typename __type_traits<T>::is_POD_type的T 为int char double 等类型，is_POD_type为__true_type；
其他类型则is_POD_type为__false_type。

如果是POD type，就是基本数据类型(int char double等)那么就直接拷贝即可。

代码如下：

__true_type
return copy(first, last, result);

如果不是POD type 就需要依次调用构造函数创建数据

代码如下

__false_type
for ( ; first != last; ++first, ++cur)
　　construct(&*cur, *first);

copy是吧：

---

下面这种写法会有问题吗？

vector< int > ivec; 
ivec[0] = 1024;

源码之前，了无密码

// 本实作中默认构造出的vector不分配内存空间
vector() : start(0), finish(0), end_of_storage(0) {}

ivec 还没有第一个元素，我们只能索引 vector 中已经存在的元素 size()操作返回 vector 包含的元素的个数 。

reference operator[](size_type n) { return *(begin() + n); }

那push_back为什么就可以呢？

void push_back(const T& x)
{
    // 内存满足条件则直接追加元素, 否则需要重新分配内存空间
    if (finish != end_of_storage)
    {
        construct(finish, x);	//这是一个请求重新分配空间的函数
        ++finish;
    }
    else
        insert_aux(end(), x);
}

---

STL 中vector删除其中的元素，迭代器如何变化？

当前迭代器及当前迭代器的后续迭代器全部失效，容器内元素从删除点之后全部前移，返回下一个有效的迭代器。

---

为什么要成倍的扩容而不是一次增加一个固定大小的容量呢？

成倍扩容时：

1、假定有 n 个元素,倍增因子为 m；
2、完成这 n 个元素往一个 vector 中的 push_back​操作，需要重新分配内存的次数大约为 logm(n)；
3、第 i 次重新分配将会导致复制 m^(i) (也就是当前的vector.size() 大小)个旧空间中元素;
4、n 次 push_back 操作所花费的时间复制度为O(n):

5、m / (m - 1)，这是一个常量，均摊分析的方法可知，vector 中每次 push_back 操作的时间复杂度为常量时间.。

固定大小扩容时：

1、假定有 n 个元素,每次增加k个；
2、第 i 次增加复制的数量为为：100i
3、n 次 push_back 操作所花费的时间复杂度为O(n^2):

4、均摊下来每次push_back 操作的时间复杂度为O(n)

---

为什么是以两倍的方式扩容而不是三倍四倍，或者其他方式呢？

考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2二倍的方式扩容，或者以1.5倍的方式扩容。
以2倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间：

在知乎上看到这么一张图，懂得人自然就懂了：

为了防止申请内存的浪费，现在使用较多的有2倍与1.5倍的增长方式，而1.5倍的增长方式可以更好的实现对内存的重复利用，因为更好。

释放空间？

由于vector的内存占用空间只增不减，比如你首先分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个。所有内存空间是在vector析构时候才能被系统回收。empty()用来检测容器是否为空的，clear()可以清空所有元素。但是即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收。

如果真心想释放空间，可以用swap()来帮助你释放内存。

std::vector<int> tmp;   
ivec.swap(tmp);

源码之前，了无秘密

  // 交换两个vector, 实际上是交换内部的状态指针  
  void swap(vector<T, Alloc>& x)  
  {  
    __STD::swap(start, x.start);  
    __STD::swap(finish, x.finish);  
    __STD::swap(end_of_storage, x.end_of_storage);  
  } 

看这段函数声明感觉？我一开始还以为在唬我！！不过如果真的可以这样，那时间复杂度将是极低的！！！

如果要实现，除非：

  iterator start;               // 内存空间起始点  
  iterator finish;              // 当前使用的内存空间结束点  
  iterator end_of_storage;      // 实际分配内存空间的结束点  

果然，直接接管一块空间，不是拷贝、
不过这里倒没有看到回收内存的操作啊。。。
是后台空间配置器自己回收？

---

对于插入操作

对于插入操作，我还是要提一下：

// 提供插入操作  
  
//                 insert_aux(iterator position, const T& x)  
//                                   |  
//                                   |---------------- 容量是否足够?  
//                                   ↓  
//              -----------------------------------------  
//        Yes   |                                       | No  
//              |                                       |  
//              ↓                                       |  
// 从opsition开始, 整体向后移动一个位置                     |  
// construct(finish, *(finish - 1));                    |  
// ++finish;                                            |  
// T x_copy = x;                                        |  
// copy_backward(position, finish - 2, finish - 1);     |  
// *position = x_copy;                                  |  
//                                                      ↓  
//                            data_allocator::allocate(len);  
//                            uninitialized_copy(start, position, new_start);  
//                            construct(new_finish, x);  
//                            ++new_finish;  
//                            uninitialized_copy(position, finish, new_finish);  
//                            destroy(begin(), end());  
//                            deallocate();