【C++】vector容器初步模拟

简介: 我们初步完成了对vector 的模拟实现,但是依然有问题,比如不支持string等特殊类型。所以下一篇文章我们来一起完善一下。

1 认识vector

开始了解

  1. vector是表示可变大小数组的序列容器。
  2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
  3. 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
  4. vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  5. 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
  6. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list统一的迭代器和引用更好。

使用STL的三个境界:能用,明理,能扩展 ,那么下面学习vector,我们也是按照这个方法去学习

底层实现

我们来了解一下vector的底层实现是如何做到,首先就要了解其类成员是如何定义的,这样我们才能更好的复刻vector(以下是1996年的STL版本,还比较简单):

protected:
  typedef simple_alloc<value_type, Alloc> data_allocator;
  iterator start; 
  iterator finish;
  iterator end_of_storage //容量结束;

可以看到受保护的内部成员变量是由三个迭代器构成的。

迭代器的底层是:

typedef T value_type;
typedef value_type* iterator;

也就是说底层是指针,T是模版类的参数。接下来我们在观察一下构造函数是如何操作的(参考一部分):

 vector() : start(0), finish(0), end_of_storage(0) {}
 vector(size_type n, const T& value) { fill_initialize(n, value); }
 vector(int n, const T& value) { fill_initialize(n, value); }
 vector(long n, const T& value) { fill_initialize(n, value); }

这个fill_initialize又是什么呢???是初始化函数,(在工程文件中,经常使用一层又一层的嵌套,由于我还没有丰富的工程经验,我看起来还是很费劲,晕乎乎的)。我们看一部分即可,现在我们开始手搓vector,针对内置类型进行操作。

2 开始实现

我们开始逐步进行实现。

成员变量

根据我们刚才所查看的源码,我们要使用三个迭代器,要使用迭代器,我们可以使用指针进行模拟。

//使用模版 兼容各种类型
template<typename T>
class vector {
public:
  //重命名 指针即可模拟迭代器 常量与非常量都要提供哦
  typedef T* iterator;
  typedef const T* const_iterator;
  private:
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _end = nullptr;
  };

写出三个迭代器(指针)后,我们对构造函数应该也有了大致思路:需要初始化三个迭代器,所以我们给与初始值nullptr。让后进行开辟空间。

构造函数 析构函数

这里的构造函数我设置三个接口,一个是空构造,一个是开辟 N 个空间并初始化为val,一个是拷贝构造:

//空构造
vector() 
{}
//开辟 N 个空间并初始化为val
vector(size_t n,T val = T()) {
  iterator tmp = new T[n];
  _start = tmp;
  for (iterator it = begin(); it < _start + n ;it++) {
     *it= val;
  }
  _finish = _start + n;
  _end = tmp + n ;

}
/拷贝构造
vector(vector<T>& v) {
  //依次尾插即可完成操作
  for (auto s : v) {
    push_back(s);
  }
}

析构函数就是简单的释放空间即可:

~vector()
  {
    delete[] _start;
    _start = _finish = _end = nullptr;
  }

我们完成了构造函数和析构函数,为了能够进行测试,我们现在来实现尾插操作:

尾插

尾插操作之前,根据我们实现string的经验来说,我们需要做一些准备工作,实现一些常用接口(size(),capacity(),reserve(),resize()):

注意:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。

    //注意const 保证不会进行权限的放大
    size_t size() const{
      return _finish - _start;
    }
    size_t capacity() const{
      return _end - _start;
    }
    bool empty(){
      return size() == 0;
    }
    //扩容
    void reserve(size_t newcapacity) {
      //记录位置
      size_t n = _finish - _start;
      T* tmp = new T[newcapacity];
      //拷贝
      memcpy(tmp, _start, size() * sizeof(T));
      _start = tmp;
      _finish = _start + n;
      _end = _start + newcapacity;
    }
    //改变大小
    void resize(size_t n, T val = T()) {
      //x需要扩容
      if ( n > size())
      {
        reserve(n);
         ;
        while (_finish != _end) {
          *_finish = val;
          _finish++;
        }
        
      }
      //不需扩容
      else 
      {
        _finish = _start + n;
      }
    }

实现了这些接口,就可以顺畅的进行尾插的书写,通过size()和capacity()可以判断是否需要扩容,reserve可以进行扩容。然后再_finish位置插入新的数据,再移动_finish即可。

    //尾插
    void push_back(T val) 
    {
      if (size() == capacity()) {
        //扩容
        reserve(capacity() == 0 ? 4 : 2 * capacity());
      }
      *_finish = val;
      _finish++;
    }

接下来我们在完善一下迭代器。

迭代器

迭代器的实现很简单,对指针进行重命名即可(真正的迭代器没有这么简单)'

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; }

完成了begin() 和end()函数,就可以使用基于范围的for循环了。

我们进行一个简单的测试,来看看我们写的构造,尾插是否正常。

