I'm trying to use NED-Trie, it only has a single header file.
How to use this library without using NEDTRIE_* macro? and iterate to get the key and the value from iterator? It seems there are no first and second property on the trie_iterator
#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;
}
}
From the errors, it seems trie_map cannot be used with std::string?
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.
Disclaimer: I am the author of nedtries. And you should have tagged this question with nedtries, and then I would have seen it much quicker.
You can't use anything but a size_t as a key in trie_map because the underlying C macro implementation only works with size_t keys. This is because it relies on bitscan CPU opcodes, and those take a size_t. You could use it with a double by casting it to a size_t if IEEE 754 were a stable binary format, but as it is not you cannot do this safely.
As the documentation says, pass any non-size_t keys through std::hash and check for collision after dereference. Regarding trie_map not providing first and second, well trie_map is a stonking pile of crap code. I do say in the docs not to use it. If you examine the source code, you'll see I do a large number of illegal and undefined behaviour things, all stuff you should avoid having in your code base. That said, as a rapid prototyper for "what if?" scenarios, specifically "will bitwise tries really help out my C++ code here?", it fits the bill.
The Boost C++ Libraries have seen some work done on a Trie STL container, most recently in GSoC 2013. Nothing production ready though. A shame, as C++ could really do with a proper trie STL container.
Niall