c++ - valores - Seleccionar elementos específicos de un vector

seq en r

Question

Tengo un vector v1 y un vector booleano v2 del mismo tamaño. Quiero eliminar de v1 todos los valores, de modo que el elemento paralelo de v2 sea 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;

Hay una mejor manera de hacerlo?

• en C ++ 03
• en C ++ 11

Answer 1

De hecho, me gusta bastante la forma en que lo hizo, pero haría un par de cambios para limitar el alcance del uso del vector temporal y usaría std::vector::swap para evitar una copia al final. Si tienes C++11 puedes usar std::move lugar de std::vector::swap :

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

Answer 2

En C ++ 11 puedes usar std::remove_if y std::erase con un lambda, que es el "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())

Y aquí hay un enlace para que funcione según lo previsto: cpp.sh/57jpc

Sin embargo, como señalan los comentarios, hay un poco de discusión sobre la seguridad de hacerlo de esta manera; La suposición subyacente aquí es que std::remove_if aplicará el predicado a los elementos de v1 en orden. Sin embargo, el lenguaje en el documento no garantiza explícitamente esto. Simplemente states :

La eliminación se realiza desplazando (mediante la asignación de movimiento) los elementos en el rango de tal manera que los elementos que no se deben eliminar aparezcan al principio del rango. El orden relativo de los elementos que permanecen se conserva y el tamaño físico del contenedor no se modifica. Los iteradores que apuntan a un elemento entre el nuevo extremo lógico y el extremo físico del rango aún no se pueden referenciar, pero los elementos en sí tienen valores no especificados (según la condición posterior de MoveAssignable). Una llamada a eliminar suele ir seguida de una llamada al método de borrado de un contenedor, que borra los valores no especificados y reduce el tamaño físico del contenedor para que coincida con su nuevo tamaño lógico.

Ahora, sería difícil con solo un iterador directo a un std::vector para garantizar la estabilidad de los resultados y no aplicar el predicado en orden. Pero ciertamente es posible hacerlo.

Answer 3

Si usa una list (o forward_list para C ++ 11) en lugar de un vector , puede hacer esto in situ sin la sobrecarga de movimiento / asignación / copia requerida para vector operaciones de vector . Es perfectamente posible hacer la mayoría de las cosas relacionadas con el almacenamiento con cualquier contenedor STL, pero la elección adecuada de los contenedores a menudo proporcionará mejoras significativas en el rendimiento.

Answer 4

Te escucho como lambdas.

auto with_index_into = [](auto&v){
  return [&](auto&& f){
    return [&,f=decltype(f)(f)](auto& e){
      return f( std::addressof(e)-v.data(), e );
    };
  };
};

Esto puede ser útil. Toma un contenedor de soporte de .data() , luego devuelve un lambda de tipo ((Index,E&)->X)->(E&->X) - el lambda devuelto convierte un visitante de elemento indexado en un visitante de elemento. Una especie de lambda judo.

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

porque odio la eliminación de borrar idioma en el código del cliente.

Ahora el código es bonito:

erase_if( v1, with_index_into(v1)(
  [](std::size_t i, auto&e){
    return !v2[i];
  }
));

La restricción de movimientos en eliminar / borrar debe significar que invoca a la lambda en el elemento en su posición original.

Podemos hacer esto con más pasos elementales. Se complica en el medio ...

En primer lugar, pequeña biblioteca de operadores con nombre:

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

Ahora definimos 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;

que define un token, then tal que lambda1 ->*then* lambda2 devuelve un objeto de función que toma sus argumentos, lo pasa a lambda1, luego pasa el valor de retorno a lambda2.

A continuación definimos to_index(container) :

template<class C>
auto index_in( C& c ) {
  return [&](auto& e){
    return std::addressof(e)-c.data();
  };
}

También mantenemos lo anterior en erase_if .

Esto resulta en:

erase_if( v1,
  index_in(v1)
  ->*then*
  [&](auto i){
    return !v2[i];
  }
);

resolviendo tu problema (ejemplo vivo).

Answer 5

Una alternativa basada en remove_if es:

v1.erase(std::remove_if(v1.begin(), v1.end(),
                        [&v1, &v2](const int &x){ return !v2[&x - &v1[0]]; }),
         v1.end());

También considera que si solo necesitas una vista en v1 en la que se omiten algunos elementos, puedes evitar modificar v1 y usar algo como boost::filter_iterator .

Answer 6

Una versión diferente que borra elementos en su lugar pero no requiere tantos movimientos como requiere Igor y, en caso de que se borre una pequeña cantidad de elementos, podría ser más eficiente:

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

pero este algo es inestable.

Answer 7

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

Básicamente, es igual que el suyo, excepto que funciona en el lugar y no requiere almacenamiento adicional. Esto es básicamente una reimplementación de std::remove_if (que sería difícil de usar directamente, porque el objeto de función que usa tiene un valor, no un índice o iterador en el contenedor).