title: Fast insert unique container
body: <p>I have to store elements (struct State) in a 2D vector container and each element must be unique.</p>
  
  <p>I store the elements like this:</p>
  
  <pre><code>std::vector&lt;std::vector&lt;std::unique_ptr&lt;State&gt;&gt;&gt; m_container;
  </code></pre>
  
  <p>And I have an insert function</p>
  
  <pre><code>bool insert(State &amp;&amp; value, std::size_t deepness);
  </code></pre>
  
  <p>Which should inset 'value' into m_container[deepness] if the value is unique or the new deepness is smaller then the previous in which case I have to remove the previous State (return true is inserted).</p>
  
  <p>I have multiple threads inserting at the same time, I already have an implementation but I not sure if it is the best so I am interested in a better and faster way for the insert or some improvements.</p>
  
  <p>My implementation is rather long so I try to shrink it down while keeping the logic behind it.</p>
  
  <p>other than the container I have multimap: </p>
  
  <pre><code>std::multimap&lt;std::size_t, std::pair&lt;std::size_t, std::size_t&gt;&gt; m_multimap;
  </code></pre>
  
  <p>key: hash of the state</p>
  
  <p>pair_1: deepness</p>
  
  <p>pair_2: the position of the State in m_container[deepness]</p>
  
  <p>I have a lockless_queue of struct Temp (lockless_queue m_queue) I insert here first then to the container.</p>
  
  <pre><code>template&lt;typename T&gt;
  class lockless_queue {
  public:
      // storeing the elements
      struct node;
      struct node_ptr;
  
      // insert element
      template&lt;typename... Args&gt;
      void produce(Args&amp;&amp;... args);
      void produce(T &amp;&amp; data);
      void produce(const T &amp; data);
  
      // consume all elements form queue
      node_ptr consume_all();
  
      // queue is not empty
      operator bool() const;
  };
  
  struct Temp {
      std::unique_ptr&lt;State&gt; value;
      std::size_t hash;
      std::size_t deepness;
      bool exist = false;
  
      Temp(State * v, std::size_t hash, std::size_t deepness, bool exist);
      Temp(State &amp;&amp; v, std::size_t deepness);
  
      Temp move() {
          return Temp(value.release(), hash, deepness, exist);
      }
  
      bool is_equal(const State &amp; state) const;
      bool is_equal(State * state) const;
      bool is_equal(const Temp &amp; other) const;
      bool is_equal(Temp * other) const;
  
      void swap(State &amp;&amp; v, std::size_t d) {
          deepness = d;
          value.reset(new State(std::move(v)));
      }
  };
  </code></pre>
  
  <p>The following function is the insert function which insert to the locless_queue</p>
  
  <pre><code>bool pre_emplace(State &amp;&amp; value, std::size_t deepness) {
      Temp temp(std::move(value), deepness);
      const auto range = m_multimap.equal_range(temp.hash);
      if (range.first == range.second) {
          m_queue.produce(std::move(temp));
          return true;
      } else {
          const auto &amp; container = m_container;
          const auto it = std::find_if(range.first, range.second, [&amp;temp, &amp;container](const auto &amp; iter) {
              return temp.is_equal(container[iter.second.first][iter.second.second].get());
          });
          if (it == range.second || deepness &lt; it-&gt;second.first) {
              temp.exist = true;
              m_queue.produce(std::move(temp));
              return true;
          }
      }
      return false;
  }
  </code></pre>
  
  <p>(some case the return true is invalid because the queue is not unique but it is not a problem, I only use the return value for estimating the number of iserted elements)</p>
  
  <p>this function consumes the elements from the queue into a temporary mulimap of hash and Temp</p>
  
  <pre><code>void m_finalize_cycle(std::multimap&lt;std::size_t, Temp&gt; &amp; multimap) {
      auto head = m_queue.consume_all();
      auto node = head.ptr;
      while (node != nullptr) {
          if (node-&gt;data.value == false) { node = node-&gt;next;  continue; }
          auto &amp; temp = node-&gt;data;
          const auto range = multimap.equal_range(temp.hash);
          if (range.first == range.second) {
              multimap.emplace(std::make_pair(temp.hash, temp.move()));
          } else {
              const auto it = std::find_if(range.first, range.second, [&amp;temp](const auto &amp; pair) {
                  return temp.is_equal(pair.second.value.get());
              });
              if (it == range.second) {
                  multimap.emplace_hint(range.first, std::make_pair(temp.hash, temp.move()));
              } else if (temp.deepness &lt; it-&gt;second.deepness) {
                  it-&gt;second.value.reset(temp.value.release());
                  it-&gt;second.deepness = temp.deepness;
              }
          }
          node = node-&gt;next;
      }
  }
  </code></pre>
  
  <p>and this function load all Temp value from the previous mulimep into m_container</p>
  
  <pre><code>void m_finalize_write(std::multimap&lt;std::size_t, Temp&gt; &amp; multimap) {
      for (auto &amp;[hash, temp] : multimap) {
          if (temp.exist) {
              const auto range = m_multimap.equal_range(temp.hash);
              auto &amp; container = m_container;
              const auto it = std::find_if(range.first, range.second, [&amp;temp, &amp;container](const auto &amp; iter) {
                  return temp.is_equal(container[iter.second.first][iter.second.second].get());
              });
              if (it != range.second) {
                  m_container.at(it-&gt;second.first).at(it-&gt;second.second).reset(nullptr);
                  m_multimap.erase(it);
              }
          } else {
          }
          // extend m_container
          extend_if_needed(temp.deepness);
          m_container.at(temp.deepness).push_back(std::move(std::unique_ptr&lt;State&gt;(temp.value.release())));
          m_multimap.emplace(hash, std::make_pair(temp.deepness, m_container[temp.deepness].size() - 1));
      }
  }
  </code></pre>
  
  <p>while I insert elements I run the m_finalize_cycle in every 10 microseconds then if I finished with the inserts I call the m_finalize_write.</p>
  
  <p>This implementation works fine for me but unfortunately, it is the slowest part of my code so I am interested in better ways.</p>