std :: map <K, std :: vector <E>> распределение

Question

У меня есть сегменты, снабженные ключом K с элементами типа E. Изначально мы не знаем, что это за ключи K, поэтому мы не можем предварительно выделить с известными значениями K.Вы можете переместить произвольные элементы в начало корзины после их заполнения, что позволяет использовать список для контейнера.

template <typename K, typename E>
std::map< K, std::list<E> > buckets;

Каков наилучший способ вставить элементы в корзины?И K, и E, вероятно, будут на практике 32-битными целыми числами без знака.K должен иметь мощность менее 256 элементов.E может сотни миллионов, но все будет уникальным.

Answer 1

Наивное решение, просто вставив не конвертируя в список.

#include <map>
#include <random>
#include <unistd.h>
#include <vector>

int main() {
  size_t size = 100000000;
  size_t *arr = (size_t *)malloc(sizeof(size_t) * size);
  for (size_t i = 0; i < size; i++) {
    arr[i] = (size_t)rand() % 30;
  }
  system("/bin/date +%s%M");
  std::map<char, std::vector<size_t>> buckets;
  for (size_t i = 0; i < size; i++) {
    buckets[arr[i]].push_back(i);
  }
  system("/bin/date +%s%M");
  return 0;
}
/*
152996960333
152996960733
So about 400 milliseconds
*/