一. 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(),只不过多了对变量值的修正操作 } }
相关推荐
list_.erase(hash_map[key]->next); } else { if (hash_map.size() == capacity_) { evict(); } } Node* newNode = new Node{key, value, nullptr, list_.front()}; list_.front()->prev = newNode; list_....
STL hash_map: 链式散列 版权所有 (c) 2014,龙 (Ryan) 南宫。 保留所有权利。 邮箱: 创建时间:2014 年 7 月 15 日 这是无序的哈希映射,它具有恒定的插入、删除、搜索时间,并支持向前/向后迭代。 hash_map 的...
`unordered_map`提供了丰富的成员函数,如`insert()`用于插入元素,`find()`用于查找元素,`erase()`用于删除元素,`size()`用于获取元素数量,`empty()`用于检查是否为空,以及`operator[]`用于访问或修改元素等。...
- `hash`在C++中通常是指`unordered_map`或`unordered_set`容器,它们使用哈希表来存储元素,提供快速的查找和插入操作。 - 哈希表通过计算元素的哈希值来确定其存储位置,理想情况下,哈希函数可以将不同元素均匀...
在C++中,可以通过`hash`模板类自定义哈希函数,并通过`equal_to`模板类自定义键的比较函数。 **性能考虑** 虽然`unordered_map`在平均情况下提供了高效的查找,但在最坏的情况下(所有键哈希到同一个位置),性能...
2. **哈希函数和等价比较**:`std::unordered_map`需要一个哈希函数(hash function)和等价比较函数(equality predicate)来确定元素的位置和查找。对于自定义的结构体,开发者需要提供这两个函数,确保它们能正确...
map.erase(it); } } private: std::vector<T> data; std::unordered_map, size_t> map; }; ``` 这个`VectorHashSet`类提供了插入、检查和删除元素的基本功能。请注意,这种实现不考虑性能优化,实际应用中,`...
这些类可能包括如`insert`、`erase`、`find`、`contains`等方法,允许用户进行基本操作。同时,由于它们是模板类,所以可以用于各种类型的键值对或元素。 在实现上,Tessil的库可能采用了动态调整大小的策略,当...
`sparsehash`是一个C++库,提供了多种不同类型的哈希表,如`ds::sparse_hash_map`、`ds::dense_hash_map`等。这些容器都实现了键值对的快速查找和插入操作,且内存开销相对较小,尤其适合存储稀疏的数据集。`...
通过`std::hash`模板类的特化或者`std::unordered_set/map`的`hash_function`成员函数进行设置。 - **等价关系**:对于`std::unordered_map`,键的等价关系默认由`==`运算符决定。如果需要自定义,可以提供一个比较...
1. 自定义哈希函数和等价函数:`std::unordered_map`默认提供了一些常见的哈希和等价函数,但为了提高效率或处理自定义类型,我们可能需要提供自己的哈希函数(`hash_function`)和等价函数(`equal_function`)。...
hash_map.erase(old->key); } LRUNode* newNode = new LRUNode(key, value); insert(newNode); hash_map[key] = newNode; } } ``` `remove`和`insert`是辅助函数,分别用于从链表中移除节点和将节点插入链表...
实现了创建哈希表的函数 createHashtable,哈希函数 hash,插入键值对的函数 insert,查找键对应值的函数 get,删除指定键的节点的函数 erase,以及打印哈希表的函数 printHashtable。 在 main 函数中进行了简单的...
- **哈希函数(Hash Function)**:将键转换为哈希码,用于快速定位元素。 - **负载因子(Load Factor)**:桶中元素数量与桶总数的比值,影响查找效率。 3. **创建和初始化** 创建一个空的`unordered_map`,...
它可能还提供了丰富的接口,如`insert`、`erase`、`find`、`count`等,以满足常见的操作需求。此外,为了保证线程安全,可能还包含了对多线程环境的支持,如使用原子操作或锁来保护数据结构。 Hopscotch Map的效率...
std::cout << searchKey << " not found in the hash map." ; } ``` 使用`find`成员函数可以检查哈希表中是否包含特定的键。如果找到该键,则返回指向该键值对的迭代器;如果没有找到,则返回`end()`迭代器。 ###...
3. **删除联系人**:删除操作则使用`unordered_map::erase`方法,传入要删除的联系人的姓名,即可从散列表中移除相应的条目。 此外,为了提高效率,我们还需要考虑如何处理散列冲突。常见的解决冲突的方法有开放...
- **哈希容器**:hash_set、hash_multiset、hash_map和hash_multimap,提供基于哈希表的快速查找。 2. **不要编写独立于容器类型的代码**: - 尽管可以尝试编写通用的代码,但不同容器有不同的性能特征和使用场景...
在非标准关联容器方面,如hash_set、hash_multiset、hash_map和hash_multimap,它们以哈希表的形式实现,适用于快速查找操作。 容器实现的选择应该基于数据结构的特性以及对程序性能的需求。例如,如果需要快速随机...
在C++11及以后的版本,推荐使用`unordered_map`而非旧版的`hash_map`,因为`unordered_map`更现代,性能通常更好,并且不需要使用特定的命名空间。如果需要自定义哈希函数,可以重载`unordered_map`的哈希函数。 ...