Kiedy używanie std:: multimap ma sens

Obecnie eksperymentuję nad wykorzystaniem stl-datastructures. Jednak nadal nie jestem pewien, kiedy użyć którego i kiedy użyć określonej kombinacji. Obecnie próbuję się dowiedzieć, czy użycie std::multimap ma sens. Z tego, co widzę, można łatwo zbudować własną implementację multimap poprzez połączenie std::map i std::vector. Pozostaje mi więc pytanie, Kiedy należy użyć każdej z tych struktur danych.

• Simplicity: a STD:: multimap jest zdecydowanie prostszy do użyj, ponieważ nie trzeba obsługiwać dodatkowego zagnieżdżania. Jednak dostęp do szeregu elementów jako luzem może być konieczne skopiowanie danych z iteratorów do innej struktury danych (na przykład std::vector).
• prędkość: położenie wektora najprawdopodobniej sprawia, że iteracja w zakresie równego elementu jest znacznie szybsza, ponieważ użycie pamięci podręcznej jest zoptymalizowane. Jednak domyślam się, że std::multimaps mają również wiele trików optymalizacyjnych za plecami, aby iterację nad równymi elementami jako jak najszybciej. Również dotarcie do właściwego zakresu elementów może być zoptymalizowane dla std::multimaps.

Aby wypróbować problemy z prędkością zrobiłem kilka prostych porównań za pomocą następującego programu:

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

Jak podejrzewałem zależy to głównie od stosunku między num_partitions i num_elements , więc nadal jestem w stratach tutaj. Oto kilka przykładowych wyjść:

Dla num_partitions = 100000 i 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

Dla num_partitions = 100000 i 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

Dla num_partitions = 100000 i 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

Dla num_partitions = 1000 i 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