c++学习之---vector

        vector常用接口的介绍:       

 reserve的使用细节:

reserve的扩容机制在不同平台下的差别

1. vector<char> v1;
2. cout << "initial size:" << v1.size() <<" " << "initial capacity:" << v1.capacity() << endl;
3. for (size_t i = 0; i < 20; i++)
4. {
5.         int size = v1.size(), capacity = v1.capacity();
6.         v1.push_back('i');
7.         if (capacity != v1.capacity())
8.                 cout << "new capacity:" << v1.capacity() << endl;
9.                
10. }

复制代码

 

缩容的代价(重新开空间) :

           在上面的步伐中 ,  我试图使用reserve来减少vector对象的capacity , 却发现没有结果 , 查文档也可以发现 , 即使想要调解的目的容量是大于元素个数size , 也没法缩容 , 因为缩容的代价很大!!!
  

        resize的使用细节:

           resize的是和上面的reserve比较类似的接口 , 只不过resize的权利更大 , 他可以对多出来的空间进行初始化(第二个参数,默认用0填充,既可以当作数字也可以当作字符串停止符\0) ,也可以把多余的数据给删除 , 这是reserve所不具备的.
   

        隐藏的"下标访问":

           刚学完string后转到vector可能会因为没有 下标访问操纵符[]的重载而不太习惯 , 起始有一个美满的平替----那就是迭代器!!!

1. vector<char> v4{'d','c','e','s','a','p'};
3. cout << *v4.begin() << endl;
4. cout << *(v4.begin() + 3) << endl;
5. cout << typeid(v4.begin()).name() << endl;

复制代码

           上图中可以看到 : 只管vector的迭代器在使用上可以原生指针一样 , 但他的底层还是做了很多封装的 , 有vector类内部的 typedef , 也有对解引用操纵符 * 的重载 . 
          当然咯 , vector本质上毕竟还是次序表 ,内部存储空间的地点依旧和string一样是连续的 , 以是之后我们自己模拟实现他的迭代器还是会比较简单的
           模拟实现的一些细节:

1,reserve扩容时的小细节(初版...):

           和string不同 , vector底层的成员变量是三个指向一段内存空间不同位置的指针 , 由此也影响了他对于元素个数size和容量capacity的计算 , 标题由此而来...

1. 有问题的函数实现
2. void reserve(size_t newCapacity)
3. {
4.         if (newCapacity > capacity())
5.         {
6.                 iterator newStart = new T[newCapacity];
7.                 memcpy(newStart, _start, sizeof(T) * size());
8.                 _start = newStart;
9.                 _finish = _start + size();
10.                 _end_of_storage = _start + newCapacity;
11.         }
12. }

复制代码

 

           要解决标题也很简单 , 因为最重要的成员变量就是_start , 别的两个都是在它的基础上往后增加的 , 以是 , 想要在_start更新后还可以得到精确的_finish值 , 只需要在_start扩容之前(也就是_start更改之前) 记载下_finish相对于_start的偏移量就好了.
          精确代码如下:

1. void reserve(size_t newCapacity)
2. {
3.         if (newCapacity > capacity())
4.         {
5.                 size_t oldSize = size();  //再扩容之前记录下_finish相对于_start的偏移量,也就是元素个数
6.                 iterator newStart = new T[newCapacity];
7.                 memcpy(newStart, _start, sizeof(T) * size());
8.                 _start = newStart;
9.                 _finish = _start + oldSize;  //用更新后的_start加上偏移量,就可以再次定位到新的_finish
10.                 _end_of_storage = _start + newCapacity;
11.         }
12. }

复制代码

 2,模版和类域的豪情碰撞(同时也体会下关键字auto的伟大)!!!

           下面是一个对于vector范例对象通用的打印函数

1. template<class T>
2. void print_vector(vector<T>& v)  //全局函数,所以需要自己传递vector对象
3. {
4.         vector<T>::iterator it = v.begin();
5.         while (it != v.end())
6.         {
7.                 cout << *(it++) << " ";
8.         }
9. }

复制代码

           上述代码在编译时会报错 , 下面是分析:
   

           当然了,如果不想在这里各种弯弯绕绕的,直接使用小巧精悍的auto: 

1. template<class T>
2. void print_vector(vector<T>& v)
3. {
4.         //typename vector<double>::iterator it = v.begin();
5.         auto it = v.begin();   //不用写那么多,直接auto!!!
6.         while (it != v.end())
7.         {
8.                 cout << *(it++) << " ";
9.         }
10. }

复制代码

3, 构造函数的灵活写法(复用push_back)

           写法一的代码如下 : 主要是使用了函数局部域对象出了栈帧会主动销毁的特性 

