C++之打造my vector篇（上）-阿里云开发者社区

前言

前面章节我们讲解了vector相关接口，方法的使用，本节内容我们将自己创造vector,模仿官方的接口方法。

1.参照官版，打造vector的基本框架

通过查看官方文档我们知道，vector是个可以变化的数组，是个容器，可以储存一系列数据，

是典型的模版类。

且有三个基本成员start,finish,end_of_storage,我们可以理解为指向数组的开端，数据的结尾，以及容量的结束指针。

上图为插入成员后的分布情况。

故创造了一下的基本框架，因为是我们自己的实现，所以定义了一个my_vector的命名空间，

namespace my_vector {
  template<class T>
  class vector {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
    vector() 
    {}
   ~vector() {
  if (_start) {
    delete[]_start;
    _start = _finish = _end_of_storage = nullptr;
  }
}
private:
  iterator _start = nullptr;
  iterator _finish=nullptr;
  iterator _end_of_storage=nullptr;
};

这里我们采用初始化列表来进行默认构造，直接使用私有成员的缺省值，较为简便。

C++11前置生成默认构造

vector()=default;

2.丰富框架，实现接口方法

基本的迭代器实现

iterator begin() {
  return _start;
}
iterator end() {
  return _finish;
}
const_iterator begin()const {
  return _start;
}
const_iterator end() const{
  return _finish;
}

就是比较简单的返回开始和结束的指针。

数据的[]访问

T& operator[](size_t i) {
  assert(i < size());
  return _start[i];
}
const T& operator[](size_t i) const
{
  assert(i < size());
  return _start[i];
}

顾名思义就是相似于数组的下标访问

容量和数据空间的改变

void reserve(size_t n) {
  if (n > capacity()) {
    size_t oldsize = size();
    T* temp = new T[n];
       memcpy(tmp, _start, old_size * sizeof(T));
/*
    for (size_t i = 0; i < oldsize; i++) {
      temp[i] = _start[i];
    }
*/
    delete[]_start;
    _start = temp;
    _finish =temp + oldsize;
    _end_of_storage = temp+n;
  }
}

对于扩容操作，我们创建了一个新的数组，然后定义一个oldsize来存储以前的数据空间，来确定之后的_finish位置，因为我们在之前释放了原来的数组了，如果不想这样操作，不想定义一个oldsize,就要把delete操作放在_finish=temp+size（）之后。

这里用了memcpy函数来转移数据，但是我们会发现有一个小小的问题，当数据类型为string时，程序会崩溃，这个后续会讲解的。

void resize(size_t n, T val = T())
    {
      if (n < size())
      {
        _finish = _start + n;
      }
      else
      {
        reserve(n);
        while (_finish < _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
    }

resize函数的作用是调整容器的大小，使其能够容纳n个元素。如果n小于当前容器的大小，则容器会被截断；如果n大于当前容器的大小，则容器会被扩展，并且新增的元素会被初始化为val的值。

T val = T()：表示一个默认参数，它是容器的元素类型T的默认构造函数生成的对象。如果调用resize时没有指定这个参数，就会使用元素类型的默认值。

如果n小于当前容器的大小

_finish = _start + n;：这条语句会截断容器，使其大小变为n。这里_start是指向容器第一个元素的指针，_finish是指向容器最后一个元素的下一个位置的指针。通过将`_finish`向前移动到_start + n的位置，容器的大小就被减少了。

如果`n`大于或等于当前容器的大小

- reserve(n);：调用reserve函数确保容器的容量至少为n。如果当前容量小于n，reserve会重新分配内存以容纳至少n个元素。

- 默认构造函数`T()`必须存在，以便能够为新元素提供默认值。如果`T`没有默认构造函数，则这段代码在尝试使用默认参数时会出错。

vector空间大小的返回与判空

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

大小返回就是几个指针加减即可

数据的增删

对于数据的增删，模拟尾插，尾删，指定位置的插入，删除（后两者都与迭代器iterator相结合）

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;
}
void erase(iterator pos) {
  assert(pos >= _start);
  assert(pos <= _finish);
  iterator it = pos + 1;
  while (it != end()) {
    *(it - 1) = *it;
    it++;
  }
  _finish--;
}
iterator insert(iterator pos,const T&x) {
  assert(pos >= _start  && 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 = *(end - 1);
    end--;
  }
  *pos = x;
  _finish++;
  return pos;
}

对于插入数据的操作都要进行扩容的判断操作，对于数据的挪动我们可以采用依次赋值，就像代码中的*end=*(end-1);end--//*(it-1)=*it;it++;

通过画图可以更加清楚的理解。

数据打印

template<class T>
void print_vector(const vector<T>& v) {
  //typename vector<T>::const_iterator it = v.begin();
  auto it = v.begin();
  while (it != v.end()) {
    cout << *it << " ";
    it++;
  }
  cout << '\n';
    for  (auto e:v) {
    cout << e << " ";
  }
  cout << endl;
}
template<class Container>
void print_container(const Container& v) {
  auto it = v.begin();
  while (it != v.end()) {
    cout << *it << " ";
    it++;
  }
  cout << '\n';
  for (auto e : v) {
    cout << e << " ";
  }
  cout << endl;
}

规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator是类型还是静态成员变量，所以在注释的部分我们看见前面加了个typename.

//typename vector::const_iterator it = v.begin();

print_vector 函数专门用于打印 std::vector 类型的容器。

print_container 函数是一个更通用的模板函数，可以用于打印任何符合容器概念的类型。

void vector5()
{
  vector<string> v;
  v.push_back("11111111111111111111");
  v.push_back("11111111111111111111");
  v.push_back("11111111111111111111");
  v.push_back("11111111111111111111");
  print_container(v);
  v.push_back("11111111111111111111");
  print_container(v);
}

拷贝构造和赋值重载

vector(const vector<T>& v) {
reserve(v.size());
for (auto e : v) {
  push_back(e);
}
}
vector<T>operator=(const vector<T>& v) {
if (this != v) {
  reserve(v.size());
  for (auto e : v) {
    push_back(e);
  }
}
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& operator=(vector v)
    vector<T>& operator=(vector<T> v)
    {
      swap(v);
      return *this;
    }

这种思路是交换的方式，通过调用官方库中的函数，指针交换，将v的地址给了创建的对象。

template <class InputIterator>
vector(InputIterator first, InputIterator last) {
  while (first != last) {
    push_back(*first);
    first++;
  }
}

通过传需要拷贝的对象的数据范围给新对象（迭代器区间），是个函数模版，可以用任意的迭代器初始化，类型匹配即可。

模板构造函数，用于构造一个std::vector，该构造函数接受两个迭代器first和last，它们定义了要复制到新vector中的元素的范围。

C++之打造my vector篇（下）：https://developer.aliyun.com/article/1624991

C++之打造my vector篇（上）

前言

1.参照官版，打造vector的基本框架

2.丰富框架，实现接口方法

基本的迭代器实现

数据的[]访问

容量和数据空间的改变

vector空间大小的返回与判空

数据的增删

数据打印

拷贝构造和赋值重载

热门文章

最新文章

相关课程

相关电子书