Вставка карты typedef в хеш-таблицу

Question

В программе ниже у меня есть typedef map.Что я хочу сделать, это реализовать хэш-таблицу.Я пытаюсь использовать unordered_map, так как я слышал, что это эффективно, так как это занимает O (1) время.Я использую свой typedef map везде в моей основной программе (другой программе, над которой я работаю), поэтому я не хочу это менять.Я хочу реализовать хеш-таблицу в одной из функций, и я пытаюсь выяснить, как вставить содержимое моей карты в хеш-таблицу и найти ключ позже.Я вставил комментарий в двух местах, где у меня проблемы.Пожалуйста, помогите.

#include <iostream>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>

using namespace std;

typedef vector<int> v_t;
typedef set<int> s_t;
typedef map<s_t, v_t> m_t;
typedef m_t::iterator m_it;
typedef std::unordered_map<s_t, v_t> Mymap;

int main(){
    m_t sample;
    for (int i = 0; i < 100; i = i+2) {
        v_t v;
        for(int k = 100 ; k<=105 ; ++k)
            v.push_back(k);
        s_t k;
        k.insert(i);
        sample.insert(sample.end(), make_pair(k, v));
    }

    //---------Debug--------------------
    for( m_it it(sample.begin()) ; it!=sample.end(); ++it) {
        cout << "Key: ";
        copy(it->first.begin(), it->first.end(), ostream_iterator<int>(cout, " "));
        cout << " => Value: ";
        copy (it->second.begin(),it->second.end(),ostream_iterator<double>(cout," "));
        cout << endl;
    }
    //---------------------------------

    Mymap c1;

    for( m_it it(sample.begin()) ; it!=sample.end(); ++it) {
        c1.insert(Mymap::value_type(it->first,it->second));   // how to do this ?
    }
    s_t s;
    s.insert(72);
    if(c1.find(s)!=c1.end())                                // does this work ?
        cout << "Success" << endl;
    return 0;
}

Я ценю любую помощь или комментарии.

После прочтения комментариев Джейсона я понимаю, почему я не могу использовать std::set в качестве ключа в unordered_map, поэтому я попыталсяиспользуйте std::string в качестве ключа, но функция find не будет работать.Не могли бы вы мне помочь.

Mymap c1;

for( m_it it(sample.begin()) ; it!=sample.end(); ++it) {
    v_t v1;
    std::string key;
    key.insert(key.begin(),it->first.begin(),it->first.end()); 
    copy(it->second.begin(), it->second.end(),std::back_inserter(v1));
    c1.insert(Mymap::value_type(std::make_pair(key,v1)));
}

string s = "72";
if((c1.find(s) != c1.end()) == true) 
    cout << "Success" << endl;
return 0;

Answer 1

Основной элемент, который вам не хватает для этой работы, - это определение функции хеширования для вашего std::set, который вы используете в качестве ключа. STL уже определяет равенство и лексикографический порядок для std::set, поэтому вы можете без проблем использовать его в качестве значения ключа в std::map как есть. Однако он не определяет хеш-функцию, так что это то, что вам нужно сделать, перегружая std :: hash. Это довольно просто и может быть сделано путем определения следующей функции:

namespace std
{
    template<>
    struct hash<std::set<int> > : public std::unary_function<std::set<int>, size_t>
    {
        size_t operator()(const std::set<int>& my_set) const
        {
           //insert hash algorithm that returns integral type
        }
    };
}

Приведенный выше объект функтора возвращает целочисленный тип size_t и принимает в качестве аргумента std::set. Вам нужно определить его внутри namespace std, чтобы std::unordered_map распознал его. «Легким» алгоритмом может быть просто суммирование элементов, поскольку у вас есть набор типа int. Существуют более сложные алгоритмы, которые уменьшают количество коллизий, которые такой простой алгоритм может создать за счет времени хеширования. Однако после того, как вы это определили, у вас не должно возникнуть проблем с вставкой значений ключей std::set в unordered_map, а также с созданием новых значений ключей и их нахождением в хеш-таблице.

Вы можете увидеть пример вашего исходного кода, работающего по адресу: http://ideone.com/DZ5jm

РЕДАКТИРОВАТЬ: Джейсон код размещены здесь для справки:

#include <iostream>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>

using namespace std;

namespace std
{
        template<>
        struct hash<set<int> > : public unary_function<set<int>, size_t>
        {
            size_t operator()(const std::set<int>& my_set) const
            {
               set<int>::iterator iter = my_set.begin();
               int total = 0;

               for (; iter != my_set.end(); iter++)
               {
                   total += *iter;
               }

               return total;
            }
        };
}



typedef vector<int> v_t;
typedef set<int> s_t;
typedef map<s_t, v_t> m_t;
typedef m_t::iterator m_it;
typedef std::unordered_map<s_t, v_t> Mymap;

int main(){

m_t sample;
for (int i = 0; i < 100; i = i+2) {
        v_t v;
        for(int k = 100 ; k<=105 ; ++k)
           v.push_back(k);
        s_t k;
        k.insert(i);
        sample.insert(sample.end(), make_pair(k, v));
    }

//---------Debug--------------------
for( m_it it(sample.begin()) ; it!=sample.end(); ++it) {
   cout << "Key: ";
   copy(it->first.begin(), it->first.end(), ostream_iterator<int>(cout, " "));
   cout << " => Value: ";
   copy (it->second.begin(),it->second.end(),ostream_iterator<double>(cout," "));
   cout << endl;
   }
//---------------------------------

Mymap c1;

for( m_it it(sample.begin()) ; it!=sample.end(); ++it) {
   c1.insert(Mymap::value_type(it->first,it->second));   // how to do this ?
   }
s_t s;
s.insert(72);
if(c1.find(s)!=c1.end())                                // does this work ?
   cout << "Success" << endl;
return 0;
}