版本: 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是透过什么方式找到的？
想请问是否有比较详细的解释，
或是不知道去哪看这段程式码？
谢谢大家

要直接看程式码的话 GCC、Clang跟MSVC网络上都有得看

第一题是在问 Amortized 的概念, 它并不单看单一存取的时间而是将许多次同样操作所需要的时间进行平均Amortized (均摊) 常数时间代表, 虽然有可能单一操作会花稍微多一点, 但其他时候的状况的时间都很短当考虑进各种状况的比例及所需操作平摊之后平均每个操作的时间仍然是常数, 那就说这是个均摊常数时间

2 的话只要平常多维护一个 linked list 就可以做到了吧?

第二题, 最简单的做法是右→左→左→左→…到底但这个方法在往上时要知道从哪里来的, 所以也有另外维护下一个元素所在指标的方式 (这可以在树有调整时一起调整)补充一点均摊分析的东西, 这种分析一般其实并不会真的去求各种状况的比例, 而是实际去看全部跑下来会有哪些操作常用技巧是利用某个虚拟 token 摆在结构中表示未来可能操作接着去证明每个地方只要某个数量的 token 的数目这样就代表不管状况怎样, 总操作数目不会超过一个已知数量从这个已知数量即可推得均摊的时间复杂度