【C++练级之路】【Lv.7】【STL】vector类的模拟实现

快乐���流畅：个人主页 个人专栏：《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！

---

文章目录

• 引言
• 一、成员变量
• 二、默认成员函数
• • 2.1 constructor
  • 2.2 destructor
  • 2.3 copy constructor
  • 2.4 operator=
  • 三、迭代器
  • • 3.1 begin
    • 3.2 end
    • 四、元素访问
    • • 4.1 operator[ ]
      • 五、容量
      • • 5.1 size
        • 5.2 capacity
        • 5.3 reserve
        • 5.4 resize
        • 5.5 empty
        • 六、修改
        • • 6.1 push_back
          • 6.2 pop_back
          • 6.3 insert
          • 6.4 erase
          • 6.5 swap
          • 总结

            引言

            关于STL容器的学习，我们来到了运用最广泛、最常见的vector。有了之前关于string的学习，我们对容器设计有了一个大概的了解，而今天在熟悉的基础上去探求vector相比于string有哪些异同，同时迎来更多的新挑战……

            一、成员变量

            vector类中包含了

            • _start（指向有效空间的头）
            • _finish（指向有效空间的尾）
            • _end_of_storage（指向可用空间的尾）

              细节：

              1. 三个成员变量均迭代器（此刻即指针）
              2. 使用缺省值，不必写多份初始化列表

              templateclass vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};

              二、默认成员函数

              2.1 constructor

              无参构造

              vector(){}

              带参构造

              细节：

              1. 分别重载 size_t 和 int 类型，防止参数匹配时，匹配到迭代器区间构造，从而导致间接寻址错误
              2. 初始化的val的缺省值，是匿名构造的对象

              vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i  
              迭代器区间构造
               
              细节：
               
              使用类模板，可以传任意类型的迭代器
              迭代器访问，条件最好使用不等于（！=）
              template vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}
               
              2.2 destructor
               
              ~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
               
              2.3 copy constructor
               
              近代写法
               
              细节：
               
              先开辟一维空间
              再用赋值重载，进行深拷贝（不能用memcpy，它是浅拷贝）
              vector(const vector& x){_start = new T[x.capacity()];for (size_t i = 0; i  
              现代写法
               
              细节：
               
              用迭代器区间构造，构造出临时对象
              再使用vector中的swap，交换*this和tmp的值，完成拷贝构造
              vector(const vector& x){vector tmp(x.begin(), x.end());swap(tmp);}
               
              2.4 operator=
               
              近代写法
               
              细节：大体与拷贝构造相同
               
              vector& operator=(const vector& x){if (this != &x){_start = new T[x.capacity()];for (size_t i = 0; i  
              现代写法
               
              细节：
               
              传参变成传值，这样就会拷贝构造出一个临时对象
              再使用vector中的swap，交换*this和tmp的值，完成赋值重载
              vector& operator=(vector x){swap(x);return *this;}
               
              三、迭代器
               
              3.1 begin
               
              迭代器的实现和编译器有关，不同的编译器有不同的实现方式。这里用指针来实现迭代器。
               
              同时，重载了普通迭代器和const迭代器。
               
              iterator begin(){return _start;}const_iterator begin() const{return _start;}
               
              3.2 end
               
              迭代器遵循左闭右开的原则，begin指向首元素，end指向末元素的下一位。
               
              iterator end(){return _finish;}const_iterator end() const{return _finish;}
               
              悄悄告诉你：范围for的底层实现，就是运用了迭代器。
               
              四、元素访问
               
              4.1 operator[ ]
               
              为了方便的访问元素，我们重载了[ ]运算符。同时，也分为普通版本和const版本，对应不同vector类的权限。
               
              T& operator[](size_t pos){assert(pos  
              五、容量
               
              5.1 size
               
              获取当前有效数据个数
               
              细节：const修饰，保证普通和const类型vector类都能访问
               
              size_t size() const{return _finish - _start;}
               
              5.2 capacity
               
              获取当前最大有效容量
               
              细节：同上
               
              size_t capacity() const{return _end_of_storage - _start;}
               
              看了上面size和capacity的实现，是不是就瞬间明白_start、_finish和_end_of_storage的含义了？
               
              悄悄告诉你：其实当你不懂成员变量的含义时，可以先看看size和capacity的实现。
               
              5.3 reserve
               
              改变当前最大容量
               
              细节：
               
              只扩容，不缩容
              用赋值重载，进行深拷贝
              更新成员变量时（如果按照顺序更新），先保存size的大小，防止_finish失效。因为如果为_finish = tmp + size()，等价于_finish = tmp + _finish - _start，而_start已经更新了，所以size()计算的大小失效，最终_finish并没有更新。
              void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];if (_start){for (size_t i = 0; i  
              5.4 resize
               
              改变当前有效数据个数
               
              细节：
               
              如果nsize，则填充指定值，直至达到n个
              运用赋值重载，实现深拷贝
              void resize(size_t n, T val = T()){if (n > size()){reserve(n);for (size_t i = size(); i  
              5.5 empty
               
              判断是否为空
               
              细节：const修饰，保证普通和const类型vector类都能访问
               
              bool empty() const{return _start == _finish;}
               
              六、修改
               
              6.1 push_back
               
              尾插
               
              细节：需要扩容时，判断容量是否为空
               
              void push_back(const T& val){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = val;++_finish;}
               
              6.2 pop_back
               
              尾删
               
              细节：断言vector不为空，才进行删除
               
              void pop_back(){assert(!empty());--_finish;}
               
              6.3 insert
               
              指定位置插入
               
              细节：
               
              断言判断pos的合法性
              扩容前，先保存pos的相对位置，扩容后，刷新pos，防止迭代器失效
              返回指向新插入元素的迭代器，防止迭代器失效
              iterator insert(iterator pos, const T& val){assert(pos >= _start && pos size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end = pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;}
               
              6.4 erase
               
              指定位置删除
               
              细节：
               
              断言判断pos的合法性
              返回指向删除元素的后一位的迭代器，防止迭代器失效
              iterator erase(iterator pos){assert(pos >= _start && pos  
              上述有两种迭代器失效：
               
              野指针
              指向含义改变
              关于迭代器失效，我们统一认为，进行过插入或删除操作的迭代器pos，已经失效，不能再使用。只有接收其返回值，刷新pos，才能重新使用。
               
              6.5 swap
               
              交换两个vector类的值
               
              细节：使用std库中的swap函数，交换各个成员变量的值
               
              void swap(vector& x){std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_end_of_storage, x._end_of_storage);}
               
              总结
               
              我们在有了学习string的基础后，学习vector的成本降低了不少，函数名和用法大体相同。但是，我们依旧遇到了新的问题与挑战，如多层深拷贝，迭代器失效等。我与C++的故事，仍在无声地诉说……
                  真诚点赞，手有余香