C ++: Справка по созданию unordered_map с пользовательским хешем / равенством - PullRequest
Новая
       25

C ++: Справка по созданию unordered_map с пользовательским хешем / равенством

2 голосов
/ 01 декабря 2011

Я пытаюсь создать std :: unordered_map, используя определяемую пользователем хэш-функцию и предикат равенства, для строк матрицы встроенных встроенных типов. Я использую std :: bind, так как мне нужны функторы хеширования и равенства для работы с переменными диапазонами. Как бы получить следующий код для компиляции и работы, как задумано? Я предполагаю, что моя ошибка в нижней части списка, где я использую std :: bind и создаю экземпляр std :: unordered_map.

Некоторые уточнения:

Я не могу использовать boost :: hash_combine, потому что я забочусь об отдельных битах в целых числах, хранящихся в строке матрицы, поэтому, если я не создам свой собственный итератор, boost :: hash_combine объединит целые числа, что приведет к ошибочным результатам. Кроме того, мне нужны функторы хеша и равенства для работы с диапазонами от 1 до ~ 200 000, поэтому указание диапазона в параметрах шаблона не будет разумным вариантом. 


template <class T,class F,class A>
struct row_hash_right : std::function<size_t(
        ublas::matrix_row<ublas::matrix<T,F,A>>,
        unsigned, unsigned)>
{
        typedef ublas::matrix_row<ublas::matrix<T,F,A>> row_type;

        // I want to use std::bind to bind the last two arguments.
        size_t operator()(row_type& a, unsigned s, unsigned e)
        {
                // Implementation of hash function.
        }
};

template <class T,class F,class A>
struct row_equal_right : std::function<bool(
        ublas::matrix_row<ublas::matrix<T,F,A>>,
        ublas::matrix_row<ublas::matrix<T,F,A>>,
        unsigned, unsigned)>
{
        typedef ublas::matrix_row<ublas::matrix<T,F,A>> row_type;

        bool operator()(row_type& a, row_type& b, unsigned s, unsigned e)
        {
                // Implementation of equality predicate.
        }
};

// Inside a function.
for (unsigned i = 0; i < len; ++i) {
        for (unsigned j = i + 1; j < len; ++j) {
                auto x = std::bind(r_hash, _1, i, j);
                auto y = std::bind(r_equal, _1, _2, i, j);
                // ERROR:
                std::unordered_map<row_type, unsigned,
                        decltype(x), decltype(y)> m(256, x, y);
        }
}

Ошибка:

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

/ usr / include / c ++ / 4.6 / bits / stl_pair.h: 92: 11: ошибка: ‘std :: pair <_T1, _T2> :: first ’имеет неполный тип /usr/include/boost/numeric/ublas/fwd.hpp:73:11: ошибка: объявление ‘const struct повышение :: числовыми :: ublas :: matrix_row, boost :: numeric :: ublas :: unbounded_array>>> ’

Если вы хотите увидеть все это, я выложил все это здесь: 

<code>
In file included from /usr/include/c++/4.6/bits/stl_algobase.h:65:0,
                 from /usr/include/c++/4.6/bits/char_traits.h:41,
                 from /usr/include/c++/4.6/ios:41,
                 from /usr/include/c++/4.6/ostream:40,
                 from /usr/include/c++/4.6/iostream:40,
                 from src/test/read_test.cpp:1:
