分块刨析从函数原型到分块实现C++STL(vector)

简介: 分块刨析从函数原型到分块实现C++STL(vector)

一, 函数原型部分分析(简单举例使用便于理解)

  • 简单测试使用:
int main() {
  std::vector<int> vint;
  vint.reserve(3);
  cout << vint.capacity() << endl;
  vint.resize(10, 5);
  cout << vint.size() << endl;
  for (auto& e : vint) {
    cout << e << " ";
  }
  cout << endl;
  return 0;
}

如上可以证明的就是resize改变的size ,reserve改变的是capacity是预先开出空间,至于使用reserve的使用可以减少扩容的次数.. 提高效率..

迭代器函数, 返回迭代器. 支持迭代器, 有了迭代器才能支持范围的遍历方式. 像是上述使用的for (aoto& e : vint) 的遍历方式都是因为存在迭代器作为支撑才可以的


为了验证, 简单的使用迭代器模板类模拟实现一下  for_each


引入一下小小的知识点,迭代器类型   +   仿函数类型   作为类型模板是一种很常见的使用方式.    这种方式常用在对于一段区间的元素做函数处理的场景下:  (很重要的trait)

template<class InputIterator, class Function>
  void Func(InputIterator first, InputIterator last, Function f) {
    while (first != last) {
      f(*first);
      ++first;
    }
    return;
  }

eg :      

template<class T >
  struct Print {
    void operator()(T& val)const {
      cout << val << " ";
    }
  };
  template<class InputIterator, class Function>
  void for_each(InputIterator first, InputIterator last, Function f) {
    while (first != last) {
      f(*first);
      ++first;
    }
    return;
  }
}
int main() {
  std::vector<int> vint;
  vint.reserve(3);
  cout << vint.capacity() << endl;
  vint.resize(10, 5);
  cout << vint.size() << endl;
  //for (auto& e : vint) {
  //  cout << e << " ";
  //}
  tyj::for_each(vint.begin(), vint.end(), tyj::Print<int>());
  cout << endl;
  return 0;
}
  • 所以可以证明的是for(aoto& e : 容器)的这种遍历方式应该底层也是基于迭代器实现的

二、 迭代器设计思想,vector迭代器分析

因为  vector 的底层就是一个动态数组.维护的是一个线性空间,  所以普通的原生指针可以直接使用做迭代器, 因为本身指针就是支持operator++  operator-- operator*这些运算的

    typedef T* iterator;
    typedef const T* const_iterator;

三,整体的大体可以快速看见效果的框架

对于上述先解释一下,很多时候我们要写一个很大的东西, 为了降低deBug的成本, 其实可以先实现必要性的可以看见效果的区块, 大体的框架性写好, 效果看到了然后


插入元素时候的扩容机制: 如果是需要扩容,采取的一般是二倍扩容的方式进行扩容的,扩容分为三部,新开空间,转移数据,销毁原有空间...      (记住转移数据调用深拷贝,不可以memcpy) why?

namespace tyj {
  template <class T>
  class vector {
    typedef T* iterator;
    typedef const T* const_iterator;
  public:
    vector() //默认构造
      : start(nullptr)
      , finish(nullptr)
      , end_of_storage(nullptr) {
    }
    vector(int n, const T& val = T()) //带参构造
      : start(new T[n]) {
      finish = start + n;
      end_of_storage = finish;
      for (int i = 0; i < n; ++i) {
        start[i] = val;
      }
    }
    iterator begin() {
      return start;
    }
    const_iterator begin() const {
      return start;
    }
    iterator end() {
      return finish;
    }
    const_iterator end() const {
      return finish - 1;
    }
    size_t size() const {
      return finish - start;
    }
    size_t capacity() const {
      return end_of_storage - start;
    }
    void reserve(int n) {//预先开空间
      if (n <= capacity()) return;
      //说明需要新开空间, 三步
      //1.新开空间
      T* pTemp = new T[n];
      //2.转移数据
      int _size = size();
      for (int i = 0; i < _size; ++i) {
        pTemp[i] = start[i];
      }
      //3.销毁原有空间
      delete[] start;
      start = pTemp;
      finish = start + _size;
      end_of_storage = start + n;
    }
    void push_back(const T& val) {
      if (size() == capacity()) {
        reserve(size() == 0 ? 8 : (size() << 1));
      }
      //放入数据
      *finish = val;
      finish++; //尾部迭代器后移
    }
  private:
    //[start, finish)
    iterator start;//当前使用空间起点
    iterator finish;//当前使用空间末尾
    iterator end_of_storage; //空间末尾
  };
  template <class T >
  struct Print {
    void operator()(T& val) const {
      cout << val << " ";
    }
  };
  template<class InputIterator, class Function>
  void for_each(InputIterator first, InputIterator last, Function f) {
    while (first != last) {
      f(*first);
      ++first;
    }
  }
}
int main() {
  tyj::vector<int> vint;
  for (int i = 0; i < 5; ++i)
    vint.push_back(i);
  cout << vint.size() << endl;
  tyj::for_each(vint.begin(), vint.end(), tyj::Print<int>());
  cout << endl;
  return 0;
}

