STL中迭代器什么时候会失效？

• 对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。

说明

当删除一个元素后，内存中的数据会发生移动以保证数据的紧凑。所以删除一个元素后，其他数据的地址发生了变化，之前获取的迭代器根据原有信息就访问不到正确的数据。

//迭代器失效
void vectorTest()
{
    vector<int> container;
    for (int i = 0; i < 10; i++)
    {
        container.push_back(i);
    }
 
    vector<int>::iterator iter;
     for (iter = container.begin(); iter != container.end(); iter++)
    {
            if (*iter > 3)
              container.erase(iter);
    }
 
     for (iter = container.begin(); iter != container.end(); iter++)
    {
            cout<<*iter<<endl;
    }
}

//代码修改，ok
	void vectorTest()
{
    vector<int> container;
    for (int i = 0; i < 10; i++)
    {
        container.push_back(i);
    }
 
    vector<int>::iterator iter;
     for (iter = container.begin(); iter != container.end();)
    {
            if (*iter > 3) {
				iter = container.erase(iter);
			}
			else {
				iter ++;
			}
    }
 
     for (iter = container.begin(); iter != container.end(); iter++)
    {
            cout<<*iter<<endl;
    }
}

• 对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

说明：

虽然删除了一个元素，整棵树也会调整，以符合红黑树规范，但是单个节点在内存中的地址没有变化，变化的是各节点之间的指向关系。删除一个结点不会对其他结点造成影响。 erase迭代器只是被删元素的迭代器失效。

#include<iostream>
#include<string>
#include<map>
using namespace std;

int main()
{
    map<string, int> mapData;
    mapData["a"] = 1;
    mapData["b"] = 2;
    mapData["c"] = 3;

    map<string, int>::iterator itMap = mapData.begin();
    while (itMap != mapData.end())
    {
        if (strcmp(itMap->first.c_str(), "a") == 0)
        {
            mapData.erase(itMap++);
        }
        else
        {
            itMap++;
        }

        /* 迭代器失效
        if (strcmp(itMap->first.c_str(), "a") == 0)
        {
            mapData.erase(itMap);
        }
        itMap++;
        */
    }
}

• list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器

上面两种方法都可以使用。

STL中迭代器的作用，有指针为何还要迭代器？

• 迭代器作用

（1）用于指向顺序容器和关联容器中的元素。

（2）通过迭代器可以读取它指向的元素。

（3）通过非const迭代器可以修改其指向的元素。

• 迭代器和指针的区别

迭代器不是指针，是类模板，表现得像指针。迭代器模拟了指针的一些功能，重载了指针的一些操作符。迭代器本质是封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为，可以看成一种智能指针，他可以根据不同类型的数据结构来实现不同的++，--等操作。

• 迭代器产生的原因

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

STL 迭代器是怎么删除元素的

这主要考察迭代器失效的问题，上面已经总结。

STL 中 resize 和 reserve 的区别

• 两个概念

（1）capacity：该值在容器初始化时赋值，指的是容器能够容纳的最大的元素的个数。还不能通过下标等访问，因为此时容器中还没有创建任何对象。

（2）size：指的是此时容器中实际的元素个数。可以通过下标访问0-(size-1)范围内的对象。

• resize和reserve区别

（1）resize既分配了空间，也创建了对象；reserve表示容器预留空间，但并不是真正的创建对象，需要通过insert（）或push_back（）等创建对象。

（2）resize既修改capacity大小，也修改size大小；reserve只修改capacity大小，不修改size大小

（3）两者的形参个数不一样。 resize带两个参数，一个表示容器大小，一个表示初始值（默认为0）；reserve只带一个参数，表示容器预留的大小。

STL 容器动态链接可能产生的问题？

• 可能会产生什么问题

容器是一种动态分配内存空间的一个集合类型的变量。在一般的程序函数里，局部容器，参数传递容器，参数传递容器的引用，参数传递容器指针都是可以正常运行的，而在动态链接库函数内部使用容器也是没有问题的，但是给动态库函数传递容器的对象本身，则会出现内存堆栈破坏的问题。

• 产生问题原因

容器和动态链接库相互支持不够好，动态链接库函数中使用容器时，参数中只能传递容器的引用，并且要保证容器的大小不能超出初始大小，否则导致容器自动重新分配，就会出现内存堆栈破坏问题

map 和 unordered_map 的区别？底层实现

• map实现机理

map内部实现了一个红黑树，红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。对于map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉查找树存储的（左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）。中序遍历可将键值按照从小到大遍历出来。

• unordered_map实现机理

unordered_map内部实现了一个哈希表，通过把关键码值映射到Hash表中一个位置来访问记录，查找时间复杂度可达O（1），在海量数据处理中有着广泛应用。因此，元素的排列顺序是无序的。

push_back 和 emplace_back 的区别

要将一个临时变量push到容器的末尾，push_back()需要先构造临时对象，再将这个对象拷贝到容器的末尾，而emplace_back()则直接在容器的末尾构造对象，这样就省去了拷贝的过程。

#include<iostream>
using namespace std;
#include<string>
#include<vector>

class TestA
{
public:
	string str;
	TestA(int i)
	{
		str = to_string(i);
		cout << "构造函数的调用" << endl;
	}

	~TestA()
	{
		//cout << "析构函数的调用" << endl;
	}

	TestA(const TestA& other) :str(other.str)
	{
		cout << "拷贝函数构造" << endl;
	}

};

int main()
{
	vector< TestA> vec;
	vec.reserve(10);
	for (int i = 0; i < 10; i++)
	{
		//调用了10次构造函数和10次拷贝构造函数
		vec.push_back(i);

		//调用了10次构造函数,没有调用拷贝构造函数
		//vec.emplace_back(i);
	}
	return 0;
}

push_back()运行结果：

emplece_back()运行结果：