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[].