在实现Trees/Heaps/Lists等时,为什么`find`方法会将迭代器返回给对象而不是obect本身？

Question

我看到很多不同的C++程序员在我们的数据结构实现中一直比我自己更了解这一点.例如,在这个AVL树实现中,

/**
* iterator find(const Key& key);
* const_iterator find(const Key& key);
* Usage: if (myAVLTree.find("Skiplist") != myAVLTree.end()) { ... }
* -------------------------------------------------------------------------
* Returns an iterator to the entry in the AVL tree with the specified key,
* or end() as as sentinel if it does not exist.
*/
iterator find(const Key& key);
const_iterator find(const Key& key) const;

我试图弄清楚在什么情况下这比返回与key对应的值更有用.

如果我将这个采用到我自己的实现中(假设我正在设计某种容器)什么时候这样做会让我受益？

Answer 1

返回迭代器有几个显着的优点:

(1)如果找不到密钥,则指示失败是一个很好的策略; 即返回end()清楚表明未找到密钥.替代方案包括抛出异常(at()成员函数将执行)或返回nullptr,这将要求成功时也返回指针.

(2)某些数据结构维护一个顺序,例如std::map.当返回迭代器时,这使调用者能够递增或递减迭代器以获得排序中的下一个/上一个键/值对.

(3)许多标准容器成员函数将迭代器作为参数,例如std::vector::erase或std::map::erase.通过传入迭代器,容器可以有效地对特定元素进行操作,而不必按键进行另一次查找.例如,std::map::erase(const key_type&)必须是O(log(N))操作,但是std::map::erase(iterator)是O(1)操作.