Re: Remove_if или что-то ещё - C/C++

Есть кусок кода:

     for( std::vector< STATUS >::iterator it = m.begin() ; it != m.end() ; )
     {
          if( it->state == StatusOk )
          {
               it = m.erase( it );
          }
          else
          {
               ++it;
          }
     }

Точно понимаю, что это оптимизируется в нормальный вызов remove_if. Как лучше сделать? А с бустом?

Здравствуйте, Аноним, Вы писали:

А>Есть кусок кода:

А>

А>     for( std::vector< STATUS >::iterator it = m.begin() ; it != m.end() ; )
А>     {
А>          if( it->state == StatusOk )
А>          {
А>               it = m.erase( it );
А>          }
А>          else
А>          {
А>               ++it;
А>          }
А>     }
А>

А>Точно понимаю, что это оптимизируется в нормальный вызов remove_if. Как лучше сделать? А с бустом?

Не знаю, проще ли это:

m.erase( remove_if( m.begin(), m.end(),
     boost::bind(
          std::equal_to< тип, где StatusOk >(),
          boost::bind( &STATUS::state, _1 ), StatusOk )
     ),
     m.end() );

Здравствуйте, Аноним, Вы писали:

А>Есть кусок кода:

А>

А>     for( std::vector< STATUS >::iterator it = m.begin() ; it != m.end() ; )
А>     {
А>          if( it->state == StatusOk )
А>          {
А>               it = m.erase( it );
А>          }
А>          else
А>          {
А>               ++it;
А>          }
А>     }
А>

А>Точно понимаю, что это оптимизируется в нормальный вызов remove_if. Как лучше сделать? А с бустом?

#include <boost/range/algorithm_ext/erase.hpp>

struct STATUS
{
    int state;
};

const int StatusOk = 2;

int main()
{
    std::vector<STATUS> v = {{0},{1},{2},{3}};
    boost::remove_erase_if(v, [](STATUS _e) { return _e.state == StatusOk; });
}

Здравствуйте, Аноним, Вы писали:

А>

А>     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.

Здравствуйте, Аноним, Вы писали:

А>Есть кусок кода:

А>

А>     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. показалось что ТС говорил про автоматическую оптимизацию компилятором

Здравствуйте, andyp, Вы писали:

А>>Точно понимаю, что это оптимизируется в нормальный вызов 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 );

Здравствуйте, night beast, Вы писали:

NB>у себя по старинке индексами обхожусь:
NB>

NB>size_t size = m.size( );
NB>for ( size_t i = 0; i != size; ++i ) {
NB>    if ( m[i].state == StatusOk ) {
NB>        std::swap( m[i--], m[--size] );
NB>    }
NB>}
NB>m.resize( size );
NB>

да я тоже. написал свои срезы и использую оператор индексации. мне так понятнее. оригинальный пример был призван минимизировать diff

Здравствуйте, andyp, Вы писали: ...

Здесь есть одна тонкость. Если требуется сохранить порядок эелементов в массиве, то нужно использовать 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

Подобный алгоритм есть и в его Notes on Programming (я что-то подобное тут уже показывал)

Здравствуйте, 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 и подправил две строки)

	От:	Аноним
	Дата:	17.07.13 07:54
	Оценка:

	От:	BerAn
	Дата:	17.07.13 09:07
	Оценка:

	От:	pzhy
	Дата:	17.07.13 10:25
	Оценка:	+1

	От:	Evgeny.Panasyuk
	Дата:	17.07.13 11:16
	Оценка:	+1

	От:	andyp
	Дата:	17.07.13 13:38
	Оценка:	+2

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	17.07.13 14:36
Оценка:

	От:	Шахтер
	Дата:	18.07.13 19:50
	Оценка:	37 (2)

	От:	Jack128
	Дата:	19.07.13 11:08
	Оценка:	7 (1) +1