Applying a permutation to a vector, part 3


We spent the last two days looking at the apply_permutation function and arguing pros and cons of various implementation choices. Today's we're going to look at generalization.

One of the things you are taught in mathematics is that after you've proved something, you should try to strengthen the conclusion and weaken the hypotheses. Can we apply that principle here?

I don't see much that can be done to strengthen the conclusion, but I see a way to weak the hypotheses: The inputs don't actually have to be vectors. Anything that supports random access will do. So let's use a random access iterator.

And the indices don't have to be integers. Anything that can be used to index the random access iterator will do. So let's not require to to be an integer; we'll take whatever it is.

template<typename Iter1, typename Iter2>
void
apply_permutation(
    Iter1 first,
    Iter1 last,
    Iter2 indices)
{
 using T = std::iterator_traits<Iter1>::value_type;
 using Diff = std::iterator_traits<Iter2>::value_type;
 Diff length = last - first;
 for (Diff i = 0; i < length; i++) {
  Diff current = i;
  if (i != indices[current]) {
   T t{std::move(first[i])};
   while (i != indices[current]) {
    Diff next = indices[current];
    first[current] = std::move(first[next]);
    indices[current] = current;
    current = next;
   }
   first[current] = std::move(t);
   indices[current] = current;
  }
 }
}

Note that we used std::iterator_traits to determine the appropriate types for the indices and the underlying type. This is significant when the iterator returns a proxy type (such as the infamous vector<bool>).

Another observation is that the indices don't have to be in the range [0, N − 1]; as long as we can map the values into that range. But we don't need to generalize that, because that can already be generalized in another way: By creating a custom iterator whose * operator returns a proxy object that does the conversion.

Okay, I think I've run out of things to write about this apply_permutation function. But we'll use it later.

Exercise: Write an apply_inverse_permutation which applies the inverse of the specified permutation: Instead of each element of the indices telling you where the item comes from, it specifies where the item goes to. In other words, if v is a copy of the original vector and v2 is a copy of the result vector, then v2[indices[i]] = v[i].


Comments (3)
  1. ildjarn says:

    Your alias declarations are missing `typename`.

  2. Ben Voigt (Visual Studio and Development Technologies MVP with C++ focus) says:

    iterator_traits has a difference_type, which is what a type alias “Diff” clearly intends. If you really meant to use the value_type corresponding to Iter2, as the code actually does, you need a better name for the type alias. (and I see no reason that locals i and current should be signed, so I agree that difference_type is not actually wanted, just the name is bad)

    1. Hauke Heibel says:

      I did not look it up in the standard, but according to what is described here (https://goo.gl/PZCSYq) for the RandomAccessIterator concept, ‘current’, ‘next’ and ‘i’ should be ‘difference_type’. On a 64bit build, I actually get a warnings when using 32 bit integer indices.

Comments are closed.

Skip to main content