有在C++哈希表

Question

複合鍵我有一個數據結構，它具有，

<Book title>, <Author>, and <rate> 

由於書名或作者可以被複制，我想建立一個複合鍵。 （比方說，我不能讓額外的唯一關鍵，如ID）

由於數據是相當巨大的，我使用的GCC unordered_map速度， 着想，我建我的結構是這樣的：

typedef pair<string, string> keys_t 
typedef unordered_map<keys_t, double> map_t; 

一般情況下，一切正常， 但是，當我想引用一個特定的鍵時，問題發生。例如，假設我想找到名爲「數學」的書籍中得分最高的書籍，或者我想找到「托爾斯泰」書籍的平均費率。
在這種情況下，這變得非常麻煩，因爲我不僅可以只引用密鑰對中的一個。

我碰巧找到boost::multi_index但我在理解文檔時遇到了一些麻煩。 有沒有人有一些想法或指導呢？

解決方案使多個索引，multi_index簡單的例子，任何其他方法等..任何幫助將不勝感激。

謝謝。

Answer 1

我想通了如何使用boost::multi_index 我提到這個代碼：Boost multi_index composite keys using MEM_FUN

這裏是我的代碼供您參考。

#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/mem_fun.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/composite_key.hpp> 
#include <boost/multi_index/member.hpp> 
#include <iostream> 
#include <string> 

using namespace boost::multi_index; 
using namespace std; 

class Book { 
public: 
    Book(const string &lang1, const string &lang2, const double &value) : m_lang1(lang1) , m_lang2(lang2) , m_value(value) {} 

    friend std::ostream& operator << (ostream& os,const Book& n) { 
     os << n.m_lang1 << " " << n.m_lang2 << " " << n.m_value << endl; 
     return os; 
    } 

    const string &lang1() const { return m_lang1; } 
    const string &lang2() const { return m_lang2; } 
    const double &value() const { return m_value; } 
private: 
    string m_lang1, m_lang2; 
    double m_value; 
}; 

// These will be Tag names 
struct lang1 {}; 
struct lang2 {}; 
struct value {}; 

typedef multi_index_container < 
    Book, 
    indexed_by< 
     ordered_non_unique<tag<lang1>, BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang1) 
     >, 
     ordered_non_unique<tag<lang2>, BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang2) 
     >, 
     ordered_non_unique<tag<value>, BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const double &, value), greater<double> 
     >, 
     ordered_unique< 
      // make as a composite key with Title and Author 
      composite_key< 
       Book, 
       BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang1), 
       BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang2) 
      > 
     > 
    > 
> Book_set; 

// Indices for iterators 
typedef Book_set::index<lang1>::type Book_set_by_lang1; 
typedef Book_set::index<lang2>::type Book_set_by_lang2; 
typedef Book_set::index<value>::type Book_set_by_value; 

int main() { 

    Book_set books; 
    books.insert(Book("Math", "shawn", 4.3)); 
    books.insert(Book("Math", "john", 4.2)); 
    books.insert(Book("Math2", "abel", 3.8)); 
    books.insert(Book("Novel1", "Tolstoy", 5.0)); 
    books.insert(Book("Novel1", "Tolstoy", 4.8)); // This will not be inserted(duplicated) 
    books.insert(Book("Novel2", "Tolstoy", 4.2)); 
    books.insert(Book("Novel3", "Tolstoy", 4.4)); 
    books.insert(Book("Math", "abel", 2.5)); 
    books.insert(Book("Math2", "Tolstoy", 3.0)); 

    cout << "SORTED BY TITLE" << endl; 
    for (Book_set_by_lang1::iterator itf = books.get<lang1>().begin(); itf != books.get<lang1>().end(); ++itf) 
     cout << *itf; 

    cout << endl<<"SORTED BY AUTHOR" << endl; 
    for (Book_set_by_lang2::iterator itm = books.get<lang2>().begin(); itm != books.get<lang2>().end(); ++itm) 
     cout << *itm; 

    cout << endl<<"SORTED BY RATING" << endl; 
    for (Book_set_by_value::iterator itl = books.get<value>().begin(); itl != books.get<value>().end(); ++itl) 
     cout << *itl; 

    // Want to see Tolstoy's books? (in descending order of rating) 
    cout << endl; 
    Book_set_by_lang2::iterator mitchells = books.get<lang2>().find("Tolstoy"); 
    while (mitchells->lang2() == "Tolstoy") 
     cout << *mitchells++; 

    return 0; 
} 

謝謝大家發表了評論！

Answer 2

如果是不經常操作，您可以搜索該值。

for(auto& p : m) 
{ 
    if(p.second.name==name_to_find) 
    { 
      //you now have the element 
    } 
} 

然而如果映射爲大，這將是有問題的，因爲這將是一個線性程序，而不是O（log n）的，這是一個問題，因爲地圖是固有地緩慢。

Answer 3

我在類似情況下所做的是使用單個容器包含 個對象，並將std::multiset<ObjectType const*, CmpType>分別用於 每個可能的索引;當插入時，我會做一個push_back，然後從back()恢復 的地址，並將其插入到每個std::set。 （std::unordered_set和std::unordered_multiset將是 你的情況更好：在我的情況下，不僅是訂單顯著，但我沒有 訪問最近的編譯器unordered_set無論是。）

注意，這個假設是一旦它們位於容器中，對象就是不可變的。如果你要改變其中的一個，你可能應該從所有的集合中提取它，做修改，然後重新插入它。

這也假設主容器類型永遠不會使對象的指針和引用無效 ;在我的情況下，我知道前面的最大尺寸爲 ，所以我可以做一個reserve()並使用std::vector。 如果沒有這個，你可以使用std::deque，或者簡單地使用主要（完整）密鑰的std::map 。

即使這需要訪問密鑰中的完整元素。這不是 從您發佈的內容清楚這是否是足夠— 「書題爲 數學」讓我的事情，你可能需要在 標題字符串搜索（也應該「托爾斯泰」比賽「利奧 托爾斯泰」？）。如果你想匹配一個任意子字符串，或者 你的multiset將會非常非常大（因爲你會插入所有可能的 子字符串作爲條目），否則你會進行線性搜索。 （在長條目 正在運行的系統中條目不變，可能值得 妥協：第一次進行線性搜索時請求的子串是 ，但將結果緩存在多重集中，以便下一次， 您可以快速找到它們。這可能是因爲人們往往會使用 相同的子串，如「對於任何一本書在其標題 「數學」數學」）

Answer 4

有關於同一主題的文章： http://marknelson.us/2011/09/03/hash-functions-for-c-unordered-containers/

筆者，馬克·納爾遜，試圖做類似：「用一個簡單的類或結構的持有人的名字」，基本上他使用他unordered_map一對關鍵（就像你）：

typedef pair<string,string> Name; 

int main(int argc, char* argv[]) 
{ 
    unordered_map<Name,int> ids; 
    ids[Name("Mark", "Nelson")] = 40561; 
    ids[Name("Andrew","Binstock")] = 40562; 
    for (auto ii = ids.begin() ; ii != ids.end() ; ii++) 
     cout << ii->first.first 
     << " " 
     << ii->first.second 
     << " : " 
     << ii->second 
     << endl; 
     return 0; 
} 

他意識到unordered_map不知道如何創建的std ::對給定密鑰類型的哈希。 因此，他演示了創建用於unordered_map的散列函數的4種方法。