У меня есть вектор v1 и булев вектор v2 того же размера. Я хочу удалить из v1 все значения, чтобы параллельный элемент v2 был false:
vector<int> v3; // assume v1 is vector<int>
for (size_t i=0; i<v1.size(); i++)
if (v2[i])
v3.push_back(v1[i]);
v1=v3;
Есть ли лучший способ сделать это?
size_t last = 0;
for (size_t i = 0; i < v1.size(); i++) {
if (v2[i]) {
v1[last++] = v1[i];
}
}
v1.erase(v1.begin() + last, v1.end());
То же, что и у вас, кроме того, что он работает на месте, не требуя дополнительного хранилища. Это в основном повторная реализация std::remove_if (что было бы трудно использовать напрямую, потому что объект функции, который он использует, получает значение, а не индекс или итератор в контейнер).
В С++ 11 вы можете использовать std::remove_if и std::erase с помощью лямбды, которая является "erase-remove-idiom" :
size_t idx = 0;
v1.erase(std::remove_if(v1.begin(),
v1.end(),
[&idx, &v2](int val){return !v2[idx++];}),
v1.end())
И здесь ссылка на него функционирует по назначению: cpp.sh/57jpc
Однако, как отмечают в комментариях, там немного обсуждается безопасность такого поведения; основное предположение здесь состоит в том, что std::remove_if будет применять предикат к элементам v1 по порядку. Однако язык в документе явно не гарантирует этого. Это просто состояние:
Удаление выполняется путем смещения (посредством назначения перемещения) элементов в диапазоне таким образом, чтобы элементы, которые не должны быть удалены, появлялись в начале диапазона. Относительный порядок оставшихся элементов сохраняется и физические размеры контейнера не изменяются. Итераторы, указывающие на элемент между новым логическим концом и физическим концом диапазона, все еще разыскиваются, но сами элементы имеют неуказанные значения (в соответствии с пост-условием MoveAssignable). Вызов для удаления обычно сопровождается вызовом метода стирания контейнера, который стирает неуказанные значения и уменьшает физический размер контейнера в соответствии с его новым логическим размером.
Теперь было бы сложно, если бы только прямой итератор с std::vector гарантировал стабильность результатов и не применял предикат в порядке. Но это, безусловно, возможно.
A remove_if - альтернатива:
v1.erase(std::remove_if(v1.begin(), v1.end(),
[&v1, &v2](const int &x){ return !v2[&x - &v1[0]]; }),
v1.end());
Также подумайте, что если вам нужно только просмотр v1, в котором некоторые элементы пропущены, вы можете избежать изменения v1 и использовать что-то вроде boost::filter_iterator.
Я слышал, что ты любишь лямбды.
auto with_index_into = [](auto&v){
return [&](auto&& f){
return [&,f=decltype(f)(f)](auto& e){
return f( std::addressof(e)-v.data(), e );
};
};
};
Это может быть полезно. Он принимает контейнер .data() suporting, затем возвращает лямбда типа ((Index,E&)->X)->(E&->X) - возвращенная лямбда преобразует посетителя с индексированным элементом в посетителя элемента. Вид лямбда-дзюдо.
template<class C, class Test>
auto erase_if( C& c, Test&& test) {
using std::begin; using std::end;
auto it=std::remove_if(begin(c),end(c),test);
if (it==end(c)) return false;
c.erase(it, end(c));
return true;
}
потому что я ненавижу удалить стирание идиомы в клиентском коде.
Теперь код довольно:
erase_if( v1, with_index_into(v1)(
[](std::size_t i, auto&e){
return !v2[i];
}
));
Ограничение на перемещение в remove/erase должно означать, что он вызывает лямбду на элементе в исходном положении.
Мы можем сделать это с помощью более элементарных шагов. Он усложняется посередине...
Во-первых, небольшая названная операторская библиотека:
namespace named_operator {
template<class D>struct make_operator{};
enum class lhs_token {
star = '*',
non_char_tokens_start = (unsigned char)-1,
arrow_star,
};
template<class T, lhs_token, class O> struct half_apply { T&& lhs; };
template<class Lhs, class Op>
half_apply<Lhs, lhs_token::star, Op>
operator*( Lhs&& lhs, make_operator<Op> ) {
return {std::forward<Lhs>(lhs)};
}
template<class Lhs, class Op>
half_apply<Lhs, lhs_token::arrow_star, Op>
operator->*( Lhs&& lhs, make_operator<Op> ) {
return {std::forward<Lhs>(lhs)};
}
template<class Lhs, class Op, class Rhs>
auto operator*( half_apply<Lhs, lhs_token::star, Op>&& lhs, Rhs&& rhs )
{
return named_invoke( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
}
template<class Lhs, class Op, class Rhs>
auto operator*( half_apply<Lhs, lhs_token::arrow_star, Op>&& lhs, Rhs&& rhs )
{
return named_next( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
}
}
Теперь определим then:
namespace lambda_then {
struct then_t:named_operator::make_operator<then_t> {} then;
template<class Lhs, class Rhs>
auto named_next( Lhs&& lhs, then_t, Rhs&& rhs ) {
return
[lhs=std::forward<Lhs>(lhs), rhs=std::forward<Rhs>(rhs)]
(auto&&...args)->decltype(auto)
{
return rhs( lhs( decltype(args)(args)... ) );
};
}
}
using lambda_then::then;
который определяет токен then таким образом, что lambda1 ->*then* lambda2 возвращает объект функции, который принимает его аргументы, передает его lambda1, затем передает возвращаемое значение в lambda2.
Далее мы определяем to_index(container):
template<class C>
auto index_in( C& c ) {
return [&](auto& e){
return std::addressof(e)-c.data();
};
}
мы также сохраняем выше erase_if.
Это приводит к:
erase_if( v1,
index_in(v1)
->*then*
[&](auto i){
return !v2[i];
}
);
Мне действительно нравится, как вы это делали, но я бы сделал пару изменений в ограничении области применения временного вектора, и я бы использовал std::vector:: swap, чтобы избежать копирования в конце. Если у вас есть C++11, вы можете использовать std:: move вместо std::vector:: своп:
#include <vector>
#include <iostream>
int main()
{
std::vector<int> iv = {0, 1, 2, 3, 4, 5, 6};
std::vector<bool> bv = {true, true, false, true, false, false, true};
// start a new scope to limit
// the lifespan of the temporary vector
{
std::vector<int> v;
// reserve space for performance gains
// if you don't mind an over-allocated return
// v.reserve(iv);
for(std::size_t i = 0; i < iv.size(); ++i)
if(bv[i])
v.push_back(iv[i]);
iv.swap(v); // faster than a copy
}
for(auto i: iv)
std::cout << i << ' ';
std::cout << '\n';
}
Разная версия, которая стирает элементы на месте, но не требует столько ходов, сколько требует Igor algo, и в случае небольшого количества стираемых элементов может быть более эффективной:
using std::swap;
size_t last = v1.size();
for (size_t i = 0; i < last;) {
if( !v2[i] ) {
--last;
swap( v2[i], v2[last] );
swap( v1[i], v1[last] );
} else
++i;
}
v1.erase(v1.begin() + last, v1.end());
но этот алгоритм нестабилен.
Если вы используете list (или forward_list для С++ 11) вместо vector, вы можете сделать это на месте без затрат на перемещение/распределение/копирование, необходимых для операций vector. Совершенно возможно делать большинство связанных с хранилищем вещей с любым контейнером STL, но соответствующий выбор контейнеров часто дает значительные улучшения в производительности.