27

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

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

4

4 回答 4

31

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

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

于 2011-06-06T21:49:47.947 回答
8

很多时候，一棵红黑树。参见Dobb 博士的STL 的红黑树。

于 2011-06-06T21:48:12.723 回答
3

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

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

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

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

于 2014-09-26T15:51:54.727 回答
0

multimap 就像它的更简单版本一样，即 std::map，主要是使用红黑树构建的。C++ 标准本身并没有指定实现。但在大多数情况下（我亲自检查过 SGI STL）都使用红黑树。红黑树是高度平衡的树，因此对它们的获取/读取操作始终保证为 O(log(n)) 时间。但是，如果您想知道键的值是如何存储的。每个key->pair都保存为红黑树中的一个单独节点（即使同一个键可能会出现多次，就像'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) 插入是使用 operator< 完成的，因为第二个 'b' 不小于第一个插入的'b'，它被插入到'二叉树的右分支'。

我使用的编译器是 gcc-5.1 ( C++14)。

于 2015-11-17T13:49:32.477 回答