Compressing a vector into a specific range

Question

I want to solve the following task --- I am given a vector of integers. I want to 'compress' this list, where the elements will be replaced with numbers 0 through n - 1, where n is the number of unique elements in the vector, such that the relative ordering among the elements is preserved, i.e., if previously vector[index1] < vector[index2], then that is still true after the compression. In other words, each element is replaced with its ranking among the source vector.

For example, given the vector {1, 3, 10, 6, 3, 12}, the elements will be replaced with 0 through 4 since there are 5 unique value. To preserve ordering, it will be transformed into {0, 1, 3, 2, 1, 4}.

Right now, to complete this, I use the following algorithm:

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int compress_vector(vector<int>& vec) {
  // function compresses the vector passed in by reference
  // and returns the total number of unique elements
  map<int, int> m;
  set<int>      s;
  for (auto i : vec) s.insert(i);
  int counter = 0;
  for (auto i : s) {
    m[i] = counter;
    counter++;
  }
  for (auto& i : vec) i = m[i];
  return s.size();
}

int main() {
  vector<int> vec = { 1, 3, 10, 6, 3, 12 };  //

  int size = compress_vector(vec);

  // Should output "0 1 3 2 1 4", then a newline, then a "5"
  for (auto i : vec) cout << i << " ";
  cout << endl;
  cout << size;

  return 0;
}

However, I feel this function is quite messy --- it uses maps, sets, and counters. While this is functional, is there a faster or cleaner way to do this?

Thanks

Answer 1

Algorithm improvements

I really don’t understand what this algorithm is supposed to be doing. Your description of it is incomplete and vague (for example, you say vector[index1] < vector[index2]… but what is index1 and index2?), and the single example is not illuminating. It looks like you’re just trying to get the sorted position of each element in the vector. So it’s very possible that there is a much better algorithm that can solve this; there’s no way for me to know when what you’re trying to do makes no sense to me.

However, I can look at what your existing implementation is doing and at least improve on that a bit.

You use a set to get all the unique elements in the vector, and then you use a map to get… I dunno, something something count (the sorted index?). I can’t help you with the second part. But I can help you with the first part, because you don’t need the set. You can use the map to get the unique values, like so:

auto compress_vector(std::vector<int>& vec)
{
    auto m = std::map<int, int>{};

    // You don't need the set. You can use the map's keys to get the unique
    // values.
    for (auto i : vec)
        m[i] = 0;

    // And then you can recover the "set" of unique values by just iterating
    // on the map's keys.
    auto counter = 0;
    for (auto [i, _] : m)
        m[i] = counter++;

    // The above loop may be optimized by avoiding the duplicate lookup:
    //  for (auto& p : m)
    //      p->second = counter++;

    for (auto& i : vec)
        i = m[i];

    return m.size();
}

You could also go the other way, and keep the set but ditch the map:

auto compress_vector(std::vector<int>& vec)
{
    auto s = std::set<int>{};

    for (auto i : vec)
        s.insert(i);

    // The values of the map are just the indices of the set.
    for (auto& i : vec)
        i = std::distance(s.begin(), s.find(i));

    return s.size();
}

Depending on a lot of factors, it might be more efficient to ditch the set and use a sorted vector instead:

auto compress_vector(std::vector<int>& vec) {
    // Take care of the degenerate case of an empty input vector first.
    //
    // Not strictly necessary, but will save a lot of work.
    if (vec.empty())
        return 0;

    // You could also do this:
    //  if (vec.size() == 1)
    //  {
    //      vec[0] = 0;
    //      return 1;
    //  }

    // A second container, either a map, set, or second vector, is probably
    // unavoidable, because we need to keep track of the original values while
    // also changing the vector's contents, in order to know the sorted
    // indices.
    //
    // Note that this is the lazy way of building the sorted vector. If there
    // are a lot of duplicate values, it *might* be faster to:
    //  1)  reserve vec.size()
    //  2)  for each element in vec, do a lower_bound() search, to find if
    //      it's already in sorted, and if not, then you have the insert
    //      position
    auto sorted = vec;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());

    // Transform each element in the input vector into the index of the
    // element in the sorted vector.
    std::transform(vec.begin(), vec.end(), vec.begin(),
        [&sorted](auto i)
        {
            // Instead of std::find(), you could also use a binary search,
            // like std::lower_bound().
            return static_cast<int>(
                std::distance(
                    sorted.begin(),
                    std::find(sorted.begin(), sorted.end(), i)
                )
            );
        }
    );

    return sorted.size();
}

Code review

using namespace std;

This is always a bad idea. You can probably get away with it in simple, toy programs, but you should never do it in real code.

int compress_vector(vector<int>& vec)

