A reversed-string Trie data structure

This is a simple Trie data structure for strings, except it puts the strings into the structure backwards.

The insert method simply iterates over chars from the string-to-be-inserted backwards, and starting at the root of the graph, looks for an edge that is labeled with the current char. If an edge is found, we move to the next vertex and next char. If no edge is found, a new edge and target vertex is created, with the new edge labeled with the current char.

The containsWord method is similar. It follows labeled edges until it comes to the a word terminator '\0' or returns false as soon as it cannot find the next edge.

I'm fairly new to C++. I'd like to know about any style errors or anything outside of accepted convention. Or if this is just not a good way of creating this structure.

My unit tests are working ok with this, but performance seems to be lagging a boost::unordered_set for lookups. Tries are supposed to have \$O(length of key)\$ lookup time, which I would think would be about the same as the cost of calculating the hash code of a string to look up in a set.

```
#include
#include
#include

class TrieVertex;

typedef boost::shared_ptr VertexPtr;

class TrieEdge
{
public:
char fC;
VertexPtr fTarget;
TrieEdge(char c, VertexPtr target) : fC(c), fTarget(target) {}
};

typedef boost::shared_ptr EdgePtr;

class TrieVertex {
public:
boost::unordered_map fOutEdges;
TrieVertex() : fOutEdges() {}
};

class ReverseTrie {
private:
VertexPtr fRoot;
size_t fSize;

public:
ReverseTrie( ): fRoot(boost::make_shared()), fSize(0) {}

~ReverseTrie() {
fRoot.reset();
}

void clear() {
boost::make_shared().swap(fRoot);
fSize = 0;
}

size_t size() {
return fSize;
}

bool insertStringR(const std::string &word) {
VertexPtr currentVertex = fRoot;

for (std::string::const_reverse_iterator i = word.rbegin(); i != word.rend(); ++i) {
if (*i

I don't have the time to do a completely thorough review at the moment, but here are some things that I noticed that may help you improve your code.

Supply the missing logWarning function

This is more a matter of helping reviewers rather than necessarily a flaw in your code, but without the implementation of the logWarning code that's called from within the logEdges routine, it's not entirely clear what that function might do, although it's possible to make a guess.

Prefer std to boost functions

It's in no way a slight to the excellent boost library, but all of the boost elements this code uses are all now standardized (as of C++11). By using the std forms rather than the boost versions, your code is likely to be more portable.

Prefer private to public where practical

The TrieVertex class has its only data member fOutEdges as a public member. Rather than do it that way, it might be better to keep it private and declare ReverseTrie to be a friend. That way ReverseTrie would continue to have access to the data member, but no other class would. This seems like a safer design to me. The same is true for TrieEdge.

Eliminate unused variables

The fC member of the TrieEdge class is never used. It can be omitted.

Consider adding utility functions

By adding some simple utility functions to the TrieVertex class, you can make many portions of the code much easier to understand. Here are the functions I propose:

bool noEdges() const { return fOutEdges.size() == 0; }
bool noEdges(char ch) const { return fOutEdges.count(ch) == 0; }
VertexPtr addEdge(char ch) {
    VertexPtr targetVertex = std::make_shared();
    EdgePtr   e = std::make_shared(targetVertex);
    fOutEdges[ch] = e;
    return e->fTarget;
}

Here's a some existing code without them:

if (currentVertex->fOutEdges.count('\0') == 0) {
    VertexPtr targetVertex = boost::make_shared();
    EdgePtr   e = boost::make_shared('\0', targetVertex);
    currentVertex->fOutEdges['\0'] = e;
    exists = false;
}

Here's how it looks with them:

if (currentVertex->noEdges('\0')) {
    currentVertex->addEdge('\0');
    exists = false;
}

StackExchange Code Review Q#68435, answer score: 4