logo标签列表

如何在不使用宏的情况下正确地使用NED-Trie？

c++trie
3
我正在尝试使用NED-Trie，它只有一个标题文件。 如何在不使用NEDTRIE_*宏的情况下使用该库？并且如何迭代以从iterator获取键和值？似乎在trie_iterator上没有first和second属性。
#include <cstring>
#include "nedtrie.h"
#include <iostream>
#include <string>
using namespace std;
typedef nedtries::trie_map<string,double> MSD;
int main() {
  MSD m;
  m["test"] = 1234;
  m["yay"] = 2345;
  m["foo"] = 3456;
  m["bar"] = 4567;
  for(auto it = m.begin(); it != m.end(); ++it) {
     string key = it->first;
     double val = it->second; 
  } 
}

从错误来看，似乎无法使用std::string和trie_map一起使用？

In file included from nedtrie.cpp:2:
./deps/nedtrie.h:1813:20: error: no viable conversion from 'const std::basic_string<char>' to 'size_t' (aka 'unsigned long')
            return r->key;
                   ^~~~~~
./deps/nedtrie.h:1625:14: note: in instantiation of member function 'nedtries::intern::findkeyfunct_t<std::basic_string<char>, double, nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>,
      std::_List_iterator<unsigned long> >, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double> >::operator()' requested here
      return keyfunct_()(*v);
             ^
./deps/nedtrie.h:611:17: note: in instantiation of function template specialization 'nedtries::intern::to_Ckeyfunct<nedtries::intern::findkeyfunct_t<std::basic_string<char>, double, nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> >, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double> >, nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >' requested here
    size_t rkey=keyfunct(r), keybit, nodekey;
                ^
./deps/nedtrie.h:1898:14: note: in instantiation of function template specialization 'nedtries::triefind<nedtries::trie_map_head<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>,
      std::_List_iterator<unsigned long> > >, nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> >, 24, &nedtries::intern::to_Ckeyfunct>' requested here
      return triefind<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<intern::findkeyfunct_t<keytype, type, mapvaluetype, keyfunct> > >(&triehead, (mapvaluetype *) buffer);
             ^
./deps/nedtrie.h:2069:50: note: in instantiation of member function 'nedtries::trie_map<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>,
      double>, std::_List_iterator<unsigned long> >, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > > > >::triehead_find' requested here
      mapvaluetype *r=const_cast<mapvaluetype *>(triehead_find(key));
                                                 ^
nedtrie.cpp:9:8: note: in instantiation of member function 'nedtries::trie_map<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>,
      double>, std::_List_iterator<unsigned long> >, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > > > >::operator[]' requested here
      m["test"] = 1234;
       ^
In file included from nedtrie.cpp:2:
./deps/nedtrie.h:1814:18: error: no viable conversion from 'std::basic_string<char>' to 'size_t' (aka 'unsigned long')
          return keyfunct()(v);
                 ^~~~~~~~~~~~~
./deps/nedtrie.h:1728:19: warning: unused variable 'ensure_trie_link_offset_is_bounded' [-Wunused-variable]
      static char ensure_trie_link_offset_is_bounded[trie_link_offset+sizeof(trie_link)<=sizeof(*this)];
                  ^
./deps/nedtrie.h:1939:76: note: in instantiation of member function 'nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> >::trie_maptype' requested here
      iterator it=iterator(this, stlcontainer::insert(stlcontainer::end(), std::move(val)));
                                                                           ^
./deps/nedtrie.h:2075:12: note: in instantiation of member function 'nedtries::trie_map<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>,
      double>, std::_List_iterator<unsigned long> >, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > > > >::triehead_insert' requested
      here
        it=triehead_insert(key, std::move(type()));
           ^
nedtrie.cpp:9:8: note: in instantiation of member function 'nedtries::trie_map<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>,
      double>, std::_List_iterator<unsigned long> >, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > > > >::operator[]' requested here
      m["test"] = 1234;
       ^
In file included from nedtrie.cpp:2:
./deps/nedtrie.h:1625:14: error: no viable conversion from 'std::basic_string<char>' to 'size_t' (aka 'unsigned long')
      return keyfunct_()(*v);
             ^~~~~~~~~~~~~~~
./deps/nedtrie.h:323:17: note: in instantiation of function template specialization 'nedtries::intern::to_Ckeyfunct<nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >' requested here
    size_t rkey=keyfunct(r), keybit, nodekey;
                ^
