Использование unordered_map для массива пар - PullRequest
Новая
       8

Использование unordered_map для массива пар

1 голос
/ 24 марта 2012

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

int main() {
  std::tr1::unordered_map<double*, double*> cache;

  double x1[] = { 1.0, 3.14 };
  double x2[] = { 1.0, 3.14 };

  cache[x1] = x1;

  std::cout << "x1: " << cache.count(x1) << std::endl;
  std::cout << "x2: " << cache.count(x2) << std::endl;

  return 0;
}

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

> ./tmp
x1: 1
x2: 0

Когда я действительно хочу увидеть: 

> ./tmp
x1: 1
x2: 1

Довольно ясно, как создавать пользовательские функции хеширования и равенства, когда размер массивов фиксирован во время компиляции , но я не знаю, как создавать пользовательские функции, которые зависят от конкретного экземпляра ... Я создал класс ниже, но я не уверен, что он полезен или как его можно использовать. 

class Hash_double_vec {

public:
  int dim;
  Hash_double_vec(int d) { dim = d; }

  size_t operator()(const double *x) const{
    std::tr1::hash<double> hash_fn;
    size_t r = hash_fn(x[0]);
    for(int i=1;i<dim;i++) r ^= hash_fn(x[i]);
    return r;
  }

  bool operator()(const double *x, const double *y) const{
    for(int i=1;i<dim;i++) if (fabs(x[i]-y[i]) > 1e-10) return false;
    return true;
  }
};

1 Ответ

3 голосов
/ 24 марта 2012

Один из способов - создать структуру для хранения указателя на последовательность пар: 

struct DoubleRegion
{
    double* p;
    size_t size;
};

bool operator==(DoubleRegion a, DoubleRegion b)
{
    return a.size == b.size && memcmp(a.p, b.p, a.size) == 0;
}

size_t hash(DoubleRegion dr) 
{
    size_t h = 0;
    for (double* p = dr.p; p != dr.p + dr.size; ++p)
        h ^= hash(*p);
    return h;
}

А затем используйте его: 

unordered_map<DoubleRegion, DoubleRegion> cache;

Конечно, ваша проблема заключается в том, чтобы убедиться, что срок службы резервной памяти является расширенным набором времени жизни DoubleRegion.

Старый ответ :

Если до времени выполнения вы не знаете, насколько велики будут ключ и значение, используйте std :: vector: 

unordered_map<vector<double>, vector<double>> cache;

Если вы знаете во время компиляции, насколько велик вы можете использовать std :: array: 

unordered_map<array<double, N>, array<double, N>> cache;

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

...