『C++成长记』vector模拟实现

🔥博客主页：小王又困了

📚系列专栏：C++

🌟人之为学，不日近则日退

❤️感谢大家点赞👍收藏⭐评论✍️

 

目录

一、存储结构

二、默认成员函数

📒2.1构造函数

📒2.2拷贝构造

📒2.3赋值重载

三、容量操作

📒3.1获取有效元素个数

📒3.2获取空间容量大小

📒3.3使用reverse扩容

四、数据访问

📒4.1下标访问

📒4.1迭代器访问

 五、修正操作

📒5.1尾插数据

📒5.2尾删数据

📒5.3在任意位置插入数据

📒5.4在任意位置删除数据

---

🗒️前言：

vector是STL容器之一，其底层实现类似于数据结构顺序表，相当于string来说得益于泛型模板的加持使得vector可以变为任何类型，且是可以动态扩容。接下来我们就通过vector各种接口的模拟实现来深入了解vector。

一、存储结构

        与string底层结构不同，vector底层空间结构为三个指针:

namespace bit
{template<class T> //模板参数Tclass vector{public:typedef T* iterator;		//指针重命名为迭代器typedef const T* const_iterator;private:iterator _start; iterator _finish; iterator _end_of_storage; }；
}

• _start：指向空间的起始地址
• _finish：指向最后一个数据的下一个地址，相当于_size
• _end_of_stroage：指向空间最后一个最末地址,相当于_capacity

小Tips：由于vector使用了模板，所以函数实现都在头文件中，防止因为模板导致的链接错误的问题！

二、默认成员函数

📒2.1构造函数

        我们在这里实现三个版本，分别是：默认构造函数，带参构造函数和迭代器区间构造。 

• 默认构造函数：初始化三个指针置空即可
• 带参构造函数：初始化n个T类型的value值在对象中
• 迭代器区间构造：通过其他容器迭代器或指针迭代插入其所有值

//默认构造函数
vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{}vector () = default //强制编译器生存默认构造//构造n个T类型数据
vector(size_t n, const T& value = T()) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (int i = 0; i < n; ++i){*(_finish++) = value;}
}//迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (first != last) //迭代器插入数据{push_back(*first);++first;}
}

注意：我们实现了带参构造函数的n为size_t类型的版本，如果我们使用带参构造函数实例化，则会发生非法间接寻址的错误！这是因为size_t是整型，实例化T数据类型也是整型，此时编译器会自动匹配最合适的构造函数，于是匹配到了迭代器区间构造。我们只要写一个n为int类型的带参构造参数去匹配，就可以解决问题。

📒2.2拷贝构造

        对于拷贝构造我们要考虑深浅拷贝的问题，我们希望当一个vector对象拷贝另一个对象时新对象开辟新的空间拷贝数据，而不是两个对象共用同一块空间，否则会析构两次造成内存泄漏。

vector(const vector<T>& v)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}

📒2.3赋值重载

        赋值重载与拷贝构造的问题类似，也要注意深拷贝问题；区别于拷贝构造的地方在于不需要新建对象，但是需要判断是否为同一个对象避免重复开空间。

//传统写法
vector<T>& operator=(const vector<T>& v)
{if (&v != this) {clear(); reserve(v.capacity()); for (int i = 0; i < v.size(); ++i){*(_finish++) = v._start[i]; }}return *this;
}//现代写法
void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}// v1 = v3
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

三、容量操作

📒3.1获取有效元素个数

size_t size() const
{return _finish - _start;
}

📒3.2获取空间容量大小

size_t capacity() const
{return _end_of_storage - _start;
}

 小Tips：vevtor是使用3个指针对空间进行管理，使用_finish(有效数据指针)减去_start(空间首地址)就能得出有效数据个数，容量同理。我们只是对数据进行访问不涉及修改，所以使用const修饰this指针。

📒3.3使用reverse扩容

void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();//获取扩容前有效数据个数T* tmp = new T[n];if(_start){//memcpy(tmp, _start, sizeof(T*) * size());for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}
}
//错误写法：_finish = _start + size() ；

小Tips：我们要用oldsize记录扩容前有效数据的个数，按照错误写法size()是用扩容前的_finish和扩容后的_start来计算的，结果是错误的。当string类型的对象要扩容时，memcpy对数据进行的是浅拷贝，两个对象指向同一块空间，会析构两次造成内存泄漏。

四、数据访问

📒4.1下标访问

        下标访问是通过重载 [ ] 运算符实现的，在下标pos正确的情况下，返回当前下标字符的引用，否则assert报错。

T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}const T& operator[](size_t pos) const //const引用版本,不可以修改
{assert(pos < size()); return _start[pos];
}

         at 函数我们可以复用运算符[ ]来实现。 at 函数的检查手段是抛异常。

T& at(size_t pos) 
{ return (*this)[pos]; 
}const T& at(size_t pos) const 
{ return (*this)[pos]; 
}

📒4.1迭代器访问

typedef T* iterator;
typedef const T* const_iterator;const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }iterator begin() { return _start; }
iterator end() { return _finish; }//范围for
for (auto e : v1)
{cout << e << " ";
}
cout << endl;

 五、修正操作

📒5.1尾插数据

        在尾插前检查容量是否充足，空间不够扩容，然后直接插入_finish的空位下即可，_finish指针移动到下一个空位。

void push_back(const T x)
{if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;//insert(end(), x);    //复用
}

📒5.2尾删数据

        尾删只需要--_finish，但需要判断size是否>0。

void pop_back()
{assert(size() > 0);--_finish;
}

📒5.3在任意位置插入数据

        当我们传递一个迭代器在pos位置插入数据时，可能涉及容器扩容，如果扩容，那么迭代器是旧空间的迭代器，则会导致迭代器失效，因为原有空间已经被释放，但迭代器还是指向原空间(那么就是野指针)，所以我们在插入或删除后要更新迭代器。

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;_finish++;return pos;
}

小Tips：如果要进行扩容我们用len来记录扩容前从_start到pos位置数据的个数，然后扩容后更新pos的位置。

📒5.4在任意位置删除数据

        删除元素也会有迭代器失效的问题，可能会越界访问 。

iterator earse(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;it++;}--_finish;return pos;    //返回删除元素位置的下一个元素的迭代器
}

---

🎁结语： 

     本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。