Est-ce que cette utilisation de carte non ordonnée est efficace?

Question

Je veux en savoir plus sur les fonctions de mappage en c/C++ en général, il s'agit donc d'un programme de base sur le mappage non ordonné. J'utilise la cartographie non ordonnée parce que mes données d'entrée ne sont pas triées et j'ai lu que unordered_map est très efficace. Ici, j'ai un tableau avec lequel je crée la table de hachage et j'utilise la fonction lookup pour trouver si les éléments d'un autre tableau sont dans la table de hachage ou non. J'ai plusieurs questions concernant cette mise en œuvre:

#include <stdio.h> 
#include <unordered_map> 
using namespace std; 

typedef std::unordered_map<int,int> Mymap; 
int main() 
{ 
int x,z,l=0; 
int samplearray[5] = {0,6,4,3,8}; 
int testarray[10] = {6,3,8,67,78,54,64,74,22,77}; 

Mymap c1; 

for (x=0;x< sizeof(samplearray)/sizeof(int);x++) 
c1.insert(Mymap::value_type(samplearray[x], x)); 

for (z=0;z< sizeof(testarray)/sizeof(int);z++) 
if((c1.find(testarray[z]) != c1.end()) == true) 
    l++; 

printf("The number of elements equal are : %d\n",l); 
printf("the size of samplearray and testarray are : %d\t%d\n",sizeof(samplearray)/sizeof(int),sizeof(testarray)/sizeof(int)); 
} 

1. Tout d'abord, est-ce une bonne façon de mettre en œuvre? Je reçois les réponses à droite mais semble que j'utilise trop de pour la boucle.
2. Cela semble assez correct avec de très petites données mais si j'ai affaire à des fichiers de taille> 500MB cela semble que si je crée une table de hachage pour un fichier de 500MB, la taille de la table de hachage sera deux fois beaucoup qui est 1000MB. Est-ce toujours le cas?
3. Quelle est la différence entre la carte std :: non ordonnée et boost :: carte non ordonnée?

Enfin, une petite requête. Je suis nouveau en C/C++ donc si vous donnez des suggestions comme utiliser d'autres typedef/bibliothèques, j'apprécierais grandement si vous pouviez utiliser un petit exemple ou l'implémenter sur mon code. Merci

Answer 1

Vous commencez du mauvais pied. Un map (ordonné ou autrement) est destiné à stocker une clé ainsi que certaines données associées. Dans votre cas, vous n'enregistrez qu'un nombre (deux fois, à la fois la clé et les données). Pour cette situation, vous voulez un set (à nouveau, ordonné ou autrement) au lieu d'une carte.

Je voudrais aussi éviter au moins la première boucle for, et utiliser à la place std::copy:

// There are better ways to do this, but it'll work for now: 
#define end(array) ((array) + (sizeof(array)/sizeof(array[0])) 

std::copy(samplearray, 
      end(samplearray), 
      std::inserter(Myset)); 

Si vous ne besoin de compter le nombre d'éléments sont communs entre les deux ensembles, votre boucle est assez raisonnable. Si vous avez besoin/voulez réellement savoir quels éléments sont communs entre eux, vous voudrez peut-être envisager d'utiliser std::set_intersection:

std::set<int> myset, test_set, common; 

std::copy(samplearray, end(samplearray), std::inserter(myset)); 
std::copy(testarray, end(testarray), std::inserter(test_set)); 

std::set_intersection(myset.begin(), myset.end(), 
         test_set.begin(), test_set.end(), 
         std::inserter(common)); 

// show the common elements (including a count): 
std::cout <<common.size() << " common elements:\t"; 
std::copy(common.begin(), common.end(), 
      std::ostream_iterator<int>(std::cout, "\t"); 

Notez que vous n'avez pas besoin d'avoir une réelle set à utiliser set_intersection - tout ce que vous avez besoin est une collection triée d'éléments, donc si vous préférez, vous pouvez juste trier vos deux tableaux, puis utiliser directement set_intersection sur eux. De même, le résultat pourrait aller dans une autre collection (par exemple, un vector) si vous préférez.

Answer 2

Comme mentionné par Jerry, vous pouvez utiliser une boucle for pour la recherche si vous avez seulement besoin de connaître le nombre de correspondances. Si tel est le cas, je recommanderais d'utiliser un unordered_set puisque vous n'avez pas besoin des éléments à trier.