Quand est-ce que l'utilisation d'un std :: multimap est logique

Question

Je suis actuellement à l'essai sur un certain usage de la stl-structures de données. Cependant, je ne suis pas encore sûr à utiliser l'un et de l'utilisation d'une certaine combinaison. Actuellement, je suis à essayer de comprendre, lors de l'utilisation d'un std::multimap ne font sens. Aussi loin que je peux voir, on peut facilement construire votre propre multimap mise en œuvre en combinant std::map et std::vector. Donc, je suis parti avec la question lors de chacune de ces structures de données doit être utilisé.

• Simplicité: Un std::multimap est certainement plus simple à utiliser, parce que l'on n'a pas à gérer l'imbrication supplémentaire. Cependant, l'accès à une gamme d'éléments en vrac on pourrait avoir besoin de copier les données de la itérateurs à l'autre discbased (par exemple un std::vector).
• Vitesse: La localité de le vecteur le plus probable fait une itération sur la plage de l'égalité élément beaucoup plus rapide, parce que l'utilisation du cache est optimisé. Cependant, je devine que std::multimaps y a aussi beaucoup de l'optimisation des trucs derrière le dos pour faire une itération sur les éléments égaux aussi vite que possible. Pour passer à l'élément correct de gamme pourrait probablement être optimisé pour std::multimaps.

Pour essayer de la vitesse de questions, j'ai fait quelques comparaisons simples en utilisant le programme suivant:

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

Comme je le soupçonnais, il dépend essentiellement du rapport entre num_partitions et num_elements, je suis donc toujours à une perte ici. Voici quelques exemples de sorties:

Pour num_partitions = 100000 et 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

Pour num_partitions = 100000 et 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

Pour num_partitions = 100000 et 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

Pour num_partitions = 1000 et 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

Je ne suis pas certain sur la façon d'interpréter ces résultats. Comment feriez-vous pour décider de la bonne structure de données? Existe-il des contraintes supplémentaires pour la decission, dont j'ai peut-être raté?

Answer 1

Il est difficile de dire si votre référence est en train de faire la bonne chose, donc je ne peux pas commenter sur les nombres. Cependant, quelques points:

• Pourquoi multimap plutôt que de la carte de vecteurs: Cartes, multimaps, des décors et des multisets sont tous essentiellement la même structure de données, et une fois que vous en avez un, il est trivial de simplement énoncer tous les quatre. Donc, la première réponse est: "pourquoi ne pas l'avoir"?

• Comment est-il utile: Multimaps sont une de ces choses que vous avez besoin que rarement, mais quand vous en avez besoin, vous avez vraiment besoin d'eux.

• Pourquoi ne pas rouler ma propre solution? Comme je l'ai dit, je ne suis pas sûr au sujet de ces critères, mais même si vous pourriez faire quelque chose d'autre qui n'est pas pire que le conteneur standard (dont je doute), alors vous devriez considérer la charge globale de bien faire les choses, de le tester et de le maintenir. Imaginez un monde dans lequel vous être imposés pour chaque ligne de code que vous avez écrit (c'est Stepanov est une suggestion). La ré-utilisation de composants standard chaque fois que possible.

Enfin, voici la manière classique de vous réitérer un multimap:

for (auto it1 = m.cbegin(), it2 = it1, end = m.cend(); it1 != end; it1 = it2)
{
  // unique key values at this level
  for ( ; it2->first == it1->first; ++it2)
  {
    // equal key value (`== it1->first`) at this level
  }
}

Answer 2

Vous avez oublié une alternative très importante: pas toutes les séquences sont créés égaux.

Surtout, pourquoi un vector et pas un deque ou list ?

À l'aide de list

Un std::map<int, std::list<int> > doit effectuer à peu près équivalente à un std::multimap<int, int> depuis list est le nœud de base ainsi.

À l'aide de deque

Un deque est le conteneur par défaut à utiliser lorsque vous ne savez pas pour qui aller et n'ont aucune exigence particulière.

Quant à l' vector, vous du commerce, de quelques de la vitesse de lecture (pas beaucoup) pour accélérer push et pop des opérations.

À l'aide d'un deque au lieu de cela, et quelques optimisations évidentes, j'obtiens:

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)

Ou dans le "mauvais" cas:

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)

Ainsi, la lecture est toujours plus rapide, mais le remplissage est aussi beaucoup plus lent.

Answer 3

Une carte de vecteurs est livré avec la surcharge de la mémoire pour la capacité de chaque vecteur. std::vector généralement alloue de l'espace pour plus d'éléments que vous avez réellement. Il peut ne pas être une grosse affaire pour votre application, mais il est un autre compromis que vous n'avez pas considérés.

Si vous faites beaucoup de lectures, puis l'O(1) recherche du temps d' unordered_multimap pourrait être un meilleur choix.

Si vous avez un assez moderne compilateur (et compte tenu de la présence de l' auto mot-clé, vous n') puis en général, vous allez avoir un moment difficile de battre les conteneurs standards en termes de performances et de fiabilité. Les personnes qui les écrivent sont des experts. Je commence toujours avec le conteneur standard qui plus facilement exprime ce que vous voulez faire. Le profil de votre code tôt et le plus souvent, et si il ne tourne pas assez vite, puis chercher des moyens de l'améliorer (p. ex., à l'aide de l' unordered_ conteneurs, principalement lit).

Donc, pour répondre à votre question de départ, si vous avez besoin d'un tableau associatif des valeurs où ces valeurs ne sera pas unique, puis à l'aide de std::multimap fait vraiment bon sens.