什么时候使用std :: multimap是有意义的
我目前正在尝试使用stl-datastructures。 但是，我仍然不确定何时使用哪一个，何时使用某个组合。 目前我想弄清楚，当使用std::multimap确实有道理。 就我所见，通过组合std::map和std::vector ，可以轻松地构build自己的multimap实现。 所以我留下了这些数据结构应该被使用的问题。
- 简单性：std :: multimap使用起来更简单，因为不需要处理额外的嵌套。 但是，作为批量元素访问一系列元素可能需要将数据从迭代器复制到另一个数据结构（例如
std::vector）。 - 速度：vector的局部性最有可能使迭代在相等元素的范围上更快，因为caching使用被优化。 不过，我猜测，
std::multimaps也有很多优化技巧背后，尽可能快地迭代相同的元素。 同样，正确的元素范围可能会被优化为std::multimaps。
为了尝试速度问题，我使用下面的程序做了一些简单的比较：
#include <stdint.h> #include <iostream> #include <map> #include <vector> #include <utility> typedef std::map<uint32_t, std::vector<uint64_t> > my_mumap_t; const uint32_t num_partitions = 100000; const size_t num_elements = 500000; int main() { srand( 1337 ); std::vector<std::pair<uint32_t,uint64_t>> values; for( size_t i = 0; i <= num_elements; ++i ) { uint32_t key = rand() % num_partitions; uint64_t value = rand(); values.push_back( std::make_pair( key, value ) ); } clock_t start; clock_t stop; { start = clock(); std::multimap< uint32_t, uint64_t > mumap; for( auto iter = values.begin(); iter != values.end(); ++iter ) { mumap.insert( *iter ); } stop = clock(); std::cout << "Filling std::multimap: " << stop - start << " ticks" << std::endl; std::vector<uint64_t> sums; start = clock(); for( uint32_t i = 0; i <= num_partitions; ++i ) { uint64_t sum = 0; auto range = mumap.equal_range( i ); for( auto iter = range.first; iter != range.second; ++iter ) { sum += iter->second; } sums.push_back( sum ); } stop = clock(); std::cout << "Reading std::multimap: " << stop - start << " ticks" << std::endl; } { start = clock(); my_mumap_t mumap; for( auto iter = values.begin(); iter != values.end(); ++iter ) { mumap[ iter->first ].push_back( iter->second ); } stop = clock(); std::cout << "Filling my_mumap_t: " << stop - start << " ticks" << std::endl; std::vector<uint64_t> sums; start = clock(); for( uint32_t i = 0; i <= num_partitions; ++i ) { uint64_t sum = 0; auto range = std::make_pair( mumap[i].begin(), mumap[i].end() ); for( auto iter = range.first; iter != range.second; ++iter ) { sum += *iter; } sums.push_back( sum ); } stop = clock(); std::cout << "Reading my_mumap_t: " << stop - start << " ticks" << std::endl; } }
据我猜测，这主要取决于num_partitions和num_elements之间的比例，所以我在这里仍然处于亏损状态。 以下是一些示例输出：
对于num_partitions = 100000和num_elements = 1000000
Filling std::multimap: 1440000 ticks Reading std::multimap: 230000 ticks Filling my_mumap_t: 1500000 ticks Reading my_mumap_t: 170000 ticks
对于num_partitions = 100000和num_elements = 500000
Filling std::multimap: 580000 ticks Reading std::multimap: 150000 ticks Filling my_mumap_t: 770000 ticks Reading my_mumap_t: 140000 ticks
对于num_partitions = 100000和num_elements = 200000
Filling std::multimap: 180000 ticks Reading std::multimap: 90000 ticks Filling my_mumap_t: 290000 ticks Reading my_mumap_t: 130000 ticks
对于num_partitions = 1000和num_elements = 1000000
Filling std::multimap: 970000 ticks Reading std::multimap: 150000 ticks Filling my_mumap_t: 710000 ticks Reading my_mumap_t: 10000 ticks
我不确定如何解释这些结果。 你将如何去决定正确的数据结构？ 是否有任何额外的约束，这可能是我错过了？
很难判断你的基准是否正确，所以我不能评论这个数字。 但是，一些一般的观点：
-
为什么使用多图而不是vector地图：地图，多地图，集合和多重数据都是基本相同的数据结构，一旦你有了它，只需拼出所有四个数据就很简单。 所以第一个答案是，“为什么不拥有它”？
-
它有什么用处 ：Multimaps是你很less需要的东西之一，但是当你需要时，你真的需要它们。
-
为什么不推出自己的解决scheme？ 正如我所说，我不确定这些基准，但即使你可以做一些不比标准容器（我质疑）更糟糕的东西，那么你应该考虑把它做好的总体负担，testing它并维护它。 设想一个世界，你会为你写的每一行代码征税 （这是斯捷潘诺夫的build议）。 尽可能重用行业标准组件。
最后，这里是迭代multimap的典型方法：
for (auto it1 = m.cbegin(), it2 = it1, end = m.cend(); it1 != end; it1 = it2) { // unique key values at this level for ( ; it2 != end && it2->first == it1->first; ++it2) { // equal key value (`== it1->first`) at this level } }
你忘记了一个非常重要的select：并不是所有的序列都是平等的。
特别是，为什么一个vector而不是一个deque或list ？
使用list
std::map<int, std::list<int> >应该执行与std::multimap<int, int>大致等价std::multimap<int, int>因为list也是基于节点的。
使用deque
deque是当你不知道要去哪里并且没有任何特殊要求时使用的默认容器。
就vector ，为了更快的push和pop操作，您会增加一些读取速度（不是太多）。
使用一个deque代替，并且有一些明显的优化 ，我得到：
const uint32_t num_partitions = 100000; const size_t num_elements = 500000; Filling std::multimap: 360000 ticks Filling MyMumap: 530000 ticks Reading std::multimap: 70000 ticks (0) Reading MyMumap: 30000 ticks (0)
或者在“不好”的情况下：
const uint32_t num_partitions = 100000; const size_t num_elements = 200000; Filling std::multimap: 100000 ticks Filling MyMumap: 240000 ticks Reading std::multimap: 30000 ticks (0) Reading MyMumap: 10000 ticks (0)
因此，阅读是无条件的更快，但填补也是较慢。
vector图随着每个vector的容量而带有内存开销。 std::vector通常会为实际拥有的元素分配更多的空间。 这对你的应用程序来说可能不是什么大不了的事情，但这是你没有考虑过的另一个折衷。
如果你正在做大量的读操作，那么unordered_multimap的O（1）查找时间可能是更好的select。
如果你有一个合理的现代编译器（并且有auto关键字的话），那么一般来说，就性能和可靠性而言，你将很难打败标准容器。 写他们的人是专家。 我总是从容易expression你想要做的标准容器开始。 提前对代码进行简档分析，如果运行速度不够快，则寻找改进方法（例如，在大部分读取时使用unordered_容器）。
所以，要回答你原来的问题，如果你需要一个值的关联数组，那么值不会是唯一的，那么使用std::multimap肯定是有道理的。
