欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL 源码分析-Vector

程序员文章站 2022-07-12 22:51:02
...

最近在学习STL源码,想对经常使用的标准容器了解其底层实现原理,知其然知其所以然,虽然无法达到侯捷大师说的“源码底下,了无秘密”的境界,但是向源码学习,了解的会更加深入。本文章是笔者学习《stl 源码剖析》的学习笔记,因个人的水平有限,难免会有理解不当的地方。如有理解错误,欢迎指出改正。

Vector描述

Vector是一种序列式容器,与Array非常相似,唯一的差别是空间运用的灵活性,Array是静态空间,大小定义后就不能改变,vector是动态空间,它的内部机制会自行扩充空间以容纳新元素。

Vector数据结构

Vector内部是三个迭代器指针实现对空间操作,start指向目前使用空间的头,finish指向目前空间的尾,end_of_storage表示目前可用的空间的尾。因vector是线性连续空间,所以vector的迭代器是一种普通指针实现的。

template <class T, class Alloc = std::allocator<T> >
class Vector
{
public:
	typedef T            value_type;
	typedef value_type*  point;
	typedef value_type*  itertor;
private:
	itertor start;
	itertor finish;
	itertor end_of_storage;
};

Vector接口实现

Vector的几种构造方式

Vector() :start(0), finish(0), end_of_storage(0) {}
Vector(size_type n) { fill_initialize(n, 0); }
Vector(size_type n, const T& value) { fill_initialize(n, value); }
Vector(const Vector<T, Alloc>& x)
{
	start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
	finish = start + (x.end() - x.begin());
	end_of_storage = finish;

}
Vector(const iterator first, const iterator last)
{
	size_type n = 0;
	distance(first, last, n);
	start = allocate_and_copy(n, first, last);
	finish = start + n;
	end_of_storage = finish;
}

常用的几个接口实现

1.start()获取vector的首元素地址

         iterator begin()const {return start;}

2.end()获取vector最后一个元素的下一个地址

        iterator end()const {return finish;}

3.获取vector大小

         size_type size() {return size_type(end() - begin());}

4.获取vector开辟容量大小

         size_type capacity() {return size_type(end_of_storage- begin());}

5.判断vector是否为空

         bool empty(){return (begin() == end());}

6.根据索引获取对象

         reference operator[](size_type n){return *(begin()+n);}

7.往vector里添加新的对象,主要考虑是否需要扩容,vector内部扩容机制是按照两倍空间扩容。

void push_back(const T& x)
{
	if (finish != end_of_storage)
	{
		construct(finish, x);
		finish++;
	}
	else
	{
		insert_aux(end(), x);
	}
}
template<class valuetype>
void insert_aux(iterator position, const valuetype & x)
{
	if (finish != end_of_storage)//还有备用空间
	{
		construct(finish, *(finish - 1));
		++finish;
		T x_copy = x;
		std::copy_backward(position, finish - 2, finish - 1);
		*position = x_copy;
	}
	else//已无备用空间
	{
		const size_type old_size = size();
		const size_type len = old_size != 0 ? 2 * old_size : 1;
		iterator new_start = std::allocator<T>().allocate(len);
		iterator new_finish = new_start;
		try
		{
			//将原vector内容拷贝
			new_finish = std::uninitialized_copy(start, position, new_start);
			construct(new_finish, x);
			++new_finish;
			new_finish = std::uninitialized_copy(position, finish, new_finish);
		}
		catch (const std::exception&)
		{

		}
		catch (...)
		{

		}

		deallocate();
		start = new_start;
		finish = new_finish;
		end_of_storage = new_start + len;
	}
}

8. 在vector某一位置插入元素。源码中分三种情况进行考虑。① 空间足够时,插入位置后现有元素的个数大于需要插入的元素的个数;②空间足够时,插入点后元素的个数小于等于需要插入元素的个数;③备用空间小于插入个数,需要考虑重新开辟新空间,将数据进行拷贝

void insert(iterator position, size_type n, const T& x)
{
	if (n < 1)return;
	//当n!=0时,才进行以下所有操作
	if (size_type(end_of_storage - finish) >= n)//剩余的空间可以插入新值
	{
		T x_copy = x;
		//计算插入点后元素的个数
		const size_type elems_after = finish - position;
		iterator old_finish = finish;
		if (elems_after > n)
		{
			//如果插入点后现有元素的个数“大于”需要插入元素的个数
			std::uninitialized_copy(finish - n, finish, finish);
			finish += n;//尾端后移
			std::copy_backward(position, old_finish - n, old_finish);
			std::fill(position, position + n, x_copy);
		}
		else
		{
			//如果插入点后现有元素的个数“小于等于”需要插入元素的个数
			std::uninitialized_fill_n(finish, n - elems_after, x_copy);
			finish += (n - elems_after);
			std::uninitialized_copy(position, old_finish, finish);
			finish += elems_after;
			std::fill(position, old_finish, x_copy);
		}
	}
	else//备用空间小于插入个数,需要重新开辟新空间
	{
		const size_type old_size = size();
		const size_type len = old_size + std::max(old_size, n);
		iterator new_start = std::allocator<T>().allocate(len);
		iterator new_finish = new_start;
		new_finish = std::uninitialized_copy(start, position, new_start);
		new_finish = std::uninitialized_fill_n(new_finish, n, x);
		new_finish = std::uninitialized_copy(position, finish, new_finish);
		//析构原始对象
		//destory(start, finish);
		deallocate();
		//调整标记位
		start = new_start;
		finish = new_finish;
		end_of_storage = start + len;
	}
}

9、clear()清空vector里面元素

         void clear() { erase(start, finish); }

以上是介绍vector的几个基本的api实现方法,后续可能会增加些其他接口。

测试代码

#include <iostream>
#include <xmemory>
#include<string>
#include "stl_vector.h"

int main()
{
	// 使用分配器申请内存
	int *p = nullptr;
	std::allocator<int> alloca1;
	p = alloca1.allocate(1);
	*p = 4;
	alloca1.deallocate(p, 1);
	// test STL::Vector , test int
	STL::Vector<int>vecInt0;
	std::cout <<"VecInt0 size and capacity:"<< vecInt0.size() << "  "<<vecInt0.capacity() << std::endl;
	for (size_t i = 1; i < 6; i++)
	{
		vecInt0.push_back(i);
		std::cout << "VecInt0 size and capacity:" << vecInt0.size() << "  " << vecInt0.capacity() << std::endl;
	}
	vecInt0.insert(&vecInt0[2], 3, 8);
	for (auto iter = vecInt0.begin(); iter != vecInt0.end(); iter++)
	{
		std::cout << *iter << " ";
	}
	std::cout<<std::endl;
	vecInt0.clear();
	std::cout << "VecInt0 size and capacity:" << vecInt0.size() << "  " << vecInt0.capacity() << std::endl;
	return 0;
}

本文只是介绍vector相关api的实现,不会介绍开辟内存的空间适配器,本文使用的是std::allocator空间适配器,和stl源码解析中用的适配器不太一样。

push/insert时间复杂度:

源代码里讲到vector当容量空间不够时,会进行2倍空间动态扩容,这样设计效率是不是很低呢?其实不是的。我们可以分析下时间复杂度,即每次花费o(n)时间进行一次扩容,vector的容量就会加倍,也就是说每次的o(n)的扩容操作,都会跟着n-1次的o(1)的insert或push操作。因此,在这种连续的操作下,均摊的时间复杂度是o(1)。