bas*_*sav 5 c++ dictionary multimap data-structures
使用地图，我可以理解它被实现为二叉搜索树（例如红/黑树）及其时间复杂度。
但是对于多重映射，内部如何处理关键冲突？是否为所有具有相同键的节点维护了一个列表？或者进行一些其他处理。我遇到了一种情况，我可以使用 amap<int,vector<strings>>或 amultimap<int,string>并想知道权衡。
C++ 规范没有给出 的具体实现std::multimap，而是给出了操作std::multimap应该有多快以及对这些操作应该保持什么保证的要求。例如，insert在multimap需要插入键/值对进multimap，并在一定程度上使得它配有相同的密钥的所有现有条目后这样做。这必须在 O(log n) 时间内工作，并且特别是分摊 O(1)，如果插入发生时带有提示，并且提示是元素应该去的位置之前的位置。仅凭这些信息，就multimap可以通过拥有一个包含多个节点的红/黑树来工作，每个节点一个，或者它可以是一个存储一个红/黑树的红/黑树vector每个键的值。（不过，这排除了 AVL 树，因为 AVL 树插入中涉及的旋转不会在分摊 O(1) 时间内运行。但是，它也允许诸如 2-3-4 树或确定性跳过列表之类的东西）。
但是，随着我们添加更多要求，某些实现被排除在外。例如，erase如果为要擦除的元素提供迭代器，则操作需要在摊销常数时间内运行。这排除了使用具有键和vector值a 的单个节点，但不排除具有键和值的双向链接列表的单个节点。该iterator类型需要能够取消对 a 的引用value_type，它需要匹配底层allocator的value_type。这排除了在红/黑树中具有单个键和值的链接列表的单个节点的可能性，因为您无法以value_type这种方式获得对 a 的引用。
总的来说，限制是这样一种允许的实现是一个红/黑树，每个键/值对有一个节点，但其他的也是可能的。其他想法 - 例如使用 AVL 树，或将给定键的值合并为vectoror list- 是不可能的。
希望这可以帮助！