容器中的iterator | 沉默杀手

先看vector的部分源码，只看变量声明：

template <class T, class Alloc = alloc>  // 预设使用 alloc 为配置器
class vector
{
public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef value_type* iterator;
  typedef const value_type* const_pointer;
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  ...  
}

容器的迭代器iterator其实是类模板，不是一个指针，但实现了指针的功能，不能赋值为NULL，也不能与NULL比较。迭代器采用了iterator模式，类似于数据库中的游标,它屏蔽了底层存储空间的不连续性，在上层使容器元素维持一种连续的假象，迭代器代表的是元素在容器中的相对位置。

如果迭代器iterator要初始化或者做空值比较，需要使用end()，它默认指向容器最后一个元素的下一个位置，可以理解为空．如果非要对iterator进行初始化的话，可以将iterator指向end()函数即可。判断是否为空即与end()函数做比较即可

看下面代码：

std::vector<int> vec;
vec.push_back(1);
vec.push_back(3);
vec.push_back(5);
vec.push_back(7);
std::vector<int>::iterator it= vec.end();
qDebug()<<*(--it);		// 像游标
it++;
if(it == vec.end())
    qDebug()<<"vec end";

运行结果为:

1
2

7
vec end

迭代器失效

迭代器指向容器中的某个或某些元素的存储发生了变化，使之成为无效迭代器，使用无效迭代器和无效指针一样危险。

解决迭代器失效问题有两种方式：

使用迭代器时重新获取迭代器
在修改容器前为其预留足够的空闲空间，以避免存储空间重分配。

vector<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);
l.push_back(6);

vector<int>::iterator it = l.begin();
vector<int>::iterator end = l.end();
Print(l);
cout<<"size: "<<l.size()<<"  capacity: "<<l.capacity()<<endl;   　// 6   8
cout<< "begin: "<<*it <<endl;       // 1
cout<< "end: "<< *(--end) <<endl;    // 6
// 再插入元素
l.push_back(7);
l.push_back(8);
//    l.push_back(9);

Print(l);
cout<<"size: "<<l.size()<<"  capacity: "<<l.capacity()<<endl;  // 8   8
cout<<"after push_buck begin: "<< *it <<endl;
cout<<"after push_buck end: "<< *(end) <<endl;  // 6

运行结果：

1 2 3 4 5 6 
size: 6  capacity: 8
begin: 1
end: 6

1 2 3 4 5 6 7 8 
size: 8  capacity: 8
after push_buck begin: 1
after push_buck end: 6

可以看出进行push_back后，end返回的迭代器肯定是失效的，容器内部没有对其进行更新，erase也是同样结果．

上面代码加上l.push_back(9);后，运行结果成了这样：

1 2 3 4 5 6 
size: 6  capacity: 8
begin: 1
end: 6
1 2 3 4 5 6 7 8 9 
size: 9  capacity: 16
after push_buck begin: 0
after push_buck end: 6

我们往vector插入6个元素，size就是6，但vector分配的容量要稍大一些．如果再插入3个元素，就超出了容量，vector会先分配一个2倍大的内存，然后把原来的元素都拷贝过来，释放原内存，这样迭代器就像悬垂指针一样失效了．当删除容器内的数据时，其存储空间不释放

有些资料说重新分配内存是增加原内存的一半，估计是STL版本和编译器版本不同的缘故，我测试的vector的容量都是2的次方


vector<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);
l.push_back(6);

vector<int>::iterator it = l.begin();
vector<int>::iterator end = l.end();
Print(l);
cout<<"size: "<<l.size()<<"  capacity: "<<l.capacity()<<endl;
cout<< "begin: "<<*it <<endl;
cout<< "end: "<< *(--end) <<endl<<endl;

l.erase(++it);
l.erase(++it);

Print(l);
cout<<"size: "<<l.size()<<"  capacity: "<<l.capacity()<<endl;
cout<<"after erase begin: "<< *it <<endl;
cout<<"after erase end: "<< *(end) <<endl;

运行结果：

1 2 3 4 5 6 
size: 6  capacity: 8
begin: 1
end: 6

1 3 5 6 
size: 4  capacity: 8
after erase begin: 5
after erase end: 6

显然begin是失效了

vector的push_back操作可能没事，但是一旦引发内存重分配，所有迭代器都会失效
vector的insert操作插入点之后的所有迭代器失效，但一旦发生内存重分配，所有迭代器都会失效
vector的erase操作插入点之后的所有迭代器失效
vector的reserve操作所有迭代器失效（导致内存重分配）

对于序列式容器(如vector,deque)，删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。但是erase方法可以返回下一个有效的iterator

对于节点式容器(map, list, set)元素的删除，插入操作会导致指向该元素的迭代器失效，其他元素迭代器不受影响；
对于顺序式容器(vector，string，deque)元素的删除、插入操作会导致指向该元素以及后面的元素的迭代器失效

迭代器的自增减

迭代器可以一直自增或自减，可以超出begin()和end()

vector<int> poses;
poses.push_back(1);

auto iter = poses.end();
iter++;
iter++;
iter++;
cout << " iter - begin: " << iter - poses.begin() << endl <<
        " iter - end: " << iter - poses.end() << endl;
cout << "poses size: " << poses.size() << endl;
cout << "iter pose: " << *iter << endl;   // 不确定的结果

运行结果:

iter - begin: 4
iter - end: 3
poses size: 1
iter pose: 0

超出范围的迭代器，不要取对应的元素值，否则就是bug，最好加判断 if(iter - poses.end() >0)