C++ 模拟实现vector

���录

一、定义

二、模拟实现

1、无参初始化

2、size&capacity

3、reserve

4、push_back

5、迭代器

6、empty

7、pop_back

8、operator[ ]

9、resize

10、insert

迭代器失效问题

11、erase

12、带参初始化

13、迭代器初始化

14、析构函数

15、深拷贝

16、赋值运算符重载

完整版代码&测试代码

---

一、定义

本次参考SGI版本STL中的vector模拟实现。

我们可以看到上述源代码中，SGI版本vector是借助指针实现的，元素的处理是通过两个指针来实现的，而不是三个迭代器。这两个指针分别是_start和_finish。

• _start指针指向vector中的第一个元素。
• _finish指针指向vector中最后一个元素的下一个位置。

  通过_start和_finish指针，可以确定vector中存储的元素范围。

   

  此外，SGI版本的vector还使用了一个指针_end_of_storage来表示vector分配的内存空间的末尾位置。

  这些指针的使用使得SGI版本的vector能够高效地进行元素的插入、删除和访问操作。

  为了不影响VS中STL库已有的vector，我们选择将模拟实现的vector放在自定义命名空间中。

  namespace byte{templateclass vector{    public:    private:    iterator _start;    iterator _finish;    iterator _end_of_storage;    };}

  二、模拟实现

  1、无参初始化

  vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}

  2、size&capacity

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

  3、reserve

  void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}

  1. if (n > capacity())：检查传入的n是否大于当前vector的容量。如果是，则需要进行内存重新分配。

  2. size_t sz = size();：保存当前vector的大小（元素个数）。

  3. T* tmp = new T[n];：创建一个新的大小为n的动态数组tmp，用于存储重新分配后的元素。

  4. if (_start)：检查_start指针判断旧空间是否为非空。如果_start指针不为空，说明vector中已经有元素存储在旧的内存空间中。

  5. memcpy(tmp, _start, sizeof(T) * size());：使用memcpy函数将旧的内存空间中的元素复制到新的内存空间tmp中。这样可以保留元素的值。

  6. delete[] _start;：释放旧的内存空间。

  7. _start = tmp;：将_start指针指向新的内存空间tmp。

  8. _finish = _start + sz;：更新_finish指针，使其指向新的内存空间中的最后一个元素的下一个位置。

  9. _end_of_storage = _start + n;：更新_end_of_storage指针，使其指向新的内存空间的末尾位置。 

  对上述函数进行改进：

  void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T)*size());for (size_t i = 0; i  
  第二个函数的改进在于它使用了元素级别的复制（通过赋值操作符）而不是直接内存复制（通过memcpy）。
   
  在第一个函数中，memcpy直接复制了内存块，这对于平凡的数据类型（如整数、浮点数、字符等）是没有问题的，因为这些类型的复制就是简单的内存复制。然而，对于包含自定义复制行为的类类型，memcpy可能会导致错误，因为它不会调用类的复制构造函数或赋值操作符。
   
  在第二个函数中，通过循环和赋值操作符进行元素级别的复制。这样，如果T是一个类类型，并且定义了自定义的复制构造函数或赋值操作符，那么这些函数将被正确调用，从而避免了可能的错误。
   
  因此，第二个函数的改进在于它更安全，更适合处理包含自定义复制行为的类类型。
   
  4、push_back
   
  void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}
   
   
  使用const T& x作为参数类型可以避免不必要的拷贝操作，因为传入的实参可以直接通过引用访问，而不需要进行拷贝构造。这可以提高性能和效率，特别是当处理大型对象时。
   
  另外，使用const T& x还可以确保传入的元素不会被修改，因为const关键字表示传入的引用是只读的，函数内部不能修改传入的对象。
   
   
  if (_finish == _end_of_storage) 这个条件判断用于检查当前vector是否已经达到了内存空间的末尾。如果是，则需要进行内存重新分配。
   
   
  reserve(capacity() == 0 ? 4 : capacity() * 2) 在需要进行内存重新分配时，调用reserve函数来预留更多的内存空间。这里使用了三目运算符，如果当前容量为0，则预留4个元素的空间，否则将当前容量乘以2来预留更多的空间。
   
   
  *_finish = x 将传入的元素x赋值给_finish指针所指向的位置，即在vector的末尾插入元素。
   
   
  ++_finish 将_finish指针向后移动一位，指向新插入元素的下一个位置，以便维护vector的边界。
   
  5、迭代器
   
  typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}
   

  • 首先，通过typedef关键字，定义了两个迭代器类型：iterator和const_iterator。iterator表示可修改元素的迭代器，而const_iterator表示只读元素的迭代器。
  • 然后，定义了begin()和end()函数的多个重载版本，用于返回不同类型的迭代器。

    6、empty

    bool empty(){return _start == _finish;}

    7、pop_back

    void pop_back(const T& x){assert(!empty());--_finish;}

    8、operator[ ]

    这个类中有两个重载的下标运算符函数，一个是非常量版本的 operator[]，另一个是常量版本的 operator[]。这是为了支持对类对象的读写操作和只读操作的区分。

    T& operator[](size_t pos){assert(pos  
    9、resize
     
    void resize(size_t n, T val = T()){if (n    
    函数签名为 void resize(size_t n, T val = T())，接受两个参数：n 表示新的大小，val 表示新元素的默认值（默认为 T()，通过匿名对象T()调用类型 T 的默认构造函数）。
      
    函数的作用是将容器的大小调整为 n。如果 n 小于当前的大小，则将容器的大小缩小为 n，丢弃多余的元素；如果 n 大于当前的大小，则在容器的末尾添加新的元素，直到容器的大小达到 n。
     
    首先，函数会检查 n 是否小于当前的大小。如果是，说明需要缩小容器的大小，将 _finish 指针移动到新的位置 _start + n，丢弃多余的元素。
    如果 n 大于等于当前的大小，则需要添加新的元素。首先，函数会检查 n 是否大于容器的容量 capacity()。如果 n 大于容量，则调用 reserve 函数来增加容器的容量，以确保容器有足够的空间来存放新的元素。
    然后，使用循环将新的元素 val 添加到容器的末尾，直到容器的大小达到 n。循环中，将 val 赋值给 _finish 指向的位置，然后将 _finish 指针向后移动一位。
    匿名对象调用默认构造初始化。
      
        templatevoid f(){T x = T();cout = _start && pos    
     当我们运行以下代码程序VS会报错，linux下g++不会报错。
      
    void test4(){std::vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout