vector的模拟实现

vector的模拟实现

• begin()
• end()
• size()
• capacity()
• reserve()
• push_back()
• pop_back()
• empty()
• operator[]
• insert()

vector.h

#pragma once

#include<iostream>
#include<list>
#include<assert.h>
#include<string>

using namespace std;

namespace wbc
{
	template<class T>
	class vector
	{
	public:
		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;
		}

		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;
			}
		}

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

			*_finish = x;
			++_finish;
    	}

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

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

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

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

		iterator insert(iterator pos, const T& x)
		{
			if (_finish == _end_of_storage)
			{
				// 扩容后_start可能会变
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + len;
				// 所以更新一下pos,不让pos指向原来的空间
			}

			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];
		}

	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};

	/*void vector_print(const vector<int>& v)
	{
		vector<int>::const_iterator it = v.begin();

		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto x : v)
		{
			cout << x << " ";
		}
		cout << endl;
	}*/

	template<class T>
	void vector_print(const vector<T>& v)
	{
		// 规定没有实例化的类模版里取东西，编译器是无法区分const_iterator是
		// 静态成员变量还是类型,加了typename 就表明是类型
		// typename vector<T>::const_iterator it = v.begin();
		auto it = v.begin();

		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto x : v)
		{
			cout << x << " ";
		}
		cout << endl;

	}

	void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);

		for (size_t i = 0; i < v.size(); i++)
			cout << v[i] << " ";
		cout << endl;

		vector<int>::iterator it = v.begin();
		for (size_t i = 0; i < v.size(); i++)
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto x : v)
			cout << x << " ";
		cout << endl;
 
		vector_print(v);

		vector<double> vv;
		vv.push_back(1.1);
		vv.push_back(2.2);
		vv.push_back(3.3);
		vv.push_back(4.4);
		vv.push_back(5.5);

		vector_print(vv);

	}

	void test_vector2()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
        
		vector_print(v);

		v.insert(v.begin() + 2, 30);
		vector_print(v);

		int x;
		cin >> x;
		auto pos = find(v.begin(), v.end(), x);
		if (pos != v.end())
		{
			pos = v.insert(pos, 30);
			//(*pos) *= 10;
			(*(pos+1)) *= 10;
		}

		vector_print(v);
	}
}

test.cpp

#include"vector.h"

int main()
{
	wbc::test_vector2();

	return 0;
}

模版不能分离到两个文件 .h和.cpp,会出现链接错误
reserve是不缩容的

• vector<vector< int >> 调用的是两个类的模版

• vector的底层

protected:
iterator start;
// 数据开始的位置
iterator finish; // 指针 + size()
// 数据结束的下一个位置
iterator end_of_storage;// 指针 + capacity()
// 空间结束的下一个位置

insert_aux(end(),x);
// end() 数据结束的下一个位置
// 在最后一个位置插入x,相当于尾插

• reserve是怎么给_start,_finish和_end_of_storage的？

// 错误写法
reserve(n > capacity)
{
  _start = tmp;
  _finish = tmp + size();
  // size() 为 _finish - _start
  // 之前的_finish减去更新后的_start
  // 这样肯定是错误的
  _end_of_storage = _start + n;
}

size_t size()
{
   return _finish - _start;
}
// 正确写法
reserve(n > capacity)
{
   _finish = tmp + size();// size()为0
   _start = tmp;
   _end_of_storage = _start + n;
}

• vector< T >:: const_iterator it = v.begin(),vector< T >未实例化会分不清是类型还是静态成员变量 ？

vector< int > :: const_iterator it = v.begin()
实例化后的vector< int > 可以取到类型
：：域作用限定符后面会跟类型或静态成员变量

template<class T>
	void vector_print(const vector<T>& v)
	{
		// 规定没有实例化的类模版里取东西，编译器是无法区分const_iterator是
		// 静态成员变量还是类型,加了typename 就表明是类型
		// typename vector<T>::const_iterator it = v.begin();
		auto it = v.begin();