模板类模拟实现STL中Vector容器类

2017-04-01 14:32 阅读 875 次 评论 0 条

Vector的存储结构

模板类vector类似于strig类,也是一种动态数组,即在运行阶段设置vector对象的长度,可在末尾或者中间插入新数据,基本上,它是使用new创建动态数组的替代品。

Vector实现的顺序存储的结构对于尾删和尾插是比较方便的,只需要改动最后一个元素即可,但是既然是顺序存储,其地址也必然是连续的,当我们对其进行头删或者头插的时候,就需要将n-1个节点的位置都进行移动,随之带来的时间复杂度为O(n),而我们的链表的时时间复杂度是O(1),因此Vector的局限性不容乐观。

除了使用下标来访问vector对象的元素外,标准库还提供了另一种检测元素的方法:使用迭代器(iterator)。迭代器是一种允许程序员检查容器内元素,并实现元素遍历的数据类型。

标准库为每一种标准容器(包括vector)定义了一种迭代器类型。迭代器类型提供了比下标操作更一般化的方法:所有的标准库容器都定义了相应的迭代器类型,而只有少数的容器支持下标操作。因为迭代器对所有的容器都适用,现代C++程序更倾向于使用迭代器而不是下标操作访问容器元素,即使对支持下标操作的vector类型也这样。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:模板类模拟实现STL中Vector容器类 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情