gpt4 book ai didi

c++ - 提示插入到 std::map 会导致树不平衡吗?

转载 作者:塔克拉玛干 更新时间:2023-11-03 00:37:41 27 4
gpt4 key购买 nike

这是否会导致 std::map/set 中的树不平衡(以及随后的搜索性能不佳):

std::set<int> s;
for(int i = 0; i< 1000; ++i)
s.insert(s.end(), i);

?

或者换句话说:“提示插入”会根据需要重新平衡底层树吗?

Afaik,C++ 标准并不能保证这一点,但我想知道大多数流行的实现在这种情况下的表现如何。

最佳答案

不管有序关联容器的底层实现是什么(标准没有规定,虽然通常是自平衡二叉查找树),hinted insert (iterator insert( const_iterator hint, const value_type& value );) 可以用下面的简单算法来满足:

  1. 比较值与*hint 和*prev(hint)

  2. 如果它适合它们,将它插入那里。

  3. 否则,忽略提示。

只要 prev(hint) 是摊销常数时间,只要 hint 是正确的,该算法就是摊销常数时间。 (“正确”的意思是它是插入点之后的位置。)

如果提示不正确,忽略提示是完全可以接受的,因此提供不正确的提示不会对数据结构造成任何影响;它仍然与插入之前一样平衡(可对数访问)。但是提供不正确的提示会强制计算 O(1) 次额外比较,因此仅当提示通常正确时才应使用插入的提示版本,对于“通常”的某些值。

一个常见的用例是当已经对要插入的条目进行了搜索,因此插入位置是明确已知的。这避免了在插入之前需要做某事时搜索两次的开销,而不会在其他进程修改 find() 之间的 set 的情况下牺牲安全性并提示 insert()(当然,假设适当的锁定)。

关于c++ - 提示插入到 std::map 会导致树不平衡吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50381746/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com