vector

概念

        vector就是数据结构中的顺序表，具有可下标随机访问、尾插尾删效率高、物理空间连续、高速缓存效率高的优点。

vector的使用

vector在实际应用中十分具有意义，我们需要了解它常见的接口：

vector的定义

vector初始化代码 

无参构造

vector()//使用初始化列表即可 	: _start(nullptr) 	, _finish(nullptr) 	, _endOfStorage(nullptr) {}

构造并初始化n个val

vector(size_t n, const T& value = T()) 	: _start(nullptr) 	, _finish(nullptr) 	, _endOfStorage(nullptr) { 	reserve(n); 	while (n--) 	{ 		push_back(value); 	} }  vector(int n, const T& value = T()) 	: _start(new T[n]) 	, _finish(_start + n) 	, _endOfStorage(_finish) { 	for (int i = 0; i < n; ++i) 	{ 		_start[i] = value; 	} }

 拷贝构造

vector(const vector<T>& v) 	: _start(nullptr) 	, _finish(nullptr) 	, _endOfStorage(nullptr) { 	reserve(v.capacity()); 	iterator it = begin(); 	const_iterator vit = v.cbegin(); 	while (vit != v.cend()) 	{ 		*it++ = *vit++; 	} 	_finish = it; }

迭代器进行初始化构造 

// 若使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器 // 重新声明迭代器，迭代器区间[first,last)可以是任意容器的迭代器 template<class InputIterator> vector(InputIterator first, InputIterator last) { 	while (first != last) 	{ 		push_back(*first); 		++first; 	} }

析构函数 

~vector() { 	if (_start) 	{ 		delete[] _start; 		_start = _finish = _endOfStorage = nullptr; 	} }

我们对上面接口进行调用：

    vector<int> first;                                     vector<int> second(4, 100);                           vector<int> third(second.begin(), second.end());       vector<int> fourth(third); 

        第一个调用无参构造；第二个构造4个vector类型并且初始化为100；第三个是使用迭代器进行初始化构造；第四个是对第三个进行拷贝构造。

vector中iterator（迭代器）的使用

 图示如下：

begin为初始位置的下标，而end为末尾位置的下一个位置的下标。 

我们以begin + end为例，使用范围for来演示：

vector<int>::iterator it = fourth.begin(); while(it != fourth.end()) {     cout << *it << " ";     ++it; }  for(auto e : fourth) {     cout << e << endl; }

迭代器实现 

template<class T>  typedef T* iterator; typedef const T* const_iterator;  iterator begin() { 	return _start; }  iterator end() { 	return _finish; }  const_iterator begin() const { 	return _start; }  const_iterator end() const { 	return _finish; } 

vector的空间增长 

代码实现

reserve

void reserve(size_t n) { 	if (n > capacity()) 	{ 		size_t old_size = size(); 		T* tmp = new T[n]; 		memcpy(tmp, _start, size() * sizeof(T)); 		delete[] _start;  		_start = tmp; 		_finish = tmp + old_size; 		_end_of_storage = tmp + n; 	} }

size 

 size_t size() const { 	return _finish - _start; } 

capacity

size_t capacity() const {     return _end_of_storage - _start; }

 empty

bool empty() { 	return _start == _finish; }

注意

1.capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2
倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是
根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

2.reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代
价缺陷问题。

3.resize在开空间的同时还会进行初始化，影响size。 

vector增删查改

代码实现 

尾插

void push_back(const T& x) { 	// 扩容 	if (_finish == _end_of_storage) 	{ 		reserve(capacity() == 0 ? 4 : capacity() * 2); 	}  	*_finish = x; 	++_finish; }

 尾删

void pop_back() { 	assert(!empty()); 	--_finish; }

 插入

iterator insert(iterator pos, const T& x) { 	// 扩容 	if (_finish == _end_of_storage) 	{ 		size_t len = pos - _start; 		reserve(capacity() == 0 ? 4 : capacity() * 2); 		pos = _start + len; 	}  	iterator end = _finish - 1; 	while (end >= pos) 	{ 		*(end + 1) = *end; 		--end; 	} 	*pos = x;  	++_finish;  	return pos; }

方括号下标访问

T& operator[](size_t i) { 	assert(i < size());  	return _start[i]; }  const T& operator[](size_t i) const { 	assert(i < size());  	return _start[i]; }

vector迭代器失效问题

        迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。

因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

会使迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、
assign、push_back等。解决方法是在进行以上操作之后，给迭代器重新赋值即可。

2.指定位置元素的删除操作--erase

int a[] = { 1, 2, 3, 4 }; vector<int> v(a, a + sizeof(a) / sizeof(int)); // 使用find查找3所在位置的iterator vector<int>::iterator pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据，导致pos迭代器失效。 v.erase(pos); cout << *pos << endl; // 此处会导致非法访问 return 0;

        erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理
论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end
的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素
时，vs就认为该位置迭代器失效了，因为iterator指向的位置已经不是我们想要的位置了,尽管可能编译器没有报错（例如g++），但我们仍然认为iterator失效。

        解决方法仍然是进行操作时再次给it赋值，如下代码：

int main() { 	vector<int> v{ 1, 2, 3, 4 }; 	auto it = v.begin(); 	while (it != v.end()) 	{ 		if (*it % 2 == 0) 			v.erase(it); 		++it; 	} 	return 0; } 

我们只需给it赋值即可：

int main() { 	vector<int> v{ 1, 2, 3, 4 }; 	auto it = v.begin(); 	while (it != v.end()) 	{ 		if (*it % 2 == 0) 			it = v.erase(it); 		++it; 	} 	return 0; }

 memcpy拷贝问题

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存
空间中
2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型
元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy 的拷贝实际是浅
拷贝。

3.memcpy是浅拷贝，在拷贝资源管理类结构时会导致指针指向已经释放的空间（例如栈，队列等）可能会导致内存泄漏进而导致程序崩溃。

动态二维数组

即使用vector定义二维数组vv,而vv中每个元素都是vector<int>，从而形成二维数组。

Frenemy::vector<Frenemy::vector<int>> vv(n); // 将二维数组每一行中的vecotr<int>中的元素全部设置为1 for (size_t i = 0; i < n; ++i) 	vv[i].resize(i + 1, 1); // 给杨辉三角出第一列和对角线的所有元素赋值 for (int i = 2; i < n; ++i) { 	 		Frenemy::vector<Frenemy::vector<int>> vv(n);  		 		for (int j = 1; j < i; ++j) 		{ 			vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1]; 		} }

我们以vv[5]为例：

以杨辉三角的形式将数据填入即可得到：