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

这篇具有很好参考价值的文章主要介绍了【C++】:STL源码剖析之vector类容器的底层模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】:STL源码剖析之vector类容器的底层模拟实现,C/C++,c++,stl

📚1.vector接口总览

namespace lyp
{
	//模拟实现vector
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		//默认成员函数
		vector();                                           //构造函数
		vector(size_t n, const T& val);                     //构造函数
		template<class InputIterator>                      
		vector(InputIterator first, InputIterator last);    //构造函数
		vector(const vector<T>& v);                         //拷贝构造函数
		vector<T>& operator=(const vector<T>& 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<T>& v);

		//access
		T& operator[](size_t i);
		const T& operator[](size_t i)const;

	private:
		iterator _start;        //指向容器的头
		iterator _finish;       //指向有效数据的尾
		iterator _endofstorage; //指向容器的尾
	};
}

【C++】:STL源码剖析之vector类容器的底层模拟实现,C/C++,c++,stl

📚2.vector模拟实现

📚构造函数

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

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

📚拷贝构造函数

/*vector(const vector<T>& 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<T>& v)
{
	reserve(v.capacity());
	for (const auto& e : v)
	{
		push_back(e);
	}
}
void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstorage, v._endofstorage);
}

// v1 = v3
vector<T>& operator=(vector<T> 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<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstorage, v._endofstorage);
}

// v1 = v3
vector<T>& operator=(vector<T> 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 < size 时,直接将 _finish = _start + n (将有效数据长度缩小)即可
(2).当 size < n <= capacity 时,我们将有效数据的长度增加到 n,增加出来的有效数据内容是val
(3).当 n > capacity时,先调用上面的 reserve 函数进行增容,再将有效数据的长度增加到 n,增加出来的有效数据内容是val

void resize(size_t n,const T& val = T())
{
	// 第一种 n < size()
	if (n < size())
	{
		_finish = _start + n;
	}
	// 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 <= _finish);

	if (_finish == _endofstorage)
	{
		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;
}

📚剩下两三个接口我们在下一篇博客和List类的底层模拟实现给大家补上

📚STL中的vector类源码简单剖析含小部分注释

vector的数据结构:一个线性连续空间
下面介绍vector的3个数据结构:
start:表示目前使用空间的头
finish:表示目前使用空间的尾
end_of_storage:表示目前可用空间的尾

template <class T, class Alloc = alloc>
class vector {
...
protected:
    iterator start; //表示目前使用空间的头
    iterator finish; //表示目前使用空间的尾
    iterator end_of_storage; //表示目前可用空间的尾
    ...
};

说明:为了降低空间配置时的速度成本,vector实际配置的大小可能比客户端需求量更大一些,以备将来可能的扩充。这便是容量的概念。也就是说,一个vector的容量永远大于或等于其大小。一旦容量等于大小,下次再新增元素时就需要新开辟一块空间。如下图所示
【C++】:STL源码剖析之vector类容器的底层模拟实现,C/C++,c++,stl
运用start、finish、end_of_storage三个迭代器,vector提供了首尾标示、大小、容量、空容器判断、注标[]运算符、最前端元素值、最后端元素值…等机能,如下:

template <class T, class Alloc = alloc>
class vector {
...
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); }
    ...
};

📚vector的构造与内存管理(constructor、push_back)

template <class T, class Alloc = alloc>
class vector {
protected:
    // simple_alloc<>见前面文章介绍
    typedef simple_alloc<value_type, Alloc> data_allocator;
    ...
};
//构造函数,允许指定vector大小n和初值value
vector(size_type n, const T& value) { 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;
}

push_back()函数:当我们以push_back() 将新元素安插入于vector尾端时,该函式首先检查是否还有备用空间,如果有就直接在备用空间上建构元素,并调整迭代器finish,使vector变大。如果没有备用空间了,就扩充空间(重新配置、搬移数据、释放原空间)。push_back()原型如下:

void push_back(const T& x) {
    if (finish != end_of_storage) { //还有备用空间
        construct(finish, x); //全局函式
        ++finish; //调整水位高度
    }
    else //已无备用空间
        insert_aux(end(), x); // vector member function,见下
}
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
    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;
    }
}

源码就给大家分享这么多 源码不是我们要关注的 简单了解即可

【C++】:STL源码剖析之vector类容器的底层模拟实现,C/C++,c++,stl文章来源地址https://www.toymoban.com/news/detail-759984.html

到了这里,关于【C++】:STL源码剖析之vector类容器的底层模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】STL——vector 深度剖析 及 模拟实现

    这篇文章我们来学习一下STL里面的vector,它属于STL中容器的一员,我们先来学习一下它的使用,然后,我们也会对vector进行一个深度的剖析和模拟实现。 1.1 vector的介绍 vector的文档介绍 vector 是表示大小可以更改的数组的序列容器: 其实大家可以认为 vector就是我们之前数据结

    2024年02月05日
    浏览(47)
  • 【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 和string的学习不同 vector即要掌握它的用法 更要会自己去实现一个vector 本章重点: 熟悉STL库中vector的接口函数 自己实现一个简易vector类 本

    2024年02月11日
    浏览(38)
  • C++ —— STL容器【vector】模拟实现

    本章代码gitee仓库:vector模拟实现、vector源码 看源码发现 vector 是类模板定义的,成员是采用迭代器进行管理 当涉及到容器类时,通常有一些关键函数,如构造函数、析构函数和拷贝构造函数,它们负责初始化容器对象、销毁对象和进行对象的拷贝等 这里注意拷贝构造要实现

    2024年02月16日
    浏览(46)
  • C++ stl容器list的底层模拟实现

    目录 前言: 1.创建节点 2.普通迭代器的封装 3.反向迭代器的封装 为什么要对正向迭代器进行封装? 4.const迭代器 5.构造函数 6.拷贝构造 7.赋值重载 8.insert 9.erase 10.析构 11.头插头删,尾插尾删 12.完整代码+简单测试 总结: 1.创建节点 注意给缺省值,这样全缺省就会被当做默认

    2024年04月23日
    浏览(44)
  • C++ stl容器string的底层模拟实现

    目录 前言: 1.成员变量 2.构造函数与拷贝构造函数 3.析构函数 4.赋值重载 5.[]重载 6.比较关系重载 7.reserve 8.resize 9.push_back,append和重载+= 10.insert 11.erase 12.find 14.迭代器 15.流插入,流提取重载 16.swap 17.c_str 18.完整代码+测试 总结: 1.成员变量 首先注意的就是_str,不能是const类型

    2024年04月23日
    浏览(44)
  • 深入篇【C++】手搓模拟实现list类(详细剖析底层实现原理)&&模拟实现正反向迭代器【容器适配器模式】

    1.一个模板参数 在模拟实现list之前,我们要理解list中的迭代器是如何实现的。 在vector中迭代器可以看成一个指针,指向vector中的数据。它的解引用会访问到具体的数据本身,++会移动到下一个数据位置上去,这些都是因为vector具有天生的优势:空间上是连续的数组,这样指

    2024年02月15日
    浏览(46)
  • C++入门之stl六大组件--List源码深度剖析及模拟实现

    文章目录 前言 一、List源码阅读 二、List常用接口模拟实现 1.定义一个list节点 2.实现一个迭代器 2.2const迭代器 3.定义一个链表,以及实现链表的常用接口 三、List和Vector 总结 本文中出现的模拟实现经过本地vs测试无误,文件已上传gitee,地址:list: 模仿实现stl的list - Gitee.com 首

    2024年02月13日
    浏览(51)
  • C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现

    目录 前言 一、stack的介绍和使用 1.stack的介绍 2.stack的使用 3.stack的模拟实现 二、queue的介绍和使用 1.queue的介绍 2.queue的使用 3.queue的模拟实现 三、priority_queue的介绍和使用 1.priority_queue的介绍 2.priority_queue的使用 3.priority_queue的模拟实现 3.1解决一个topK问题 四、容器适配器 1

    2024年02月14日
    浏览(49)
  • 【C++庖丁解牛】vector容器的简易模拟实现(C++实现)(最后附源码)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 我们前面介绍了vector容器的概念以及对其基本使用进行了介绍,如果你在这里不知道vector是什么以及不知

    2024年03月14日
    浏览(45)
  • 【C++STL】模拟实现vector容器

    本文带你进入vector的模拟实现,对于vector,是我们深入学习STL的必要途径。 根据库的实现方式,成员函数如下: c++11开始可以对成员变量使用缺省值,在这里我们可以使用缺省值。 size的大小为_finish - _start capacity的大小为_end_of_storage - _start 该函数的作用是:扩容。 思路:

    2024年02月16日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包