我怎样才能有效地实现这个显然不存在的功能(为什么?):
std::pair<iterator,bool> std::set::insert (const_iterator hint, const value_type& val);
我想有效地插入一个值(有提示),同时有一个 bool 值告诉我它是否已被插入(这是必不可少的)。
为什么没有这样的功能。我无法想出有效地做到这一点的可能性?
非常感谢!
最佳答案
通常假设如果你有一个提示迭代器,你通过 find
、equal_range
、lower_bound
或 upper_bound< 获取它
,或者正在插入一个排序的序列,所以如果你需要知道你可以检查 *hint
(或者可能 *prev(hint)
)是否等同于 val
你自己:
iterator hint = s.lower_bound(val);
// (hint == s.end() || !(*hint < val)) && (hint == s.begin() || *prev(hint) < val)
if (hint != s.end() && !(val < *hint))
; // equivalent
else
s.insert(hint, val); // guaranteed to insert
请注意,如果插入失败,insert-with-hint 不保证在 O(1) 内执行(即 *hint
等同于 val
),因此您应该在调用 insert
之前检查插入是否成功。
类似地,对于从 upper_bound
派生的提示迭代器:
iterator hint = s.upper_bound(val);
// (hint == s.end() || val < *hint) && (hint == s.begin() || !(val < *prev(hint)))
if (hint != s.begin() && !(*prev(hint) < val))
; // val is equivalent to *prev(hint)
else
s.insert(hint, val); // guaranteed to insert
关于c++ - std::map 和 std::set 不返回带提示的 bool,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22541268/