template<class T>
void print_vector(const vector<T> v) {
  for (size_t i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
}
//构造,尾插测试
void vector_test1() {
  cout << "---------构造 ,尾插测试---------\n";
  vector<int> v1;
  vector<int> v2(4);

  v2.push_back(1);
  v2.push_back(2);
  v2.push_back(3);
  v2.push_back(4);

  print_vector(v2);

  v1.push_back(5);
  v1.push_back(6);
  print_vector(v1);
  cout << v1.size() << endl;
  cout << v1.capacity() << endl;

  vector<int> v3(v1);
  print_vector(v3);
}

看一下效果:

没有问题!!!

插入 删除 寻找操作

这个也很简单,对数据进行挪动就可以完成:

//任意位置插入
void insert(size_t pos = 0,T val = T()) {
//保证在数据范围之内
  assert(pos >= 0);
  assert(pos <= size());
  //检查
  if (size() == capacity()) {
    //扩容
    reserve(capacity() == 0 ? 4 : 2 * capacity());
  }

  iterator it = end();
  //依次后移 然后插入
  while (it >= begin() + pos) {
    *(it + 1) = *it;
    it--;
  }
  it++;
  *it = val;
  _finish++;
}
void erease(size_t pos) 
{
//保证在数据范围之内
  assert(pos >= 0);
  assert(pos <= size());

  iterator it = begin() + pos;
  //依次前移
  while (it < end()) {
    *it = *(it + 1);
    it++;
  }
  _finish--;

}
//尾删
void pop_back() {
  erease(size());
      
}
size_t find(T val = T()) 
{
  //依次寻找
  for (iterator it = _start; it < _finish;it++) {
    if (*it == val) return it - _start;
  }
  return -1;
}

操作符重载

vector容器最重要的操作符应该就是[ ]操作了吧,此外重载一个 = :

//提供常量与非常量
T& operator[](size_t n) { assert(n >= 0); assert(n < size()); return *(_start + n); }
const T& operator[](size_t n) const { assert(n >= 0); assert(n < size()); return *(_start + n); }
//类似拷贝
vector<T>& operator=(vector<T>& v){

  T* tmp = new T[v.capacity()];
  memcpy(tmp, v._start, v.size() * sizeof(T));
  size_t pos = v.size();
  size_t n = v.capacity();

  _start = tmp;
  _finish = _start + pos;
  _end = _start + capacity();

  return *this;
}

这样就完成了:

我们进行一个测试来看看是否可行:

void vector_test2() {
  cout << "---------resize find insert erase测试---------\n";
  
  vector<int> v1;

  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(4);
  v1.push_back(5);
  v1.push_back(6);
  print_vector(v1);
  cout << v1.find(2) << endl;

  v1.resize(10, 0);
  print_vector(v1);
  v1.insert(0, 0);
  print_vector(v1);
  v1.erease(5);
  print_vector(v1);
  
}

来看效果:

成功!!!

swap函数

接下来在提供一个swap 函数以供交换,注意一定是深拷贝!!!

    void swap(vector& v) {

      T* tmp = new T[v.capacity()];
      memcpy(tmp, v._start, v.size() * sizeof(T));
      size_t pos = v.size();
      size_t n = v.capacity();

      v._start = _start;
      v._finish = _finish;
      v._end = _end;

      _start = tmp;
      _finish = _start + pos;
      _end = _start + capacity();


    }

来进行一个简单测试:

//交换测试
void vector_test3() {
  cout << "---------swap 测试---------\n";
  vector<int> v1;

  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(4);
  v1.push_back(5);
  v1.push_back(6);
  print_vector(v1);
  vector<int> v2(4);

  v2.push_back(1);
  v2.push_back(3);
  v2.push_back(1);
  v2.push_back(4);
  print_vector(v2);
  v2.swap(v1);

  print_vector(v1);
  print_vector(v2);

}

来看效果:

成功交换!!!

总结

我们初步完成了对vector 的模拟实现,但是依然有问题,比如不支持string等特殊类型。所以下一篇文章我们来一起完善一下。

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

相关文章
|
1月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
46 2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
|
18天前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
16 1
|
1月前
|
安全 测试技术 C++
【C++篇】从零实现 C++ Vector:深度剖析 STL 的核心机制与优化2
【C++篇】从零实现 C++ Vector:深度剖析 STL 的核心机制与优化
57 6
|
28天前
|
编译器 C++
【C++】—— vector模拟实现
【C++】—— vector模拟实现
|
1月前
|
存储 C++ 容器
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器1
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
51 5
|
1月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
47 2
|
23天前
|
算法 C++ 容器
C++之打造my vector篇(下)
C++之打造my vector篇(下)
25 0
|
23天前
|
存储 编译器 C++
C++之打造my vector篇(上)
C++之打造my vector篇(上)
25 0
|
28天前
|
算法 C++ 容器
【C++】—— vector使用
【C++】—— vector使用
|
30天前
|
存储 缓存 C++
C++番外篇——list与vector的比较
C++番外篇——list与vector的比较
21 0