我目前正在尝试使用 STL 数据结构。但是我仍然不确定何时使用哪个以及何时使用某种组合。目前我试图弄清楚，当使用 std::multimap 确实有意义。据我所知，通过结合 std::map 和 std::vector 可以轻松构建自己的多 map 实现。所以我留下了一个问题，什么时候应该使用这些数据结构中的每一个。

• 简单性:std::multimap 使用起来肯定更简单，因为不必处理额外的嵌套。但是，作为批量访问一系列元素可能需要将数据从迭代器复制到另一个数据结构(例如 std::vector)。
• 速度: vector 的局部性很可能使在相等元素范围内的迭代速度更快，因为缓存的使用得到了优化。但是我猜 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

我不确定如何解释这些结果。您将如何决定正确的数据结构？是否有任何其他我可能遗漏的决定限制？

最佳答案

很难判断您的基准测试是否正确，因此我无法对数字发表评论。但是，有几点一般性:

• 为什么使用 multimap 而不是 vector 映射:映射、多重映射、集合和多重集合本质上都是相同的数据结构，一旦有了，它就是简单地拼出所有四个。所以第一个答案是，“为什么没有拥有它”？

• 它有什么用处: multimap 是你很少需要的东西之一，但是当你需要它们时，你真的需要它们。

• 为什么不推出我自己的解决方案？ 正如我所说，我不确定这些基准，但即使 if 你也可以做出其他的东西不比标准容器差(我对此提出质疑)，那么您应该考虑正确处理、测试和维护它的总体负担。想象一个世界，在这个世界中，您编写的每一行代码都会被征税(这是 Stepanov 的建议)。尽可能重复使用行业标准组件。

最后，这是迭代 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
  }
}

关于c++ - 什么时候使用 std::multimap 有意义，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8342445/