vector扩容问题
vector在尾部插入（push_back）时的扩容
void test3()
{
vector<int> num = {1,2,3,4,5};
cout << "num.size() = " << num.size() << endl;
cout << "num.capacity() = " << num.capacity() << endl;
num.push_back(6);
cout << "num.size() = " << num.size() << endl;
cout << "num.capacity() = " << num.capacity() << endl;
num.push_back(7);
num.push_back(8);
num.push_back(9);
num.push_back(0);
num.push_back(11);
cout << "num.size() = " << num.size() << endl;
cout << "num.capacity() = " << num.capacity() << endl;
}
运行结果：
可以看到每次扩容都是原来容量的2倍，是固定的。
vector在任意位置插入（insert）时的扩容
void test4()
{
vector<int> num = {1,2,3,4,5};
num.push_back(6);
vector<int>::iterator it = num.begin();
it++;
it++;
cout << "num.size() = " << num.size() << endl;
cout << "num.capacity() = " << num.capacity() << endl;
cout << "设size = m = 6，capacity = n = 10，待插入元素个数为 t." << endl;
cout << "1.当 t <= n -m 时，不会扩容" << endl;
cout << "2.当 n - m < t < m 时，此时会按照 2 * m 进行扩容:" << endl;
num.insert(it,5,66);
cout << " m = num.size() = " << num.size() << endl;
cout << " n = num.capacity() = " << num.capacity() << endl;
cout << "3.当 n - m < t 且 m <= t 时，此时会按照 m + t 进行扩容:" << endl;
// 注意，此时需要更新迭代器的位置才能插入
it = num.begin();
it++;
it++;
num.insert(it,11,777);
cout << " m = num.size() = " << num.size() << endl;
cout << " n = num.capacity() = " << num.capacity() << endl;
}
运行结果：
小结
对于vector的扩容，由于push_back()和insert()引起的扩容，其底层扩容机制是不一样的。
- 在尾部插入时，每次只能插入一个元素，此时按照2 * capacity进行扩容即可，是肯定不会出现问题的。
- 但是通过insert插入时，每次插入元素的个数不确定，所以不能单纯按照2 * capacity进行扩容。
- 当 待插入元素t <= capacity - size 时，不需要扩容
- 当 capacity - size < 待插入元素t ，且待插入元素t < m 时，此时按照 2 * size进行扩容
- 当 capacity - size < 待插入元素t ，且m <= 待插入元素t 时，此时按照 size + t 进行扩容
迭代器失效问题
我们知道，vector在进行扩容时，会开辟一块新的空间，将原有空间中的内容复制过来，随后将原有的空间回收。而此时迭代器仍然指向原来的那片内存，故此时迭代器就会出现失效的问题。
void test2()
{
vector<int> num = {1,2,3,4,5};
vector<int>::iterator it = num.begin();
cout << "*it = " << *it << endl;
printf("it = %p\n",&(*it));
num.insert(it,3000,66);
cout << "*it = " << *it << endl; // 未定义的行为（此时it所指向的区域已经被回收了）
printf("it = %p\n",&(*it));
// num.insert(it,3000); // error，如果仍然以原有的迭代器为基准进行插入，就会出现错误
// 解决方法：更新迭代器
cout << "更新迭代器的位置 " << endl;
it = num.begin();
cout << "*it = " << *it << endl;
printf("it = %p\n",&(*it));
cout << "插入数据" << endl;
num.insert(it,777); // ok
cout << "*it = " << *it << endl; // 未定义的行为
printf("it = %p\n",&(*it));
vector<int>::iterator it2 = num.begin();
cout << "*it2 = " << *it2 << endl; // ok
printf("it2 = %p\n",&(*it2));
}
运行结果：
小结
- 对于vector，其迭代器是真实的指针，所以可以在上述例子中用printf打印出来，但是对于其他容器的迭代器，很有可能根本不是一个真实的指针，是不可以这样操作的，这一点需要注意。
- 由此可见，vector在插入元素时，有时会引起其底层的扩容，这时会导致原有的迭代器失效。为解决此问题，我们在插入元素之后，操作迭代器之前，最好更新一下迭代器的位置，让迭代器指向新的空间的位置，避免出错。
- 特别的，对于deque而言，去进行insert操作的时候，也有可能迭代器失效，所以最好还是可以每次使用迭代器的时候，像vector一样，将迭代器的位置进行更新，指向新的空间的位置。