三,重点函数分块分析图解实现, 仅仅只是写哪些可能大家不清楚的,都可以写的部分写了也没用

  • 然后就是一个一个函数的分析应该如何设计的问题

各种构造函数的设计思想,如何只写一个然后实现代码复用

  • 区间范围range构造

  • swap为复用代码做准备

  • 赋值重载

同样的道理,已经复用了拷贝构造函数构造出来了  vec 对象直接  窃取  vec 换成自己的,马匪看过吗,让我成为你, 你成为空气

  • 移动构造   (更加强盗,不齿,直接抢将死之人的身份)

insert  +  erase 的设计,以及分析返回值,加之分析迭代器失效会出现的位置,和抛出设计中的细节之处

  • insert

  • erase

  • 再看   insert   +  erase   都存在一个  iterator作为返回值,为啥,跟新旧的迭代器,防止迭代器失效。。。   向如下的代码为啥要  接收一下  erase 之后的返回值也就可以理解了,防止使用失效的迭代器
void test() {
  std::vector<int> vec(5, 1);
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    it = vec.erase(it);
  }
}
it = v.begin();
PrintVector(v);
while (it != v.end()) {
  if (*it % 2 == 0)
    it = v.erase(it);
  else
    ++it;
}

  • 至此比较有用的部分都已经分析完成了。

四. 整体代码  (实现代码)

#include <vector> 
#include <algorithm>
#include <iostream>
#include <assert.h>
using namespace std;
namespace tyj {
  template <class T >
  class vector {
  public:
    //原生指针作为迭代器
    typedef T* iterator;
    typedef const T* const_iterator;
    //无参构造函数
    vector()
      : start(nullptr)
      , finish(nullptr)
      , end_of_storage(nullptr) {
    }
    vector(int n, const T& val = T()) 
      : start(new T[n]), 
      finish(start + n), 
      end_of_storage(start + n) {
      //放入数据
      for (int i = 0; i < n; ++i) {
        start[i] = val;
      }
    }
    //写范围构造函数
    template<class InputIterator>
    vector(InputIterator first, InputIterator last) {
      //利用范围进行构造
      while (first != last) {
        push_back(*first++);//直接进行复用接口
      }
    }
    //接下来写拷贝构造, 赋值运算符重载,移动构造,全部进行复用接口
    void swap(vector<T>& vec) {
      ::swap(start, vec.start);
      ::swap(finish, vec.finish);
      ::swap(end_of_storage, vec.end_of_storage);
    }
    vector(const vector<T>& vec) 
      : start(nullptr)
      , finish(nullptr)
      , end_of_storage(nullptr) {
      vector<T> tmp(vec.begin(), vec.end());
      swap(tmp);//复用范围构造代码
    }
    vector<T>& operator=(vector<T> vec) {
      swap(vec);//复用拷贝构造代码
      return *this;
    }
    //移动构造, 窃取资源,窃取将亡对象的底层堆区资源
    //反正你都要死亡了不如用来给我构造
    vector(vector<T>&& vec) 
      : start(nullptr)
      , finish(nullptr)
      , end_of_storage(nullptr) {
      swap(vec);
    }
    iterator begin() {
      return start;
    }
    const_iterator begin() const {
      return start;
    }
    iterator end() {
      return finish;
    }
    const_iterator end() const {
      return finish;
    }
    void resize(size_t n, const T& val = T()) {
      if (n <= size()) return;  //啥事不用做
      //至此说明了超出的部分需要设置为val
      if (n > capacity()) reserve(n);//先扩容
      //然后赋值
      while (finish != start + n) {
        *finish++ = val;
      }
    }
    void reserve(int n) {
      //预先开空间,三部曲目
      if (n <= capacity()) return;
      //至此说明需要重新开空间
      T* pTemp = new T[n];
      size_t sz = size();//保存之前容器中的元素大小
      //转移数据
      for (int i = 0; i < sz; ++i) {
        pTemp[i] = start[i];
      }
      delete [] start;//删除掉原有的空间
      start = pTemp;
      finish = pTemp + sz;
      end_of_storage = start + n;
    }
    void push_back(const T& val) {
      if (finish == end_of_storage) {
        reserve(capacity() > 0 ? capacity() << 1 : 4);
      }
      //有了空间,然后就是进行数据插入
      *finish++ = val;//放入数据
    }
    bool empty() {
      return start == nullptr;
    }
    size_t size() {
      return finish - start;
    }
    size_t capacity() {
      return end_of_storage - start;
    }
    //网pos位置插入一个元素,插入一定谨防的是插入扩容的原有迭代器失效问题
    iterator insert(iterator pos, const T& val) {
      assert(pos >= start && pos <= finish);//断言位置合法
      if (finish == end_of_storage) {
        size_t step = pos - start;
        //扩容首先
        reserve(capacity() > 0 ? capacity() << 1 : 4);
        //扩容之后原有的pos迭代器会失效跟新
        pos = start + step;
      }
      //拿到finish迭代器同时finish迭代器后移动
      iterator it = finish++;
      //腾出空间
      while (it != pos) {
        *it = *(it - 1);
        --it;
      }
      *pos = val;//放入插入数据
      return pos;//返回插入位置元素
    }
    //删除一定注意的是删除的位置其实还是pos 因为返回下一个元素其实是覆盖到pos位置了
    iterator erase(iterator pos) {
      //覆盖删除整个元素
      assert(pos >= start && pos < finish);
      iterator it = pos + 1;
      while (it <= finish) {
        *(it - 1) = *it;//覆盖删除
        ++it;
      }
      --finish;//尾部迭代器前移动
      return pos;
    }
    ~vector() {
      if (start) {
        delete[] start;
      }
      start = finish = end_of_storage = nullptr;
    }
  private:
    T* start;
    T* finish;
    T* end_of_storage;
  };
  template<class InputIterator, class Function>
  void for_each(InputIterator first, InputIterator last, Function f) {
    while (first != last) {
      f(*first);
      ++first;
    }
  }
  template<class T>
  struct Print {
    void operator()(T& val) const {
      cout << val << " ";
    }
  };
}
template<class T>
void PrintVector(tyj::vector<T>& vec) {
  tyj::for_each(vec.begin(), vec.end(), tyj::Print<T>());
  cout << endl;
}

