RadixSet - a growing-only radix/patricia tree I'm looking for a structure to store large amounts of strings (5k to 100k) and then test for existence of new strings against the previous inserted data, in the least possible amount of time (memory is mostly irrelevant). The structure would first be fully loaded at the program start, without any queries. After the building process, it would receive many many queries (about 200 million), then the program exists (no mid-execution destruction). Also, there are about 150-200 simultaneous independent structures in-memory.

Initially I though about a HashSet of string keys. This approach is amortized \$O(1)\$ with the data set size and \$O(K)\$ with the the query string size. However, the cost includes some collision handling and bucketing. I learned about Radix Trees, which perform the insert and query operations in the same time complexity as a hash set of strings, but with less overhead.

When I went to search the web for a good implementation, most implementations offer more functionality than needed, bringing some additional overhead. Some build the structure as a map instead of a set, or have operations like removing items and checking for prefixes, that are not needed at all and may incur some performance penalty on the two needed operations. Or worse, they do not deal with non-ASCII strings.

Since there are only two operations and the Radix Tree is not that complex, I thought I could roll it on my own. Even though I'm not proficient in C++, the project runs it (not to mention the performance needs).

Here is my current implementation:

#ifndef radixset_hpp
#define radixset_hpp

#include &lt;string&gt;

class radixset {
public:

   radixset() : isword(false), children(nullptr) { }

   ~radixset() {
      if (children != nullptr) {
         for(auto i = 0; i &lt; 256; i++) {
            delete children[i];
         }
         delete children;
      }
   }


   void insert(std::string str) {
      radixset* node = this;
      for (unsigned char c : str) {
         if (node-&gt;children == nullptr) {
            node-&gt;children = new radixset*[256];
         }
         node-&gt;children[c] = new radixset;
         node = node-&gt;children[c];
      }
      node-&gt;isword = true;
   }


   bool contains(std::string str) {
      radixset* node = this;
      for (unsigned char c : str) {
         if (node == nullptr || node-&gt;children == nullptr) {
            return false;
         }
         node = node-&gt;children[c];
      }
      return node-&gt;isword;
   }

private:
   bool isword;
   radixset** children;
};

#endif


And a basic set of tests:

#include "radixset.hpp"
#include &lt;cassert&gt;

int main() {
   radixset r = radixset{};

   assert(!r.contains(""));
   assert(!r.contains("abc"));
   assert(!r.contains("def"));

   r.insert("abc");
   r.insert("def");
   r.insert("");

   assert(r.contains("abc"));
   assert(r.contains("def"));
   assert(r.contains(""));
   assert(!r.contains("ab"));
   assert(!r.contains("defg"));

   assert(!r.contains("áý"));
   r.insert("áý");
   assert(r.contains("áý"));
}


The assertions all work as intended. Although every critic is welcome, I'm mostly looking for 1) performance increase, 2) the pointers here are really ugly (radixset** children, really?), a less headache-y/more modern version would be nice.

If it matters, my make runs the line:

g++ -Wall -std=c++11 radixset.hpp test.cpp -o output/test`


I'm on a Linux/Debian 8 system. I haven't yet spent time choosing compiler flags, don't bother with that. Also, I know the documentation is missing.

Side question: is the contains operation thread-safe? Since it only reads (not writing) members I'm inclined to guess so, but I find the C++ world so confusing...
As Olzhas Zhumabek mentioned in the comments, the allocation and de-allocation is poorly done and cause undefined behavior, which will most likely cause a segmentation fault.

First, the allocation in the insert function: every time you insert, you're overwriting the previous node with the line node-&gt;children[c] = new radixset;, and it's a bug that your tests do not cover (happens in the case of inserting two words with the same prefix), so you haven't noticed it. Also, it would be better to allocate all the children upfront to avoid pointing to garbage; so, the insert function becomes:

void insert(std::string str) {
   radixset* node = this;
   for (unsigned char c : str) {
      if (node-&gt;children == nullptr) {
         node-&gt;children = new radixset*[256];
         for (auto i = 0; i &lt; 256; i++) {
            node-&gt;children[i] = new radixset;
         }
      }
      node = node-&gt;children[c];
   }
   node-&gt;isword = true;
}


Then, the de-allocation. Whenever you allocate using new[] you must de-allocate using delete[], and not just delete. The allocations to the recursive radixset structure do not use the subscript allocation, so their delete also do not use the subscript.

~radixset() {
   if (children != nullptr) {
      for (auto i = 0; i &lt; 256; i++) {
         delete children[i];
      }
      delete[] children;
   }
}


And don't forget to add the non-tested case to the test cases! (Note: I have changed the tests from cassert to GoogleTest).

TEST (RadixSetInsert, MatchingPrefixLongerFirst) {
   radixset r = radixset{};
   r.insert("abc");
   r.insert("ab");
   ASSERT_TRUE(r.contains("ab"));
   ASSERT_TRUE(r.contains("abc"));
}

TEST (RadixSetInsert, MatchingPrefixShorterFirst) {
   radixset r = radixset{};
   r.insert("ab");
   r.insert("abc");
   ASSERT_TRUE(r.contains("ab"));
   ASSERT_TRUE(r.contains("abc"));
}




Actually, the memory usage for sparse data sets is way too much in this implementation. To avoid allocating too much and still not pointing to garbage, point to nullptr and allocate as needed:

if (node-&gt;children == nullptr) {
    node-&gt;children = new radixset*[256];
    for (auto i = 0; i &lt; 256; i++) {
        node-&gt;children[i] = nullptr;
    }
}
if (node-&gt;children[c] == nullptr) {
    node-&gt;children[c] = new radixset;
}


And check for nullptr properly when deleting the children members.