深度剖析vector

vector 的介绍

• vector是表示可变大小数组的序列容器
• 同数组一样，vector采用连续的存储空间来存储元素，因此可以采用下标对vector的元素进行访问，和数组一样高效，与数组不同的是，vector的大小可以动态改变，而且它的大小会被容器自动处理。
• 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入的时候，这个数组需要被重新分配大小，为了增加存储空间，做法就是，分配一个新的数组，然后将全部的元素移到这个数组。
• vector的空间分配策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。
• 与其他动态序列容器相比，vector在访问元素时更加高效，在末尾添加个删除元素相对高效，但对于其他不在末尾删除和插入的操作效率更低。

vector 的构造函数

1) 无参构造 vector()
2) 构造并初始化n个val vector(size_type n, const value_type& val = value_type())
3) 拷贝构造 vector(const vector& x)
4) 使用迭代器进行初始化构造 vector (InputIterator first, InputIterator last)

int main()
{
	vector<int> v1;//int型的空vector
	vector<int> v2(4, 10);//4个10
	vector<int> v3(v2);//拷贝v3  拷贝构造
	vector<int> v3(v2.begin(), v2.end());//迭代v2中的元素
	return 0;
}

vector 的迭代器

1) 获取第一个数据位置的iterator begin()
2) 获取最后一个数据的下一个位置的iterator end()
3) 获取最后一个数据的iterator rbegin()
4) 获取第一个数据前一个位置的iterator rend()
5) 获取第一个数据位置的const iterator cbegin()
6) 获取最后一个数据的下一个位置的const iterator cend()

使用迭代器进行遍历打印：

void PrintVector(const vector<int>& v)
{
	//使用const迭代器进行遍历打印，注意const迭代器不能修改vector的内容
	vector<int>::const_iterator it = v.cbegin();
	while (it != v.cend())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
int main()
{
	//使用push_back
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	//使用迭代器进行遍历打印
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//使用迭代器进行修改
	it = v.begin();
	while (it != v.end())
	{
		*it *= 2;
		++it;
	}
	PrintVector(v);
	//使用反向迭代器进行遍历打印
	vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	return 0;
}

vector 的空间增长问题

1) 获取数据个数 size()
2) 获取容量大小 capacity()
3) 判断容量是否为空 empty()
4) 改变vector的size void resize(size_type n, value_type val = value_type())
5) 改变vector放入capacity void reserve(size_type n)

• capacity的代码在vs和g++下分别运行会发现，在vs下capacity是按1.5倍增长的，在g++下是按2倍增长的。不能固化的认为顺序表增容都是按2倍增长，具体增长多少是根据具体的需求定义的
• reserve只负责开辟空间，如果确定知道需要多少空间，reserve可以缓解vector增容的代价缺陷问题
• resize在开辟空间的同时还会进行初始化，影响size的大小

int main()
{
	size_t sz;
	std::vector<int> foo;
	sz = foo.capacity();
	std::cout << "making foo grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		foo.push_back(i);
		if (sz != foo.capacity())
		{
			sz = foo.capacity();
			std::cout << "capacity changed:" << sz << '\n';
		}
	}
	return 0;
}

可以看出capacity是按照2倍增长的

reserve()测试

void reserveTest2() {
    int sz = 0;
    std::vector<int> bar;
    sz = bar.capacity(); //sz == 0
    bar.reserve(100);
    std::cout << sz << std::endl;
    std::cout << "making bar grow:\n";
    for(int i = 0; i < 100; i++) {
        bar.push_back(i);//99的时候
        if(sz != bar.capacity()) {
            sz = bar.capacity();
            std::cout << "capacity changed:" << sz << std::endl;
        }
    }
}

resize()测试

std::vector<int> myvector;
for(int i = 1; i < 10; i++) {
    myvector.push_back(i);
}
myvector.resize(5);         //直接截断 1 2 3 4 5
myvector.resize(8,12);   //前5个有数据 默认为原数据 后3个填100
myvector.resize(12);       //默认填0  1 2 3 4 5 12 12 12 0 0 0 0

vector 的增删改查

1) 尾插 void push_back (const value_type& val);
2) 尾删 void pop_back();
3) 查找（这个是算法模块实现，不是vector的成员接口） InputIterator find (InputIterator first, InputIterator last, const T& val)；
4) 在pos之前插入val iterator insert (iterator position, const value_type& val)；
5) 删除position位置的数据 iterator erase（iterator position；
4) 交换两个vector的数据空间 void swap (vector& x)；
5) 像数组空间一样访问 reference operator[] (size_type n)；

尾插、尾删测试：