./deps/nedtrie.h:1942:7: note: in instantiation of function template specialization 'nedtries::trieinsert<nedtries::trie_map_head<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>,
      std::_List_iterator<unsigned long> > >, nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> >, 24, &nedtries::intern::to_Ckeyfunct>' requested here
      trieinsert<trie_map_head<mapvaluetype>, mapvaluetype, trie_fieldoffset, intern::to_Ckeyfunct<keyfunct> >(&triehead, const_cast<mapvaluetype *>(&(*it)));
      ^
./deps/nedtrie.h:2075:12: note: in instantiation of member function 'nedtries::trie_map<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>,
      double>, std::_List_iterator<unsigned long> >, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > > > >::triehead_insert' requested
      here
        it=triehead_insert(key, std::move(type()));
           ^
nedtrie.cpp:9:8: note: in instantiation of member function 'nedtries::trie_map<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>,
      double>, std::_List_iterator<unsigned long> >, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > > > >::operator[]' requested here
      m["test"] = 1234;
       ^
In file included from nedtrie.cpp:2:
./deps/nedtrie.h:1773:9: error: no matching function for call to 'trienext'
        trienext<trie_map_head<mapvaluetype>, mapvaluetype, mapvaluetype::trie_link_offset, intern::to_Ckeyfunct<typename mapvaluetype::trie_keyfunct_type> >(&parent->triehead, (mapvaluetype *)(&**this)) :
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nedtrie.cpp:13:47: note: in instantiation of member function 'nedtries::trie_iterator<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, nobblezeros, std::list<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>,
      std::_List_iterator<unsigned long> >, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > > >,
      std::_List_iterator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, 1, nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> >, nedtries::trie_iterator<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>,
      std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, nobblezeros, std::list<nedtries::trie_maptype<std::basic_string<char>, double,
      nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> >, std::allocator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>,
      std::_List_iterator<unsigned long> > > >, std::_List_const_iterator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > >, 1,
      nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> >,
      nedtries::intern::noconstiteratortype<std::_List_const_iterator<nedtries::trie_maptype<std::basic_string<char>, double, nedtries::trie_maptype_keyfunct<std::basic_string<char>, double>, std::_List_iterator<unsigned long> > > > > >::operator++' requested
      here
      for(auto it = m.begin(); it != m.end(); ++it) {
                                              ^
./deps/nedtrie.h:1141:120: note: candidate template ignored: invalid explicitly-specified argument for template parameter 'keyfunct'
  template<class trietype, class type, size_t fieldoffset, size_t (*keyfunct)(const type *RESTRICT)> DEBUGINLINE type *trienext(const trietype *RESTRICT head, const type *RESTRICT r)
                                                                                                                       ^
1 warning and 4 errors generated.
1
从Readme.html中得知，它的两个主要缺点是：(i) 它只能使用size_t作为关键字（即void *的大小），因此它不能像哈希表那样使用任意大的关键字（尽管当然可以将大的关键字哈希成一个size_t大小的关键字）。 - PiotrNycz
1个回答
3
免责声明：我是nedtries的作者。您应该使用nedtries作为问题标签，这样我就能更快地看到它了。
在trie_map中，您不能使用除size_t以外的任何内容作为键，因为基础的C宏实现只适用于size_t键。这是因为它依赖于bitscan CPU操作码，而这些操作码需要一个size_t。如果IEEE 754是稳定的二进制格式，您可以通过将double转换为size_t来使用它，但由于它不是这样，所以您不能安全地这样做。
如文档所述，请通过std::hash传递任何非size_t的键，并在解引用后检查冲突。关于trie_map不提供first和second，那么trie_map是一堆可怕的代码。我在文档中说过不要使用它。如果您查看源代码，您会发现我做了大量非法和未定义的行为，所有这些都是您应避免将其放入您的代码库中的东西。尽管如此，作为“如果？”情况的快速原型制作工具，特别是“位Trie真的会在这里帮助我的C++代码吗？”，它合适。
Boost C++库对Trie STL容器进行了一些工作，最近是在GSoC 2013中进行的。然而，没有任何生产就绪的版本。很遗憾，因为C++确实需要一个合适的Trie STL容器。
Niall
我想补充一下，使用位运算字典树实现并发映射比红黑树更好。如果我在 https://svn.boost.org/trac/boost/wiki/SoC2015 的并发哈希表 GSoC 项目中得到一个非常优秀的学生，我会让他们将 concurrent_map 实现为 Boost 赞助的 GSoC 扩展。 - Niall Douglas
以下标签不存在：[nedtrie] [nedtries]。 - Kokizzu
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接