测试代码

void TestVector3()
{
  int a[] = { 1, 2, 3, 4 };
  tyj::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));
  // 使用find查找3所在位置的iterator
  auto pos = find(v.begin(), v.end(), 3);
  //pos迭代器可以失效,  插入操作迭代器也会失效
  // 在pos位置之前插入30
  v.insert(pos, 30);
  PrintVector(v);
  // 删除pos位置的数据
  pos = find(v.begin(), v.end(), 3);
  v.erase(pos);
  PrintVector(v);
}
void TestVector1()
{
  // constructors used in the same order as described above:
  tyj::vector<int> first; // empty vector of 
  tyj::vector<int> second(4, 100); // four ints with value 
  tyj::vector<int> third(second.begin(), second.end()); // iterating through 
  tyj::vector<int> fourth(third); // a copy of third
  // the iterator constructor can also be used to construct from arrays:
  int myints[] = { 16, 2, 77, 29 };
  tyj::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
  std::cout << "The contents of fifth are:";
  for (tyj::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
    std::cout << *it << " ";
  std::cout << endl;
  // 测试T是string时,拷贝问题
  tyj::vector<string> strV;
  strV.push_back("1111");
  strV.push_back("2222");
  strV.push_back("3333");
  strV.push_back("4444");
}
void TestVector2()
{
  // 使用push_back插入4个数据
  tyj::vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  PrintVector(v);
  // 使用迭代器进行修改
  auto it = v.begin();
  while (it != v.end())
  {
    *it *= 2;
    ++it;
  }
  PrintVector(v);
  // 这里可以看出C++11支持iterator及接口,就支持范围for
  for (auto e : v)
    cout << e << " ";
}
// iterator失效问题
void TestVector4()
{
  int a[] = { 1, 2, 3, 4 };
  tyj::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));
  // 删除pos位置的数据,导致pos迭代器失效
  auto pos = find(v.begin(), v.end(), 3);
  v.erase(pos);
  cout << *pos << endl; // 此处会导致非法访问
  // 在pos位置插入数据,导致pos迭代器失效。
  // insert会导致迭代器失效,是因为insert可
  // 能会导致增容,增容后pos还指向原来的空间,而原来的空间已经释放了。
  pos = find(v.begin(), v.end(), 3);
  v.insert(pos, 30);
  cout << *pos << endl; // 此处会导致非法访问
  // 实现删除v中的所有偶数
  // 下面的程序会崩溃掉,如果是偶数,erase导致it失效
