佟年为韩商言做的网站,搜狗推广开户,郑州网站设计,西安米德建站下面是简单的实现vector的功能#xff0c;没有涉及使用内存池等复杂算法来提高效率。
一、vector的概述
#xff08;一#xff09;、抽象数据类型定义
容器#xff1a;向量#xff08;vector#xff09;vector是表示大小可以变化的数组的序列容器。像数组一样#xf… 下面是简单的实现vector的功能没有涉及使用内存池等复杂算法来提高效率。
一、vector的概述
一、抽象数据类型定义
容器向量vectorvector是表示大小可以变化的数组的序列容器。像数组一样向量对其元素使用连续的存储位置这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素并且与数组中的元素一样高效。但与数组不同的是它们的大小可以动态变化它们的存储由容器自动处理。 模板类 templateclass T 操作 一、构造函数 vector(); 默认构造 vector(size_t n,const T val T()); 用n个val进行填充初始化 vector(int n, const T val T()); 防止vector(int,int)与下面的模板函数发生歧义 templateclass InputIterator vector(InputIterator first, Inputiterator last); 迭代器区间初始化 vector(std::initializer_list list); 用初始化列表进行初始化 vector(const vectorT v) 拷贝构造函数 vectorT operator(const vectorT v); 赋值构造 ~vector(); 析构函数 二、迭代器 iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; 三、容量 size_t size() const; 返回当前容器存储的数据个数 size_t capacity() const; 返回当前容器的容量大小 void resize(size_t n); 改变容器数据个数 bool empty() const; 判断当前容器是否为空 void reserve(size_t n); 改变容量大小 四、访问数据 T operator[](size_t n); 可读可写 const T operator[](size_t n) const; 只可读 五、修改操作 void push_back(const T val); 尾插操作 void pop_back(); 尾删操作 iterator insert(iterator pos, const T x); 在指定位置插入 iterator erase(iterator pos); 指定位置删除 void swap(vectorT v); 交换两个vector容器的数据
二、成员变量
templateclass T
class vector
{
public://vector的迭代器可以为原生指针typedef T* iterator;typedef const T* const_iterator;
private:iterator _start nullptr;//指向第一个数据的迭代器iterator _finish nullptr;//指向最后一个有效数据的后一个位置iterator _endOfStorage nullptr;//指向数组末尾的后一个位置
}; 这里的迭代器就是我们的原生指针T*它的私有成员变量就和线性表一样要存储数据的起始位置的指针、数据的有效数据的个数、存储容量等。这里直接全部定义成指针来维护容器的数据数组_start指向数组的起始位置_finish指向有效数据个数的后一个的位置当我们将这两个指针相减_finish - _start 就能得到数据的有效数据个数了。最后一个endOfStorage就是指向数组的末尾的下一个位置(虽然越界但不解引用就没事),当我们拿_endOfStorage - _start 就得到了这段空间的容量个数。 注意我们的每个构造函数在一开始时都要把迭代器置为空指针而我们在声明迭代器时顺便给上初始值这样会更好以免忘记初始化带来不必要的麻烦。
迭代器维护的空间示意图: 二、具体实现 我们不按上面的函数声明的顺序来依次定义函数我们按照从易到难的顺序一点一点实现其成员函数的定义每个阶段测试一下。
一、默认构造、析构、迭代器、尾插、尾删、下标访问
1、默认构造、析构
//默认构造
vector() :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) { ; } 因为是空容器所以三个指针都初始化为nullptr。
//析构
~vector()
{delete[] _start;_start _finish _endOfStorage nullptr;
} 删除动态分配的空间后记得将指针置为空因为析构是可以手动调用的。
2、迭代器
//迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; } 两组迭代器分别构成重载。 注意重载不是因为返回值的不同而是其参数不同一个是this另一个是const this的指针。
3、尾插和尾删操作 注意:需要对容器满时进行扩容处理。
1、辅助其扩容的函数
empty()判断容器是否为空
bool empty() const { return (_finish - _start) 0; }
size()返回容器的有效数据个数
size_t size() const { return _finish - _start; }
capacity()返回容器的容量
size_t capacity() const { return _endOfStorage - _start; }
reserve()扩容操作
void reserve(size_t n)//改变容量大小
{//如果n为0,默认给4个空间n n 0 ? 4 : n;//不允许缩容if (n capacity())return;//扩容size_t nSize size();//保存有效数据个数iterator itTem new T[n];//拷贝到新数组for (int i 0; i nSize; i){*(itTem i) *(_start i);}delete[] _start;_start itTem;_finish _start nSize;_endOfStorage _start n;
}
2、尾插、尾删
//修改操作
void push_back(const T val)//尾插操作
{//判断容器空间是否足够if (size() capacity()){size_t newCapacity capacity() * 2;//两倍扩容//扩容reserve(newCapacity);//std::cout capacity() ;}//尾插*_finish val;_finish;
}
void pop_back()//尾删操作
{if (!empty())_finish--;
}
4、下标访问 //访问操作T operator[](size_t n){//防止越界访问assert(n 0 n size());return *(_start n);}const T operator[](size_t n) const{//防止越界访问assert(n 0 n size());return *(_start n);} 注意构成函数重载的是参数不是返回值。
5、代码测试
void test1()
{const int N 10;//测试数据的个数MySpace::vectorint v1;for (int i 0; i N; i){v1.push_back(i 1);}//手动使用迭代器遍历MySpace::vectorint::iterator it1 v1.begin();while (it1 ! v1.end()){cout *it1 ;it1;}cout endl;//数组方式访问for (int i 0; i N; i)cout v1[i] ;cout endl;//测试尾删for (int i 0; i N 2; i)//2是为了测试一下删空容器{cout endl;for (auto e : v1)//测试范围for{cout e ;}v1.pop_back();}
}
运行结果: 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 1 2 3 4 5 6 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1 二、其余的构造函数
1、迭代器区间和参数初始化表初始化
迭代器区间初始化构造函数 因为迭代器的类型可能不同不一定所有的迭代器的类型都是指针有可能是自定义类型。所以用模板函数。注意迭代器不一定都支持加减操作所以用迭代器加减的方式获得迭代器区间的大小是不安全的做法。
//迭代器区间初始化
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{//这里不可以像指针那样直接 last - first 算出数据个数//因为有的迭代器是不支持加减的//可以采取以下方法先算大小防止频繁扩容导致效率降低size_t n 0;InputIterator itFirst first;InputIterator itLast last;while (itFirst ! itLast){n;itFirst;}reserve(n);while (first ! last){push_back(*first);first;}
}
参数初始化列表初始化构造函数
//用参数初始化表初始化
vector(std::initializer_listT list)
{ reserve(list.size());for (auto e: list){push_back(e);}
}
2拷贝构造函数 //拷贝构造vector(const vectorT v){reserve(v.capacity());for (auto e : v){push_back(e);}}
3交换两个容器和赋值构造函数
实现交换容器的函数swap()来辅助赋值构造函数的实现
void swap(vectorT v)//交换两个的数据
{std::swap(_start, v._start);std::swap(_finish,v._finish);std::swap(_endOfStorage, v._endOfStorage);
}
赋值构造函数
//赋值构造
vectorT operator(const vectorT v)
{//复用拷贝构造函数vectorT tem(v);swap(tem);return *this;
}
4填充初始化 //填充初始化vector(size_t n, const T val T())//用n个val进行初始化{reserve(n);for (int i 0; i n; i){push_back(val);}}//用来防止调用vector(int,int)时发生歧义//发生歧义的函数:vectorInputIterator InputIteratorvector(int n, const T val T()){reserve(n);for (int i 0; i n; i){push_back(val);}}
5、代码测试
void test2()
{const int N 8;MySpace::vectorint v1;for (int i 0; i N; i){v1.push_back(i 1);}for (auto e : v1){cout e ;}cout endl;//测试迭代器区间初始化构造MySpace::vectorint v2(v1.begin() 2, v1.end()-2);for (auto e : v2){cout e ;}//测试参数初始化列表构造cout endl;MySpace::vectorint v3({ 1,2,3,4,5,6,7,8,9,10 });for (auto e : v3){cout e ;}//测试拷贝构造cout endl;MySpace::vectorint v4(v3);for (auto e : v4){cout e ;}//测试赋值构造cout endl;MySpace::vectorint v5;v5 v4;for (auto e : v5){cout e ;}//测试填充初始化cout endl;MySpace::vectorint v6(10,7);for (auto e : v6){cout e ;}
}
运行结果 1 2 3 4 5 6 7 8 3 4 5 6 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 7 7 7 7 7 7 7 7 7 7 三、指定位置插入和删除
1、指定位置插入 iterator insert(iterator pos, const T x)//在指定位置插入{//判断插入的位置及是否合法assert(pos _start pos _finish);//判断是否需要扩容if (size() capacity()){//防止扩容后pos迭代器失效size_t nPos pos - _start;//计算pos距离_start的偏移量size_t newCapacity capacity() * 2;reserve(newCapacity);pos _start nPos;}//将插入位置及之后的元素往后挪iterator it _finish;while (it pos){*it *(it - 1);it--;}//插入元素*pos x;_finish;return pos;} 注意扩容时pos迭代器会失效扩容前要计算pos距离起始位置的偏移量然后再更新pos的迭代器。所以外部的迭代器pos是有失效的可能性的而不管怎么样外部的pos是不能再继续使用的若要继续使用则需要接受函数的返回值更新pos的迭代器防止迭代器失效此时pos迭代器指向新插入的数据。
2、指定位置删除
iterator erase(iterator pos)//指定位置删除
{//判断删除的位置是否合法assert(pos _start pos _finish - 1);//将pos位置后的元素往前挪iterator cur pos 1;while (cur ! _finish){*(cur - 1) *cur;cur;}_finish--;return pos;
} 注意vector删除元素时有可能缩容的虽然这里实现的vector不会缩容为了防止外部的迭代器失效我们也需要返回一个迭代器更新其pos的位置此时pos指向的位置是删除的元素的下一个元素的位置。
3、代码测试
void test3()
{MySpace::vectorint v1{ 1,2,3,4,5,6 };//测试指定位置插入v1.insert(v1.begin(), 999);v1.insert(v1.end(), 999);v1.insert(v1.end() - 2, 999);for (auto e : v1){cout e ;}cout endl;//结合find删除所有999//找不到则返回结尾的迭代器MySpace::vectorint::iterator itFind;while ((itFind std::find(v1.begin(), v1.end(), 999)) ! v1.end()){cout endl;v1.erase(itFind);for (auto e : v1){cout e ;}}
}
4 运行结果 999 1 2 3 4 5 999 6 999 1 2 3 4 5 999 6 999 1 2 3 4 5 6 999 1 2 3 4 5 6 四、修改有效数据个数大小
具体实现代码
void resize(size_t n)//改变容器数据个数
{assert(n 0);//判断是否需要扩容if (n capacity()){reserve(n);}//将其他位置初始化为数据的默认构造for (int i size(); i n; i){*(_start i) T();}_finish _start n;
}
代码测试
void test4()
{//测试resizeMySpace::vectorint v1{ 1,2,3,4,5,6,7,8,9,10 };for (auto e : v1){cout e ;}cout endl;//缩容v1.resize(2);for (auto e : v1){cout e ;}cout endl;//调大有效数据个数大小v1.resize(10);for (auto e : v1){cout e ;}
} 1 2 3 4 5 6 7 8 9 10 1 2 1 2 0 0 0 0 0 0 0 0 以上就是vector的简易实现。
