<p>In addition to the two current great posted answers, there are some important point to take into account in order to write an efficient implementation.</p>
<p>First of all, using a <strong>hash-map can be very efficient</strong> if the number of different items is small so that the hash-map can <strong>fit in cache</strong>. Classical sorting algorithm (eg. introsort/mergesort/heapsort) tends to be significantly slower because of the <code>log n</code> factor in the complexity. However, when the number of different items is big, a sort is generally much faster since the <em>unpredictable random-like hash-map access pattern in RAM</em> can be very expensive: each access can be as slow as the RAM <strong>latency</strong> (typically 40~100 ns).</p>
<p>Additionally, sort implementations can be vectorized using <strong>SIMD instructions</strong> (see <a href="https://arxiv.org/pdf/1704.08579.pdf" rel="nofollow noreferrer">here</a> for AVX-512 and <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8627236/" rel="nofollow noreferrer">there</a> for SVE) and parallelized using <strong>multithreading</strong>. This is especially true in this case since <code>np.unique</code> is generally applied on numbers. C++17 provides parallel algorithms (PSTL) including parallel sorts. Numpy sorting algorithms have recently been improved to use AVX-512 resulting in an order of magnitude faster execution. Alternatively, an <code>O(n)</code> radix sort can be used to efficiently sort small array with short-sized keys (eg. 4-bytes).</p>
<p>Moreover, <strong>not all hash-map implementations are equivalent in term of performance</strong>. The STL <code>std::unordered_map</code> tends to be pretty slow. This is due to restrictions in the C++ standard (about the invalidation of iterators) that (almost) force the STL not to use an <a href="https://en.wikipedia.org/wiki/Open_addressing" rel="nofollow noreferrer">open addressing</a> strategy. Instead, STL implementations generally use linked lists to solve hash conflicts and this cause slow allocation as described by @Homer512. The thing the fastest existing hash-map implementations mainly use open addressing. For example, <a href="https://en.wikipedia.org/wiki/Hopscotch_hashing" rel="nofollow noreferrer">hopscotch hashing</a> provide good performance with some interesting guarantees (eg. good performance when the <a href="https://en.wikipedia.org/wiki/Hash_table#Key_statistics" rel="nofollow noreferrer">load factor</a> is close to 90~100%). <a href="https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html" rel="nofollow noreferrer">Tessil</a> has provided a very interesting benchmark about several hash-map implementations and has written very fast implementations (generally much faster than the one of the mainstream STL implementations).</p>
<p><code>std::map</code> is usually implemented using a <a href="https://en.wikipedia.org/wiki/Red%E2%80%93black_tree" rel="nofollow noreferrer">red-black tree</a>. It is written in a pretty efficient way in mainstream STL implementations. However, the <strong>allocator</strong> used by default is clearly not optimized for this use-case. Indeed, the number of nodes to be inserted is bounded. Thus, one can use a <a href="https://en.cppreference.com/w/cpp/memory/monotonic_buffer_resource" rel="nofollow noreferrer">monotonic allocator</a> to speed up the computation. An optimized implementation can even use few simple big arrays with <em>no additional allocation</em>.</p>
<p>Finally, note that <code>np.unique</code> provides the <strong>index of the first unique value</strong> and not all of them. This enable further optimisations. For example, no <code>std::vector</code> is needed for the <code>std::map</code>-based implementation of @Dúthomhas resulting in a smaller memory footprint and probably higher performance.</p>
C++ equivalent of numpy.unique on std::vector with return_index and return_inverse
<p><code>numpy</code> has an implementation of the <code>unique</code> algorithm that returns :</p>
<ol>
<li>the <em>sorted unique elements</em> of a numpy array (<em>i.e.</em> with no duplicates)</li>
</ol>
<p>In addition, <a href="https://numpy.org/doc/stable/reference/generated/numpy.unique.html" rel="noreferrer">numpy.unique()</a> can also return :</p>
<ol start="2">
<li>the indices of the input array that give the unique values</li>
<li>the indices of the unique array that reconstruct the input array</li>
</ol>
<p>The C++ standard library also implements  a <code>unique</code> algorithm (<a href="https://en.cppreference.com/w/cpp/algorithm/unique" rel="noreferrer">here</a>), that somehow  eliminates consecutive duplicates. Combined with <code>std::vector&lt;&gt;::erase</code> and <code>std::sort()</code>, this can return the <em>sorted unique elements</em> of the vector (output 1 of <code>numpy.unique()</code>).</p>
<p>My question is : is there any algorithm in the <code>stl</code> or elsewhere that can also return  outputs 2 and 3 of <code>numpy.unique()</code>. If not, is there a way to efficiently implement it ?</p>