C++ reorder std::vector elements using std::list of pointers

I ran into this problem when I tried to write out an new algorithm to reorder elements in std::vector. The basic idea is that I have std::list of pointters pointing into std::vector in such way that *list.begin() == vector[0], *(++list.begin()) == vector[1] and so on. However, any modifications on list's element positions breaks the mapping. (Including appended pointers) When the mapping is broken the list's elements can be in random order but they point still into correct 开发者_运维百科elements on vector. The task would be to reorder the elements in vector to correct the mapping.

Simplest method to do it (How I have done it now):

• create new empty std::vector and resize it to equal size of the old vector.
• iterate through the list and read elements from the old vector and write them into new vector. Set the pointer to point into new vector's element.
• swap vectors and release the old vector.

Sadly the method is only useful when I need more capacity on the vector. It's inefficient when the current vector holding the elements has enough capacity to store all incoming elements. Appended pointers on the list will point into diffrent vector's storgate. The simple method works for this because it only reads from the pointers.

So I would want to reorder the vector "in place" using constant amount of memory. Any pointer that was not pointing into current vector's storgate are moved to point into current vector's storgate. Elements are simple structures. (PODs) I'll try post an example code when I have time..

What should I do to achieve this? I have the basic idea done, but I'm not sure if it is even possible to do the reordering with constant amount of memory.

PS: I'm sorry for the (possibly) bad grammar and typos in the post. I hope it's still readable. :)

First off, why do you have a list of pointers? You might as well keep indices into the vector, which you can compute as std::distance(&v[0], *list_iter). So, let's build a vector of indices first, but you can easily adapt that to use your list directly:

std::vector<T> v;        // your data
std::list<T*> perm_list; // your given permutation list
std::vector<size_t> perms;

perms.reserve(v.size());
for (std::list<T*>::const_iterator it = perm_list.begin(), end = perm_list.end(); it != end; ++it)
{
  perms.push_back(std::distance(&v[0], *it));
}

(There's probably a way to use std::transform and std::bind, or lambdas, to do this in one line.)

Now to do the work. We simply use the cycle-decomposition of the permutation, and we modify the perms vector as we go along:

std::set<size_t> done;

for (size_t i = 0; i < perms.size(); while(done.count(++i)) {})
{
  T tmp1 = v[i];
  for (size_t j = perms[i]; j != i; j = perms[j])
  {
    T tmp2 = v[j];
    v[j] = tmp1;
    tmp1 = tmp2;

    done.insert(j);
  }
  v[i] = tmp1;
}

I'm using the auxiliary set done to track which indices have already been permuted. In C++0x you would add std::move everywhere to make this work with movable containers.