有在C++哈希表
复合键我有一个数据结构,它具有,有在C++哈希表
<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简单的例子,任何其他方法等..任何帮助将不胜感激。
谢谢。
我想通了如何使用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;
}
谢谢大家发表了评论!
如果是不经常操作,您可以搜索该值。
for(auto& p : m)
{
if(p.second.name==name_to_find)
{
//you now have the element
}
}
然而如果映射为大,这将是有问题的,因为这将是一个线性程序,而不是O(log n)的,这是一个问题,因为地图是固有地缓慢。
我在类似情况下所做的是使用单个容器包含 个对象,并将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将会非常非常大(因为你会插入所有可能的 子字符串作为条目),否则你会进行线性搜索。 (在长条目 正在运行的系统中条目不变,可能值得 妥协:第一次进行线性搜索时请求的子串是 ,但将结果缓存在多重集中,以便下一次, 您可以快速找到它们。这可能是因为人们往往会使用 相同的子串,如“对于任何一本书在其标题 “数学”数学”)
谢谢,我真的碰巧建立一个'boost :: multi_index',但你的想法也有帮助。 – devEvan 2012-03-03 21:42:07
有关于同一主题的文章: 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种方法。
你还应该看看助推入侵容器 – PlasmaHH 2012-03-02 11:19:05
我建议你看看这个例子,它演示了组合键的使用:http://www.boost.org/doc/libs/1_49_0/libs/multi_index/example /composite_keys.cpp,此外,此页面:http://www.boost.org/doc/libs/1_49_0/libs/multi_index/doc/tutorial/indices.html,介绍如何定义多个索引(将它们想象为“意见“相同的数据) – Nim 2012-03-02 11:25:40
我知道你说你看看文档,但这个具体的例子显示如何形成一个组合键http://www.boost.org/doc/libs/1_49_0/libs/multi_index/doc /examples.html#example7 – 111111 2012-03-02 11:27:33