How to keep only the last duplicate when iterating through rows
<p>Following code iterates through many data-rows, calcs some score per row and then sorts the rows according to that score:</p>

<pre><code>unsigned count = 0;
score_pair* scores = new score_pair[num_rows];
while ((row = data.next_row())) {
    float score = calc_score(data.next_feature())
    scores[count].score = score;
    scores[count].doc_id = row-&gt;docid;
    count++;
}

assert(count &lt;= num_rows);
qsort(scores, count, sizeof(score_pair), score_cmp);
</code></pre>

<p>Unfortunately, there are many duplicate rows with the same docid but different score. Now i like to keep the last score for any docid only. The docids are unsigned int, but usually big (=> no lookup-array) - using a HashMap to lookup the last count for a docid would probably be too slow (many millions of rows, should only take seconds not minutes...).</p>

<p>Ok, i modified my code to use a std:map:</p>

<pre><code>map&lt;int, int&gt; docid_lookup;
unsigned count = 0; 
score_pair* scores = new score_pair[num_rows];
while ((row = data.next_row())) {
    float score = calc_score(data.next_feature())

    map&lt;int, int&gt;::iterator iter;
    iter = docid_lookup.find(row-&gt;docid);
    if (iter != docid_lookup.end()) {
        scores[iter-&gt;second].score = score;
        scores[iter-&gt;second].doc_id = row-&gt;docid;
    } else {
        scores[count].score = score;
        scores[count].doc_id = row-&gt;docid;
        docid_lookup[row-&gt;docid] = count;
        count++;
    }
}
</code></pre>

<p>It works and the performance hit is not as bad as i expected - now it runs a minute instead of 16 seconds, so it's about a factor of 3. Memory usage has also gone up from about 1Gb to 4Gb.</p>
