可能重复：
如何实现 C++ 多图？
多图通常实现为二叉搜索树。
但是它们典型的内部表示是什么？是像std::map<Key, std::list<Value> >还是类似？我担心的是在一组具有相同键的元素上插入和迭代的复杂性。
问问题
1045 次
1 回答
1
如果您想了解特定操作的复杂性，您只需查看标准即可。该标准对复杂性有保证，但实现可以自由地以任何他们希望的方式满足这些保证。
对于插入，复杂性是O(lg n)，除非您每次都指定最佳提示，在这种情况下，复杂性会被O(1)摊销。（在此处查看详细信息：http: //en.cppreference.com/w/cpp/container/multimap/insert）
对于具有相同键的一组元素的迭代，复杂性与从任何迭代器到另一个迭代器的迭代相同。鉴于您已经找到了迭代器，迭代与您正在迭代的项目数呈线性关系。（抱歉，目前无法找到此参考）
于 2013-01-29T12:17:13.287 回答