网站如何做友情链接,湖南网站推广营销设计,wordpress删除多余图片,途牛网网站是哪家公司做的前言#xff1a;
在C标准库#xff08;STL#xff09;中#xff0c;vector容器是最常见使用的动态数组。它结合了链表与数组的优点#xff0c;提供了灵活的大小调整与高效的随机访问。本文将简单的对vector容器进行介绍并且对vector容器简单的模拟实现。
一、vector的文… 前言
在C标准库STL中vector容器是最常见使用的动态数组。它结合了链表与数组的优点提供了灵活的大小调整与高效的随机访问。本文将简单的对vector容器进行介绍并且对vector容器简单的模拟实现。
一、vector的文档介绍 1. vector 是表示可变大小数组的序列容器。 2. 就像数组一样 vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 3. 本质讲 vector 使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 4. vector 分配空间策略 vector 会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 5. 因此 vector 占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 6. 与其它动态序列容器相比 deque, list and forward_list vector 在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list 和 forward_list统一的迭代器和引用更好。 二、模拟实现的简单准备工作
在模拟实现之前我们需要明确我们想要实现的基本接口。
根据https://cplusplus.com/reference/vector/vector/cplusplus网站的信息我们可以知道vector虽然相对于string简化很多但仍然有许多的接口既然是简单的模拟实现我们只需要实现最基本常用的接口就行了。
另外由于stl库里自带系统的vector类模板为了区分我们可以在自己的命名空间内完成对vector模板代码的编写。
三、模拟实现
1、vector的类参数
根据vector文档可知本质上vector功能的正常运行大多都离不开三个指针分别是_start,_finish,_endOfStorage。这三个指针分别指向vector的开头实际存储数据的末尾后一位以及开辟的空间大小末尾通过类函数成员对这三个参数的使用来实现了不同的功能。
于是我们首先要定义的就是vector类模板的成员参数注意应该在private下定义。
namespace MyVector
{templateclass Tclass vector{private:T* _start;T* _finish;T* _endOfStorage;};
}
2、类的迭代器
我们通过对vector源代码的剖析发现vector迭代器实际上是一个指针于是我们可以用typedef重命名来定义我们vector的迭代器并且为了美观我们顺便把类的参数类型也修改为迭代器iterator。
注意迭代器有两种类型一种是可以修改参数的另外一种是不能修改参数的“常量”迭代器。定义我们应该重命名两个迭代器。
namespace MyVector
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterater;private:iterator _start;iterator _finish;iterator _endOfStorage;};
}
3、begin(),end()的实现
有了迭代器自然会产生操控迭代器位置的一系列接口beginend应该是最常见的两个接口分别返回容器的首位置以及实际存储元素位置的下一位。
注意这两个接口应该都有对应的返回常量迭代器的重载版本。
iterator begin()
{return _start;
}const_iterator begin() const
{return _start;
}iterator end()
{return _finish;
}const_iterator end() const
{return _finish;
}
4、sizecapacity的实现
我们用size返回此时存储元素的多少capacity返回此时开辟的空间大小。
size_t size()
{return _finish - _start;
}size_t capacity()
{return _endOfStorage - _start;
}
5、reservepush_back,pop_back的实现
根据算法的基本原理push_back实际上本身就是检查空间是否满了满了就先扩容随后在确认空间足够的情况下 在尾部插入元素的接口。
避免频繁扩容的问题我们使用 reserve 预分配足够的内存。
void reserve(size_t n)
{if (n capacity()){size_t oldsize size();iterator tmp new T[n];if (_start){//这里不能使用memcpy会引发浅拷贝的一些问题for (int i 0; i oldsize; i){tmp[i] _start[i];}delete[]_start;}_strat tmp;_finish _start oldsize;_endOfStorage _start n;}
}void push_back(const T x)
{if (_endOfStorage _finish){size_t newcapacity capacity() 0 ? 4 : 2 * capacity();reserve(newcapacity);}*finish x;_finish;
}void pop_back()
{assert(size() 0);_finish--;
}
6、构造函数赋值重载拷贝构造函数析构函数swap的实现
在大部分情况下编译器默认生成的构造函数就足够我们使用所以我们只需要实现拷贝构造与赋值重载函数就行了。
但是我们注意到如果我们手动写的拷贝构造与赋值重载编译器就不会自动生成默认的拷贝函数为了防止这个问题我们需要用default来强制让编译器生成。
在写赋值重载函数的时候我们面临这一个抉择我们可以实现现代写法swap高效的实现赋值重载所以我们就需要先实现一个swap函数
vector default;//强制生成构造函数vector(const vectorT v)//拷贝构造
{reserve(v.size());for (auto it : v){push_back(it);}
}vectorT operator (vectorT v)
{swap(v);return *this;
}~vector()
{delete[]_start;_start _finish _endOfStorage nullptr;
}void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);
}
7、各种自定义类型迭代器的构造函数实现
我们发现vector也支持其他自定义类型的迭代器传参来构造。
为了接受不同的类型所以我们又要使用模板来实现一个函数模板
templateclass InputIterator
vector(InputIterator first, InputIterator last)//类模板中的函数模板,支持各种自定义类型的迭代器的构造
{while (first ! last){push_back(*first);first;}
}
8、[],resize的实现
为了向数组一样支持随机访问我们需要对[]进行重载。
由于reserve()只修改capacity大小不修改size大小所以我们需要实现一个resize函数既修改capacity大小也修改size大小。
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}const T operator[](size_t pos)
{assert(pos size());return _start[pos];
}void resize(size_t n, const T value T())//调用T类型的默认默认构造函数
{if (n size()){_finish _start n;}if (n size()){reserve(n);while (_finish ! _start n){push_back(value);}}
}
9、erase与insert的实现
erase与insert是vector容器接口中比较难实现的部分不仅要检查是否越界我们还要格外注意迭代器的失效问题当然为了解决迭代器的失效我们需要返回新的迭代器并在原来的使用中让原迭代器接受返回的迭代器 iterator insert(iterator pos, const T x){assert(pos _finish);assert(pos _start);if (_finish _endOfStorage){size_t oldsize pos - _start;size_t newcapacity capacity() 0 ? 4 : 2 * capacity();reserve(newcapacity);pos _start oldsize;}iterator i _finish - 1;while (i pos){*(i 1) *i;i--;}*pos x;_finish;return pos;}iterator erase(iterator pos){assert(pos _finish);assert(pos _start);iterator tmp pos 1;while (tmp _finish){*(tmp - 1) *tmp;tmp;}--_finish;return pos;}四、结语
Vector 容器在 C 编程中扮演着重要角色其灵活性和高效性使其成为处理动态数组的首选。通过深入理解 vector 的机制和最佳实践可以更高效地进行编程充分发挥 C 的强大功能。
希望本文对你深入了解 C 中的 vector 容器有所帮助
