c++的学习之路：13、vector（2）-阿里云开发者社区

一、STL源码

今天看的是STL30这个源码，他的vector点开是下图这种可以看出他也是调用了几个头文件，上面注释的就是一些开源声明，大概就是说是可以使用、增删查改甚至售卖，做出有用的修改也需要声明。

如下图二可以看出vector的参数是只有三个原生指针，这个就是从图一这里就可以看出是一个typede进行的重定义的。

他的size，capacity是如下图这样使用的，下面九不一一展示了，源码上传了可以自己看看。

二、构造与析构

如下方代码就是这个构造和析构，这里是放在了我的命名空间中以防和库里面的vector重复，这里是利用了缺省传值，在定义的时候直接赋值为nullptr然后进行一个空的初始化，然后如下方代码中vector(size_t n, const T& val = T())这一句就是利用一个匿名对象进行初始化，因为这样就可以直接使用模板进行构造，因为这样就可以使用不用的类型进行初始化对象，然后又利用了模板参数InputIterator进行初始化，这里就是如上篇文章中可以使用范围进行初始化，这里就是利用迭代器的原理，first就是迭代器的begin，last就是迭代器的end，也就是首和尾，然后进行构造，相当于缺省值的构造，这里面构造是需要开辟空间和插入数据，所以这里先写在这了，代码在后面文章， vector(int n, const T& val = T())有个这个是因为写入的值默认是整形，在构造时会进行隐形类型转换，size_t是无符号整形，需要转化，但是有类模板会优先使用这个就会造成野指针。

namespace ly
{
    template
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;
        vector()
        {}
        vector(size_t n, const T& val = T())
        {
            reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }
        vector(int n, const T& val = T())
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }
        template 
        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }
        ~vector()
        {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
        }
    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };
}

三、迭代器与【】、size、capacity、empty

如下方代码所示，先看迭代器，在上文中就已经重定义了iterator是T*，所以这里begin就是直接返回start的指针，end就是finish，看过源码和之前模拟实现过string就会发现这里很好用，这里也是同样的有const，因为这里需要重载就是因为需要访问const类型的，size就是finish-start就能得出size，同理capacity就是end_of_storage - start，enpty就是判断是否满了，这里就是start等于finish的时候就是满了，【】就是直接访问就可以了，在pos位置进行访问，这里也是如下方代码所示。

iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }
        const_iterator begin() const
        {
            return _start;
        }
        const_iterator end() const
        {
            return _finish;
        }
        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity() const
        {
            return _end_of_storage - _start;
        }
        bool empty()
        {
            return _start == _finish;
        }
        T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }
        const T& operator[](size_t pos) const
        {
            assert(pos < size());
            return _start[pos];
        }

四、reserve与resize

