title: Build tree from flat JSON array in c++
body: <p>Essentially I have a JSON structure like this:</p>
  
  <pre><code>[
      {
          "id": "foo",
          "parent_id": null,
          "value": "This is a root node"
      },
      {
          "id": "bar",
          "parent_id": "foo",
          "value": "This is 2nd level node"
      },
      {
          "id": "baz",
          "parent_id": "bar",
          "value": "This is a 3rd level node"
      },
      {
          "id": "moo",
          "parent_id": "foo",
          "value": "This is another 2nd level node"
      },
      {
          "id": "woo",
          "parent_id": null,
          "value": "This is another root node"
      }
  ]
  </code></pre>
  
  <p>(Note that there's no ordering going on).</p>
  
  <p>Now I would like to take that and parse it into a tree structure. Something like this (except using C++ types, not JSON):</p>
  
  <pre><code>[
      {
          "id": "foo",
          "value": "This is a root node",
          "children": [
              {
                  "id": "bar",
                  "value": "This is 2nd level node",
                  "children": [
                      {
                          "id": "baz",
                          "value": "This is a 3rd level node",
                          "children": []
                      }
                  ]
              },
              {
                  "id": "moo",
                  "value": "This is 2nd level node"
                  "children": []
              }
          ]
      },
      {
          "id": "woo",
          "value": "This is another root node"
          "children": []
      }
  ]
  </code></pre>
  
  <p>I would imagine that it would look something like this, in pseudo-code, but I don't know enough C++ to actually make it work (I'm in the middle of a hack week. I have no idea what I'm doing :) )</p>
  
  <pre><code>struct NodeValue {
      std::string id;
      std::string value;
      std::string parent_id;
  }
  
  struct Node {
      NodeValue value;
      Node parent;
      std::deque&lt;Node&gt; children;
  }
  
  std::deque&lt;Node&gt; buildTree(json::Value nodes) {
      std::unordered_map&lt;std::string, Node&gt; lookup;
  
      // Populate our lookup map with all the nodes
      for (unsigned int i = 0; i &lt; nodes.size(); ++i) {
          lookup.insert(std::make_pair(nodes[i].id, Node {
              NodeValue {
                 nodes[i]["id"].asString(),
                 nodes[i]["value"].asString(),
                 nodes[i]["parent_id"].asString()
              },
              nodes[i]["id"].asString()
          }));
      }
  
      // Populate children
      for (lookup::iterator i = lookup.begin(); i != lookup.end(); ++i) {
          Node parent;
          try {
              parent = lookup.at(lookup[i].value.parent_id);
              parent.children.emplace_back(lookup[i]);
          } catch (out_of_range &amp;e) {
              continue;
          }
      }
  
      // Remove all non-root nodes
      it = lookup.begin();
      while ((it = std::find_if(it, lookup.end(), [] (const Node&amp; n) { return n.parent_id != NULL; })) != lookup.end()) {
          lookup.erase(it++);
      }
  
      return lookup;
  }
  </code></pre>
  
  <p>I don't think this solution would work, unless the nodes are pre-sorted according to their depth level? Also, I literally wrote my first line of C++ two days ago, so have mercy.</p>
  
  <p>Could anyone help me out?</p>