Я видел некоторые специальные случаи, когда std::rotate можно было использовать или комбинацию с одним из алгоритмов поиска, но в целом: когда у одного есть вектор из N элементов и он хочет кодировать функцию, например:
void move( int from, int count, int to, std::vector<int>& numbers );
Я думал о создании нового вектора + std::copy или комбинации вставки/стирания, но не могу сказать, что у меня появилось какое-то приятное и элегантное решение.
Всегда важно определить профиль, прежде чем перейти к каким-либо выводам. Сопряженность памяти данных vector может обеспечить значительные преимущества кэширования, которые не поддерживаются контейнерами на основе node. Итак, возможно, вы могли бы попробовать прямой подход:
void move_range(size_t start, size_t length, size_t dst, std::vector<T> & v)
{
const size_t final_dst = dst > start ? dst - length : dst;
std::vector<T> tmp(v.begin() + start, v.begin() + start + length);
v.erase(v.begin() + start, v.begin() + start + length);
v.insert(v.begin() + final_dst, tmp.begin(), tmp.end());
}
В С++ 11 вы переносите итераторы в первой и третьей строках в std::make_move_iterator.
(Требование состоит в том, чтобы dst не лежало внутри [start, start + length), иначе проблема не определена корректно.)
В зависимости от размера вектора и диапазонов, это может быть менее дорогостоящим, чем выполнение копирования/стирания/вставки.
template <typename T>
void move_range(size_t start, size_t length, size_t dst, std::vector<T> & v)
{
typename std::vector<T>::iterator first, middle, last;
if (start < dst)
{
first = v.begin() + start;
middle = first + length;
last = v.begin() + dst;
}
else
{
first = v.begin() + dst;
middle = v.begin() + start;
last = middle + length;
}
std::rotate(first, middle, last);
}
(Предполагается, что диапазоны действительны и не перекрываются.)
Pre-С++ 11 (хотя следующее остается в силе), вы можете получить более эффективные "ходы" для скрытых типов, которые специализируются/перегружают std::swap. Чтобы воспользоваться этим, вам нужно сделать что-то вроде
std::vector<Foo> new_vec;
Foo tmp;
for (/* each Foo&f in old_vec, first section */) {
swap (f, tmp);
new_vec .push_back (tmp);
}
for (/* each Foo&f in old_vec, second section */) {
swap (f, tmp);
new_vec .push_back (tmp);
}
for (/* each Foo&f in old_vec, third section */) {
swap (f, tmp);
new_vec .push_back (tmp);
}
swap (new_vec, old_vec);
Вышеприведенное может также дать хорошие результаты для С++ 11, если Foo имеет оператор перемещения, но не имеет специализированного swap.
Связанные списки или некоторый умный тип последовательности могут работать лучше, если Foo не имеет семантики перемещения или оптимизированной в противном случае swap
Заметим также, что если выше указано в функции
std::vector<Foo> move (std::vector<Foo> old_vec, ...)`
то вы могли бы выполнить всю операцию без копирования чего-либо, даже в С++ 98, но для этого вам понадобится передать по значению и не по ссылке, что противоречит общепринятой прецедентной мудрости.