// 对失效的迭代器进行++it,会导致程序崩溃
  auto it = v.begin();
  //while (it != v.end())
  //{
  //  if (*it % 2 == 0)
  //    v.erase(it);
  //  ++it;//每一次erase之后进行跳跃
  //}
  // 以上程序要改成下面这样,erase会返回删除位置的下一个位置
  it = v.begin();
  PrintVector(v);
  while (it != v.end())
  {
    if (*it % 2 == 0)
      it = v.erase(it);
    else
      ++it;
  }
}
int main() {
  //tyj::vector<int> vec1;
  //for (int i = 0; i < 5; ++i) {
  //  vec1.push_back(i);
  //}
  //PrintVector<int>(vec1);
  //tyj::vector<int> vec2;
  //vec2.resize(5, 1);
  //PrintVector<int>(vec2);
  //int nums[5] = { 1, 2, 3, 4, 5 };
  //tyj::vector<int> vec3(nums, nums + sizeof(nums) / sizeof(int));
  //PrintVector<int>(vec3);
  //tyj::vector<int> vec4(vec3);
  //PrintVector<int>(vec4);
  //TestVector3();
  //TestVector2();
  //TestVector4();
  TestVector1();
  return 0;
}

五. 整合小结一下,以及特别谈一谈如何写一个STL容器和迭代器设计思想(迭代器是什么),迭代器失效的问题.

如何实现一个STL书写的方法论


首先分析如果要写一个STL容器应该如何下手的问题,找到一个官方文档分析组件 + 接口


推荐官方文档网址:   www.cplusplus.com  


写一个STL 需要将迭代器设计和整体的设计分开来,先实现迭代器的设计 + 实现最简单的插入接口 (完成框架),测试插入接口,一来可以获得一定成就,而来可以知道自己基本框架是否搭建正确


阅读文档分析重点接口函数,可以买一本STL源码刨析,结合侯捷老师的讲述去设计接口,   将有用的接口一一实现.   (在实现的过程中不断测试以及发现细节坑点)


总结实现细节中出现的坑点   +  快速复现重写整个框架  (记忆熟练)


其实谈迭代器的设计在此处不算很合适,因为T* 就是一个原生指针,而且还是连续的线性存储空间,原生指针作为迭代器,本身迭代器就支持  ++  --  *  这些操作,加之元素本身就是连续存储的,  所以此处没有对迭代器的设计画太多功夫。


迭代器,算是一个智能指针类的感觉,但是也不完全是,可以帮助我们管理访问容器中的元素,支持 ++  -- *  这些操作来访问复杂存储结构中的  元素。


迭代器的设计是为了统一,是为了做粘合剂,做通用各式各样容器和算法之间的粘合剂,  有了迭代器,我们才能做各式各样容器的统一泛型算法操作,才能统一各种格式各样的容器元素的遍历方式,提供统一遍历接口.   是STL中特别重要的组件

上述这些算法,没有迭代器根本不可能这样写


迭代器失效,说白了其实本质是内存问题,扩容后,原来的迭代器全部不可以用了,因为原来的迭代器指向原来的那片空间,可是 扩容后原来那片空间都释放掉了,你如何敢访问,所以每一次关于迭代器的操作我们需要接收返回值就是这个道理,跟新旧的迭代器,避免使用失效迭代器,     it = e.erase(it)            不能是    e.erase(it++); ; 因为删除之后你不清楚,it   的情况如何,但是返回迭代器是指向下一个元素的有效迭代器,所以需要接收返回值.              删除it 之后 it 本质是一个失效迭代器了,如何赶直接  ++  因为他的本质在接收返回值之前还是哪个即将别删除的迭代器


所以 删除,插入扩容,都可能导致迭代器失效,插入失效是因为扩容,删除失效是因为它已经别干掉了,很可能是delete  或者其他操作


相关文章
|
1月前
|
程序员 C++ 容器
在 C++中,realloc 函数返回 NULL 时,需要手动释放原来的内存吗?
在 C++ 中,当 realloc 函数返回 NULL 时,表示内存重新分配失败,但原内存块仍然有效,因此需要手动释放原来的内存,以避免内存泄漏。
|
1月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
70 5
|
1月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
21 1
|
1月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
53 1
|
1月前
|
存储 前端开发 C++
C++ 多线程之带返回值的线程处理函数
这篇文章介绍了在C++中使用`async`函数、`packaged_task`和`promise`三种方法来创建带返回值的线程处理函数。
47 6
|
1月前
|
C++
C++ 多线程之线程管理函数
这篇文章介绍了C++中多线程编程的几个关键函数,包括获取线程ID的`get_id()`,延时函数`sleep_for()`,线程让步函数`yield()`,以及阻塞线程直到指定时间的`sleep_until()`。
25 0
C++ 多线程之线程管理函数
|
1月前
|
编译器 C++
【C++】—— vector模拟实现
【C++】—— vector模拟实现
|
1月前
|
算法 安全 Linux
【C++STL简介】——我与C++的不解之缘(八)
【C++STL简介】——我与C++的不解之缘(八)
|
1月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
23 0
|
1月前
|
算法 C++ 容器
C++之打造my vector篇(下)
C++之打造my vector篇(下)
27 0