在STL(标准模板库)中经常会碰到要删除容器中部分元素的情况,本人在编程中就经常编写这方面的代码,在编码和测试过程中发现在STL中删除容器有很多陷阱,网上也有不少网友提到如何在STL中安全删除元素这些问题。本文将讨论编程过程中最经常使用的两个序列式容器vector、list中安全删除元素的方法和应该注意的问题, 其它如queue、stack等配接器容器(container adapter),由于它们有专属的操作行为,没有迭代器(iterator),不能采用本文介绍的删除方法,至于deque,它与vector的删除方法一样。STL容器功能强大,but no siliver bullet,如果你使用不当,也将让你吃尽苦头。
1.手工编写for循环代码删除STL序列式容器中元素的方法<o:p></o:p>
例如,你能看出以下代码有什么问题?
例1:
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
// 初始化vector容器
for (i = 0; i < 5; i++ ) {
vectInt.push_back( i );
}
// 以下代码是要删除所有值为4的元素
vector<int>::iterator itVect = vectInt.begin();
for ( ; itVect != vectInt.end(); ++itVect ) {
if ( *itVect == 4 ) {
vectInt.erase( itVect );
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
<o:p></o:p>
}
例2:
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
// 初始化vector容器
for ( i = 0; i < 5; i++ ) {
vectInt.push_back( i );
if ( 3 == i ) {
// 使3的元素有两个,并且相临。这非常关键,否则将发现不了bug。
// 具体解释见下。
vectInt.push_back( i );
}
}
vector<int>::iterator itVect = vectInt.begin();
vector<int>::iterator itVectEnd = vectInt.end(); // 防止for多重计算
// 以下代码是要删除所有值为3的元素
for ( ; itVect != itVectEnd; ++itVect ) {
if ( *itVect == 3 ) {
itVect = vectInt.erase( itVect );
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
例3:
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt( 5 );
int i;
vectInt[ 0 ] = 0;
vectInt[ 1 ] = 1;
vectInt[ 2 ] = 2;
vectInt[ 3 ] = 3;
vectInt[ 4 ] = 4; // 替换为 vectInt[ 4 ] = 3;试试
vector<int>::iterator itVect = vectInt.begin();
vector<int>::iterator itVectEnd = vectInt.end(); // 防止for多重计算
// 以下代码是要删除所有值为3的元素
for ( ; itVect != itVectEnd; ) {
if ( *itVect == 3 ) {
itVect = vectInt.erase( itVect );
}
else {
++itVect;
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
}
<o:p></o:p>
分析:
这里最重要的是要理解erase成员函数,它删除了itVect迭代器指向的元素,并且返回要被删除的itVect之后的迭代器,迭代器相当于一个智能指针,指向容器中的元素,现在删除了这个元素,将导致内存重新分配,相应指向这个元素的迭代器之后的迭代器就失效了,但erase成员函数返回要被删除的itVect之后的迭代器。
例1将导致程序未定义的错误,在windows中即是访问非法内存,程序当掉。因为vectInt.erase( itVect );调用后itVect之后的迭代器已无效了,所以当执行++itVect后,*itVect访问了非法内存。例1也是初学者最容易犯的错误,这个错误也比较容易发现。
例2可能会导致不能把vectInt中所有为3的元素删除掉。因为第一次删除成功时,itVect = vectInt.erase( itVect );itVect为指向3之后的位置,之后再执行++itVect,itVect就掉过了被删除元素3之后的元素3,导致只删除了一个为3的元素,这个bug比较隐蔽,因为如果不是两个均为3的元素相临,就将很难捕捉到这个bug,程序有可能在一段时间运行良好,但如碰到容器中两值相同的元素相临,则程序就要出问题。
例3,对于本例你可能要说程序没有任何问题,解决了上面的两个bug,程序也运行正常。但且慢,你把 “vectInt[ 4 ] = 4;” 这一行改为 “vectInt[ 4 ] = 3;”试试,一运行,程序当掉,访问非法内存!你疑惑不解:从程序看不出bug,而且我还把vectInt.end()放在外面计算以防止for多重计算,提高效率。哈哈,问题就出在最后一句话!算法大师Donald Knuth有一句名言:不成熟的优化是一切恶果的根源( Permature optimization is the root of all evil )。由于在for循环中要删除元素,则vectInt.end()是会变化的,所以不能在for循环外计算,而是每删除一次都要重新计算,所以应放在for循环内。那你要问,为什么把 “vectInt[ 4 ] = 4;” 这一行改为 “vectInt[ 4 ] = 3;”程序就会当掉,而不改程序就很正常呢?这就跟vector的实现机制有关了。下面以图例详细解释。
vectInt的初始状态为:
<o:p></o:p>
| end
0 1 2 3 4 <o:p></o:p>
删除3后,
<o:p></o:p>
|新的end | 原来的end
0 1 2 4 4 <o:p></o:p>
<o:p></o:p>
<o:p></o:p>
<o:p></o:p>
注意上面“新的end”指向的内存并没有被清除,为了效率,vector会申请超过需要的内存保存数据,删除数据时也不会把多余的内存删除。
然后itVect再执行++itVect,因为此时*itVect等于4,所以继续循环, 这时itVect 等于“新的end”但不等于“原来的end”(它即为itVectEnd),所以继续,因为 *itVect访问的是只读内存得到的值为4,不等于3,故不删除,然后执行++itVect此时itVect等于itVectEnd退出循环。从上面过程可以看出,程序多循环了一次(删除几次,就要多循环几次),但程序正常运行。
如果把 “vectInt[ 4 ] = 4;” 这一行改为 “vectInt[ 4 ] = 3;”过程如下:<o:p></o:p>
<o:p></o:p>
<o:p></o:p>
| end
0 1 2 3 3 <o:p></o:p>
<o:p></o:p>
删除3后,
<o:p></o:p>
|新的end |原来的 end
0 1 2 3 3 <o:p></o:p>
<o:p></o:p>
<o:p></o:p>
删除第2个3后,
<o:p></o:p>
|新的end |原来的 end
0 1 2 3 3 <o:p></o:p>
<o:p></o:p>
这时itVect 等于“新的end”但不等于“原来的end”(它即为itVectEnd),所以继续,因为 *itVect访问的是只读内存得到的值为3,等于3,所以执行删除,但因为*itVect访问的是只读内存不能删除,所以程序当掉。
综上,我们知道当要删除的值在容器末尾时,会导致程序删除非法内存,程序当掉;即使程序正常运行,也是for循环多执行了等于删除个数的循环。所以把vectInt.end()放在for循环外面执行,完全是错误的。对于list容器,list.end()在删除过程中是不会变的,可以把它放在for循环外面计算,但由于list.end()是个常量,把list.end()放在for循环中计算编译器应该可以优化它。从安全考虑,除非你能保证for循环中不会改变容器的大小,否则都应该对容器的值在for循环中计算,对于 vectInt.size()这样的计算,也应该在for循环中计算,不要因为微小的优化而导致程序出错。
<o:p></o:p>
正确的方法:
例4:
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
分享到:
相关推荐
STL关联容器入门
Set 容器中元素的类型可以是任何类型,包括内置类型和用户定义类型。元素类型必须满足以下条件: * 元素类型必须支持小于运算符(<),用于比较元素的大小。 * 元素类型必须支持复制构造函数和赋值运算符,用于元素...
迭代器是一种特殊的指针,它可以指向容器中的元素,并提供了丰富的操作方法来访问和操作容器中的元素。 在STL容器中,我们可以使用算法来对容器中的元素进行操作。算法是对容器中的元素进行操作的函数,STL提供了...
关联式容器是SGI STL中的一类重要数据结构,它们允许通过键(key)来高效地查找、插入和删除元素。在本压缩包中,我们很可能会找到如`set`、`multiset`、`map`和`multimap`等关联式容器的源代码。 关联式容器的核心...
在STL中,`vector`是一种非常重要的容器,它是一个动态数组,允许在任意位置进行元素的插入和删除,并能保持元素的顺序。 `vector`容器的主要特点包括: 1. 动态数组:`vector`的底层实现是一个动态数组,这意味着...
在本文中,我们将重点讨论STL中的容器,特别是序列式容器和关联式容器。 1. 序列式容器: 序列式容器是一类按照元素插入顺序存储的容器,包括vector、queue、deque、priority_queue、list和stack。这些容器有着...
关联式容器是C++标准模板库(STL)中的一类特殊容器,它们的特点在于每个元素都有一个独特的键值(key)和对应的实值(value)。这些容器不像序列式容器(如vector、list)那样有明显的头部和尾部,也不提供push_back、...
STL容器都提供了一些基本的成员变量和成员函数,用于对容器中的元素进行操作。这些成员变量和成员函数包括: * size():返回容器中的元素个数。 * max_size():返回容器的最大容量。 * empty():检查容器是否为空。...
vector是一个动态数组,它是一个序列式容器,提供了在容器末尾添加和删除元素的操作。vector的迭代器类型通常为随机访问迭代器,这意味着我们可以使用迭代器像使用指针一样来访问vector中的元素。 通过对vector容器...
STL容器提供了一系列操作方法,包括构造、赋值、插入、删除、查找、容量管理等。例如: - 构造函数:初始化容器,可以指定初始容量、拷贝构造等。 - 插入操作:如push_back()(向向量尾部添加元素)、insert()(在...
STL不仅提供容器,还有一系列通用算法,如`sort`, `find`, `copy`, `transform`等,这些算法可以作用于任何满足一定要求的序列上,极大提高了编程效率和代码的可读性。例如: - `sort`: 对容器进行排序。 - `find`: ...
- **erase**: 删除容器中的一个或多个元素。 - `c.erase(pos)`: 删除`pos`位置的数据,返回下一个数据的位置。 - `c.erase(beg, end)`: 删除区间`[beg, end)`内的所有元素,返回下一个数据的位置。 - **front**: ...
在C++标准模板库(STL)中,`set`容器是一种非常重要的关联容器,主要用于存储唯一元素,并且这些元素会根据其键值自动排序。`set`内部通常采用红黑树(一种自平衡的二叉查找树)来实现,这使得它在执行插入、删除和...
在STL中,容器是一类能够存储数据的对象,包括vector、string、deque、queue、list、set、multiset、map和multimap。下面将详细介绍这些容器的使用和API方法。 1. **vector**:动态数组,可以自动扩展其大小。常用...
STL定义的三类容器——顺序性容器、关联式容器和容器适配器,各自拥有独特的优势和适用场景。了解并掌握这些容器的特点和使用方法对于有效地进行C++程序开发至关重要。通过合理选择合适的容器类型,可以大大提高代码...
本文将详细介绍C++ STL中两种主要类型的容器:序列式容器与关联式容器。 #### 二、序列式容器 序列式容器是基于元素在内存中连续或接近连续存储的特点设计的,主要包括vector、deque、list等几种类型。 ##### 1. ...
在标题和描述中提到的"基于stl共享内存,可以像使用STL容器一样使用共享内存",指的是通过设计一个自定义的内存分配器(Allocator),使得STL容器如vector、list、map等能够在共享内存上进行操作。这种方式的优势...
C++实战篇:STL-容器 C++实战篇:STL-容器 C++实战篇:STL-容器 C++实战篇:STL-容器 C++实战篇:STL-容器 C++实战篇:STL-容器 C++实战篇:STL-容器 C++实战篇:STL-容器 C++实战篇:STL-容器 C++实战篇:STL-容器 ...
`deque`(双端队列)是C++标准模板库(STL)中的一种重要容器,它提供了类似数组的功能,同时支持在两端进行高效插入和删除操作。与vector相比,deque在两端操作时通常具有更好的性能,因为它不需要移动大量元素。...
STL(Standard Template Library,标准模板库)是C++编程语言中的一个重要组成部分,它提供了一系列高效、可重用的数据结构和算法。这个“STL中文手册 doc文档”显然是为了解决C++程序员在使用STL时遇到的问题,帮助...