hash_map erase

 

一.  hash_map

    使用STL标准库时，如不了解其实现细节，很容易写出错误的代码。常见操作如遍历容器时时同时删除元素，见代码：

#include <ext/hash_map>

using namespace __gnu_cxx;    // linux使用hash_map必须使用该命名空间

hash_map<int,Person*> hash;
Person *per = NULL;

hash_map<int,Person*>::iterator it;
for( it=hash.begin();it!=hash.end();it++ )
{
	per = it->second;
	
	if( per->age == 20 )
	{
		hash.erase( it );		// 删除年龄为20的节点
	}
}

  

  上面代码运行几次后，突然就崩溃了。hash_map内部采用哈希表实现，迭代器其实就是指向节点的指针，在访问下一个节点时通过it++移动到下一个节点的地址。执行erase(it)后，it成为一个非法指针，执行it++就会出错。正确的使用方式应该在删除节点前，将指针移到下一个正确地址上。

  

// 正确写法
for( it=hash.begin();it!=hash.end(); )
{
	per = it->second;
	
	if( per->age == 20 )
	{
		hash.erase( it++ );		// 方法一：执行it++指向下一个节点
		//it = hash.erase( it );	// 方法二：接收erase()返回值
	}
	else
	{
		it++;
	}
}

 

二. Java容器

    Java中操作list,set,map容器时，经常会抛出 ConcurrentModificationException 异常。

// 错误写法
Iterator<String> it = list.iterator();
while( it.hasNext() ){
	String val = it.next();
	
	if( val == "boy" )
	{
		list.remove(val);   // 删除元素boy
	}
}

 

   有兴趣可以分析list实现源码，在遍历时执行remove()导致迭代器内部记录变量值不一致所致。正确的写法使用Iterator.remove()。

 

// 正确写法，调用迭代器删除方法
it = list.iterator();
while( it.hasNext() ){
	String val = it.next();
	
	// 删除元素boy
	if( val == "girl" )
	{
		it.remove();	// 内部也是调用list.remove()，只不过多了对变量值的修正操作
	}
}