title: Why C++ is so much slower than Java in this Trie algorithm?
body: <p>I'm solving <a href="https://leetcode.com/problems/palindrome-pairs/" rel="nofollow noreferrer">problem336</a> in Leetcode, while I found the highest upvoted answer <a href="https://leetcode.com/problems/palindrome-pairs/discuss/79195/O(n-*-k2)-java-solution-with-Trie-structure" rel="nofollow noreferrer">here</a> used Trie structure in java. So, I wrote it in C++ again. I tried to optimize, but the Runtime and Memory are still very bad. Initially, I used shared_ptr, then the runtime: ~800 ms, memory: 400Mb. Then, I used new pointer, it became ~300ms, 200Mb. Still much slower than Java (20ms, 50Mb). I tried several times, but it's still 10x slower. My code structure and logic is just the same with the java implemented code, but it's so slow. I cannot figure out why!
  here is my code: </p>
  
  <pre><code>struct TrieNode {
      TrieNode *next[26];
      int index = -1;
      vector&lt;int&gt; list;
      TrieNode(){
          memset(next,NULL,sizeof(next));
      }
      ~TrieNode() {
          for (int i = 0; i &lt; 26; ++i) {
              if (next[i]) delete(next[i]);
          }
      }
  };
  
  bool isPalindrome(const string &amp;word, int start, int end) {
      while (start &lt; end) {
          if (word[start] != word[end])
              return false;
          ++start;
          --end;
      }
      return true;
  }
  
  int addword(TrieNode* root, const string &amp;word, int index) {
      for (int i = word.size() - 1; i &gt;= 0; --i) {
          int j = word[i] - 'a';
          if (!(root-&gt;next[j])) {
              root-&gt;next[j] = new TrieNode;
          }
          if (isPalindrome(word, 0, i))
              root-&gt;list.push_back(index);
          root = root-&gt;next[j];
      }
      root-&gt;index = index;
      root-&gt;list.push_back(index);
      return 0;
  }
  
  void search(TrieNode* root, vector&lt;string&gt; &amp;words, int index, vector&lt;vector&lt;int&gt;&gt; &amp;res) {
      for (int i = 0; i &lt; words[index].size(); ++i) {
          if (root-&gt;index &gt;= 0 &amp;&amp; root-&gt;index != index &amp;&amp; isPalindrome(words[index], i, words[index].size() - 1)) {
              res.push_back({index, root-&gt;index});
          }
          root = root-&gt;next[words[index][i] - 'a'];
          if (!root) return;
      }
      for (int i : root-&gt;list) {
          if (i == index) continue;
          res.push_back({index, i});
      }
  }
  
  vector&lt;vector&lt;int&gt;&gt; palindromePairs(vector&lt;string&gt;&amp; words) {
      vector&lt;vector&lt;int&gt;&gt; res;
      TrieNode *root = new TrieNode;
      for (int i = 0; i &lt; words.size(); ++i) {
          addword(root, words[i], i);
      }
      for (int i = 0; i &lt; words.size(); ++i) {
          search(root, words, i, res);
      }
      delete root;
      return res;
  }
  </code></pre>