[C++标准程序库的问题] 在删除操作很多的情况下，应该选择什么样的容器？

Answer 1

引用~0&1~的，这就是一个好答案！！！
按照标准程序库的说明，当删除/插入只发生在容器的尾部时，应该使用vector；当删除/插入只发生在容器的首/尾部时，应该使用deque；当删除/插入操作很多，而且删除/插入不是只在容器的首尾，这时应该选择list。
　　但是这里也有一个问题，在使用list时，由于其迭代器只能一次移动一个位置，在有大量删除的操作时，需要大量的迭代器移动操作，因此使用list的效率会很低；list的另一个缺点是，占用空间要比同等容量大小的vector要大，这是由于list的实现需要指针，每个元素就多比vector中的元素多两个指针（双向链表），因此在每个元素都很小（几个字节），而且元素数量很大时，使用list就非常浪费空间了。
　　如果使用vector，那么删除中间元素会导致大量的元素移动操作，效率也不高，为了解决这个问题，我们可以这样作：使用vector容器，但是不直接删除元素，而是再申请一个临时vector，将原来vector中未删除的有用元素依次加入/保存到临时vector，然后用这个临时vector替换原来的vector，如果实现知道要删除的元素的个数，那么可以事先预留临时vector的空间，再将有用元素存到临时vector中，代码如下：
#include
<vector>
using
namespace
std;
vector
myVec;
…
//
myVec的初始化以及其它操作
vector
tempVec;
//
删除myVec中的num个元素
tempVec.reserve(
myVec.size()
-
num
);
//
预留临时vector的空间
for
(
;;
)
{
将myVec中的有用元素存到tempVec中;
}
myVec.swap(
tempVec
);
//
myVec的容量等于或稍大于myVec.size()
…
//
其它操作

Answer 2

按照标准程序库的说明，当删除/插入只发生在容器的尾部时，应该使用vector；当删除/插入只发生在容器的首/尾部时，应该使用deque；当删除/插入操作很多，而且删除/插入不是只在容器的首尾，这时应该选择list。
　　但是这里也有一个问题，在使用list时，由于其迭代器只能一次移动一个位置，在有大量删除的操作时，需要大量的迭代器移动操作，因此使用list的效率会很低；list的另一个缺点是，占用空间要比同等容量大小的vector要大，这是由于list的实现需要指针，每个元素就多比vector中的元素多两个指针（双向链表），因此在每个元素都很小（几个字节），而且元素数量很大时，使用list就非常浪费空间了。
　　如果使用vector，那么删除中间元素会导致大量的元素移动操作，效率也不高，为了解决这个问题，我们可以这样作：使用vector容器，但是不直接删除元素，而是再申请一个临时vector，将原来vector中未删除的有用元素依次加入/保存到临时vector，然后用这个临时vector替换原来的vector，如果实现知道要删除的元素的个数，那么可以事先预留临时vector的空间，再将有用元素存到临时vector中，代码如下：
#include
<vector>
using
namespace
std;
vector
myVec;
…
//
myVec的初始化以及其它操作
vector
tempVec;
//
删除myVec中的num个元素
tempVec.reserve(
myVec.size()
-
num
);
//
预留临时vector的空间
for
(
;;
)
{
将myVec中的有用元素存到tempVec中;
}
myVec.swap(
tempVec
);
//
myVec的容量等于或稍大于myVec.size()
…
//
其它操作
这只是我目前总结的几个问题，以后遇到问题随时解决，随时总结。