Является ли это использование неупорядоченной карты эффективным/правильным способом?

Question

Я хочу узнать о функциях отображения в c/C++ вообще, так что это базовая программа для неупорядоченного отображения. Я использую неупорядоченное сопоставление, потому что мои входные данные не отсортированы, и я читал, что unordered_map очень эффективен. Здесь у меня есть массив, с которым я создаю хеш-таблицу, и использую функцию lookup, чтобы определить, находятся ли элементы в другом массиве в хэш-таблице или нет. Я несколько вопросов относительно этой реализации:

#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. Прежде всего, это правильный способ реализовать? Я получаю ответы правильно, но кажется, что я использую слишком много для цикла.
2. Это кажется довольно хорошим с очень маленькими данными, но если я имею дело с файлами размером> 500 МБ, то это кажется, что если я создам хеш-таблицу для файла 500 МБ, тогда размер самой хэш-таблицы будет в два раза больше много, что составляет 1000 МБ. Это всегда так?
3. В чем разница между std :: неупорядоченной картой и boost :: неупорядоченной картой?

И наконец, небольшая просьба. Я новичок в C/C++, поэтому, если вы даете советы, подобные некоторым другим typedef/libraries, я был бы очень признателен, если бы вы могли использовать небольшой пример или реализовать его в своем коде. Спасибо

Answer 1

Вы начинаете с неправильной ноги. A map (заказанный или иным образом) предназначен для хранения ключа вместе с некоторыми связанными данными. В вашем случае вы только сохраняете номер (дважды, как ключ, так и данные). Для этой ситуации вы хотите получить set (опять же, заказанный или иным образом) вместо карты.

Я бы также избежать, по крайней мере первый for цикл, и использовать вместо 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)); 

Если вы только нужно подсчитать, сколько элементов являются общими между двумя наборами, ваш цикл является довольно разумно. Если вам нужно/хочу, чтобы действительно знать, какие элементы являются общими между ними, вы можете рассмотреть вопрос об использовании 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"); 

Обратите внимание, что вам не нужно иметь реальную set использовать set_intersection - все, что вам нужно это отсортированный набор элементов, поэтому, если вы предпочли бы, чтобы вы просто отсортировали ваши два массива, используйте для них непосредственно set_intersection. Аналогичным образом, если вы предпочитаете, результат может пойти в другой коллекции (например, vector).

Answer 2

Как упоминалось Джерри, вы можете использовать цикл for для поиска, если вам нужно знать только количество совпадений. Если это так, я бы рекомендовал использовать unordered_set, так как вам не нужны элементы для сортировки.