何时使用std::multimap是有意义的？

Question

我目前正在尝试使用STL数据结构。然而，我仍然不确定何时使用哪种数据结构以及何时使用某种组合。目前，我正在尝试弄清楚，在什么情况下使用std::multimap是有意义的。据我所知，人们可以通过组合std::map和std::vector来轻松构建自己的multimap实现。因此，我想知道应该在什么情况下使用这些数据结构。

• 简单性：使用std::multimap肯定更简单，因为不需要处理额外的嵌套。但是，要将元素范围作为一个整体访问，可能需要将迭代器中的数据复制到另一个数据结构（例如std::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

我不确定如何解读这些结果。你是如何决定正确的数据结构的？是否还有其他决策的限制，我可能会错过了什么？

- LiKao

---

不要过早地进行优化。性能是一个问题吗？如果是，选择容器很可能不会成为瓶颈。 如果不是，那就使用更易理解和可维护的东西。 - KeatsPeeks

@Samuel_xL：同意避免过早优化，但正确选择容器可以让你走得更远。 - user405725

@Samuel_xL：目前在应用程序中使用了更复杂的嵌套数据结构解决方案。我主要想弄清楚是否有特定原因不应该触及它，还是可以用更简单的东西替换它。如果我可以自由选择，我也会选择std::multimap解决方案。 - LiKao

如果只需要插入一次但需要多次读取，可以考虑使用排序向量。这样可以消除“嵌套”，同时保持最大的缓存一致性。 - fjardon

我认为multimap更适合被描述为一个list的map而不是一个vector的map。 - CAFxX

Answer 1

很难确定你的基准测试是否正确，因此我不能对数字进行评论。然而，有一些普遍的观点：

• 为什么使用multimap而不是向量地图：映射、多映射、集和多集本质上都是相同的数据结构，一旦你有了其中一个，拼写出所有四个就很简单了。所以第一个答案是，“为什么不用它”？

• 它有什么用处：多重映射是那种你很少需要，但当你需要它们时，你确实需要它们。

• 为什么不自己打造解决方案？如我所说，我不确定这些基准测试，但即使你可以制作出不比标准容器差的其他东西（我对此表示怀疑），那么你也应该考虑到获得正确性、测试和维护的整体负担。想象一下这样一个世界，在这个世界里，你编写的每一行代码都要被征税（这是Stepanov的建议）。尽可能重用工业标准组件。

最后，这是迭代多映射的典型方式:

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
  }
}

- Kerrek SB

Answer 2

一个向量映射表会带来每个向量容量的内存开销。通常情况下，std::vector 会为更多的元素分配空间。这对你的应用程序可能不是什么大问题，但这是另一个你没有考虑到的权衡。

如果你需要进行大量的读取操作，那么 unordered_multimap 的 O(1) 查找时间可能是更好的选择。

如果你有一个相当现代的编译器（并且鉴于 auto 关键字的存在，你肯定有），那么通常情况下你很难在性能和可靠性方面超越标准容器。编写它们的人都是专家。我总是从最容易表达你要做的事情的标准容器开始。尽早、经常地对你的代码进行性能分析，如果它运行得不够快，那么就寻找改进它的方法（例如，在大多数情况下使用 unordered_ 容器）。

因此，回答你最初的问题，如果你需要一个值的关联数组，其中这些值不会是唯一的，那么使用 std::multimap 绝对是明智的选择。

- Michael Kristofik

---

是的，使用unordered_类型的容器很可能是最大的改进，因为我们几乎从不使用有序容器提供的排序。但是我不确定我们正在使用的STL版本是否提供了这些容器。 - LiKao

@LiKao，如果你的编译器支持的话，你可能会在std::tr1命名空间中找到它们。 - Michael Kristofik

谈论使用std::vector时的内存开销值得一提。 - Soumen

如果我们讨论内存开销，std::multimap 不是会为每个有 N 个值的键保存 N 个副本吗？我认为这可能会成为 std::multimap 在处理更大的键（例如字符串）时的一个麻烦。 - Michał Górny

向量的开销可能不会比在映射中拥有更多项的开销更糟糕，除非这些元素至少相当大。 - Francesco Dondi

Answer 3

你忘记了一个非常重要的选择：并非所有序列都是相同的。

特别是，为什么使用vector而不是deque或list？

使用list std::map<int, std::list<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)

因此，读取速度无条件更快，但填充速度也慢得多。

- Matthieu M.