C++ 怎么样？实现了多重映射容器吗？

Question

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

我知道 C++ 多重映射是一对多关系，但内部结构是什么？

Answer 1

C++ 标准没有定义标准容器应该如何实现，它只给出了某些约束，就像你所说的向量一样。

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

Answer 2

通常，红黑树。请参见 Dobb 博士的 STL 红黑树。

Answer 3

除了“首选”答案之外，因为 SO 不允许我发表评论：

给定一个值为 B、C、D 的键，如果每个元素都有自己的节点，则迭代器的行为会更容易实现。 Find() 定义为返回系列中的第一个结果，后续迭代将带您遍历其余元素。映射和多重映射之间事实上的区别是多重映射使用排序。在整个 value_type 上，其中映射使用 <仅针对 key_type

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

Dobbs 博士的这篇文章讨论了底层的 rb-tree常用的实现。需要注意的要点是，重新平衡操作实际上根本不关心键，这就是为什么您可以构建一个允许重复键的 rb 树。

Answer 4

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

  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)) 的保证获取时间。此外，打印出值的地址可以确认具有公共键的值不是连续的。

它们的键是使用运算符<插入的，因此具有相同键的值按照插入的顺序存储。

所以如果我们先插入
（键 = 'b'，值 = 20）
进而
（键 = 'b'，值 = 10）
插入是使用operator< 完成的。 ，由于第二个“b”不小于第一个插入的“b”，因此它被插入“二叉树的右分支”。

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