精华内容
下载资源
问答
  • 研究STL之vector的push_back函数解析

    千次阅读 2012-06-08 22:00:39
    突然对vector的push_back好奇,于是看了一下vector的源码,做了以下总结。技术水平不行,写作水平更不行,没空画图。大家看看指出错误。  1、如果有足够空闲的申请的空间,直接插入到最后,调用了通用的一个函数...

             突然对vector的push_back好奇,于是看了一下vector的源码,做了以下总结。技术水平不行,写作水平更不行,没空画图。大家看看指出错误。

            1、如果有足够空闲的申请的空间,直接插入到最后,调用了通用的一个函数Fill,插入数目是N(N==1)。插入过程是,先备份起始插入地址P,备份地址是B,循环N次,选一段空间M,对这段空间执行元素的Placement New的复制构造函数,成功后,P后移,如果构造过程有异常,则从B到P的元素全部反构造,反构造方法就是调用析构函数。成功执行Fill后,返回一个指针作为vector的元素后界限,即vector::end()这个迭代器对应的位置。想想为什么要复制构造?在一块未用过的空间定义对象要让空间变为有效,就得构造,复制构造的方式是复制数据到未用过的空间最直接的方式,难不成用空构造,再赋值?
            2、如果发现空闲的申请的空间不够,调用Insert到最后,Insert会自动增涨空间,Insert就在指定位置I插入N(N==1)个元素。Insert在调试模式下会检查插入位置I的迭代器的容器是不是自己,有没有越界(指插入位置不是vector::begin()的vector::end()闭区间),有就报错。这里把传入的Val用本地变量通过复制构造复制了一份,原因,后面会进行数据的移动,万一Val本身就是vector的一个元素,移数据后Val就无效了。Insert发现N是0就直接不管了,发现插入数据后会超出所允许用的容量,就报错。 

            要插入数据了,这时有三种情况。

            一是申请的空间的剩余空间不够插入N个元素,这时要重新分配申请的空间,先试试增涨50%(相对于全部申请的空间),如果涨50%会超出允许用的容量,就只涨N个,涨空间就是重新伸请一段空间,指针P,备份指针B,涨完了,这时要移数据了和填新数据到新空间了,移填数据过程先不细说,过程是移填移,就是要插入数据的位置的前半段是移,新数据是填,后半段也是移,移填数据完后,P指向新空间中被填的元素(即是新数据)的后一个位置,这时如果移动或填充数据失败,会对B到P之间的新空间元素逐个调用析构函数,新空间数据完成后,就把老数据也逐个调用析构函数,并释放全部老空间,然后修改有效数据层指针、新申请的空间尾指针、起始数据指针,再说移填数据,填数据跟上一段一样,看移数据,其实就是复制数据,复制办法就是把X个要复制的数据在目标空间逐段用Placement New调用复制构造函数,如果发生异常就把复制了的元素逐个调用析构函数给清理掉,返回值为目标空间里末元素后的地址,为什么P不是指向后半段的后地址,那是因为前半段移过程异常,P就是指向B,这时P到B没什么数据,而前半段移的数据在移动函数Move里清理了,如果填的过程异常,P指向前半段的后地址,Fill清理了自己填的元素,这时要清理Move的前半段,如果后半段Move异常,则P指向填的数据的后地址,这时就要清前半段和填的数据,而后半段的数据清理Move做了。想想为什么这样做?申请新空间是必须的,把前半段,填充,后半段都是用复制构造在新空间初始化空间,这样比空构造再赋值效率高。
            二是申请的空间够,但要插入的位置I到有效数据尾L的元素个数不足N个,少了M个,这时把老数据的后半段往后移N个位置(如果移失败则Move函数自行清理)腾出空间来,然后在L处填入M数据,如果填失败,则把原来移的后半段清理掉,Fill的数据会自己清理,然后修改尾指针L为新的尾部(L+N),然后再填N-M个数据到I到老L(新L-N)区间处,这个填的过程不一样,是逐元素直接调用赋值运算。想想为什么这样做?后半段老数据要移到未使用的空间里,正如前面说的,初始化未使用的空间用复制构造更好,那M个新数据也是在未使用的空间,也用复制构造初始化未使用的空间,那N-M个新数据为什么用赋值运算来填入?那是因为赋值运算一般把老空间里的老数据清理,然后填入新数据,如果直接用复制构造,会导致老数据末清理,那N-M个数据并不是在初始化未使用的空间,那为什么第一种情况不用这样做,那是因为第一种情况都完全在新空间了,但第一种情况也要清理老数据,而且是全部的,效率低啊,赋值操作失败要清理么,不用吧,没产生新元素。
            三是其它情况,就是申请的空间够,而且插入的位置I到有效数据尾L的元素个数>=N个(够全部执行赋值操作了),假设M个,这时先把尾部N个元素移到末元素的位置之后,并修改有效数据尾指针,如果移失败,则移动函数清理这些移动后的元素,这时插入点I后面还有M-N个未处理元素,这时采用从后向前逐个复制的移动法,移到I+N处,这M-N个元素后未元素位置正好是尾L,前面用的函数都是从前到后,这次不一样了,移完了后,再用从左到右的赋值操作把N个新元素填入I到I+N-1之间,这两个赋值操作都没产生新元素,异常后不做清理操作了,为什么啊。想想为什么这样做,移到老空间的空闲区的N个元素当然用复制构造初始化空间,填入I的N个元素用赋值运算,这样I到I+N-1的元素能自己清理老数据,填入新数据,至于那M-N个从后向前移(复制)的元素怎么回事,其实是怕M-N>N,如果从前向后移,则有M-2N个数据会错误,也就是倒数M-2N个数据其实是前M-2N个数据的副本,这个跟memmove有时从后往前复制意思差不多。

    展开全文
  • 在vs2008下,当在一个结构体中有vector类型成员时,如果在定义了一个该结构体变量,并使用memset函数对其初始化,在debug版本下并不会有问题。但换成release版本后,程序运行会产生异常,并报如下信息: ...
    在vs2008下,当在一个结构体中有vector类型的成员时,如果在定义了一个该结构体的变量,并使用memset函数对其初始化,在debug版本下并不会有问题。但换成release版本后,程序运行会产生异常,并报如下信息:
    

    Microsoft Visual Studio C Runtime Library has detected a fatal error in STLtest.exe.

    Press Break to debug the program or Continue to terminate the program.

    该问题主要是由于对结构体变量使用了memset函数,如果结构体中有vector这样的类型,使用memset会导致结构体中的某些信息丢失,从而在使用push_back函数插入数据时产生异常中断。希望我的遭遇对大家有帮助。

     

     

    1. #include "stdafx.h"   
    2. #include <vector>   
    3. #include <iostream>   
    4. using namespace std;  
    5. typedef struct _structBB   
    6. {  
    7.     int i;  
    8.     vector<int> vBBs;  
    9. }BB;  
    10. int _tmain(int argc, _TCHAR* argv[])  
    11. {  
    12.         BB bb;  
    13.     memset(&bb,0,sizeof(BB));  
    14.     bb.vBBs.push_back(1);  
    15.     return 0;  
    16. }  
    展开全文
  • 在vs2008下,当在一个结构体中有vector类型成员时,如果在定义了一个该结构体变量,并使用memset函数对其初始化,在debug版本下并不会有问题。但换成release版本后,程序运行会产生异常,并报如下信息: ...
    展开全文
  • vector的push_back操作是将一个元素插入vector的末尾。源码如下:template void YVector::push_back(const T&x){if (finish !=end_of_storage){construct(finish, x);++finish;}else{insert_aux(finish, x);}}...

    vector的push_back操作是将一个元素插入vector的末尾。

    源码如下:

    template

    void YVector::push_back(const T&x)

    {if (finish !=end_of_storage)

    {

    construct(finish, x);++finish;

    }else{

    insert_aux(finish, x);

    }

    }

    函数insert_aux

    template

    void YVector::insert_aux(iterator position, const T&x)

    {if (finish !=end_of_storage)

    {

    construct(finish,*(finish - 1));++finish;

    T copy_x=x;

    copy_backward(position, finish- 2, finish - 1);*position =copy_x;

    }else{const size_type old_size =size();const size_type new_size = old_size == 0 ? 1 : 2 *old_size;

    iterator new_start=data_allocator::allocate(new_size);

    iterator new_finish=new_start;try{

    new_finish=uninitialized_copy(start, position, new_start);

    construct(new_finish, x);++new_finish;

    new_finish=uninitialized_copy(position, finish, new_finish);

    }catch(...)

    {

    destroy(new_start, new_finish);

    data_allocator::deallocate(new_start, new_size);throw;

    }

    destroy(begin(), end());

    deallocate();

    start=new_start;

    finish=new_finish;

    end_of_storage= new_start +new_size;

    }

    }

    需要理解以上源码并不容易。看我一一道来。

    1.start,finish,end_of_storage

    首先必须了解vector的数据结构。如图:

    d84488485eaeeab62ab43020cc2e5d79.png

    vector是一段连续的内存空间。start,finish,end_of_storage三个指针描述了空间状态,这三个是普通的指针。start到finish是已经使用的内存,里面有元素。finish到end_of_storage是未使用的内存,里面没有元素。

    由此三个指针可以得出一些简单的操作。

    iterator begin() { return start; } //起始位置

    iterator end() { return finish; } //结束位置

    size_type size() const { return size_type(end() - begin()); } //已可用大小

    size_type capacity() const { return size_type(end_of_storage - begin()); } //申请的内存大小

    bool empty() { return begin() == end(); } //是否为空

    reference operator[](size_type n) { return *(begin() + n); } //[]操作

    reference front() { return *begin(); } //首元素

    reference back() { return *(end() - 1); } //尾元素

    其中一些定义

    typedef T value_type;

    typedef value_type*pointer;

    typedef value_type*iterator;

    typedef value_type&reference;

    typedef size_t size_type;

    2.construct,destroy

    这个两个是全局的构造和析构函数。其中construct是调用placement new。

    有关于placement new,参考 http://www.cnblogs.com/luxiaoxun/archive/2012/08/10/2631812.html

    templateinlinevoid construct(T1* p, const T2&value)

    {new(p)T1(value);

    }

    placement new可以简单理解成在已经分配好的空间上构造。

    在puch_back这里的情境中,如果内存的备用区还有空间,则用x在finish指向的空间上构造,同时移动finish指针。这里原本finish指向的空间是已经申请了的,所以使用placement new。

    if (finish !=end_of_storage)

    {

    construct(finish, x);++finish;

    }

    destroy有两个版本。destroy实现较复杂,参看《STL源码剖析》第二章。只需知道destroy会在指定范围进行析构。

    template inlinevoid destroy(T*pointer)

    {

    pointer->~T();

    }

    templateinlinevoiddestroy(ForwardIterator first, ForwardIterator last)

    {

    //实现略

    }

    3.allocate,deallocate

    注意到定义类时出现了Alloc,这其实是配置器。vector默认使用alloc配置器。

    template

    在基本的alloc上封装一层simple_alloc。如下:

    template

    classsimple_alloc {static T* allocate(size_t n)

    { return n == 0 ? 0 : (T*)Alloc::allocate(n * sizeof(T)); }static T* allocate()

    { return (T*)Alloc::allocate(sizeof(T)); }static void deallocate(T *p, size_t n)

    { if (n == 0) Alloc::deallocate(p, n * sizeof(T)); }static void deallocate(T *p)

    { Alloc::deallocate(p, sizeof(T)); }

    };

    实际上内部实现就是调用malloc和free,但是会有复杂的分级配置处理。在此不再讨论。参看《STL源码剖析》第二章。

    可以就简单的把allocate,deallocate理解成malloc,free来辅助记忆,但务必记得没那么简单。

    4.uninitialized_copy,copy_backward

    uninitialized_copy处理如下图:

    69408527c3d9ccc930b59ffa4b02f132.png

    看起来好复杂……来看一下原型:

    template inline ForwardIterator

    uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result)

    {return__uninitialized_copy(first, last, result, value_type(result));

    }

    如果[result,result + (last - first))范围内的迭代器都指向未初始化区域,则uninitialized_copy()会使用copy construct给输入来源[first,last)范围内的每一个对象产生一个拷贝放进输出范围。

    更深的实现也贴出来:

    template inline ForwardIterator

    __uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result, T*)

    {

    typedef typename __type_traist::is_POD_type is_POD_type is_POD;return__uninitialized_copy_aux(first, last, result, is_POD());

    }

    templateinline ForwardIterator

    __uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result, __true_type)

    {returncopy(first, last, result);

    }

    templateinline ForwardIterator

    __uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result, __false_type)

    {

    ForwardIterator cur=result;for (; last != first; first++, cur++)

    {

    construct(&*cur, *first);

    }returncur;

    }

    这里面的逻辑是,首先把result的value_type得出,判断是否是POD类型……

    如果是POD类型,则调用copy函数,如果不是POD类型,则一个一个调用construct()

    所谓POD类型,指的是拥有无意义的构造、析构、拷贝、赋值函数的类型…能不能理解成比较简单的类。

    像是如果类成员里有一个其他类的指针,这种复杂的类,需要有特殊的构造函数,就没有默认的那个构造函数。因此是non-POD类型。

    接下来回到push_back。insert_aux里面判断还有备用空间的地方,有一个copy_backword函数。来看一下实现:

    templateBidirectionalIterator2 copy_backward ( BidirectionalIterator1 first,

    BidirectionalIterator1 last,

    BidirectionalIterator2 result )

    {while (last!=first) *(--result) = *(--last);returnresult;

    }

    作用是将一个范围中的元素按逆序拷贝到新的位置处。insert_aux截取如下:

    if (finish !=end_of_storage)

    {

    construct(finish,*(finish - 1));++finish;

    T copy_x=x;

    copy_backward(position, finish- 2, finish - 1);*position =copy_x;

    }

    这里面有两个问题。第一为什么要有一份拷贝T copy_x = x;问题的答案参考知乎 https://www.zhihu.com/question/56911557/answer/150928396

    第二个 copy_backward(position,finish - 2,finish - 1) 在插入位置是末尾的时候不会死循环吗?黑人问号?

    position其实是finish - 1,也就是说传入参数后first比last还后面,那岂不是死循环?

    引用:

    1.《STL源码剖析》

    2.http://www.cnblogs.com/luxiaoxun/archive/2012/08/10/2631812.html

    展开全文
  • 正常情况下push_back是往vector中添加新元素,只不过添加过程是先利用拷贝构造函数复制目标值,而 emplace_back可以 直接在目标位置上生成对象,这也正式emplace原本放置意思。 具体在使用上,如果push对象...
  • vectorpush_back和emplace_back区别

    千次阅读 2019-03-23 10:57:40
    在引入右值引用,转移构造函数,转移复制运算符之前,通常使用push_back()向容器中加入一个右值元素(临时对象)时候,首先会调用构造函数构造这个临时对象,然后需要调用拷贝构造函数将这个临时对象放入容器中。...
  • vector的push_back

    2014-11-18 14:51:04
    这两天在实际程序中使用 STL vector push_back 类对象时出现问题,偶尔发现 vectorpush_back调用类对象拷贝构造函数和析构函数有点特别,简单做下分析。 程序代码: cat > test.cpp ...
  • 首先贴函数的申明和定义部分源码: template<typename _Tp, typename _Alloc = std::allocator<_Tp> > class vector : protected _Vector... void push_back(const value_type& __x) { if (this-&
  • 在引入右值引用,转移构造函数,转移复制运算符之前,通常使用push_back()向容器中加入一个右值元素(临时对象)时候,首先会调用构造函数构造这个临时对象,然后需要调用拷贝构造函数将这个临时对象放入容器中。...
  • 一直都说尽量用C++11emplace_back替换push_back,前者效率究竟比后者快多少不甚了解,写个demo简单测试下看看,下面这个demo程序我写了个Pt类用于测试,除了普通构造函数外还有拷贝构造和移动构造,3个静态变量...
  • push_back 就是在vector的末尾插入一个元素, vector 中的erase()函数,从指定容器删除指定位置的元素或者某段范围内的元素,删除之后,返回值也是一个迭代器,指向最后一个删除元素的下一个元素, 出现的问题...
  • vector的push_back()函数的赋值方式

    千次阅读 2010-04-20 11:35:00
    vector的push_back()函数的赋值方式是拷贝整个type类型的数据,而不只是拷贝引用(地址),所以不用担心添加局部变量之后会被自动收回。
  • vector的push_back()、emplace_back等改变空间大小的操作,调用构造函数、析构函数的次数分析!!! 先看这个初始代码: #include <iostream> #include <vector> using std::cout; using std::endl; ...
  • C++ Vector容器的push_back()与pop_back()函数push_back( )pop_back( )参考链接 push_back( ) 函数将一个新的元素加到vector的最后面,位置为当前最后一个元素的下一个元素 push_back() 在Vector最后添加一个...
  • 这两天在实际程序中使用 STL vector push_back 类对象时出现问题,偶尔发现 vectorpush_back调用类对象拷贝构造函数和析构函数有点特别,简单做下分析。 程序代码: cat > test.cp
  • C++中的push_back函数

    万次阅读 2018-08-08 08:41:23
    如c++中的vector头文件里面就有这个push_back函数,在vector类中作用为在vector尾部加入一个数据。 string中也有这个函数,作用是字符串之后插入一个字符。 //basic_string_push_back.cpp //compilewith:/EHsc #...
  • c++11 之emplace_back 与 push_back的区别

    万次阅读 多人点赞 2018-12-03 14:32:45
    在引入右值引用,转移构造函数,转移复制运算符之前,通常使用push_back()向容器中加入一个右值元素(临时对象)时,首先会调用构造函数构造这个临时对象,然后需要调用拷贝构造函数将这个临时对象放入容器中。原来...
  • vector().push_back(T(args));相当于vector().emplace_back(args);C++11之前,push_back先后调用了构造函数、拷贝构造...在C++11基础上,emplace_back比push_back少了一次转移构造函数,只有构造函数。在www.cpl...
  • 向标准库对象中添加内容是拷贝一份到标准库对象中,并不调用相应构造函数吗?...在向vectorpush_back一个对象为何会析构之前所有对象? 1 #include <iostream> 2 #include "wi...
  • 这些操作分别对应push_front、insert和push_back,允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。 当调用push或insert成员函数时,我们将元素类型对象传递给它们,这些对象被拷贝到容器中。而当...
  • stl vector 函数 C ++ vector :: push_back()函数 (C++ vector::push_back() function) vector::push_back() is a library function of "vector" header, it is used to insert/add an element at the end of the ...
  • vector的push_back

    2017-11-12 20:51:42
    vector v; v.push_back(1); //v里面为: 1 v.push_back(2); //v里面为: 1,2 v.push_back(3); //v里面为: 1,2,3 vector中 push_back函数的意思是在vector的末尾插入一个元素。
  • 一、首先必须弄清楚两个概念: capacity:指容器在分配新存储空间之前能存储元素总数。 size:指当前容器所存储元素个数 由于vector对象在插入或添加时自动调整长度(注意:...push_back()成员函数的作用是在容
  • vector::push_back函数解析

    千次阅读 2014-06-16 20:54:35
    上一篇文章中,关于stl_vector的故事只是个开始. 这篇文章中,接着去分析vector中的细节问题.     再次声明,我没有看过关于stl源码分析方面的书籍,强调这一点是为了不会让别人误会我是从别的地方抄袭的. 另外...
  • 刚开始学c++,用书是《c++ primer》第五版,题目如下: !... 代码如下: ...感觉是因为输入结束之后一直跳不出push_back的while循环, 书上和网上例子都是这样,但我就不行,迷惑????
  • 静态方法与静态数据成员 什么是类静态方法? C++中,若类方法前加了static关键字,则该方法称为静态方法,反之为实例方法.静态方法为类所有,可以通过对象来使用,也可以通过类来使用.但一般提倡通过类名来使用,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,115
精华内容 446
关键字:

vector的push_back函数