is there a way to condense a vector (C++)?

Question

I have a sparsely populated vector that I populated via hashing, so elements are scattered randomly in the vector. Now what I want to do is iterate over every element in that vector. What I had in mind was essentially condensing the vector to fit the number of elements present, removing any empty spaces. Is there a way I can do this?

Answer 1

Either you save the additionally needed information during insertion of the elements (e.g. links to the previous / next element compared to a linked list) or you make one pass over all the elements and remove the unnecessary ones.

The first solution costs you some space (approx. 8 bytes / entry), the second costs you one pass over all elements. Depending on the scenario, one or both possibilities might not be useful.

Answer 2

You can condense using a version of run-length encoding.
You go over the original vector and create a new "condensed" vector which contains alternating values - a value from the original and a count of the empty spaces to the next value. For example this:

3 - - - - 4 - - 7 3 - - - 9 -

turns to this:

3 4 4 2 7 0 3 3 9 1