作者worcdlo ()
看板C_and_CPP
标题[问题] C++ iter = map.earse(iter)的实作
时间Thu May 20 21:25:31 2021
版本: C++ 11
参考网站：
https://www.cplusplus.com/reference/map/map/erase/
问题(Question)：
我们都知道map是用红黑树实践的，
但关於map.erase()，我这边有两个问题想请教各位高手：
1. 假设map.erase的引数是叠代器，代表我已经事先知道特定的node位置，
但红黑树已经指到node，经过erase之後，还是要执行「重新平衡」的动作，
这样是否真的如同网站所写，erase(iter)是逼近常数时间？
2. 另外 iter2 = map.erase(iter)，iter2应该是指到iter的下一个数字，
但这是一颗红黑树，当我们把iter所指到的节点删掉後，
红黑树的节点分布应该会有若干变化，很好奇iter2是透过什麽方式找到的？
想请问是否有比较详细的解释，
或是不知道去哪看这段程式码？
谢谢大家
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.176.57.68 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1621517134.A.33C.html
1F：→ nh60211as: 要直接看程式码的话 GCC、Clang跟MSVC网路上都有 05/20 22:23
2F：→ nh60211as: 得看 05/20 22:23
3F：推 LPH66: 第一题是在问 Amortized 的概念, 它并不单看单一存取的时间 05/21 02:39
4F：→ LPH66: 而是将许多次同样操作所需要的时间进行平均 05/21 02:39
5F：→ LPH66: Amortized (均摊) 常数时间代表, 虽然有可能单一操作会花 05/21 02:40
6F：→ LPH66: 稍微多一点, 但其他时候的状况的时间都很短 05/21 02:41
7F：→ LPH66: 当考虑进各种状况的比例及所需操作平摊之後 05/21 02:41
8F：→ LPH66: 平均每个操作的时间仍然是常数, 那就说这是个均摊常数时间 05/21 02:42
9F：→ oToToT: 2 的话只要平常多维护一个 linked list 就可以做到了吧? 05/21 02:44
10F：→ LPH66: 第二题, 最简单的做法是右→左→左→左→…到底 05/21 02:45
11F：→ LPH66: 但这个方法在往上时要知道从哪里来的, 所以也有另外维护 05/21 02:46
12F：→ LPH66: 下一个元素所在指标的方式 (这可以在树有调整时一起调整) 05/21 02:46
13F：→ LPH66: 补充一点均摊分析的东西, 这种分析一般其实并不会真的去求 05/21 02:48
14F：→ LPH66: 各种状况的比例, 而是实际去看全部跑下来会有哪些操作 05/21 02:48
15F：→ LPH66: 常用技巧是利用某个虚拟 token 摆在结构中表示未来可能操作 05/21 02:49
16F：→ LPH66: 接着去证明每个地方只要某个数量的 token 的数目 05/21 02:50
17F：→ LPH66: 这样就代表不管状况怎样, 总操作数目不会超过一个已知数量 05/21 02:50
18F：→ LPH66: 从这个已知数量即可推得均摊的时间复杂度 05/21 02:51