关于std::vector

vector应该是我们平时用到最多的容器之一了，这里我们做一下梳理。
std::vector 是动态的，在heap上分配内存，在内存中具有连续的存储空间。可以快速地随机访问，在末尾插入和删除较快，在中间插入或删除较慢。适用于元素结构简单(如果是复杂的结构体，我们可以存储它的指针)，变化小，并且频繁随机访问的场景。

insert() erase()时间复杂度

当操作发生在中间时，需要O(n) 即线性时间（liner time）完成操作。因为需要将在插入/删除之后的每一个元素都向前/向后移动。当操作发生在末尾时则只需要O(1)时间。

vector.erase() 和 std::remove() 区别

其实我们先看一下erase()的代码（https://github.com/karottc/sgi-stl/blob/master/stl_vector.h）发现erase()在移动完数据后会销毁多余的部分并重置尾指针。
再看一下cppreference关于std::remove的介绍

template< class ForwardIt, class T >
ForwardIt remove(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::find(first, last, value);
    if (first != last)
        for(ForwardIt i = first; ++i != last; )
            if (!(*i == value))
                *first++ = std::move(*i);
    return first;
}

它只是通过双指针，将所有不是value的元素依次前移。如果是auto end = std::remove(vector.begin(), vector.end(), value) 那么结果就是在end后依然有数据存在:

#include <vector>
#include <algorithm>
#include <iostream>
 
int main( )
{
    std::vector<int> c{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << c.size() << std::endl;
    std::remove(c.begin(), c.end(), 5);
    std::cout << c.size() << std::endl;
    for (auto &i : c) {
        std::cout << i << " ";
    }
}
/*output:
10
10
0 1 2 3 4 6 7 8 9 9
*/

所以如果我们想真正的让这个vector有数据的销毁以及尺寸上的变化，我们需要vec.erase(std::remove(vec.begin(), vec.end(), value),vec.end());

shrink_to_fit()

其实当我们说用erase()删除数据时，相应的内存并没有被释放，可以通过在删除前后打印capacity()查看。假设又有一种需求，我们需要释放这个内存，那么就需要vec.shrink_to_fit()来释放（我并不晓得什么样的场景我们需要用到这个）。

为什么vector以1.5倍（1，2）扩容最好

我们首先谈一下扩容，当vector尺寸达到容量大小时，如果我们需要添加新的元素就需要扩容。扩容系数的选取是时间与空间的平衡。想象一下，如果我们每次只分配capacity + 1 的空间，那么对于每一次push_back()，我们都需要需要找一个capacity+1的空间，然后把元素从之前的空间移动到新的空间，然后在末尾写入新的元素。所以当系数太小时，我们需要频繁的重新分配空间。当然，如果选取的系数过大，他会分配出远超需要的空间造成了浪费。通常情况下（在gcc里）扩容系数是2，但是对于一些厂商会将其优化到1.5。原因是2并不是一个对内存特别友好地系数，当系数为2时，我们可以得出每次扩容时，新尺寸必然大于所有之前分配总和这一结论。比如，前k次我们分配了 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 的空间，下一次我们需要分配2^(k+1) 大小的空间，刚好比前面总和大1，这样我们就不能服用之前的地址。而当系数为1.5（ 1< k < 2）时，我们就可以复用之前分配的空间（假设之前的分配都是在连续空间上的）。

push_back时间复杂度

既然聊到了扩容，我们顺便看一下push_back() 的时间复杂度。这里我们用均摊分析法(amortized)，如果系数是k，那么对于有n个元素的vector就进行了logk(n)次扩容，每次耗费的时间是k^i(因为需要把数据从现在的位置复制到新开辟的空间), i表示从1到logk(n)，和就是 nk/k-1。那么平摊到每一次就是O(1) 即常数时间（constant time）。

一些性能上的考虑

reserve()

其实通过扩容我们可以看出这是一个相当耗时的操作，它涉及到分配新的内存，拷贝旧数据，释放旧内存。所以如果我们可以确定大概的数据大小是，最好对容器进行预分配操作vec.reserve(reserve_size);.这不仅仅避免了上述的昂贵操作，同是也避免了因为扩容而导致的迭代器失效。

拷贝一个vector

当我们将一个vector2拷贝到另一个vector1时(假设同类型)，可以选择赋值，insert或者push_back()。这时我们最好用赋值，因为这时它可以一次性的拷贝vector2的内存。

vector.at(index)

at 可以检测边界防止越界，但是有时可能会比迭代器和operator[]慢。这是因为没有边界检测的读取可能只需要一条处理器指令，但是at需要读取vector大小，与index进行比较，这样会多出很多处理器指令。

避免在vector前部插入元素

如上文所述，当你需要插入元素是，每个插入节点之后的元素都需要整体复制后移。当vector的元素越多，这个性能就越差。时间复杂度是O(n)。所以如果有频繁的插入需求（比如LRU），那么我们也许可以考虑std::list，因为他的插入复杂度是O(1).

使用emplace_back()

emplace_back()的好处是他是在vector内部空间原地构造，与push_back()相比少了临时对象的拷贝/转移以及销毁。大部分时候，emplace_back() 都比 push_back() 要好。具体参考effective modern c++ item 42.

别使用vector

因为他里面不是真正的以一个字节存储这bool，而是优化成了每个bit代表一个bool。然而单个bit的引用是被禁止的，所以operator[]返回的不是bool而是一个代理对象，引用了某一bit。所以下列代码会出错：

vector<bool> v;
bool* v0 = &v[0]; // it is actually vector<bool>::reference type

wangpifu