Когда используется метод std:: multimap

В настоящее время я экспериментирую с некоторым использованием 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

Я не уверен, как интерпретировать эти результаты. Как бы вы определили правильную структуру данных? Существуют ли какие-либо дополнительные ограничения для деления, которые я, возможно, пропустил?

Ответы

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

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)