哈希表C++实现，remove()函数怎么设计好？
来源：14-5 实现属于我们自己的哈希表
Ian_Song
2020-04-22
波波老师好：
我在用c++实现一个哈希表，写remove()函数的时候，如果表里没有我们要remove的key，应该传一个空的V出来，如果用传值的话，c++好像很难表达出空的概念。但如果用传指针的话，这种情况下我们的确可以传一个空指针出来，但如果要删除的key存在的话，这个指针不能指向一个被删除的值，我能想到的只有V* res = new V(treeMap[hash][key]);，让调用者拿到这个值后再手动释放。
有没有更佳的解决方案呢？
1回答
-
C++ 确实存在这个问题。如果一定要返回删除的 key 对应的值的话，我能想到的只有你那样设计。
另一种设计方式是：不返回删除的 key 所对应的 value，只返回 bool，表示是否删除成功。如果用户想拿到删除的 key 所对应的 value，应该先使用查找的方式拿到 key 所对应的 value，然后再运行删除。也就是把删除和查找两个动作分离。
C++ 的 map 类的 size_type erase (const key_type& k); 接口是这一模式的；
如果你认为先查找，再删除，其实是做了两趟查找的话（第二遍删除也需要先查找），不优的话，那么就可以建立一层迭代器的机制了。C++ 也是这么干的。用户在查找以后，可以得到指向查找到的元素（也就是待删除元素）所对应的迭代器，之后使用这个迭代器作删除，就可以避免一轮查找了。
C++ 的 map 类的 iterator erase (const_iterator position); 接口是这一模式的。
另外，我说的虽然是 map 类，但 C++ STL 封装的哈希表类 unordered_map，接口是完全一致的。
继续加油！：）
00
相似问题