2

我怎样才能有效地实现这个显然不存在的功能(为什么?):

std::pair<iterator,bool> std::set::insert (const_iterator hint, const value_type& val);

我想有效地插入一个值(带有提示),同时有一个布尔值告诉我它是否已被插入(这是必不可少的)。

为什么不存在这样的功能。我无法想出有效地做到这一点的可能性吗?

非常感谢!

4

1 回答 1

1

通常假设如果您有一个提示迭代器,您是通过find、或获取的equal_range,或者正在插入一个排序序列,所以如果您需要知道,您可以检查是否(或可能)与您自己等效:lower_boundupper_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) 中执行,因此您应该在调用之前检查插入是否成功。*hintvalinsert

同样,对于从 派生的提示迭代器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
于 2014-03-20T18:26:44.747 回答