Shulou(Shulou.com)06/02 Report--

This article is about how to simulate the implementation of vector in C++. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Overview of vector interfaces

Namespace nzb {/ / simulated implementation of vector template class vector {public: typedef T* iterator; typedef const T* const_iterator; / / default member function vector () / / constructor vector (size_t n, const T & val); / / constructor template vector (InputIterator first, InputIterator last); / / constructor vector (const vector& v) / / copy constructor vector& operator= (const vector& v); / / assign overload ~ vector (); / / destructor / / iterator related function iterator begin () Iterator end (); const_iterator begin () const; const_iterator end () const; / / capacity correlation function 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; / / modify container correlation function 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 the container-related function T & operator [] (size_t I); const T & operator [] (size_t I) const; private: iterator _ start; / / points to the container header iterator _ finish / / pointing to the tail of valid data iterator _ endofstorage; / / pointing to the tail of the container};} default member function

Constructor function

1. No parameter construction. Initialize all member variables to null pointers.

Vector (): _ start (nullptr), _ finish (nullptr), _ endofstorage (nullptr) {}

2. Construct a vector container with n values of val.

Expand the container capacity to n first, and then insert val at the end

Vector (size_t n, const T & val): _ start (nullptr), _ finish (nullptr), _ endofstorage (nullptr) {reserve (n); / / expansion for (size_t I = 0; I

< n; i++) //尾插 { push_back(val); }} 3、利用迭代器区间进行构造 因为迭代器区间可以是其他迭代器区间，所以我们要重新定义一块模板，再将迭代器中的数据尾插 template vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr){ while (first != last) { push_back(*first); first++; }}拷贝构造 传统写法 先将容器容量扩大到n，再尾插原vector类中的数据（这里扩容和尾插调整了容器尾指针和数据尾指针，我们不必再次调整） vector(const vector& v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr){ reserve(v.capacity()); for (const auto& e : v) { push_back(e); }} 现代写法 利用迭代器构造一份vector类，再交换该类和拷贝构造的类 vector(const vector& v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { vector tmp(v.begin(), v.end()); swap(tmp); }赋值重载 传统写法 先初始化原来vector类的空间，再将数据拷贝过来 vector& operator=(const vector& v){ if (this != &v) { delete[] _start; _start = _finish = _endofstorage = nullptr; reserve(v.capacity()); for (const auto& e : v) { push_back(e); } } return *this;} 现代写法 现代写法极为巧妙，利用传值的特性（出了函数立即销毁）传入vector类，再交换该类和拷贝构造的类达到赋值的效果 vector& operator=(vector v){ swap(v); return *this;}析构函数 释放开辟存储数据的空间，再将容器的各个成员变量置为空 ~vector(){ delete[] _start; _start = _finish = _endofstorage = nullptr;}迭代器相关函数 vector当中的迭代器实际上就是容器当中所存储数据类型的指针。 typedef T* iterator;typedef const T* const_iterator;begin和end vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。 iterator begin(){ return _start;}iterator end(){ return _finish;} 我们还需写一份const版本，const版本只能读不能写，防止vector中数据被修改 const_iterator begin() const{ return _start;}const_iterator end() const{ return _finish;}容量相关函数 size和capacity size表示vector容器中已存储有效数据个数而capacity表示vector容器的最大容量，那如何得出该组数据呢？ 我们知道vector成员函数_start,_finish,_endofstorage是指针，而指针减指针得到两个指针间的数据个数，我们可以用_finish-_start得到size,用_endofstorage-_start得到capacity size_t size() const{ return _finish - _start;}size_t capacity() const{ return _endofstorage - _start;}reserve 当n大于当前的capacity时，将capacity扩大到n或大于n。 当n小于当前capacity时什么也不做。 void reserve(size_t n){ if (n >

Capacity () {size_t sz = size (); / / record the number of data in the original container T * tmp = new T [n]; / / Open up a space if (_ start) / / empty {for (size_t I = 0; I)

< sz; i++) // 拷贝数据 { tmp[i] = _start[i]; } delete[] _start; // 释放原容器中的数据 } _start = tmp; // 调整指针 _finish = _start + sz; _endofstorage = _start + n; }} 注意：这里拷贝数据不能用memcpy。当我们拷贝的是一些简单的常量时是没有问题的，但是当我们拷贝的是另一个类，如string类时，拷贝的string还是指向原来string类指向的空间。当原来string被释放时，原string类指向的空间也被释放，此时拷贝的string类指向的是一块已被释放的空间，程序结束时它将再次被释放，释放一块已被释放的空间程序报错。 resize 当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。 当n小于当前的size时，将size缩小到n。 void resize(size_t n, const T& val = T()){ if (n capacity())// 当n大于容量时，扩容 { reserve(n); } while (_finish < _start + n)// 给size到容器结尾赋值 { *_finish = val; _finish++; } }} 这里用了匿名对象T（）来作为缺省参数 empty 通过比较_start和_finish指针来判断容器是否为空 bool empty()const{ return _start == _finish;}修改容器相关函数 push_back 先判断容器是否已满，如果满了先扩容再尾插，如果没满，直接尾插 void push_back(const T& x){ if (_finish == _endofstorage)// 判断是否需要扩容 { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } // 尾插数据 *_finish = x; _finish++;}pop_back 先判空处理，再-_finish void pop_back(){ assert(!empty());// 判空 --_finish;}insert 功能：利用迭代器再指定位置插入数据。 实现方式：插入前判断是否需要扩容，再将指定位置后的数据往后挪动一位，把数据插入指定位置。 iterator insert(iterator pos, const T& x){ assert(pos >

= _ start&&pos = pos) / / move data {* (end + 1) = * end;-- end;} * pos = x bang / insert data _ finish++; return pos;}

Note: the relative positions of pos and _ start should be recorded during capacity expansion to avoid iterator failure after capacity expansion.

Erase

Function: delete the specified location data.

Implementation: first judge the validity of the incoming data, move all the data after the pos location forward one bit, and overwrite the data of the original pos location

Iterator erase (iterator pos) {assert (pos > = _ start&&pos < _ finish); / / determine the validity of incoming data iterator it = pos + 1 beat / use an iterator to record the latter while of pos (it! = _ finish) / / move the data after pos forward one bit {* (it-1) = * it; it++ } _ finish--; return pos;} swap

Function: exchange data between two vector

Implementation: exchange using swap in the library function

Void swap (vector& v) {std::swap (_ start, v._start); std::swap (_ finish, v._finish); std::swap (_ endofstorage, v._endofstorage);} access to container-related functions

Operator []

The "subscript + []" operation is also added to the vector to facilitate access to data.

T & operator [] (size_t I) / / readable and writable {assert (I < size ()); return _ start [I];} const T & operator [] (size_t I) const// can only read {assert (I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.