容器

1、几种容器的比较：

（1）vector：内部数据结构：数组

在末尾增加或者删除元素所需时间与元素数目无关，在中间或者开头增加或者删除所需时间呈线性变化。

（2）deque：内部数据结构是：数组

随机访问每个元素，所需要的时间为常量。在开头和末尾增加元素所需时间与元素数目无关，在中间增加或删除所需时间随元素数目呈线性变化。

（3）list：内部数据结构：双向环状链表

不能随机访问一个元素，可双向遍历，在开头，末尾和中间的任何地方增加或者删除元素所需时间都是常量。

（4）set：键和值相等。

键唯一，元素按照默认升序排列

（5）map：键唯一

元素按照默认升序排列

2、关于迭代器失效的问题，小心使用stl中的erase。

#include <iostream>
#include <vector> 
using namespace std;
int main(){
	vector<int> vect;
	for(int i=0;i<10;i++){
		vect.push_back(i);
	}
	
	vector<int>::iterator iter  = vect.begin();
	
	for(iter;iter!=vect.end();iter++){
		if(*iter%2==0){
			vect.erase(iter);
		}
	}
	return 0;
}

　　程序直接就crash了。iter是指向vector这个容器中的某个元素，如果不是在for，while循环中，erase删除元素是没有问题的，但是如果在forwhile循环中对容器进行迭代，删除其中符合条件的所有元素，就可能出现问题。vect.erase（iter）及其后面的迭代器已经失效了，不应该在使用这些迭代器了，在执行it+，其行为是未定义的。其他容器也会遇到迭代器失效的问题。对于vector被删除元素的迭代器机制向后面元素的迭代器全部失效。对于deque在手部或尾部删除元素这只会是指向被删除元素的迭代器失效，任何其它位置的插入和删除操作将是指向该容器元素的所有迭代器失效。

　　对于list仅有指向被删除元素的迭代器失效。为什么不同容器迭代器失效情况差别？主要与各容器的数据结构相关。

那么我们看看个容器删除元素的通用做法。

#include <iostream>
#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <list>

using namespace std;

int main()
{
	vector<int> vect;
	for(int i=0;i<10;i++){
		vect.push_back(i);
	}
	
	vector<int>::iterator iter = vect.begin();
	
	for(;iter!=vect.end();){
		if(*iter%2==0){
			iter = vect.erase(iter);
		}else{
			iter++;
		}
	}
	
	for(vector<int>::iterator iter = vect.begin();iter!=vect.end();iter++){
		cout<<*iter<<" ";
	}
}

　　

#include <iostream>
#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <list>

using namespace std;

int main()
{
	deque<int> mydeque;
	for(int i =0;i<10;i++){
		mydeque.push_back(i);
	}
	deque<int>::iterator iter = mydeque.begin();
	
	for(;iter!=mydeque.end();){
		if(*iter%2==0){
			iter = mydeque.erase(iter); 
		}
		else{
			iter++;
		}
	} 
	
	for(deque<int>::iterator iter = mydeque.begin();iter<mydeque.end();iter++){
		cout<<*iter<<" ";
	}
}

　　

#include <iostream>
#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <list>

using namespace std;

int main(){
	map<int, int> mymap;
	mymap[0] = 1;
	mymap[1] = 2;
	mymap[2] = 3;
	mymap[3] = 4;
	
	map<int, int>::iterator it = mymap.begin();

	for (; it != mymap.end();){
		if ((it->second % 2) == 0){
			//mymap.erase(it++);
			it = mymap.erase(it);
		}
		else{
			it++;
		}
	}

	for (auto iter = mymap.begin(); iter != mymap.end(); ++iter){
		cout << iter->first << " " << iter->second << endl;
	}
	system("pause");
	return 0;
}