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