C++ multimap 容器是如何实现的？

Question

例如，C++的向量是使用动态数组实现的，其中每个元素使用连续的内存空间。

我知道C++中的multimap是一对多的关系，但是它的内部结构是什么？

- user656925

Answer 1

C++标准未定义标准容器的实现方式，只规定了像向量这样的一些限制。

multimap具有某些运行时复杂度（对于有趣的操作为O(lg n)）和其他保证，并且可以作为红黑树来实现。这就是GNU标准C++库中实现它们的方式。

- Magnus Hoff

---

还有Dinkumware的STL，因此几乎所有商业C++编译器的标准库，包括VC。 - Simon Buchan

元素怎么样？假设键A有B、C、D、E。这些元素是可搜索的，还是作为树中的一个节点聚集在一起？ - user656925

@Chris：我还没有仔细考虑过，但我认为B、C、D和E可以被分成一个节点或者表示为单独的节点。不过，我不知道你所说的“可搜索”是什么意思。你可以遍历它们，但由于它们具有相同的键，你不能直接选择其中一个（通过值的任何属性）。multimap只提供按键查找的功能。 - Magnus Hoff

@Chris：最近我看了GCC的实现，发现相同键的元素在不同的节点中。虽然我认为其他实现也可以选择将它们集群在一起，但没有任何理由不这样做。 - Mike Seymour

实现一个返回键/值对引用的迭代器很棘手，除非每个节点都有自己的键。这也解释了lower_bound/upper_bound的存在。 - Mooing Duck

std::multimap<K,V> is semantically equivalent to a std::set <std::pair<K,V>>. The V values likely have a synthetic key comparator similar to std::unordered_map - Spencer

Answer 2

在IT技术中，经常会用到红黑树。例如，可以查看Dr. Dobb's网站上的STL的红黑树。

- Oliver Charlesworth

---

如果你更强调并解释了“非常频繁”，那么这个问题中的误解就可以得到纠正了！ - Lightness Races in Orbit

@Tomalak：不太明白你的意思？我不敢说“总是”（如果这是你的暗示），因为标准没有规定，而且我也不知道所有STL实现！ - Oliver Charlesworth

不是的，楼主似乎没有意识到这不是一个标准规定的事情。我只是觉得你的答案可以更好地解释这一点（就像Magnus的回答一样）。 :) （而且，咳咳，stdlib！） - Lightness Races in Orbit

好吧，尝试从听起来像雷神托尔的人那里抢风头可能大部分是毫无意义的 :P - Lightness Races in Orbit

Answer 3

除了“首选”答案外，由于SO不允许我评论：

给定一个具有值B、C、D的键，如果每个元素都有自己的节点，则迭代器的行为要容易实现得多。find()被定义为返回系列中的第一个结果，随后的迭代将穿过剩余的元素。multimap和map之间事实上的区别在于，multimap使用value_type的<进行排序，而map仅使用key_type的<进行排序

更正：C++11标准明确规定，新的（key，mapping）对将插入到具有相同key的任何现有值的末尾。这引发了一个我没有考虑过的问题：multimap是否可以包含两个节点，其中键和映射目标都相同。标准似乎没有明确表态，但值得注意的是，在映射类型上不需要比较运算符。如果编写测试程序，您会发现multimap可以将X映射到1、2、1。也就是说：“1”可以作为目标出现多次，而这两个实例将不被合并。对于某些算法来说，这是一个缺陷。

这篇来自Dr. Dobbs的文章谈到了常用的基础rb-tree实现。需要注意的主要点是，重新平衡操作实际上根本不关心键，这就是为什么可以构建一个支持重复键的rb-tree。

- Jonathan S. Shapiro

Answer 4

多重映射（multimap）就像它的简化版本std::map一样，主要是使用红黑树进行构建。C++标准本身并没有指定实现方式。但在大多数情况下（我个人检查了SGI STL），都使用红黑树。红黑树是高度平衡的树，因此对它们的获取/读取操作始终保证为O(log(n))时间。但是，如果您想知道如何存储键的值，则每个键-值对都保存在红黑树中的单独节点中（即使同一个键可能会多次出现，就像下面的键' b '的情况）。键用于查找/搜索rb-tree。一旦找到键，就会返回存储在节点中的值。

  std::multimap<char,int> mmp;

  mmp.insert(std::pair<char,int>('a',10));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('b',10));
  mmp.insert(std::pair<char,int>('b',15));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('c',25));
  mmp.insert(std::pair<char,int>('a',15));
  mmp.insert(std::pair<char,int>('a',7));


for (std::multimap<char,int>::iterator it=mmp.begin(); it!=mmp.end(); ++it){

    std::cout << (*it).first << " => "  << (*it).second << " . Address of (*it).second = " << &((*it).second) << '\n';
}

输出：

a => 10 . Address of (*it).second = 0x96cca24
a => 15 . Address of (*it).second = 0x96ccae4
a => 7 . Address of (*it).second = 0x96ccb04
b => 20 . Address of (*it).second = 0x96cca44
b => 10 . Address of (*it).second = 0x96cca64
b => 15 . Address of (*it).second = 0x96cca84
b => 20 . Address of (*it).second = 0x96ccaa4
c => 25 . Address of (*it).second = 0x96ccac4

起初我认为像'b'这样的单个键的值可能存储在std::vector中。

template <class K, class V>
struct Node {
  K key;
  std::vector<V> values; 
  struct Node* left;
  struct Node* right;
}

但后来我意识到这将违反O(log(n))的保证获取时间。此外，打印值的地址确认具有相同键的值不是连续的。

使用operator<插入键，因此具有相同键的值按照插入顺序存储。

因此，如果我们首先插入(key = 'b'，value = 20)，然后插入(key = 'b'，value = 10)。由于第二个'b'不小于第一个插入的'b'，所以它被插入到“二叉树的右分支”中。

我使用的编译器是gcc-5.1（C++14）。

- avi007

---

请阅读得到赞同的答案，它们实际上是正确的。自从4年前以来，它们也提到（由GNU）libstdc++和其他一些实际上使用RB树。 - Deduplicator

即使我也说了同样的话！RB树是红黑树。但OP提出的更微妙的问题是，相同键的值如何存储在rb树中，以及尽管两者都使用RB-Tree，但map和multimap的实现区别。我试图解释它。请仔细阅读答案。谢谢。 - avi007

重点是红黑树只是众多可能性之一。另外，即使使用了红黑树并且有一个额外的插入顺序字段，您的结构也可能不正确，因为键值对保存在std::pair中。而使用时间戳并不是一个好主意，序列号的开销较小，通常效果更好。 - Deduplicator

vector 的问题不在于获取时间（如果所有键都相等，那么您无法保持这一点），而是迭代器失效规则与 std::map 不兼容。它必须是一个列表。但是，它必须是一个 list<std::multimap<K,V>::value_type>，以便解引用迭代器产生正确的类型。然后，您的 multimap 迭代器需要指向节点和列表条目的指针，或者每个列表条目需要指向其节点的指针，以便能够超越节点。总的来说，不将每个条目存储在自己的节点中似乎相当麻烦。 - Brandlingo