C++ vector与dequeue的特性

C++ vector与dequeue的特性

目录

1.特性说明

两者在功能上存在相似,在使用上也存在争议.争议点在于vector内存占用过大.接下来我将会比较二者的特点,剖析到底要怎么用.下表为二者特性对比:

特性 vector deqeue
内存是否连续 内存连续 内存不一定连续
内存分配原理 以当前占用大小分配.内存不足时,当前空间扩大2倍,并将以前数据复制到新的地址. 以块为单位分配.最小512字节.内存不足时,扩充时不会影响以前的数据(如果类大小超过512,块大小为类大小)
初始化时大小 数组内存为0 有1块大小空间
能否预先分配空间 能(调用reserve函数)(防止内存不够浪费cpu时间)注意:可能引起迭代器失效,实际有效数据不变. 如果不预先分配内存,会在 1,2,4,8,16等大小下重新分配空间. 如果已经预先分配内存,请足额分配. 不能,因为不需要.(增加数据无其它副作用)
赋值时空间变化 多次赋值以最大的可用空间为准.(内存只增加,生命周期一直存在时,可能一直增加空间.预留空间没有删除,需要手动释放)可以删除多余的预留空间 shrink_to_fit() ,在预留>=64字节时才起作用(地址重新分配,迭代器失效) 多次赋值匹配当前空间占用值.(内存合理占用,自动释放多余空间)
构造时是否为空 一定为空,否则为库的BUG(不需要clear) 一定为空,否则为库的BUG(不需要clear)
析构是否释放内存 一定释放,否则为库的BUG(不需要写释放) 一定释放,否则为库的BUG(不需要clear)
迭代器效率 单指针.效率最高. 双指针:一个为块内简单指针,另一个为块间指针.效率略低,需要多一次比较和跨块时修改指针.
删除数据 迭代器失效.只有尾部删除时效率高.其它位置会引起数据往前移动,非常不建议使用. 迭代器失效.在头部和尾部删除效率高.其它位置会引起数据往前移动,非常不建议使用.
能否有普通指针操作 能. 起始位置为 data() 不能.  地址不连续,结果未知!
内存清空操作 template <typename _TP>inline void wfreeContainer(_TP& vt){  _TP tmp; tmp.swap(vt);}std::vector<int> a;wfreeContainer(a);  //已经清空,数组大小为0 调用clear 函数 std::deque<int> a;a.clear(); //已经清空,只有1块大小

结论:

  • 本质上vector的遍历性能与随机查找性能是要高于deque,只要对生命周期过长类的成员进行清空操作就不会存在问题.避免不了内存占用过大的风险.

  • 友情提醒,vector使用时一定要注意提前分配空间!!

  • 大部分开发人员都是用 vector 替代deque.

    注意:vector<bool> 使用位段,采取用空间换时间的方法. 建议不要使用!!可以用 vector<unsigned char>替换

2.vector提前分配内存方法

有二种提前分配的方法.

第一种: 先resize 然后调用 operator[]  (必须提前获取数组大小).
        如果超过resize 大小,会段错误.如果需要减少大小请继续调用 resize.
第二种: 先reserve然后调用 push_back (最后数组大小由push_back 次数决定).
        超过reserve大小不存在问题,只会引起内存扩大.

示例如下:

class CRobotPose2D  : public mrpt::utils::CSerializable
{
    CRobotPose2D() {}
     CRobotPose2D(double x, double y, double phi)
    {
        setX(x);
        setY(y);
        setPhi(phi);
    }
}

//法1
std::vector<CRobotPose2D> func(const std::deque<CRobotPose2D> &in)
{
    std::vector<CRobotPose2D> pose_tab;

    pose_tab.resize(in.size()); //以前有的数据不变.新添加的数据以默认构造函数填充值

    for(size_t i = 0; i < in.size(); ++i)
    {
        pose_tab[i] = in[i]; //operator[] 算法效率极高,仅次于迭代器,极致可以用指针
    }

    return pose_tab;
}


//法2
std::vector<CRobotPose2D> func(const std::deque<CRobotPose2D> &in)
{
    std::vector<CRobotPose2D> pose_tab;

    pose_tab.reserve(in.size()); //提前分配内存大小

    for(auto &v : in)
    {
        pose_tab.push_back(v); //空间足够,不会引起内存重分配, push_back性能低于operator[]
    }

    return pose_tab;
}

//法3:
std::vector<CRobotPose2D> func(const std::deque<CRobotPose2D> &in)
{
    std::vector<CRobotPose2D> pose_tab;

    pose_tab.reserve(in.size()); //提前分配内存大小
    pose_tab.insert(pose_tab.end(), in.begin(), in.end()); //迭代器复制插入.简单高效. 比push_back高效
    return pose_tab;
}
   

二种方法怎样选:

如果类的`默认构造函数代价` < `一次比较和++指针`  可以用第一种(只有默认构造为空,且类和类的成员仅为基本数据结构)
本人推荐用第二种方法.

3. at方法和operator[]杂谈

对于容器访问数据有二种方法 at 和 operator[] ,两者都能获取到数据的值. 效率方面operator[] > at. at为检测范围抛异常再套一个operator[]的马甲)

std::vector<CRobotPose2D> pose_tab;
CRobotPose2D in;
pose_tab.resize(3);
pose_tab[0] = in;     //operator[]  强烈推荐该方法
pose_tab.a(0) = in;   //at

如果在数组范围内,两者一样. 超出数组范围 operator[]结果未知(可能段错误), at 抛出异常. 实际使用中我们一般都限定范围,且一般不不捕获异常.因此尽量不要用at, 推荐operator[].