Comment optimiser la réutilisation d'un grand std :: unordered_map en tant que temporaire dans une fonction fréquemment appelée?

Un moyen simple et efficace consiste à réutiliser le même conteneur et la même mémoire encore et encore avec un passage par référence comme suit. Dans cette méthode, vous pouvez éviter leur allocation de mémoire récursive std :: unordered_map :: reserve et std :: unordered_map :: ~ unordered_map qui ont tous deux la complexité O (num. of elemenrs):

void foo(std::vector<double>& vec)
{    
    int N = ...// set N here

    for(int i = 0; i<N; ++i)
    {
        // overwrite vec[0], ..., vec[N-1]
        vec[i] = i*0.1;
    }

    // do something and not access to vec[N], ..., vec[size-1] !            
}

Le côté appelant serait le suivant:

std::unordered_map<int,double> umap;
umap.reserve(size);

for(int i=0; i<50; ++i){
    foo(umap);
}

Mais puisque votre jeu de clés est toujours des entiers continus {1,2, ..., N} , je pense que std :: vector qui permet d'éviter les calculs de hachage serait plus préférable pour enregistrer les valeurs umap [0], ..., umap [N] :

void foo(std::unordered_map<int, double>& umap)
{        
    std::size_t N = ...// set N here

    for (int i = 0; i < N; ++i)
    {
        // overwrite umap[0], ..., umap[N-1]
        // If umap does not have key=i, then it is inserted.
        umap[i] = i*0.1;
    }

    // do something and not access to umap[N], ..., umap[size-1] !
}

Avez-vous essayé d'éviter toute allocation de mémoire en utilisant un simple tableau? Vous avez dit ci-dessus que vous connaissez la taille maximale de umap sur tous les appels à foo():

#include <iostream>
#include <unordered_map>
#include <time.h>

constexpr int size = 1000000;
double af[size];

void foo(int N) {
    // assert(N<=size);
    for (int i = 0; i < N; i++) {
        af[i] = i;
    }
    // ... af
}

int main() {    
    clock_t t = clock();

    for(int i = 0; i < 50; i++){
        foo(size /* or some other N<=size */);
    }

    t = clock() - t;
    printf ("%f s\n",((float)t)/CLOCKS_PER_SEC);

    return 0;
}

Comme je l'ai suggéré dans les commentaires, le hachage fermé serait mieux pour votre cas d'utilisation. Voici une carte de hachage fermée rapide et sale avec une taille de table de hachage fixe que vous pouvez expérimenter:

template<class Key, class T, size_t size = 1000003, class Hash = std::hash<Key>>
class closed_hash_map {
    typedef std::pair<const Key, T>                     value_type;
    typedef typename std::vector<value_type>::iterator  iterator;
    std::array<int, size>                               hashtable;
    std::vector<value_type>                             data;
 public:
    iterator begin() { return data.begin(); }
    iterator end() { return data.end(); }
    iterator find(const Key &k) {
        size_t h = Hash()(k) % size;
        while (hashtable[h]) {
            if (data[hashtable[h]-1].first == k)
                return data.begin() + (hashtable[h] - 1);
            if (++h == size) h = 0; }
        return data.end(); }
    std::pair<iterator, bool> insert(const value_type& obj) {
        size_t h = Hash()(obj.first) % size;
        while (hashtable[h]) {
            if (data[hashtable[h]-1].first == obj.first)
                return std::make_pair(data.begin() + (hashtable[h] - 1), false);
            if (++h == size) h = 0; }
        data.emplace_back(obj);
        hashtable[h] = data.size();
        return std::make_pair(data.end() - 1, true); }
    void clear() {
        data.clear();
        hashtable.fill(0); }
};

Elle peut être rendue plus flexible en redimensionnant dynamiquement la table de hachage à la demande le cas échéant, et plus efficace en utilisant robin- remplacement du capot.