例如,C++的向量是使用动态数组实现的,其中每个元素使用连续的内存空间。
我知道C++中的multimap是一对多的关系,但是它的内部结构是什么?
我知道C++中的multimap是一对多的关系,但是它的内部结构是什么?
C++标准未定义标准容器的实现方式,只规定了像向量这样的一些限制。
multimap具有某些运行时复杂度(对于有趣的操作为O(lg n))和其他保证,并且可以作为红黑树来实现。这就是GNU标准C++库中实现它们的方式。
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)。
std::pair
中。而使用时间戳并不是一个好主意,序列号的开销较小,通常效果更好。 - Deduplicatorvector
的问题不在于获取时间(如果所有键都相等,那么您无法保持这一点),而是迭代器失效规则与 std::map
不兼容。它必须是一个列表。但是,它必须是一个 list<std::multimap<K,V>::value_type>
,以便解引用迭代器产生正确的类型。然后,您的 multimap 迭代器需要指向节点和列表条目的指针,或者每个列表条目需要指向其节点的指针,以便能够超越节点。总的来说,不将每个条目存储在自己的节点中似乎相当麻烦。 - Brandlingo
std::multimap<K,V>
is semantically equivalent to astd::set <std::pair<K,V>>
. The V values likely have a synthetic key comparator similar tostd::unordered_map
- Spencer