Data structure with O(1) insertion and O(log(n)) search complexity?
<p>Is there any data structure available that would provide <em>O(1)</em> -- i.e. constant -- insertion complexity and <em>O(log(n))</em> search complexity <strong>even in the worst case</strong>?</p>

<p>A sorted vector can do a <em>O(log(n))</em> search but insertion would take <em>O(n)</em> (taken the fact that I am not always inserting the elements either at the front or the back). Whereas a list would do <em>O(1)</em> insertion but would fall short of providing <em>O(log(n))</em> lookup.</p>

<p>I wonder whether such a data structure can even be implemented.</p>