C++ - STL vector.reserve()&.push_back()

std::vector::push_back

Add element at the end Adds a new element at the end of the vector, after its current last element. The content of val is copied (or moved) to the new element. This effectively increases the container size by one, which causes an automatic reallocation of the allocated storage space if -and only if- the new vector size surpasses the current vector capacity.

std::vector::capacity

Notice that this capacity does not suppose a limit on the size of the vector. When this capacity is exhausted and more is needed, it is automatically expanded by the container (reallocating it storage space).
The theoretical limit on the size of a vector is given by member max_size. The capacity of a vector can be explicitly altered by calling member vector::reserve.

#include <iostream>
#include <vector>

#define MAX_INT 8

int main() {
    std::vector<int> vec;
    for(int i = 1; i <= MAX_INT; ++i) {
        vec.push_back(i);
    }
    vec.push_back(666);
    std::vector<int>::iterator iter = vec.begin();
    for(iter; iter != vec.end(); ++iter) {
        std::cout << *iter << ' ';
    }
    return 0;
}

output：

1 2 3 4 5 6 7 8 666

下面是出现问题的代码，当我们颠倒上面程序中如下两条语句的顺序时就会在1 2 3 4 5 6 7 8 666之前输出一段乱码

    std::vector<int>::iterator iter = vec.begin();
    vec.push_back(666);

output：

-17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 1280319716 805348782 1 2 3 4 5 6 7 8 666

问题原因：
vector是随着增加元素而动态更改容器大小。在for循环结束后，容器内的元素个数为8，且在内存中vector的动态变化的规则是2->4->8->16。而加入第九个元素666后，容器大小被更新为16，地址也被重新指向一个新的内存段落。
因此当迭代器被设定为未更新前的容器的起始位置，便会导致指向错误。

解决方法：

std::vector::reserve

void reserve (size_type n);

Request a change in capacity
Requests that the vector capacity be at least enough to contain n elements.
If n is greater than the current vector capacity, the function causes the container to reallocate its storage increasing its capacity to n (or greater).
In all other cases, the function call does not cause a reallocation and the vector capacity is not affected.
This function has no effect on the vector size and cannot alter its elements.

频繁使用std::vector的push_back操作前最好使用reserve预留出相应内存，这样可以减小动态重分配内存所占用的时间，从而增加运行速度。

#include <iostream>
#include <vector>

#define MAX_INT 8

int main() {
    std::cout << "\nvecA:\n";
    std::vector<int> vecA;
    std::cout << "vecA.capacity: " << vecA.capacity() << std::endl;
    for(int i = 1; i <= MAX_INT; ++i) {
        vecA.push_back(i);
    }
    std::vector<int>::iterator iterA = vecA.begin();
    vecA.push_back(666);
    for(iterA; iterA != vecA.end(); ++iterA) {
        std::cout << *iterA << ' ';
    }

    std::cout << "\nvecB:\n";
    std::vector<int> vecB;
    vecB.reserve(9);
    std::cout << "vecB.capacity: " << vecB.capacity() << std::endl;
    for(int i = 1; i <= MAX_INT; ++i) {
        vecB.push_back(i);
    }
    std::vector<int>::iterator iterB = vecB.begin();
    vecA.push_back(666);
    for(iterB; iterB != vecB.end(); ++iterB) {
        std::cout << *iterB << ' ';
    }
    return 0;
}

output：

vecA:
vecA.capacity: 0
-17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -17891602 -379745926 805325510 1 2 3 4 5 6 7 8 666
vecB:
vecB.capacity: 9
1 2 3 4 5 6 7 8

注：

使用reserve指定vector的容量为n，当push_back的元素数量大于n的时候，会重新分配一个大小为2n的新空间（不跟据2的指数变化，而是在原有大小n的基础上变为2n），再将原有的n的元素和新的元素放入新开辟的内存空间中。
（注：重新分配内存，并不会在原有的地址之后紧跟着分配的新的空间，一般会重新开辟一段更大的空间，再将原来的数据和新的数据放入新的空间）