title: Efficently relabel some elements from 1 to k keeping the order
body: <p>I have a set of n elements, and some of them are uniquely labelled, with integers from 1 to k.</p>
  <p>An action will label an unlabelled element, with something like x-0.1, x \in [1,k], and remove some of the labels.</p>
  <p>After this action, I want to relabel uniquely the elements, from 1 to k', i.e. filling gaps and putting everything integers.</p>
  <p>I tried with a hashset + sorting the elements then relabeling, but it's not efficient.</p>
  <p>I tried to keep the labels in a sorted map, and then insert with hint in a new map since it's sorted. But still, according to gprof, I spend most of my time in inserting/re-balancing the tree/memcpy...</p>
  <p>I'm listening to any way of doing this task efficiently :)</p>
  <p>Example :</p>
  <p>Initially, I have elements let say:</p>
  <pre><code>v1 : no label
  v2 : 4
  v3 : 2
  v4 : no label
  v5 : 1
  v6 : 3
  </code></pre>
  <p>After 1 action:</p>
  <pre><code>v1 : 3.9
  v2 : 4
  v3 : no label
  v4 : no label
  v5 : 1
  v6 : 3
  </code></pre>
  <p>Goal:</p>
  <pre><code>v1 : 3
  v2 : 4
  v3 : no label
  v4 : no label
  v5 : 1
  v6 : 2
  </code></pre>
  <p>Edit : my c++ attemp. m is a map where keys are the labels and values are the elements, Labels is a vector indiced by the elements and containing the labels.</p>
  <pre><code>int label = 1;
  std::map&lt;float, int&gt; tmp;
  for(auto it = m.begin() ; it != m.end() ; ) {
    auto nh = m.extract(it++);
    Labels[it-&gt;second] = label; 
    nh.key() = label++;
    tmp.insert(tmp.end(), std::move(nh));   //should be O(1) given the hint
  }
  tmp.swap(m); 
  </code></pre>