1. vector(vector<T>& obj)
2. {
3.         vector<T> tmp(obj.cbegin(),obj.cend()); //构造一个符合数据要求的临时的局部对象tmp
4.         swap(tmp);  //将局部对象构造好的值交换给目标对象
5. }
7.   //除了拷贝构造函数之后 , *this对象已经拥有了tmp对象的值 , 而tmp在销毁时又会自己调用析构.
10. //需要注意的在成员变量声明是最好确定缺省值 , 防止此处来不及调用默认构造 , 将不确定的*this对象的初始值交换给临时变量tmp销毁(比如野指针)
11. //以下是成员变量的缺省值nullptr(delete对空指针不处理不会出错,但对于野指针就不是了)
12. private:
13.         iterator _start = nullptr;
14.         iterator _finish = nullptr;
15.         iterator _end_of_storage = nullptr;

复制代码

          写法二的代码如下 : 复用了push_back的功能 , 且为了制止从一个新对象开始逐一尾插导致的扩容的性能开销 , 又使用了reserve 函数 . 

1. vector(vector<T>& obj)
2. {
3.     reserve(obj.capacity()) //根据目标对象obj提前开好空间
4.         for (auto& au : obj)    //遍历目标对象obj,并一一插入元素
5.         {
6.                 push_back(au);
7.         }
8. }

复制代码

           总之 拷贝构造函数的写法是很灵活的 , 只要保证新创建的对象在拷贝内容的同时还能有自己完全独立的空间 , 制止两个元素拥有同一块空间导致的后续析构两次的情况
  模拟实现里的小坑:

1,借助形参传递和swap函数实现赋值重载导致的弄巧成拙:

           在赋值运算符重载的实现中 , 可以通过复用现有的构造函数和互换函数帮我们拷贝资源和互换内容 , 以及可以使用形参修改不影响实参且除了作用域就会销毁的特性 , 来实现一个间接的vector的赋值运算符重载函数.

1. //构造函数再在此省略
2. .........
4. //交换函数
5. void swap(vector<T>& obj)
6. {
7.         std::swap(_start, obj._start);
8.         std::swap(_finish, obj._finish);
9.         std::swap(_end_of_storage, obj._end_of_storage);
10. }
11. //赋值运算符重载函数
12. vector<T>& operator=(vector<T> obj)
13. {
14.         swap(obj);
15.         return *this;
16. }

复制代码

           下面是对上述代码的分析:
  

 2,begin()和end()不因使用引用返回


3,insert函数里的迭代器失效标题

           在insert函数的参数中 , 担当了外部传递的一个迭代器变量 , 也就是内存中的一块位置 . 但是如果插入这一个元素需要扩容 , 那vector底层指针指向的一整块空间的地点都会发生改变 , 因此原来的迭代器就成为了一个类似野指针的东西 , 指向了一块未知的内存空间 , 引发标题...
  

            通过下图可知 , 这一种迭代器失效发生在异地扩容时 , 目的空间变了 , 但迭代器依然指向原地 , 更新一下就好
   

1. iterator insert(iterator pos, const T& val)
2. {
3.         if (size() == capacity())
4.         {
5.                 size_t offSet = pos - _start; //记录迭代器pos相较于_start的偏移量
6.                 reserve(capacity() == 0 ? 4 : 2 * capacity());
7.                 pos = _start + offSet;        //更新pos
8.         }
9.         iterator end = _finish;
10.         while (pos < end)
11.         {
12.                 *end = *(end - 1);
13.                 end--;
14.         }
15.         *pos = val;
16.         _finish++;
17.         return pos;
18. }

复制代码

4,erase函数导致的迭代器失效(以删除序列里的偶数为例)

           erase和上面的insert函数不同 , 因为是移除数据以是不会出现异地扩容导致原来的迭代器指向未知位置地点的情况 , 他的迭代器更多的是在使用层面的失效.
         情况一 : 跳过了目的元素

        大要代码如下(其中vector对象的元素奇偶相间):

1. vector对象v的元素 {1,2,3,4,5,6}
2. //保留偶数
3. vector<int>::iterator it = v.begin();
4. while (it != v.end())
5. {
6.         if (*it % 2 != 0) //是奇数则执行erase来删除
7.         {
8.                 v.erase(it);
9.         }
10.         it++;
11. }

复制代码

        执行结果正常,只留下了偶数:

        但是如果为vector对象增加一个值 , 此处增加一个奇数 1 :

