Is there any reason at all for using a shared_ptr<node>
for your links? Why not use a unique_ptr<node>
? Why incur the extra memory payload and overhead. It seems to me that the following would be a bit simpler (and smaller, and faster):
#include <map>
#include <memory>
#include <stack>
#include <limits>
#include <iterator>
template <typename T>
class trie {
struct node {
std::map<T, std::unique_ptr<node> > link;
bool terminal;
public:
node(): terminal(false) { }
};
std::unique_ptr<node> root;
public:
trie(): root(new node()) {}
typedef std::size_t size_type;
template <typename String>
size_type match(const String& s, bool require_terminal = true) const
{
// Follow the path until the end of the string or a mismatch
auto it = &root;
for(auto sit = s.begin(); sit != s.end(); ++sit) {
auto lit = (*it)->link.find(*sit);
if(lit == (*it)->link.end())
return std::distance(s.begin(), sit); // Return the index of the mismatch
it = &( lit->second );
}
if (!require_terminal || (*it)->terminal)
return std::numeric_limits<size_type>::max(); // The path was matched completely
return s.size(); // Return the index of the mismatch
}
template <typename String>
void add(const String& s) {
auto it = &root;
// Traverse the path and extend it as necessary
for (auto c : s)
it = &( (*it)->link[c] );
(*it)->terminal = true;
}
template <typename String>
void remove(const String& s) {
auto it = &root;
// Store the reversed path
std::stack< decltype(it) > bak;
auto sit = s.begin();
for (; sit != s.end(); ++sit) {
bak.push(it);
auto lit = (*it)->link.find(*sit);
if(lit == (*it)->link.end())
return; // no match! nothing to remove! …