STL库 —— vector 的编写

一、成员变量

二、容量成员

2.1 size 函数

我们在定义私有成员时就会发现，其中 _finish 相当于 string 中的 size 的地址， _endofstorage 相当于 string 中的 capacity 的地址，所以 size 函数和 capacity 函数其实基本没有改变。

size_t size()
{
	return _finish - _start;
}

2.2 capacity 函数

size_t capacity()
{
	return _endofstorge - _start;
}

2.3 reserve 函数

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

		_start = tmp;
		_finish = tmp + _size;
		_endofstorge = tmp + n;
	}
}

有了reserve函数，我们就可以先写一个push_back来方便后续测试

void push_back(T tmp)
{
	size_t _size = size();
	size_t n = capacity() == 0 ? 4 : 2 * capacity();
	reserve(n);
	*_finish = tmp;
	_finish++;
}

2.4 resize 函数

因为reseve的性质，上述的第二种和第三种情况我们可以合并成一种

void resize(size_t n, T val = T())
{
	int _size = size(), _capacity = capacity();
	if (n < _size)
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_size++ < n)
		{
			*_finish = val;
			_finish++;
		}
	}
}

测试代码：

void test_resize()
{
	my_vector v2;
	v2.push_back(1);
	v2.push_back(2);
	v2.push_back(3);
	v2.print_vector();

	v2.resize(20, 10);
	v2.print_vector();
			
	v2.resize(5, 10);
	v2.print_vector();
			
	v2.push_back(1);
	v2.push_back(2);
	v2.print_vector();
			
	v2.resize(2);
	v2.print_vector();
	v2.push_back(1);
	v2.push_back(2);
	v2.print_vector();
}

三、迭代器

3.1 begin() 函数

typedef const T* const_iterator;

iterator begin()
{
	return _start;
}

const_iterator begin() const
{
	return _start;
}

3.2 end() 函数

iterator end()
{
	return _finish;
}

const_iterator end() const
{
	return _finish;
}

四、 元素访问成员

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

测试代码：

void test_operator_()
{
	my_vector<int> v3;
	v3.push_back(1);
	v3.push_back(2);
	v3.push_back(3);
	v3.push_back(4);
	v3.push_back(5);
	v3.push_back(6);
	v3.push_back(7);
	v3.push_back(8);
	v3.push_back(9);
	v3.push_back(0);
	for (int i = 0; i < v3.size(); i++)
	{
		std::cout << v3[i] << std::endl;
	}
			
}

五、 修饰符函数

4.1 insert 函数

先编写 insert 函数，是为了让后面的 push_back 函数有更好的写法。

下面是使用索引进行指定位置插入： 

void insert(int pos, const T& val)
{
	assert(pos <= size());
	size_t _size = size(), _capacity = capacity();
	if (_size == _capacity) reserve(_capacity == 0 ? 4 : 2 * _capacity);
	for (int i = _size; i > pos; i--)
	{
		*(_start + i) = *(_start + i - 1);
	}
	*(_start + pos) = val;
	_finish++;
}
//测试样例
void test_insert1()
{
	my_vector<int> v4;
	v4.push_back(1);
	v4.push_back(2);
	v4.push_back(3);
	v4.push_back(4);
	v4.push_back(5);
	v4.insert(3, 0);
	for (int i = 0; i < v4.size(); i++)
	{
		std::cout << v4[i] << std::endl;
	}
}

但是在库中，使用的是迭代器来定位插入元素的位置：

其中，要注意扩容后对 pos 的更新！迭代器定位插入元素时可以使用 [begin() + i] 或 [end() ...] 来传入参数。
 

void insert(Iterator pos, const T& val)
{
	assert(pos >= _start);
	assert(pos <= _finish);

	if (_finish == _endofstorage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);

		// 如果扩容了要更新pos
		pos = _start + len;
	}

	Iterator it = _finish - 1;
	while (it >= pos)
	{
		*(it + 1) = *it;
		--it;
	}
	*pos = val;
	++_finish;
}
//测试样例
void test_insert2()
{
	my_vector<int> v5;
	v5.push_back(1);
	v5.push_back(2);
	v5.push_back(3);
	v5.push_back(4);
	v5.push_back(5);
	v5.insert(v5.begin() + i, 0);
	for (int i = 0; i < v5.size(); i++)
	{
		std::cout << v5[i] << std::endl;
	}
}

4.2 push_back 函数 

除了上面的传统写法外，我们的 push_back 也可以借助 insert 来服用：

void push_back2(T tmp)
{    
    //借助insert1
	insert(size(), tmp);
    /借助insert2
    insert(end(), tmp);
}

4.3 erase 函数

因为官方是使用的 iterator 所以这里也只是用 iterator 的方法：

void erase(Iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);

	Iterator it = pos + 1;
	while (it < _finish)
	{
		*(it - 1) = *it;
	    ++it;
	}
	--_finish;
}

4.4 pop_back 函数

同 push_back ，可以复用 erase 函数。

void pop_back()
{
	erase(end() - 1);
}

4.5 swap 函数

这里需要注意参数要设置成引用的格式！

void swap(my_vector& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstorage, v._endofstorage);
}
//测试代码
void test_swap()
{
	my_vector<double> v7;
	v7.push_back2(1.1);
	v7.push_back2(2.2);
	v7.push_back2(3.3);
	v7.print_vector();
	my_vector<double> v8;
	v8.push_back1(3.3);
	v8.push_back1(6.6);
	v8.push_back1(9.9);
	v8.print_vector();

	v7.swap(v8);
	v7.print_vector();
}

4.6 clear 函数

void clear()
{
	_start = _finish = _endofstorage = nullptr;
}
//测试代码
void test_clear()
{
	my_vector<double> v9;
	v9.push_back2(1.1);
	v9.push_back2(2.2);
	v9.push_back2(3.3);
	v9.print_vector();
	v9.clear();
	v9.print_vector();
	v9.push_back1(6.6);
	v9.print_vector();
}

六、成员函数

6.1 构造函数

全缺省构造函数直接使用了“类内初始化器”，即 "In-Class Member Initializer" 

private:
	Iterator _start = nullptr;
	Iterator _finish = nullptr;
	Iterator _endofstorage = nullptr;

标准构造函数，它接受一个大小参数 n 和一个默认值 val ，并创建一个大小为 n 的 vector ，如下

my_vector(size_t n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

还有两种 C++11 及之后引入的构造函数如下：

1. 使用初始化列表构造，允许使用花括号 {} 来初始化对象，如

my_vector<int> v = {1, 2, 3, 4, 5};  // 调用 `vector(initializer_list<T> il)` 构造函数

其代码为：

my_vector(initializer_list<T> il)
{
	reserve(il.size());
	for (auto& e : il)
	{
		push_back(e);
	}
}

 2. 范围构造函数，它接收两个迭代器，表示要复制的元素的范围，如

std::vector<int> source = {1, 2, 3, 4, 5};
my_vector<int> v(source.begin(), source.end());  // 调用 `vector(InputIterator first, InputIterator last)` 构造函数

其代码为：

template <class InputIterator>        
my_vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

 6.2 析构函数

~my_vector()
{
	delete[] _start;
	_start = _finish = _endofstorage = nullptr;
}

6.3 拷贝构造函数

my_vector(const my_vector<T>& v)
{
	reserve(v.capacity());
	for (auto& e : v)
	{
		push_back(e);
	}
}

6.3 = 的重载

注意这里的传入参数并没有使用引用，这也是可以直接使用 swap 的原因：

my_vector<T>& operator=(my_vector<T> v)
{
	swap(v);
	return *this;
}