【C++】：STL源码剖析之vector类容器的底层模拟实现

📚1.vector接口总览

namespace lyp
{
	//模拟实现vector
	template
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		//默认成员函数
		vector();                                           //构造函数
		vector(size_t n, const T& val);                     //构造函数
		template                      
		vector(InputIterator first, InputIterator last);    //构造函数
		vector(const vector& v);                         //拷贝构造函数
		vector& operator=(const vector& v);           //赋值运算符重载函数
		~vector();                                          //析构函数
		//iterator
		iterator begin();
		iterator end();
		const_iterator begin()const;
		const_iterator end()const;
		//capacity
		size_t size()const;
		size_t capacity()const;
		void reserve(size_t n);
		void resize(size_t n, const T& val = T());
		bool empty()const;
		//modifiers
		void push_back(const T& x);
		void pop_back();
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void swap(vector& v);
		//access
		T& operator[](size_t i);
		const T& operator[](size_t i)const;
	private:
		iterator _start;        //指向容器的头
		iterator _finish;       //指向有效数据的尾
		iterator _endofstorage; //指向容器的尾
	};
}

📚2.vector模拟实现

📚构造函数

构造一个空vector size和capacity为0 将_start _finish _endofstorage 都置为空指针即可

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

📚拷贝构造函数

/*vector(const vector& v)
{
	_start = new T[v.capacity()];
	memcpy(_start, v._start, v.size()* sizeof(T));
	_finish = _start + v.size();
	_endofstorage = _start + v.capacity();
}*/
// v2(v1)
vector(const vector& v)
{
	reserve(v.capacity());
	for (const auto& e : v)
	{
		push_back(e);
	}
}
void swap(vector& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstorage, v._endofstorage);
}
// v1 = v3
vector& operator=(vector v)
{
	swap(v);
	return *this;
}

传统写法 :

1). 新开辟一块和 v 同样容量的空间，更新 _start， _finish， _endofstorage

2). 将 v 中的数据拷贝到新开辟的空间中

注意 : 不要使用memcpy函数拷贝数据，如果数据是内置类型或浅拷贝的自定义类型，使用memcpy是没有什么问题的，但如果数据是需要深拷贝的自定义类型(string)，问题就出现了，拷贝的数据和源数据指向同一块空间

现代写法 :

使用范围for进行遍历，变量e是v中元素的拷贝，如果v中元素是需要深拷贝的自定义类型，会调用拷贝构造函数构造e，从而使e和v中元素所指向的空间不一样 (auto& e : v 也可以，因为push_back在实现的时候还会调用深拷贝类型的赋值运算符重载)

void push_back(const T& x)
{
	if (_finish == _endofstorage)
	{
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
	}
	*_finish = x;
	++_finish;
}

📚赋值运算符重载

传统写法

1).释放原空间，新开一块容量和v一样大的空间，更新_start，_finish， _endofstorage

2).将v中的数据拷贝到新空间中

注意 : 不能使用memcpy进行拷贝

现代写法

1).调用拷贝构造函数生成tmp对象

2).分别交换tmp和this的_start，_finish， _endofstorage

void swap(vector& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstorage, v._endofstorage);
}
// v1 = v3
vector& operator=(vector v)
{
	swap(v);
	return *this;
}

📚析构函数

1). 判断容器是否为空，若为空无需析构

2). 若不为空，将空间释放掉，_start，_finish， _endofstorage置为空指针

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

📚iterator

begin/end

begin()返回第一个元素的地址，end()返回最后一个元素下一位置的地址，为了能够让const对象调用，加入const版本的begin()和end()

iterator begin()

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

📚size

返回容器中有效数据的个数，用 _finish - _start 即可

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

📚capacity

返回容器的容量，用_endofstorage - _start 即可

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

📚reserve

1). 当n大于对象当前的capacity时，将capacity扩大到n或大于n。

2). 当n小于对象当前的capacity时，什么也不做。

实现步骤

1). 新开辟一块空间，若容器为空，将_start，_finish指向新开辟空间的首元素地址， _endofstorage指向新开辟空间的最后一个元素下一个位置

2). 若容器不为空，将数据拷贝到新空间，释放掉旧空间，更新_start，_finish， _endofstorage的位置

注意 : 将数据拷贝到新空间，仍然不能用memcpy函数，因为对于需要深拷贝的自定义类型，使用memcpy函数以后，新开辟空间里的元素和原空间里的元素所指向的内存空间是一样的，当旧空间被释放时，会调用自定义类型的析构函数，从而使得新开辟空间里的元素指向的内存空间也被释放掉了

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

📚resize

1). 当 n

(2).当 size

void resize(size_t n,const T& val = T())
{
	// 第一种 n  size()
	else
	{
		// 增容
		if (n > capacity())
			reserve(n);
		// 填充数据val
		size_t count = n - size();
		while (count--)
		{
			*_finish = val;
			++_finish;
		}
	}
}

📚empty

判断 size() == 0 即可

bool empty()const
{
	return size() == 0;
}

📚pop_back

尾删时，首先要判断容器是否为空，若为空，则断言报错，不为空，_finish-- 即可

void pop_back()
{
	assert(size() > 0);
	--_finish;
}

📚insert

1). 容量不够，先增容，增容之前先记录下 pos - _start 的值，否则增容之后，pos 还指向原来已经被释放的空间

2). 将 pos 位置往后的数据往后挪动一位，在pos位置插入值val

void insert(iterator pos, const T& x)
{
	assert(pos >= _start && pos 
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}
	memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
	*pos = x;
	++_finish;
}

...
protected:
    iterator start; //表示目前使用空间的头
    iterator finish; //表示目前使用空间的尾
    iterator end_of_storage; //表示目前可用空间的尾
    ...
};

...
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const { return size_type(end() - begin()); }
    size_type capacity() const {
        return size_type(end_of_storage - begin()); 
    }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }
    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
    ...
};

protected:
    // simple_alloc fill_initialize(n, value); }
// 充填并予初始化
void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}
// 配置而后充填
iterator allocate_and_fill(size_type n, const T& x) {
    iterator result = data_allocator::allocate(n); //配置n个元素空间
    uninitialized_fill_n(result, n, x); //全局函式，会根据第1个参数类型特性决定使用算法fill_n()或反复调用construct()来完成任务
    return result;
}

    if (finish != end_of_storage) { //还有备用空间
        construct(finish, x); //全局函式
        ++finish; //调整水位高度
    }
    else //已无备用空间
        insert_aux(end(), x); // vector member function，见下
}

    if (finish != end_of_storage) { //还有备用空间
        // 在备用空间起始处建构一个元素，并以 vector 最后一个元素值为其初值。
        construct(finish, *(finish - 1));
        // 调整水位。
        ++finish;
        T x_copy = x;
        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;
        // 以上配置原则：如果原大小为0，则配置 1（个元素大小）
        // 如果原大小不为 0，则配置原大小的两倍，
        // 前半段用来放置原数据，后半段准备用来放置新数据
        iterator new_start = data_allocator::allocate(len); // 实际配置
        iterator new_finish = new_start;
        try {
            // 将原 vector 的内容拷贝到新vector
            new_finish = uninitialized_copy(start, position, new_start);
            // 为新元素设定初值 x
            construct(new_finish, x);
            // 调整水位
            ++new_finish;
            // 将原vector的备用空间中的内容也忠实拷贝过来
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch(...) {
            // "commit or rollback" semantics.
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }
        //析构并释放原vector
        destroy(begin(), end());
        deallocate();
        // 调整迭代器，指向新vector
        vector start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}