vector的模拟实现

一、vector的基本结构

template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
private:
	iterator _start;//vector的迭代器，指向起始位置
	iterator _finish;//指向存放最后一个元素的下一个位置
	iterator _end_of_storage;//指向容量的最后一个位置
};

我们可以得知，_finish - _start就是顺序表vector的大小；_end_of_storage - _start 就是顺序表vector的容量。

二、vector的默认成员函数

1、构造函数

这里实现了三个构造函数，一个是默认构造，一个是用n个值构造，一个用迭代器区间构造。

//默认构造函数
vector()
	:_start(nullptr)
	,_finish(nullptr)
	,_end_of_storage(nullptr)
{}

//用n个value构造
vector(int n, const T& value = T())
{
	_start = new T[n];
	for (int i = 0; i < n; ++i)
	{
		_start[i] = value;
	}
	_finish = _start + n;
	_end_of_storage = _finish;
}

//用迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	int n = last - first;
	_start = new T[n];
	int i = 0;
	while (first != last)
	{
		_start[i++] = *first;
		++first;
	}
	_finish = _start + n;
	_end_of_storage = _finish;
}

2、析构函数

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

3、拷贝构造

a、这是较为简单的现代写法，用v构造一个tmp，然后把tmp的资源全部交换给自己，就完成了拷贝 ，不需要手动释放tmp，出了函数会自动调用析构函数处理。

void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}

vector(const vector<T>& v)
{
	_start = _finish = _end_of_storage = nullptr;
	vector<T> tmp(v.cbegin(), v.cend());
	swap(tmp);
}

b、这是一般的写法

vector(const vector<T>& v)
{
	int capacity = v.capacity();
	int sz = v.size();
	_start = new T[capacity];
	_finish = _start + sz;
	_end_of_storage = _start + capacity;
	for (int i = 0; i < sz; ++i)
	{
		*(_start + i) = v[i];
	}

}

4、移动赋值

与拷贝构造类似，用v构造一个tmp，最后将tmp的资源交换给自己即可。因为函数结束后会调用析构函数释放tmp，会把原本的空间释放，所以不用手动释放空间了。

vector<T>& operator=(const vector<T>& v)
{
	vector<T> tmp(v.cbegin(), v.cend());
	swap(tmp);

	return *this;
}

三、迭代器有关接口

由上面的结构(一)可以看到vector的迭代器就是 T*

typedef T* iterator;
typedef const T* const_iterator;

iterator begin()
{
	return _start;
}
iterator end()
{
	return _finish;
}
const_iterator cbegin() const
{
	return _start;
}
const_iterator cend() const
{
	return _finish;
}

四、其他的函数

1、大小size与容量capacity

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

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

2、reserve

如果n比这个vector的容量大，就扩容到n，如果更小，就什么都不用干。

void reserve(size_t n)
{
	if (_start + n > _end_of_storage)
	{
		int sz = size();
		T* tmp = new T[n];
		//memcpy(tmp, _start, size() * sizeof(T));
		for (int i = 0; i < sz; ++i)
		{
			tmp[i] = _start[i];
		}
		delete[] _start;
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

3、resize

如果n小于size，就把size减为n；如果n大于size，就把大于size的部分用val赋值；如果n大于capacity，就扩容到n。

void resize(size_t n, const T& value = T())
{
	if (_start + n > _finish)
	{
		int end = size();
		reserve(n);
		for (int i = end; i < n; ++i)
		{
			_start[i] = value;
		}
	}
	else
	{
		_finish = _start + n;
	}
}

五、增加、删除与方括号的重载

1、[]的重载

[]的重载可以让我们像数组一样用下标访问vector

T& operator[](size_t pos)
{
	return _start[pos];
}

const T& operator[](size_t pos)const
{
	return _start[pos];
}

2、尾插和尾删

void push_back(const T& x)
{
	if (_finish == _end_of_storage)
	{
		int newcapacity = _finish == nullptr ? 4 : 2 * capacity();
		reserve(newcapacity);
	}
	*_finish = x;
	++_finish;
}

void pop_back()
{
	--_finish;
}

3、任意位置的插入和删除

任意删除位置就是从 pos+1 位置，后一个数不断覆盖前一个数，最后--_finish就完成了pos位置的删除。

任意插入位置就是从最后一个数开始，每一个数都往后挪一位，到pos位置挪完后，再将值插入到pos位置。

iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);
	//memmove(pos, pos + 1, (_finish - pos - 1) * sizeof(T));
	iterator begin = pos;
	while (begin < _finish - 1)
	{
		*begin = *(begin + 1);
		begin++;
	}
	--_finish;
	return pos;
}

iterator insert(iterator pos, const T& x)
{
    if (_finish == _end_of_storage)
    {
    	int posi = pos - _start;
        int newcapacity = _finish == nullptr ? 4 : 2 * capacity();
	    reserve(newcapacity);
    	pos = _start + posi;
    }

    //memmove(pos + 1, pos, (_finish - pos) * sizeof(T));
    iterator end = _finish - 1;//n-1
    while (end >= pos)
    {
	    *(end + 1) = *end;
    	end--;
    }
    *pos = x;
    ++_finish;
    return pos;
}

六、迭代器失效问题

当我们插入或删除一个值时，有可能会导致扩容或缩容，而我们的迭代器还指向旧的空间，就会导致我们的迭代器失效。

void test3()
{
	lw::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	
	lw::vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

我们上述代码就是简单的使用迭代器遍历vector，结果如下：

而我们执行如下代码时：假如我们想在2的前面插入一个20

void test3()
{
	lw::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	
	lw::vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << " ";
		if (*it == 2)//假如我们想在2的前面插入一个20
		{
            v1.insert(it, 20);
            it++;
        }
		it++;
	}
	cout << endl;
}

执行结果就变为了：

因为insert后，会扩容，数据已经存到新的空间，而我们使用的迭代器 it 依旧指向旧的空间，就会出现随机值。