C ++ переупорядочить элементы std :: vector, используя указатели std :: list

Question

Я столкнулся с этой проблемой, когда попытался написать новый алгоритм для изменения порядка элементов в std :: vector. Основная идея состоит в том, что у меня есть std :: список указателей, указывающих на std :: vector таким образом, что *list.begin() == vector[0], *(++list.begin()) == vector[1] и так далее. Однако любые изменения в позициях элементов списка нарушают отображение. (Включая добавленные указатели) Когда отображение нарушено, элементы списка могут быть в произвольном порядке, но они по-прежнему указывают на правильные элементы на векторе. Задача состоит в том, чтобы переупорядочить элементы в векторе, чтобы исправить отображение.

Самый простой способ сделать это (Как я это сделал сейчас):

• создайте новый пустой std :: vector и измените его размер до размера старого вектора.
• переберите список, прочитайте элементы из старого вектора и запишите их в новый вектор. Установите указатель так, чтобы он указывал на элемент нового вектора.
• поменяйте местами векторы и освободите старый вектор.

К сожалению, этот метод полезен только тогда, когда мне нужно больше возможностей для вектора. Это неэффективно, когда текущий вектор, содержащий элементы, имеет достаточную емкость для хранения всех входящих элементов. Добавленные указатели в списке будут указывать на косяк другого вектора. Простой метод работает для этого, потому что он читает только из указателей.

Так что я бы хотел переупорядочить вектор «на месте», используя постоянный объем памяти. Любой указатель, который не указывал на сторгат текущего вектора, перемещается так, чтобы указывать на сторгат текущего вектора. Элементы - это простые структуры. (стручки) Я постараюсь опубликовать пример кода, когда у меня будет время ..

Что я должен сделать, чтобы достичь этого? У меня есть основная идея, но я не уверен, возможно ли вообще выполнить переупорядочение с постоянным объемом памяти.

---

PS: Извините за (возможно) плохую грамматику и опечатки в посте. Я надеюсь, что это все еще читабельно. :)

Answer 1

Во-первых, почему у вас есть список указателей? Вы можете также сохранить индексы в векторе, который вы можете вычислить как std::distance(&v[0], *list_iter). Итак, давайте сначала создадим вектор индексов, но вы можете легко адаптировать его для непосредственного использования списка:

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));
}

(Вероятно, есть способ использовать std::transform и std::bind, или лямбды, чтобы сделать это в одной строке.)

Теперь, чтобы сделать работу. Мы просто используем циклическое разложение перестановки и модифицируем вектор perms по мере продвижения:

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;
}

Я использую вспомогательный набор done, чтобы отслеживать, какие индексы уже переставлены. В C ++ 0x вы бы добавили std::move везде, чтобы это работало с подвижными контейнерами.