vector的底层模拟实现

文章目录

vector的成员变量

什么是vector呢？ vector是可变数组大小的序列容器。（跟模拟实现顺序表差不多）
模拟实现顺序表的成员变量：指针，size，capacity。
在这里插入图片描述

迭代器的模拟实现

iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			reutrn _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			reutrn _finish;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

获取size，capacity，判空操作

不修改数据的时候，我们建议都加上const

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

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

		bool empty() const
		{
			return _start == _finish;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

reserve和resize的模拟实现（重点）

reserve针对capacity，当要调整的空间大于capacity时才会调整，小于capacity不做处理（但是不一定会调整到指定大小，
因为无论是C++编译器还是Linux编译器都有自己的增容方式）
resize针对于size ，如果要调整的个数小于size，直接砍掉。但是调整的个数大于size，扩容后填数据

void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				T* tmp = new T[n];
				//memcpy(tmp,_start,sizeof(T)*size()) 如果用memcpy会出现一些错误
				//这个放到最后面再说
				if (_start)
				{
					for (size_t i = 0; i < sz; i++)
					{
						tmp[i] = _start[i];
					}

					delete[] _start;
				}
				_start = tmp;
				_finish = _start + sz;    //这里的_finis , _endofstorage都要重新刷新一下
				_endofstorage = _start + n;
			}
		}

		void resize(size_t n, const T& val = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}

			else
			{
				if (n > capacity())
				{
					reserve(n);
			    }

				while (size() < n)
				{
					*_finish++ = val;
				}
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

pop_back （尾删）和 push_back（尾插）

void push_back(const T& val)
		{
			if (_finish == _endofstorage)  //这里是判断是否满了，不要用_start去比较了
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			
			*_finish = val;
			_finish++;
		}

		void pop_back()
		{
			if (empty())
			{
				cout << "no data to delete" << endl;
				return;
			}
			else
			{
				_finish--;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

insert（任意位置的插入）和 erase （任意位置的删除）

         iterator insert(iterator pos, const T& val)
		{
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);

				//这里如果发生了扩容，pos就要刷新一下
				//否则就失效了
				pos = _start + len;
			}

			iterator it = _finish - 1;
			while (it >= pos)
			{
				*(it + 1) = *it;
				--it;
			}
			*pos = val;
			_finish++;

			return pos;
		}

		void insert(iterator pos,size_t n ,const T& val)
		{
			size_t max = n + size();
			if ( max > capacity())
			{
				size_t len = pos - _start;

				reserve(max);

				//这里如果发生了扩容，pos就要刷新一下
				//否则就失效了
				pos = _start + len;
			}

			size_t len = n;
			iterator it = _finish - 1;
			while (it >= pos)
			{
				*(it + len) = *it;
				it--;
			}

			while (n)
			{
				n--;
				*pos = val;
				pos++;
			}

			_finish = _finish + len;
		}

		iterator erase(iterator pos)
		{
			if (empty())
			{
				cout << " no data to delete" << endl;
			}
            
			iterator it = pos ;
			while (it < _finish-1)
			{
				*it = *(it + 1);
				it++;
			}
			_finish--;
			return pos;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

构造，析构，拷贝构造，赋值重载

vector()
			:_start(nullptr)
		    , _finish(nullptr)
			,_endofstorage(nullptr)
			{}

		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			_start = new T[n];
			for (size_t i = 0; i < n; i++)
			{
				_start[i] = val;
			}
			_finish = _start + n;
			_endofstorage = _start + n;
		}

		// v1(v2)
		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			_start = new T[v.capacity()];
			for (size_t i = 0; i < v.size(); i++)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
			_endofstorage = _start + v.capacity();
		}

		//v1 = v2
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}
		
        //类模板里面的模板函数
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			int len = last - first;
			_start =_finish = new T[len];
			while (first != last)
			{
				*_finish++ = *first++;
			}
			_endofstorage = _start + len;
		}

		void swap(vector<T>& v)
		{
			::swap(_start, v._start);
			::swap(_finish, v._finish);
			::swap(_endofstorage, v._endofstorage);
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61