STL-vector

简介

vector直译为向量，其与动态数组相同，具有在插入和删除时自动调整自身大小的能力，其存储由容器自动处理。

vector中的元素被放置在连续的存储中，以便使用迭代器遍历和删除它们。

vector是序列式容器

类模板

template<
    class T,                            //数据类型        
    class Allocator = std::allocator<T> //分配器
> class vector;

成员函数

迭代器相关

begin() - 返回指向 vector 第一个元素的迭代器
end() - 返回指向 vector 中最后一个元素之后的理论元素的迭代器
rbegin() - 返回指向 vector 中最后一个元素的反向迭代器（反向开始）
rend() – 返回一个反向迭代器，指向 vector 中第一个元素之前的理论元素
cbegin() - 返回指向 vector 中第一个元素的const迭代器 (C++11)
cend() - 返回一个const迭代器，指向 vector 中最后一个元素之后的理论元素 (C++11)
crbegin() – 返回指向 vector 中最后一个元素的const反向迭代器（反向开始） (C++11)
crend() - 返回指向 vector 中第一个元素之前的理论元素的const反向迭代器 (C++11)

容量相关

size() - 返回 vector 中元素数 O(1)
max_size() - 返回 vector 可以容纳的最大元素数 O(1)
capacity() - 返回当前分配给 vector 的存储空间大小 O(1)
resize() - 调整 vector 可存储数量
reserve() - 预留存储空间
empty() - 当前 vector 是否为空 O(1)
shrink_to_fit() - 减少 vector 的容量，将capacity()大小减少到与size()相等 (C++11)

元素访问相关

[g] - 返回对 vector 位置 g 处的引用 O(1)
at(g) - 返回对 vector 位置 g 处的引用，同时进行越界检查 O(1)
front() - 返回对 vector 中第一个元素的引用 O(1)
back() - 返回对 vector 中最后一个元素的引用 O(1)
data() - 返回 vector 底层数组的指针 O(1)

修改器相关

assgin() - 用新的容器替换此容器
clear() - 清空所有元素，size()置 0
insert() - 插入一个或多个元素到指定位置
erase() - 删除指定位置元素
push_back() - 尾部插入元素
pop_back() - 删除尾部元素
swap() - 交换元素
emplace() - 插入一个元素到指定位置，调用构造函数 (C++11)
emplace_back() - 插入一个元素到尾部，调用构造函数 (C++11)

vector迭代器详解

vector的所有迭代器都是随机访问迭代器

1. 正向迭代器

此迭代器是由 begin(), end() 所返回的，其对其的操作为正向，且当 vector 元素不为 const 时可以更改其指向的值，即：

vector<int> v{ 1,2,3,4,5,6 };
auto i = v.begin(); //*i为1
i += 2;             //*i为3
*i = 100;           //*i为100

2. 反向迭代器

此迭代器由 rbegin(), rend() 所返回，对其的操作为反向，且也满足当 vector 元素不为 const 时可以更改其指向的值，即：

vector<int> v{ 1,2,3,4,5,6 };
auto i = v.rbegin();//*i为6
i += 2;             //*i为4
*i = 100;           //*i为100

3. const迭代器

此迭代器由 cbegin(), cend(), crbegin(), crend() 返回，只能对其操作，不能更改其指向的值，即：

vector<int> v{ 1,2,3,4,5,6 };
auto i = v.cbegin();//*i为1
i += 2;             //*i为3
*i = 100;           //error！

关于vector扩容

1. 为什么要成倍的扩容而不是固定值

成倍方式
花费时间为常量
固定值
花费时间为 O(n)
2. 倍数最好为多少
使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说之前分配的空间不可能被使用。这样对于缓存并不友好，最好把增长因子设置为1 < k < 2

比较一下两者的情况：

k = 2, c = 4
0123
    01234567
            012345789ABCDEF
                           0123456789ABCDEF0123456789ABCDEF
                                                           012345...

k = 1.5, c = 4
0123
    012345
          012345678
                   0123456789ABCD
                                 0123456789ABCDEF0123
0123456789ABCDEF0123456789ABCD
                              0123456789ABCDEF0123456789ABCDEF...

可以看到，k=1.5 在几次拓展后，可以重用之前的内存空间

但在C++标准库中，使用的增长因子是由编译器决定的

简介

类模板