- vector
- class Dog;
- // 例 1:
- vector<Dog> vec(6); // vec.capacity() == 6, vec.size() == 6,
- // 默认构造生成 6 Dogs
- // 例 2:
- vector<Dog> vec; // vec.capacity()>= 0, vec.size() == 0
- vec.resize(6); // vec.capacity()>= 6, vec.size() == 6,
- // 默认构造生成 6 Dogs
- // 例 3:
- vector<Dog> vec;
- vec.reserve(6); // vec.capacity()>= 6, vec.size() == 0,
- // 不调用默认构造
- // vector 容量指数型增长, 用完之后会重新分配, 拷贝元素
- /*
- * 避免重新分配内存的策略:
- * 1. 如果所需的最大元素个数已知, reserve(MAX);
- * 2. 如果不知道, 先 reserve 尽可能多, 等所有元素插入完毕, 再将剩余的切除.
- */
- deque
- /*
- * - 没有重新分配
- * deque 没有 reserve() 和 capacity()
- * - 比 vector 稍慢, 因为数据结构比 vector 复杂, 因为不连续定位也有一定的开销, 更多的 cache miss 或 page fault
- * - 现代编译器往往会把他们放到一起
- */
- // 固定大小线性增长
如何选择
一般原则
- 经常需要在前面插入的? -> deque
- 性能重要的? -> vector
详细分析
元素类型
如果不是很小的类型, 那么 deque 相比 vector 并不会低效很多
内存的可用性
大块的连续内存分配是否可能成为问题, 内存受限
数据增长是否不可预期
- vector<int> vec;
- for (int x=0; x<1025; x++)
- vec.push_back(x); // 11 reallocations performed (growth ratio = 2)
- // workaround: reserve()
因为增长带来的指针 / 引用 / 迭代器失效
- vector<int> vec = {2,3,4,5};
- int* p = &vec[3]
- vec.push_back(6);
- cout <<*p << endl; // 未定义的行为
- deque<int> deq = {2,3,4,5};
- p = &deq[3];
- deq.push_back(6);
- cout <<*p << endl; // OK
- // push_front() 也 OK
- // deque: 在首尾插入不会使指针失效
- // 注: 在中间插入删除的话, 还是会使指针失效
vector 独有的特性: 兼容 C
- vector<int> vec = {2,3,4,5};
- void c_fun(const int* arr, int size);
- c_fun(&vec[0], vec.size());
- // 对于其他容器, 需要先将数据拷贝到 vector
- list<int> mylist;
- ...
- vector<int> vec(mylist.gegin(), mylist.end());
- c_fun(&vec[0], vec.size());
- // 注: &vector[0] 可以当做 C 的数组使用
- // 一个例外是: vector<bool>
- void cpp_fun(const bool* arr, int size);
- vector<bool> vec = {true, true, false, true};
- cpp_fun(&vec[0], vec.size()); // vector<bool > 的每个元素优化为由 1bit 来表示, 可以用 vecter<int > 或者 bitset
总结
经常 push_front() - deque
高性能 - vector
不是细小的数据类型 - deque
内存受限 - deque
不可预期的增长 - deque
指针有效性 - deque
C 接口 - vector
来源: http://www.bubuko.com/infodetail-2905314.html