1. vector对象v的元素 {1,1,2,3,4,5,6}  //变成了有两个奇数1相邻
2. //保留偶数
3. vector<int>::iterator it = v.begin();
4. while (it != v.end())
5. {
6.         if (*it % 2 != 0) //是奇数则执行erase来删除
7.         {
8.                 v.erase(it);
9.         }
10.         it++;
11. }

复制代码

        执行结果就出了标题 , 有一个奇数1没有被精确删除:

        下面绘图来明晰标题的根源:

情况二 : 跳过了迭代器的停止条件!!!

        大题代码还是稳定 , 只不过元素的个数变成的奇数个:

1. vector对象v的元素 {1,2,3,4,5}  //总共只有奇数个元素!!!
2. //保留偶数
3. vector<int>::iterator it = v.begin();
4. while (it != v.end())
5. {
6.         if (*it % 2 != 0)
7.         {
8.                 v.erase(it);
9.         }
10.         it++;
11. }

复制代码

         执行结果如下 , 出了标题, 代码崩溃 ...

        下面还是绘图来明晰标题的根源:

 微调步伐的执行逻辑来制止迭代器失效的影响:

           由于刚才的两个标题本质上都在于erase清除一个元素后导致的元素挪动让下一个待判断元素主动被it指向 , 也就是说:如果删除了元素,it就相当于已经++到下一个元素了 , 因此 , 使用一个分支语句让it在没有执行erase时才会++就可以了.

1. //正确的代码
2. vector<int>::iterator it = v.begin();
3. while (it != v.end())
4. {
5.         if (*it % 2 != 0)
6.         {
7.                 v.erase(it);
8.         }
9.         else   //关键在于用else语句来避免it无脑的++
10.         {
11.                 it++;
12.         }
13. }

复制代码

 5,构造函数的参数匹配原则导致的歧义:

           vector有这样两个比较重要的构造函数版本 : 一是用 n 个val初始化 ,二是用迭代器区间初始化 . 但他们同时定义后如果不稍加小心也可能会打架!!!
  

           解决方法有很多种 , 这里我们很库里的实现保持同等 , 直接提供现成的版本 , 免得编译器自己在那瞎倒腾: 
  

 6 , 扩容时使用memcpy拷贝数据的隐患:

           这个标题藏得比较深 , 也是浅拷贝 , 下面通过代码和图来表明说明:
          元素为内置范例(正常):         

当vector的元素范例是内置范例时的代码和执行结果(统统正常) :

1.         vector<int> v;
2.                 v.push_back(1);
3.                 v.push_back(1);
4.                 v.push_back(1);
5.                 v.push_back(1);
6.                 v.push_back(1);
7.                 print_container(v);

复制代码

        元素为类范例(异常) :

当vector的元素范例是内置范例时的代码和执行结果(发生段错误) :

1.         std::string st("hello");
2.                 vector<string> v;
3.                 v.push_back(st);
4.                 v.push_back(st);
5.                 v.push_back(st);
6.                 v.push_back(st);
7.                 v.push_back(st);
8.                 print_container(v);

复制代码

        剖析标题: 

           简单来说 , 标题在于push_back里的扩容逻辑有标题 , 由于我的push_back通过reserve函数来扩容 , 以是接下来就看看reserve里潜藏的隐患:

1. void reserve(size_t newCapacity)
2.                 {
3.                         if (newCapacity > capacity())
4.                         {
5.                                 size_t oldSize = size();
6.                                 iterator newStart = new T[newCapacity];
7.                                 memcpy(newStart, _start, sizeof(T) * size()); //隐患
8.                                 _start = newStart;
9.                                 _finish = _start + oldSize;
10.                                 _end_of_storage = _start + newCapacity;
11.                         }
12.                 }

复制代码

           下面一步一步来表明: 
  

 解决方案:

           既然标题出在浅拷贝 , 那修改一下reserve函数里的拷贝数据的逻辑即可:

1. void reserve(size_t newCapacity)
2.                 {
3.                         if (newCapacity > capacity())
4.                         {
5.                                 size_t oldSize = size();
6.                                 iterator newStart = new T[newCapacity];
7.                                 //memcpy(newStart, _start, sizeof(T) * size());
8.                                 for(int i = 0;i<oldSize;i++)
9.                                 {
10.                               *(newStart+i) = *(_start+i); //此处的指针解引用后是string对象,因此会去
11.                                                //调用string自己的赋值重载,实现深拷贝
12.                                 }
13.                                 _start = newStart;
14.                                 _finish = _start + oldSize;
15.                                 _end_of_storage = _start + newCapacity;
16.                         }
17.                 }

复制代码