这里是和之前模拟实现string的时候差不多，判断容量是否够，不够减扩容，这里因为需要计算—finish地址，所以提前记录了size，然后创建一个空间，然后利用memcpy进行拷贝数据，在把旧的start释放了，在指向新的空间，在把finish和end_of_storage计算出来就好了，resize也是需要判断是否是缩容，缩容并不需要缩容，只需要删除数据就可以了，扩容也就是需要扩容后，再把数据初始化就可以了。

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;
            }
        }
        void resize(size_t n, T val = T())
        {
            if (n < size())
            {
                _finish = _start + n;
            }
            else
            {
                if (n > capacity())
                {
                    reserve(n);
                }        
                while (_finish != _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
        }

五、push_back与pop_back

这里就是先判断是否满了，满了就先进行扩容，然后进行存入数据，没满就把数据直接存入，删除也就是直接--覆盖就好了。

void push_back(const T& x)
        {
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }
        void pop_back()
        {
            assert(!empty());
            --_finish;
        }

六、insert与erase

如下方代码，这里实现的思路是先断言，pos位置是在start和finish之间，不是就报错，如果刚好数据满了就进行扩容，这里需要注意的是扩容的时候需要进行计算pos的绝对位置，也就是距离start的长度，在扩容后在进行计算pos位置，然后就是挪动数据与把数据存入，erase就不需要判断相等finish的时候，因为满了也可以删，然后在进行挪动覆盖，这个就是erase的实现。

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

七、测试 1

这里就进行测试一下上面写的代码是否有错，如下图的代码就是测试push_back与pop_back的写发，然后这里也是测试了下迭代器的使用，for的实现就是迭代器。

void Print(const vector& v)    {
        for (auto vi : v)
        {
            cout << vi << ' ';
        }
        cout << endl;
    }
    void Test1()
    {
        vector v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        Print(v1);
        v1.pop_back();
        v1.pop_back();
        Print(v1);
    }

这里就是测试了下【】与利用模板进行范围的初始化

void Test2()
    {
        vector v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        Print(v1);
        vector v2(v1.begin(), v1.end());
        Print(v2);
        for (size_t i = 0; i < v2.size(); i++)
        {
            cout << v2[i] << ' ';
        }
        cout << endl;
    }

这里是测试插入和删除，这里利用了find找到1和3进行头插和在3的位置插入，如下方所示。

void Test3()
    {
        vector v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        Print(v1);
        auto pos = find(v1.begin(), v1.end(), 1);
        v1.insert(pos, 0);
        pos = find(v1.begin(), v1.end(), 3);
        v1.insert(pos, 30);
        Print(v1);
        pos = find(v1.begin(), v1.end(), 0);
        v1.erase(pos);
        pos = find(v1.begin(), v1.end(), 30);
        v1.erase(pos);
        Print(v1);
    }

八、代码

vector.h

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
 
namespace ly
{
  template<class T>
  class vector
  {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
 
    vector()
    {}
 
    vector(size_t n, const T& val = T())
    {
      reserve(n);
      for (size_t i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
 
    vector(int n, const T& val = T())
    {
      reserve(n);
      for (int i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
 
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
 
    ~vector()
    {
      delete[] _start;
      _start = _finish = _end_of_storage = nullptr;
    }
 
    iterator begin()
    {
      return _start;
    }
 
    iterator end()
    {
      return _finish;
    }
 
    const_iterator begin() const
    {
      return _start;
    }
 
    const_iterator end() const
    {
      return _finish;
    }
 
    size_t size() const
    {
      return _finish - _start;
    }
 
    size_t capacity() const
    {
      return _end_of_storage - _start;
    }
 
    bool empty()
    {
      return _start == _finish;
    }
 
    T& operator[](size_t pos)
    {
      assert(pos < size());
      return _start[pos];
    }
 
    const T& operator[](size_t pos) const
    {
      assert(pos < size());
      return _start[pos];
    }
 
    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;
      }
    }
 
    void resize(size_t n, T val = T())
    {
      if (n < size())
      {
        _finish = _start + n;
      }
      else
      {
        if (n > capacity())
        {
          reserve(n);
        }   
        while (_finish != _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
    }
 
    void push_back(const T& x)
    {
      if (_finish == _end_of_storage)
      {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      *_finish = x;
      ++_finish;
    }
 
    void pop_back()
    {
      assert(!empty());
      --_finish;
    }
 
    iterator insert(iterator pos, const T& val)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish == _end_of_storage)
      {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
      }
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = val;
      ++_finish;
      return pos;
    }
 
    void erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);
      iterator start = pos + 1;
      while (start != _finish)
      {
        *(start - 1) = *start;
        ++start;
      }
      --_finish;
    }
 
  private:
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _end_of_storage = nullptr;
  };
 
  void Print(const vector<int>& v)
  {
    for (auto vi : v)
    {
      cout << vi << ' ';
    }
    cout << endl;
  }
 
  void Test1()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    Print(v1);
    v1.pop_back();
    v1.pop_back();
    Print(v1);
  }
 
  void Test2()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    Print(v1);
    vector<int> v2(v1.begin(), v1.end());
    Print(v2);
    for (size_t i = 0; i < v2.size(); i++)
    {
      cout << v2[i] << ' ';
    }
    cout << endl;
  }
 
  void Test3()
  {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    Print(v1);
    auto pos = find(v1.begin(), v1.end(), 1);
    v1.insert(pos, 0);
    pos = find(v1.begin(), v1.end(), 3);
    v1.insert(pos, 30);
    Print(v1);
    pos = find(v1.begin(), v1.end(), 0);
    v1.erase(pos);
    pos = find(v1.begin(), v1.end(), 30);
    v1.erase(pos);
    Print(v1);
  }
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "vector.h"
 
int main()
{
  ly::Test3();
}

c++的学习之路：13、vector（2）

一、STL源码

二、构造与析构

三、迭代器与【】、size、capacity、empty

四、reserve与resize

五、push_back与pop_back

六、insert与erase

七、测试 1

八、代码

九、思维导图

热门文章

最新文章

相关课程

相关电子书