Использование кортежа в unordered_map
Я хочу использовать кортеж, состоящий из int,char,char в моем unordered_map, Я делаю так:
#include <string>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <tuple>
using namespace std;
tuple <int,char,char> kk;
unordered_map<kk,int> map;
int main()
{
map[1,"c","b"]=23;
return 0;
}
но это дает мне следующие ошибки:
map.cpp:9:21: error: type/value mismatch at argument 1 in template parameter list for ‘template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> class std::unordered_map’
map.cpp:9:21: error: expected a type, got ‘kk’
map.cpp:9:21: error: template argument 3 is invalid
map.cpp:9:21: error: template argument 4 is invalid
map.cpp:9:21: error: template argument 5 is invalid
map.cpp:9:26: error: invalid type in declaration before ‘;’ token
map.cpp: In function ‘int main()’:
map.cpp:14:16: error: assignment of read-only location ‘"b"[map]’
Что я делаю не так в этом?
8 ответов
Аргументы шаблона для unordered_map выглядят так:
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;
std::hash не специализируется на кортежах (прокрутите вниз до Стандартных специализаций для типов библиотек). Поэтому вам нужно предоставить свое, что-то вроде этого:
typedef std::tuple<int, char, char> key_t;
struct key_hash : public std::unary_function<key_t, std::size_t>
{
std::size_t operator()(const key_t& k) const
{
return std::get<0>(k) ^ std::get<1>(k) ^ std::get<2>(k);
}
};
// ..snip..
typedef std::unordered_map<const key_t,data,key_hash,key_equal> map_t;
// ^ this is our custom hash
И наконец, так как ответ Бенджамина Линдли уже адресован, нужно использовать std::make_tuple:
// d is data
m[std::make_tuple(1, 'a', 'b')] = d;
auto itr = m.find(std::make_tuple(1, 'a', 'b'));
Код был взят из раздела Использование std:: tuple в качестве ключа для std::unordered_map, и вот пример из жизни.
Первая ошибка:
map.cpp:9:21: error: expected a type, got ‘kk’
Как ясно говорит ошибка, параметр шаблона должен быть типом. kk это не тип, это объект. Возможно, вы хотели сделать это typedef?
typedef tuple <int,char,char> kk;
unordered_map<kk,int> map;
Вторая ошибка:
map[1,"c","b"]=23;
Здесь две проблемы. Во-первых, размещение запятых между значениями не делает их кортежем. Вы должны быть явными об этом, либо вызывая конструктор вашего типа кортежа, либо используя функцию, которая возвращает кортеж (например, std::make_tuple). Во-вторых, ваш кортеж ожидает символов ('c','b'), а не строки ("c","b").
map[std::make_tuple(1,'c','b')] = 23;
Как уже указывалось, std::hash не специализирован для кортежей. Однако, если ваш кортеж состоит из стандартных хешируемых типов, таких как string и int, следующий код из /questions/23354213/obschij-hesh-dlya-kortezhej-v-unorderedmap-unorderedset автоматически добавит такую поддержку в C++11.
Просто вставьте код в заголовочный файл и включайте его при необходимости:
#include <tuple>
// function has to live in the std namespace
// so that it is picked up by argument-dependent name lookup (ADL).
namespace std{
namespace
{
// Code from boost
// Reciprocal of the golden ratio helps spread entropy
// and handles duplicates.
// See Mike Seymour in magic-numbers-in-boosthash-combine:
// https://stackru.com/questions/4948780
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
// Recursive template code derived from Matthieu M.
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl
{
static void apply(size_t& seed, Tuple const& tuple)
{
HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
hash_combine(seed, get<Index>(tuple));
}
};
template <class Tuple>
struct HashValueImpl<Tuple,0>
{
static void apply(size_t& seed, Tuple const& tuple)
{
hash_combine(seed, get<0>(tuple));
}
};
}
template <typename ... TT>
struct hash<std::tuple<TT...>>
{
size_t
operator()(std::tuple<TT...> const& tt) const
{
size_t seed = 0;
HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
return seed;
}
};
}
У меня было требование карты вместо неупорядоченной карты:
ключ был 3-кортеж и
значение было 4-кортеж
видя все ответы я уже собирался переходить на пары
но ниже работал для меня:
// declare a map called map1
map <
tuple<short, short, short>,
tuple<short, short, short, short>
> map1;
// insert an element into map1
map1[make_tuple(1, 1, 1)] = make_tuple(0, 0, 1, 1);
// this also worked
map1[{1, 1, 1}] = { 0, 0, 1, 1 };
Я использую Visual Studio Community 2015 Ide
Для тех, кто использует boost они могут просто перенаправить хеширование для ускорения реализации, используя этот
#include "boost/functional/hash.hpp"
#include <string>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <tuple>
using Key = std::tuple<int, char, char>;
struct KeyHash {
std::size_t operator()(const Key & key) const
{
return boost::hash_value(key);
}
};
using Map = std::unordered_map<Key, int, KeyHash>;
int main()
{
Map map;
map[1,"c","b"] = 23;
return 0;
}
Использование std::integer_sequence может помочь:
struct hash_tuple {
template <std::size_t...Index>
size_t recursive_hash(const auto &x) const{
return (boost::get<Index>(x) ^ ... );
}
template <template <typename> class Ts,typename...Args>
size_t operator()(const Ts<Args...>& x) const{
return recursive_hash<std::make_integer_sequence<int,sizeof...(Args)>>(x);
}
};
using Map = std::unordered_map<Key, int, hash_tuple>;
Этот код универсален для всех кортежей, которые можно использовать в качестве ключей.
Прочитав несколько других сообщений, я пришел к этому. Он использует эффективный алгоритм комбинирования хешей и не специализируется наstdпространство имен. Вам нужно будет немного поработать, если вы хотите, чтобы этот код работал с любым кортежем хешируемых элементов в целом.
Это работает в C++11 и выше. В С ++03 вы можете использоватьboost::hash вместо того std::hash.
typedef tuple<int, char, char> MyTuple;
// define a hash function for this tuple
struct KeyHash : public std::unary_function<MyTuple, std::size_t> {
std::size_t operator()(const MyTuple& k) const {
// the magic operation below makes collisions less likely than just the standard XOR
std::size_t seed = std::hash<int>()(std::get<0>(k));
seed ^= std::hash<char>()(std::get<1>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed ^ (std::hash<char>()(std::get<2>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}
};
// define the comparison operator for this tuple
struct KeyEqual : public std::binary_function<MyTuple, MyTuple, bool> {
bool operator()(const MyTuple& v0, const MyTuple& v1) const {
return (std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1) &&
std::get<2>(v0) == std::get<2>(v1));
}
};
typedef unordered_map<MyTuple, int, KeyHash, KeyEqual> MyMap;
Вот метод для использования кортежа в качестве ключа для unordered_map без использования хеш-специализации:
#include <string>
#include <tuple>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
using namespace std;
string fToStr(unordered_map<double,int>& dToI,float x)
{
static int keyVal=0;
stringstream ss;
auto iter = dToI.find(x);
if(iter == dToI.end()) {
dToI[x]=++keyVal;
ss << keyVal;
} else {
ss << iter->second;
}
return ss.str();
}
typedef tuple<int,char,char> TICC;
const char ReservedChar=',';
string getKey(TICC& t)
{
stringstream ss;
ss << get<0>(t) << ReservedChar << get<1>(t) << ReservedChar << get<2>(t);
return ss.str();
}
int main()
{
unordered_map< string,TICC > tupleMp;
vector<TICC> ticc={make_tuple(1, 'a', 'b'),make_tuple(1, 'b', 'c'),make_tuple(2, 'a', 'b')};
for(auto t : ticc)
tupleMp[getKey(t)]=t;
for(auto t : ticc) {
string key = getKey(t);
auto val = tupleMp[key];
cout << "tupleMp[" << key << "]={" << get<0>(val) << "," << get<1>(val) << ","<< get<2>(val) << "} ";
}
cout << endl;
//for float tuple elements use a second float to int key map
unordered_map< double,int > dToI;
vector<float> v{1.234,1.234001,1.234001};
cout << "\nfloat keys: ";
for(float f : v)
cout << setprecision(7) << f << "=" << fToStr(dToI,f) << " ";
cout << endl;
return 0;
}
Выход:
tupleMp[1,a,b]={1,a,b} tupleMp[1,b,c]={1,b,c} tupleMp[2,a,b]={2,a,b}
float keys: 1.234=1 1.234001=2 1.234001=2