“Out” parameters (function parameters taken by non-const reference, and then modified with the “return” value) are generally not a great idea. They usually make functions harder to use, because they put the onus on the user to set up space for the return. What if I want the original vector and the “compressed” vector? Now I have to deal with the pain of setting up the result manually, rather than just writing auto result = compress_vector(input);. And if the vector I want to “compress” is already const (which is often the case), it’s on me to make a copy again.

I know there is an argument that out parameters can be more efficient, but that doesn’t really apply here, because you’re creating whole maps, sets, and/or copies of the vector in the function anyway.

An even better design would be to take an output iterator argument.

for (auto i : vec) s.insert(i);

Don’t do this. Saving a single line in the function just isn’t worth the risk of missing the hard-to-spot loop body and introducing bugs. If your function is so long that you actually need to save a line or two in order to fit it on screen, your function is too long in any case, and should be broken up.

for (auto i : vec) s.insert(i);
int counter = 0;
for (auto i : s) {
  m[i] = counter;
  counter++;
}
for (auto& i : vec) i = m[i];

Space out the code. There are THREE loops here, jammed all together. That is three entirely separate logical sections of the function. Each section should be separated from the others by a blank line, to make it clear where the function’s “paragraphs” are. (And, of course, both the first and last loops should not be single lines.)

You should also consider using algorithms instead of naked loops, for two reasons. First, they make your code clearer: a naked loop could be doing ANYTHING… but an algorithm spells out exactly what is happening. Also, algorithms are much easier to optimize.

So the big glob of code above could be:

std::for_each(vec.begin(), vec.end(), [&s](auto i) { s.insert(i); });

auto counter = 0;
std::for_each(s.begin(), s.end(), [&m, &counter](auto i) { m[i] = counter++; });

std::for_each(vec.begin(), vec.end(), [&m](auto& i) { i = m[i]; });

Of course, all three algorithms are for_each() here, because I don’t really understand what the loops are supposed to be doing. for_each() is what you use when nothing else makes more sense. You’ll note that in the modified algorithm I wrote above, I used more specific algorithms, like transform(), unique(), and find() because I understood what was going on.

return s.size();

You have a bug here. s.size() gives an unsigned type, which is problematic enough, but the real issue is that the type may be (and often is) larger than an int. But you are forcing it to be crammed into an int, which may cause truncation, or other weirdness. If you’re absolutely sure you want compress_vector() to return int, then you should at least assert that the size of the vector is smaller than the maximum value of int. Or, on the other hand, maybe you don’t really want compress_vector() to return int? I don’t understand what you want from this function, so I can’t guess which is the right answer.

In main():

for (auto i : vec) cout << i << " ";

Once again, this should not be on a single line. Also, you probably don’t want a whole string constant for just a space; you probably mean ' ', not " ".

cout << endl;

std::endl really makes no sense here. If you want a newline, use a newline: std::cout << '\n';.

return 0;

You don’t need this in main().

Summary

Because your description of the problem is so vague and incomplete, and your examples of the intended usage are so limited and unrevealing, it’s impossible to give good recommendations. There is just so much about this function that is unexplained, and so many unanswered questions: Does it really need to modify the input vector; could it not simply return a new vector instead? Why does it return the number of unique elements; is that really important information? Why does it return that value as an int, rather than std::size_t or std::vector::size_type? And so on and so forth.

The best I can do is offer base-level suggestions going by the literal operations in the given code; in other words, I can only give suggestions for tuning the existing algorithm… I can’t suggest better algorithms, if there are any.

That said, there are certainly some corners you could cut, and some inefficiencies you could remove. You don’t need a set and a map… that’s just overkill in just about any situation. You might even get away with a sorted vector, which should be way more efficient than either a map or a set… especially if you do a binary search.

Answer 2

It feels to me that it is a bit too much to create both std::map and std::set for such a simple purpose. You just need to generate sorted order of vec and then to adjust it a little bit so elements with same value are mapped to the same index.

size_t compress_vector(vector<int>& vec)
{
   if(vec.empty())
   {
       return 0;
   }
   // plan is to make vector ord of indices so that vec[ord[i]] is sorted
   vector<size_t> ord;
   size_t siz = vec.size();
   ord.reserve(siz);

   for(size_t i = 0; i<siz; i++)
   {
        ord.push_back(i);
   }

   std::sort(ord.begin(), ord.end(), [&vec](size_t l, size_t r){return vec[l] < vec[r];});

   // now with sorted indices one can simply iteratively figure out which mapped value do you have
   // you iterate over elements of ord and keep track of the previous element's value to see if a change in values occurred.
   int prevValue = vec.front();
   size_t count = 0;
   for(size_t i : ord)
   {
       if(prevValue != vec[i])
       {
             prevValue = vec[i];
             count++;
       }
       vec[i] = (int)count;
    }

    return count+1;
  }