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

Question

我目前正在尝试使用stl-datastructures.但是我仍然不确定何时使用哪一个以及何时使用某种组合.目前我想弄清楚,当使用时std::multimap确实有意义.据我所知,通过组合std::map和,可以轻松地构建自己的多图实现std::vector.所以当我们应该使用每个数据结构时,我都会遇到问题.

• 简单性:std :: multimap肯定更易于使用,因为不需要处理额外的嵌套.但是,作为批量元素访问一系列元素可能需要将数据从迭代器复制到另一个数据结构(例如a 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

我不确定如何解释这些结果.您将如何决定正确的数据结构？对于我可能错过的决定还有其他限制吗？

Answer 1

很难说你的基准测试是否正确,所以我无法评论数字.但是,一些一般要点:

• 为什么multimap而不是矢量地图:地图,多图,集合和多重集合都是基本相同的数据结构,一旦你有了一个,只需拼出所有四个就很简单.所以第一个答案是"为什么不拥有它"？

• 它是如何有用的:Multimaps是你很少需要的东西之一,但是当你需要它们时,你真的需要它们.

• 为什么不推出自己的解决方案？正如我说的,我不知道这些基准,但即使如果你可以做别的,不低于标准集装箱(我怀疑)糟糕,那么你应该考虑得到正确的总体负担,测试它并保持它.想象一个世界,在这个世界里你会为你写的每一行代码征税(这就是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
  }
}

Answer 2

你忘记了一个非常重要的选择:并非所有序列都是平等的.

特别是,为什么一个vector而不是一个deque或一个list？

运用 list

A std::map<int, std::list<int> >应该大致相当于a,std::multimap<int, int>因为list也是基于节点.

运用 deque

A 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)

因此读取无条件地更快,但填充也慢.

Answer 3

向量图带有每个向量容量的内存开销. std::vector通常为更多元素分配空间,而不是实际拥有的元素.对你的应用程序来说这可能不是什么大问题,但这是你没有考虑的另一个权衡.

如果您正在进行大量读取,那么O(1)查找时间unordered_multimap可能是更好的选择.

如果你有一个相当现代的编译器(并且考虑到auto关键字的存在),那么一般来说,你将很难在性能和可靠性方面击败标准容器.写这些的人都是专家.我总是从最容易表达你想做的标准容器开始.及早和经常地编写代码,如果它的运行速度不够快,那么就寻找改进它的方法(例如,unordered_在进行大多数读操作时使用容器).

因此,要回答您的原始问题,如果您需要一个值的关联数组,其中这些值不是唯一的,那么使用std::multimap肯定是有意义的.