补充的知识点:

           在系统学习语法时漏掉一些细节是很正常的 , 毕竟实践出真知 , 只有在实际情况中明白的语法才气算是体会到了 "为什么" , 而非只是 "怎么办" . 下面是一些在模拟实现vector的过程中碰到的语法细节 , 可以作为学习的补充:
  1,内置范例的构造函数

           在学习构造函数时我们知道 : 当实例化一个类范例的变量 , 就会主动调用他的构造函数 , 这是板上钉钉的事  .
          最开始学的string , 只能存储字符 , 可vector不一样 , 作为正统的STL容器之一 , 他除了存储内置范例的元素(int 、doule ...) ， 还可以存储类范例 的元素(vector 、string) , 于是在成员函数的参数里就会出现下面的情况:

2. void resize(size_t newsize, const T& val = T())
3. {
4.         if (newsize < size())
5.         {
6.                 _finish = _start + newsize;
7.         }
8.         else
9.         {
10.                 reserve(newsize);
11.                 size_t num = newsize - size();
12.                 while (num--)
13.                 {
14.                         push_back(val);
15.                 }
16.         }
17. }

复制代码

           缺省值写成匿名构造函数的情势对于类范例变量倒是好了 , 那倘若还是担当内置范例呢 , 比如担当int范例的元素. 语法设计者自然也考虑到了这一点 , 因此为内置范例开后门支持了构造函数.
  

2,c++11针对默认构造函数的关键字---default 

           虽说我在模拟实现时自己写了构造函数 , 还写了好几个版本 , 但平心而论 ,不写也可以 ,毕竟不是刚需 . 先回首一下构造函数的一些基本机制:
  

• 在创建一个类范例对象时 , 如果没有调用构造函数 , 那编译器会主动调用默认构造函数
  
• 默认构造函数有两类 : 第一类是编译器自己生成的 , 其用于初始化成员变量的值是不确定的 , 除非使用c++11的语法,即在类里生命成员变量时加上缺省值  ; 第二类是我们自己写的 , 且一定要是无参大概全缺省的构造函数才会被当做默认构造 , 否则就是平凡的构造(需要我们自己显式的调用才行)
  
• 如果我们自己写了构造函数(不论是否是默认构造) , 编译器就不会生成默认构造函数了.
  
• 拷贝构造函数也是构造函数的一种!!! 他是构造函数的重载版本 .
  
• default关键字的作用在于 : 当我们希望自由实现自己的构造函数但又不想严格遵守默认构造函数的情势(无参或全缺省)时 , 使用default就非常的香!!!
  
• 留意,如果自己写了默认构造函数(无参大概全缺省),就不能用default关键字了,会冲突.
  

 
 3,模版语法的补充 : 类模版内的函数模版

           c++的三大特性之一就是封装 , 在STL里迭代器iterator就把这点体现的很好 , 即便每个容器(string,vector...)底层的迭代器实现不同 , 但通过运算符重载和定义内部类的方式 , 对于外部的使用层来讲都是一个iterator(通过限定类域来区分) , 都有begin()和end() , 都可以++和解引用 , 也就是对上层提供了一个统一的接口.
          而使用迭代器区间来构造一个对象也是很常见的 , 因此使用这一点 , 使用模版来写一个通用的迭代器区间构造(不只是可以用vector自己的迭代器)就很重要.
    请看下图的情况 :  固然此时的list和vector的元素范例都是int , 但他们的表面的迭代器Iterator底层封装的内容可能不一样 , 因此需要在vector的迭代器区间构造函数里动一动手脚
  

 
           这是比较局限的迭代器区间构造函数 , 只能担当vector的迭代器 ,无法解决上面的情形

1. //这里的iterator是vector内部定义的内部类,因此也只能接受vector的迭代器
2. vector(iterator begin, iterator end)
3. {
4.         while (begin != end)
5.         {
6.                 push_back(*begin);
7.                 begin++;
8.         }
9. }

复制代码

           下面是一个在类内部使用了函数模版的迭代器区间构造函数 , 可以担当任何容器的迭代器. 由于不同容器的迭代器都有自己底层的解引用(*)和自增的逻辑 , 在函数模版推导出具体的迭代器范例后 , 即便是list自己的迭代器也可以通过调用他自己的解引用重载函数得到整形值
  来正常的传递到push_back里.

1. //同样还是在vector类的内部 , 但是使用了函数模版
2. //inputIterator可以根据出入的不同类型的迭代器实例化出不同的特定容器的迭代器
3. // 因此传递什么类型的迭代器都可以了.并不局限于vector::iterator
4. template<class inputIterator>
5. vector(inputIterator begin, inputIterator end)
6. {
7.         while (begin != end)
8.         {
9.                 push_back(*begin);
10.                 begin++;
11.         }
12. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。