Вопрос по c++, c++11 – Ошибка Coror unordered_map при использовании с вектором в качестве ключа

12

Предыстория: Я пришёл из мира Java и довольно плохо знаком с C ++ или Qt.

Чтобы поиграть с unordered_map, я написал следующую простую программу:

<code>#include <QtCore/QCoreApplication>
#include <QtCore>
#include <iostream>
#include <stdio.h>
#include <string>
#include <unordered_map>

using std::string;
using std::cout;
using std::endl;
typedef std::vector<float> floatVector;

int main(int argc, char *argv[]) {
    QCoreApplication a(argc, argv);

    floatVector c(10);
    floatVector b(10);

    for (int i = 0; i < 10; i++) {
        c[i] = i + 1;
        b[i] = i * 2;
    }

    std::unordered_map<floatVector, int> map;

    map[b] = 135;
    map[c] = 40;
    map[c] = 32;

    std::cout << "b -> " << map[b] << std::endl;
    std::cout << "c -> " << map[c] << std::endl;
    std::cout << "Contains? -> " << map.size() << std::endl;

    return a.exec();
}
</code>

К сожалению, я сталкиваюсь с следующей ошибкой, которая не вдохновляет. Там нет даже номера строки.

:-1: error: collect2: ld returned 1 exit status

Есть идеи о происхождении проблемы?

Заранее спасибо.

Вам нужна хеш-функция, которая принимаетvector<float> Seth Carnegie
Правильный и интересный вопрос, но я не вижу варианта использования, в котором было бы разумно использовать список в качестве ключа на карте. UmNyobe
@SethCarnegie Это было то, что я думал, что проблема тоже наступала. Тем не менее, мне кажется, что класс, базовый как вектор, должен иметь хеш-функцию по умолчанию. Если это не так, не могли бы вы объяснить, как его предоставить, или указать на какой-нибудь материал? Спасибо! Pierre-Antoine
Это не сбой во время выполнения. R. Martinho Fernandes
@UmNyobe Int - это результат тяжелых вычислений, из которых вектор является входным. Полученный результат должен быть доступен многократно и быстро. Pierre-Antoine

Ваш Ответ

2   ответа
26

# 3..5, пункт 3, гласит:

Each unordered associative container is parameterized by Key, by a function object type Hash that meets the Hash requirements (17.6.3.4) and acts as a hash function for argument values of type Key, and by a binary predicate Pred that induces an equivalence relation on values of type Key.

С помощьюvector<float> какKey а не предоставление явных типов хеша и предикатов эквивалентности означает значение по умолчаниюstd::hash<vector<float>> а такжеstd::equal_to<vector<float>> будет использоваться.

std::equal_to для отношения эквивалентности хорошо, потому что есть оператор== для векторов, и вот чтоstd::equal_to использует.

Там, однако, нетstd::hash<vector<float>> специализация, и это, вероятно, то, что говорит нам ошибка компоновщика, которую вы не показывали. Вы должны предоставить свой собственный хэш для того, чтобы это работало.

Простой способ написать такой хеш-код - использоватьboost::hash_range:

template <typename Container> // we can make this generic for any container [1]
struct container_hash {
    std::size_t operator()(Container const& c) const {
        return boost::hash_range(c.begin(), c.end());
    }
};

Тогда вы можете использовать:

std::unordered_map<floatVector, int, container_hash<floaVector>> map;

Конечно, если вам нужна другая семантика равенства на карте, вам нужно соответствующим образом определить отношение хеша и эквивалентности.

1. However, avoid this for hashing unordered containers, as different orders will produce different hashes, and the order in unordered container is not guaranteed.

@Dilip Я думаю, что это значит, что вызовhash_range (unordered_container) это плохая идея, потому что она может давать разные результаты каждый раз.
@ user1162647: Это первая вещь на этой странице документа. ; -]
Большое спасибо, это действительно решило мою проблему. Примечание для людей, у которых возникла бы та же проблема: чтобы использовать boost :: hash_range, вам нужно #include & lt; boost / functions / hash.hpp & gt; Pierre-Antoine
@ hash3r Это потому, что карта использует красные и черные деревья на бэкэнде и не связана с типом хранимых данных. Принимая во внимание, что unordered_map по существу нуждается в хэш-функции. И он может быть рассчитан только после того, как будет определен тип данных, хранящихся в векторе.
но почему map & lt; vector & lt; int & gt ;, int & gt; Работа?
2

граммирования, поскольку в большинстве случаев вам приходится иметь дело с предоставленной IDE и вы не можете использовать внешнюю библиотеку, такую какboost, Вы можете использовать следующий метод, если хотите использовать лучшее из STL.

Как уже говорилось выше, вам просто нужно написать хеш-функцию. И он должен специализироваться на типе данных, хранящихся в вашем векторе. Следующая хеш-функция предполагаетint введите данные:

struct VectorHasher {
    int operator()(const vector<int> &V) const {
        int hash=0;
        for(int i=0;i<V.size();i++) {
            hash+=V[i]; // Can be anything
        }
        return hash;
    }
};

Обратите внимание, что вы можете использовать любой вид операции для генерации хеша. Вам просто нужно проявить творческий подход, чтобы столкновения были сведены к минимуму. Например,hash^=V[i], hash|=V[i], hash+=V[i]*V[i] или дажеhash+=(V[i]<<i)*(V[i]<<i)*(V[i]<<i) все они действительны до тех пор, пока ваш хэш не переполнится.

Наконец, чтобы использовать эту хэш-функцию с вашимunordered_map, инициализируйте его следующим образом:

unordered_map<vector<int>,bool,VectorHasher> hashMap;

Похожие вопросы