Реализация хэш-таблицы в C ++ - Как вернуть ключ с определенным значением

Question

Я пытаюсь решить вопрос программирования, используя Hash Tables в C ++.Предполагается, что это довольно простая реализация хеш-таблиц.Я чрезвычайно новичок в Hash Tables, и это моя первая попытка внедрения.

Вопрос в том, что мне дали массив, который содержит целые числа.Все, кроме одного целого числа, повторяются дважды.Я должен найти целое число, которого нет.

Input: {1,2,1,3,3}
Output: 2

Мое решение состоит в том, что я начну помещать эти ключи в хеш-таблицу, и если я заранее найду ключ в хеш-таблице, я удалю этот ключ из хеш-таблицы.

Моя реализация кода работает, но теперь я хотел посмотреть, как вернуть верное значение (в данном случае 2), поскольку даже после стирания ключа ключи остаются со значением 0.

Вот мой код:

int main()
{

    int num[5] = {1,2,1,3,3};

    map <int,int> mymap;

    for(int i=0;i<5;i++)
    {
      if(mymap.find(num[i])!=mymap.end())
        {  
          mymap.erase(num[i]);
        }
      else
        {
          mymap[num[i]] = 10; //10 is just a placeholder value. 
        }
    }
    cout<<"0:"<<mymap[0]<<endl;
    cout<<"1:"<<mymap[1]<<endl;
    cout<<"2:"<<mymap[2]<<endl;   //Should only find 10 value in 2
    cout<<"3:"<<mymap[3]<<endl;
    cout<<"4:"<<mymap[4]<<endl;
}

Вывод:

0:0
1:0
2:10
3:0
4:0

Answer 1

Просто увеличьте значение на карте, так как целые числа построены по умолчанию (и таким образом инициализированы как 0):

int num[5] = {1,2,1,3,3};

unordered_map <int,int> mymap;

for(int i=0;i<5;i++)
{
   ++mymap[num[i]];
}
cout<<"0:"<<mymap[0]<<endl;
cout<<"1:"<<mymap[1]<<endl;
cout<<"2:"<<mymap[2]<<endl;   //Should only find 10 value in 2
cout<<"3:"<<mymap[3]<<endl;
cout<<"4:"<<mymap[4]<<endl;

Answer 2

std::map - это дерево, а не хеш-таблица.Для хеш-таблицы вы хотите std::unordered_map.

Но чтобы ответить на ваш вопрос:

Вы можете использовать карту итератор , чтобы получить единственное оставшееся значение:

if (!mymap.empty()) {
    cout << mymap.begin()->first;
}

Но будьте осторожны - когда вы звоните cout << mymap[X], он также добавляет X к карте.Так что удалите все эти строки отладки в конце.

И, кстати, когда у вас нет значения, только ключ, вы можете использовать вместо него set (или unordered_set).