c++ - std::map 和摊销 O(log N) 的操作

Question

我有一个任务，我必须为在 std::map 之上实现的数据结构实现插入成员函数。该成员函数有 3 个参数：firstKey、secondKey、valToInsert。

分配指定不进行超过 2 次摊销 O(log N) 的操作，与 O(1) 形成对比，其中 N 是 map 中的元素数。

我编写了代码，它可以按应有的方式编译和工作。不过，我不确定这两个操作。

我无法展示整个代码（因为它是作业的一部分），所以我只会列出我使用的地图的成员函数。他们是：

• 一auto firtstIt = map.lower_bound(firstKey);
• 一auto secondtIt = map.lower_bound(secondKey);
• 一map.insert(secondIt, {secondKey, valToInsert});
• 一map.insert_or_assign(firstIt, firstKey, valToInsert);
• 一map.erase(std::next(firstKey), secondKey);
• 几个map.erase(it);“几个”取决于 firstIt 和 secondIt 之间的距离

我是否满足任务规定的条件？如果不是，为什么？

标签： c++algorithmdictionaryc++17