//push_back pop_back
void push_pop_test() {
    int a[] = {1,2,3,4};
    vector<int> vec(a, a + sizeof(a)/ sizeof(int));
    vector<int> :: iterator it = vec.begin();
    while(it != vec.end()) {
        std::cout << *it << " ";
        it++;
    }
    std::cout << std::endl;
    vec.pop_back();
    vec.pop_back();
    it = vec.begin();
    while(it != vec.end()) {
        cout << *it << " ";
        it++;
    }
    cout << endl;
}

查找、删除、插入测试：

void find_insert_eraseTest() {
    int a[] = {1, 2, 3, 4};
    vector<int> vec(a, a + sizeof(a) / sizeof(int));
    //使用find 查找3的位置
    vector<int>::iterator pos = find(vec.begin(), vec.end(), 3);
    //在pos位置之前插入30
    vec.insert(pos,30);
    vector<int>::iterator it = vec.begin();
    while(it != vec.end()) {
        cout << *it << " ";
        it++;
    }
    cout << endl;
    //删除pos的数据
    pos = find(vec.begin(), vec.end(), 3);
    vec.erase(pos);
    it = vec.begin();
    while(it != vec.end()) {
        cout << *it << " ";
        it++;
    }
    cout << endl;

}

vector 的迭代器失效问题

使用erase(iterator)后，后边的每个元素都会失效，但是后边每个元素都会向前移动一个位置，但是erase会返回下一个有效的迭代器

vector 的模拟实现

namespace gmz {
	template <class T>
	class Vector {
	public:
		typedef T* Iterator;
		typedef const T* ConstIterator;

		Iterator Begin() { return _start; }
		Iterator End() { return _finish; }

		ConstIterator CBegin() const { return _start; }
		ConstIterator CEnd() const { return _finish; }

		size_t Size() const { return _finish - _start; }
		size_t Capacity() const { return _endOfStorage - _start; }

		Vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{}
		Vector(int n, const T& value = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			Reserve(n);
			while (n--) {
				PushBack(value);
			}

		}
		template <class InputIterator>
		Vector(InputIterator first, InputIterator last) {
			Reserve(last - first);
			while (first != last) {
				PushBack(*first);
				++first;
			}
		}

		Vector(const Vector<T>& v) :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
		{
			Reserve(v.Capacity());
			Iterator it = Begin();
			ConstIterator v_it = v.CBegin();
			while (v_it != v.CEnd()) {
				*it++ = *v_it++;
			}
			_finish = _finish + v.Size();
			_endOfStorage = _finish + v.Capacity();

		}
		void Reserve(size_t n) {
			int t_r = Capacity();
			if (n <= Capacity()) return;

			size_t size = Size();
			T* tmp = new T[n];

			if (_start) {
				for (size_t i = 0; i < size; i++) {
					tmp[i] = _start[i];
				}
			}

			_start = tmp;
			_finish = _start + size;
			_endOfStorage = _start + n;
		}
		void Resize(size_t n, const T& value = T()) {
			//1.如果给的n < 当前的size,则数据缩小到n
			if (n <= Size()) {
				_finish = _start + n;
				return;
			}

			//否则 就扩容
			if (n > Capacity()) {
				Reserve(n);
			}   
			Iterator it = _finish;
			Iterator _finish = _start + n;

			while (it != _finish) {
				*it = value;
				it++;
			}
		
		}
		void PushBack(const T& x) {
			Insert(End(), x);
		}
		void PopBack() {
			Erase(--End());
		}
		Iterator Insert(Iterator pos, const T& x) {
			assert(pos <= _finish);

			size_t posindex = pos - _start;
			if (_finish == _endOfStorage) {
				size_t size = Size();
				size_t newCapacity = Capacity() == 0 ? 1 : Capacity() * 2;
				Reserve(newCapacity);

				pos = _start + posindex;
			}
			Iterator end = _finish - 1;
			while (end >= pos) {
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
			return pos;
		}
		//返回删除数据的下一个数据
		//方便解决：一边遍历 一边删除的迭代器失效问题
		Iterator Erase(Iterator pos) {
			
			Iterator begin = pos + 1;
			while (begin != _finish) {
				*(begin - 1) = *begin;
				++begin;
			}
			//++begin;
			--_finish;
			return pos;
		}

		T& operator[](size_t pos) {
			return _start[pos];
		}
		//赋值重载 hansh
		Vector<T>& operator=(const Vector<T>& v) {
			this->Swap(v);
			return *this;
		}
		void Swap(Vector<T>& v) {
			swap(_start, v._start);
			swap(_finish, v._finish);
			swap(_endOfStorage, v._endOfStorage);
		}
		~Vector() {
			delete[] _start;
			_start = nullptr;
			_finish = nullptr;
			_endOfStorage = nullptr;
		}
	private:
		Iterator _start;          //指向数据块的开始
		Iterator _finish;         //指向有效数据的尾
		Iterator _endOfStorage;   //指向存储容量的尾
	};
}