Здравствуйте, Аноним, Вы писали:
А>Есть кусок кода:
А>
А> for( std::vector< STATUS >::iterator it = m.begin() ; it != m.end() ; )
А> {
А> if( it->state == StatusOk )
А> {
А> it = m.erase( it );
А> }
А> else
А> {
А> ++it;
А> }
А> }
А>
А>Точно понимаю, что это оптимизируется в нормальный вызов remove_if. Как лучше сделать? А с бустом?
Чтобы вернуться к линейной сложности (как у remove_if) это должно выглядеть как-то так:
std::vector< STATUS >::iterator s = m.end();
for( std::vector< STATUS >::iterator it = m.begin() ; it != s ; )
{
if( it->state == StatusOk )
{
--s; std::swap(*it,*s);
}
else
{
++it;
}
}
m.erase(s,m.end());
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Мне трудно представить что такая квадратичная кака может автоматически оптимизироваться до линейного remove_if.
Толи у меня совсем вечер, толи что... Но где там квадратичная кака? Т.е. каку да, вижу, но квадратичную каку — нет, не виже
Здравствуйте, kaa.python, Вы писали:
EP>>Мне трудно представить что такая квадратичная кака может автоматически оптимизироваться до линейного remove_if. KP>Толи у меня совсем вечер, толи что... Но где там квадратичная кака? Т.е. каку да, вижу, но квадратичную каку — нет, не виже
erase у вектора двигает все элементы после удалённых
P.S. показалось что ТС говорил про автоматическую оптимизацию компилятором
А>>Точно понимаю, что это оптимизируется в нормальный вызов remove_if. Как лучше сделать? А с бустом? A>Чтобы вернуться к линейной сложности (как у remove_if) это должно выглядеть как-то так: A>
A>std::vector< STATUS >::iterator s = m.end();
A>for( std::vector< STATUS >::iterator it = m.begin() ; it != s ; )
A> {
A> if( it->state == StatusOk )
A> {
A> --s; std::swap(*it,*s);
A> }
A> else
A> {
A> ++it;
A> }
A> }
A>m.erase(s,m.end());
A>
у себя по старинке индексами обхожусь:
size_t size = m.size( );
for ( size_t i = 0; i != size; ++i ) {
if ( m[i].state == StatusOk ) {
std::swap( m[i--], m[--size] );
}
}
m.resize( size );
Здесь есть одна тонкость. Если требуется сохранить порядок эелементов в массиве, то нужно использовать remove_if.
А если это не требуется, то нужно использовать partition. Это значительно выгоднее. Твой код не оптимален.
Здравствуйте, Шахтер, Вы писали:
Ш>Здравствуйте, andyp, Вы писали: ...
Ш>Здесь есть одна тонкость. Если требуется сохранить порядок эелементов в массиве, то нужно использовать remove_if. Ш>А если это не требуется, то нужно использовать partition. Это значительно выгоднее. Твой код не оптимален.
Посмотрел на реализацию от MSVC 2010 —
Согласен, remove_if стабилен, но мувов дофига. Согласен и с тем, что partition делает меньше свопов, сразу правильно ставя два элемента. Вобщем, спасибо за совет .
Здравствуйте, Шахтер, Вы писали:
Ш>Здравствуйте, andyp, Вы писали: ...
Ш>Здесь есть одна тонкость. Если требуется сохранить порядок эелементов в массиве, то нужно использовать remove_if. Ш>А если это не требуется, то нужно использовать partition. Это значительно выгоднее. Твой код не оптимален.
Кстати, посмотрел новый стандарт и увидел, что теперь partition должен работать и с ForwardIterator. Только количество swap для них может быть в 2 раза больше (last-first vs (last-first)/2). Кто-то из компиляторов это уже имеет в стандартной библиотеке (у меня msvc 2010 и я от жизни отстал)? С ходу не очень понятно, как написать такой алгоритм, не двигая last. Если есть под рукой стандартная библиотека с новыми алгоритмами, не мог бы ты запостить код оттуда?
Здравствуйте, andyp, Вы писали:
A>Кстати, посмотрел новый стандарт и увидел, что теперь partition должен работать и с ForwardIterator. Только количество swap для них может быть в 2 раза больше (last-first vs (last-first)/2). Кто-то из компиляторов это уже имеет в стандартной библиотеке (у меня msvc 2010 и я от жизни отстал)? С ходу не очень понятно, как написать такой алгоритм, не двигая last. Если есть под рукой стандартная библиотека с новыми алгоритмами, не мог бы ты запостить код оттуда?
Вопрос снимается — вот ответ из книжки Степанова — Elements of programming
template<typename I, typename P>
requires(Mutable(I) && ForwardIterator(I) &&
UnaryPredicate(P) && ValueType(I) == Domain(P))
I partition_semistable(I f, I l, P p)
{
// Precondition: mutable_bounded_range(f, l)
I i = find_if(f, l, p);
if (i == l) return i;
I j = successor(i);
while (true) {
j = find_if_not(j, l, p);
if (j == l) return i;
swap_step(i, j);
}
}
Здравствуйте, Шахтер, Вы писали:
Ш>Здесь есть одна тонкость. Если требуется сохранить порядок эелементов в массиве, то нужно использовать remove_if. Ш>А если это не требуется, то нужно использовать partition. Это значительно выгоднее. Твой код не оптимален.
partition тут избыточен — он делает swap-ы, каждый swap это грубо говоря 3 move'а. В то время как нам достаточно одного move — "хороший" элемент с конца, move'ается на место плохого в начале. Так как в конце нам достаточно destructible элементов.
Здравствуйте, andyp, Вы писали:
A>Вопрос снимается — вот ответ из книжки Степанова — Elements of programming
A>template<typename I, typename P> A> requires(Mutable(I) && ForwardIterator(I) && A> UnaryPredicate(P) && ValueType(I) == Domain(P)) A>I partition_semistable(I f, I l, P p)
Ты только учти две вещи:
1. это semistable алгоритм — первая часть остаётся стабильной, также как и у remove_if
2. значение предиката тут inverted по сравнению с partition в STL — в начале идут false, а в конце true
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Здравствуйте, Шахтер, Вы писали:
Ш>>Здесь есть одна тонкость. Если требуется сохранить порядок эелементов в массиве, то нужно использовать remove_if. Ш>>А если это не требуется, то нужно использовать partition. Это значительно выгоднее. Твой код не оптимален.
EP>partition тут избыточен — он делает swap-ы, каждый swap это грубо говоря 3 move'а. В то время как нам достаточно одного move — "хороший" элемент с конца, move'ается на место плохого в начале. Так как в конце нам достаточно destructible элементов.
Все-таки выяснилось, что для оптимального решения исходной задачи нужно написать разбиение Хоара руками с move
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Здравствуйте, andyp, Вы писали:
A>>Вопрос снимается — вот ответ из книжки Степанова — Elements of programming
A>>template<typename I, typename P> A>> requires(Mutable(I) && ForwardIterator(I) && A>> UnaryPredicate(P) && ValueType(I) == Domain(P)) A>>I partition_semistable(I f, I l, P p)
EP>Ты только учти две вещи: EP>1. это semistable алгоритм — первая часть остаётся стабильной, также как и у remove_if EP>2. значение предиката тут inverted по сравнению с partition в STL — в начале идут false, а в конце true
EP>Подобный алгоритм есть и в его Notes on Programming (я что-то подобное тут уже показывал
Здравствуйте, andyp, Вы писали:
EP>>partition тут избыточен — он делает swap-ы, каждый swap это грубо говоря 3 move'а. В то время как нам достаточно одного move — "хороший" элемент с конца, move'ается на место плохого в начале. Так как в конце нам достаточно destructible элементов. A>Все-таки выяснилось, что для оптимального решения исходной задачи нужно написать разбиение Хоара руками с move
Да, но это только для случая когда стабильность не важна — а в исходной задаче она сохранялась(может конечно не преднамеренно).
И да, в STL есть далеко не все алгоритмы для range'ей, afaik Степанов об этом не раз говорил.
Здравствуйте, Шахтер, Вы писали:
Ш>Здесь есть одна тонкость. Если требуется сохранить порядок эелементов в массиве, то нужно использовать remove_if. Ш>А если это не требуется, то нужно использовать partition. Это значительно выгоднее. Твой код не оптимален.
Есть другая тонкость.
remove_if не обязан помещать удалённые элементы в хвост — в отличие от partition.
То есть, может делать swap, move или даже копирующее присваивание.
А в хвосте оказывается произвольный мусор (валидные, но бесполезные элементы). И всё, что с ними остаётся сделать — это erase.
Выгоднее будет написать unstable_remove / unstable_remove_if
template<class BidirIt, class UnaryPredicate>
BidirIt unstable_remove_if(BidirIt first, BidirIt last, UnaryPredicate p)
{
while (1) {
while ((first != last) && p(*first)) {
++first;
}
if (first == last--) break;
while ((first != last) && !p(*last)) {
--last;
}
if (first == last) break;
*first++ = std::move(*last);//std::swap(*first++, *last);
}
return first;
}
(скопипастил с cppereference.com и подправил две строки)
Здравствуйте, Кодт, Вы писали:
К>Есть другая тонкость. К>remove_if не обязан помещать удалённые элементы в хвост — в отличие от partition. К>То есть, может делать swap, move или даже копирующее присваивание. К>А в хвосте оказывается произвольный мусор (валидные, но бесполезные элементы). И всё, что с ними остаётся сделать — это erase.
К>Выгоднее будет написать unstable_remove / unstable_remove_if
[...]
я тоже думал сейчас сделать такой, но вошёл в цикл поиска нормального названия и не вышел, почему-то в голову лезло только "nonstable" — что казалось слишком некрасиво.
К>(скопипастил с cppereference.com и подправил две строки)
Копипастить нужно Степанова, например с SGI STL или с Notes — потому что, во-первых у него колличество операций оптимизировано, а во-вторых работает:
template<typename I, typename P>
/*
requires
(
Mutable(I) && BidirectionalIterator(I) &&
UnaryPredicate(P) && ValueType(I) == Domain(P)
)
*/
I unstable_remove_if(I first, I last, P p)
{
while (true)
{
while (true)
if (first == last)
return first;
else if (!p(*first))
++first;
else
break;
--last;
while (true)
if (first == last)
return first;
else if (p(*last))
--last;
else
break;
*first = std::move(*last);
++first;
}
}
Код же с cppereference.com на пустом range делает last-- (кстати, они его сами написали или откуда-то взяли?)
Здравствуйте, Кодт, Вы писали:
К>Есть другая тонкость. К>remove_if не обязан помещать удалённые элементы в хвост — в отличие от partition. К>То есть, может делать swap, move или даже копирующее присваивание.
Всё-таки move по-хорошему. Для простых типов -- просто копирование.
К>Выгоднее будет написать unstable_remove / unstable_remove_if
Если не лень написать свой алгоритм -- то да. Разница с partition -- move вместо swap.