/usr/include/c++/4.6/bits/stl_pair.h: In instantiation of ‘std::pair, boost::numeric::ublas::unbounded_array > > >, unsigned int>’:
/usr/include/c++/4.6/bits/stl_function.h:486:12:   instantiated from ‘std::_Select1st, boost::numeric::ublas::unbounded_array > > >, unsigned int> >’
/usr/include/c++/4.6/bits/hashtable_policy.h:789:20:   instantiated from ‘std::__detail::_Hash_code_base, boost::numeric::ublas::unbounded_array > > >, std::pair, boost::numeric::ublas::unbounded_array > > >, unsigned int>, std::_Select1st, boost::numeric::ublas::unbounded_array > > >, unsigned int> >, std::_Bind, boost::numeric::ublas::unbounded_array > >(std::_Placeholder, std::_Placeholder, unsigned int, unsigned int)>, std::_Bind, boost::numeric::ublas::unbounded_array > >(std::_Placeholder, unsigned int, unsigned int)>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>’
/usr/include/c++/4.6/bits/hashtable.h:105:11:   instantiated from ‘std::_Hashtable, boost::numeric::ublas::unbounded_array > > >, std::pair, boost::numeric::ublas::unbounded_array > > >, unsigned int>, std::allocator, boost::numeric::ublas::unbounded_array > > >, unsigned int> >, std::_Select1st, boost::numeric::ublas::unbounded_array > > >, unsigned int> >, std::_Bind, boost::numeric::ublas::unbounded_array > >(std::_Placeholder, std::_Placeholder, unsigned int, unsigned int)>, std::_Bind, boost::numeric::ublas::unbounded_array > >(std::_Placeholder, unsigned int, unsigned int)>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, false, false, true>’
/usr/include/c++/4.6/bits/unordered_map.h:44:11:   instantiated from ‘std::__unordered_map, boost::numeric::ublas::unbounded_array > > >, unsigned int, std::_Bind, boost::numeric::ublas::unbounded_array > >(std::_Placeholder, unsigned int, unsigned int)>, std::_Bind, boost::numeric::ublas::unbounded_array > >(std::_Placeholder, std::_Placeholder, unsigned int, unsigned int)>, std::allocator, boost::numeric::ublas::unbounded_array > > >, unsigned int> >, false>’
/usr/include/c++/4.6/bits/unordered_map.h:256:11:   instantiated from ‘std::unordered_map, boost::numeric::ublas::unbounded_array > > >, unsigned int, std::_Bind, boost::numeric::ublas::unbounded_array > >(std::_Placeholder, unsigned int, unsigned int)>, std::_Bind, boost::numeric::ublas::unbounded_array > >(std::_Placeholder, std::_Placeholder, unsigned int, unsigned int)>, std::allocator, boost::numeric::ublas::unbounded_array > > >, unsigned int> > >’
./sal/alg/ehh.hpp:144:31:   instantiated from ‘sal::ehh_results sal::compute_ehh(boost::numeric::ublas::matrix&, unsigned int) [with FloatType = double, T = unsigned int, F = boost::numeric::ublas::basic_row_major, A = boost::numeric::ublas::unbounded_array >]’
src/test/read_test.cpp:11:51:   instantiated from here
/usr/include/c++/4.6/bits/stl_pair.h:92:11: error: ‘std::pair::first’ has incomplete type
/usr/include/boost/numeric/ublas/fwd.hpp:73:11: error: declaration of ‘const struct boost::numeric::ublas::matrix_row, boost::numeric::ublas::unbounded_array > > >’

1 Ответ

1 голос
/ 01 декабря 2011

Если вы хотите хэшировать разные вещи, вам нужно что-то вроде hash_combine().Я обычно снимаю эту функцию с Boost (удивительно, она не была включена в стандарт!).Вот как я буду использовать это на std::array с, и я надеюсь, что вы можете манипулировать этим во что-то, что будет работать с строками матрицы: 

#include <array>

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{
    template<typename T, size_t N> struct hash<array<T, N>>
    {
        inline size_t operator()(const array<T, N> & a) const
        {
            size_t seed = 0;
            for (size_t i = 0; i != N; ++i)
            {
                ::hash_combine(seed, a[i]);
            }
            return seed;
        }
    };
}

(Приведенная выше специализация позволяет вам использовать std::unordered_set<std::array<int, 10>> и т. Д.)

Если строки матрицы не имеют предиката равенства, вы также можете добавить специализацию std::equal_to для строк матрицы.

...