Отображение чисел в другой диапазон

Question

По одному приходят числа из диапазона [0; N], при этом из приходящих чисел M различных, M << N. Как отобразить текущее пришедшее число в уникальное число из диапазона [0; M-1]?

По сути нужен хеш, уникально отображающий набор чисел в диапазон длины, равной количеству уникальных чисел в наборе.

Относительный порядок не важен, важно взаимно однозначное соответствие между M различных чисел и [0; M-1], т.е. 0 не обязательно должен отображаться в 0 из диапазона, но обязательно в какое-то одно уникальное число.

Answer 1

Вариант решения данной проблемы со словарем:

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

using Dict = unordered_map<size_t, size_t>;

class CoDec
{
    Dict dict;
public:
    size_t code(const size_t in)
    {
        //ищем в словаре
        const auto pos = dict.find(in);
        if(pos==dict.end())
        {
            //если не нашли, пополняем словарь
            //присваиваем новый код, равный прошлой длине словаря;
            const size_t cnt=dict.size();
            return dict[in] = cnt;
        }            
        return pos->second; //если нашли, просто выдаем словарное значение
    }
    size_t decode(const size_t in) const
    {
        //выдаем из словаря нужное значение по коду
        return find_if(dict.cbegin(), dict.cend(), [&in](const Dict::value_type& a)
        {
            return in == a.second;
        })->first;
    }
};

int main() 
{
    CoDec cdc;
    cout << cdc.code(2)  <<' '<< cdc.code(5)   <<' '<< cdc.code(8)  <<' '<< cdc.code(5)  << endl ;
    cout << cdc.decode(0)<<' '<< cdc.decode(1) <<' '<< cdc.decode(2)<<' '<< cdc.decode(1)<< endl;
    return 0;
}

Ideone

БЛОГ НА HUSL

Отображение чисел в другой диапазон

Ответы (1 шт):