Выделить определенные элементы из вектора

Question

У меня есть вектор 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; 

Есть ли лучший способ сделать это?

• в C++ 03
• в 11

Answer 1

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

же, как у вас, по существу, за исключением того, что работает на месте, не требующих дополнительного хранения C++. Это в основном повторная реализация std::remove_if (что было бы трудно использовать напрямую, потому что объект функции, который он использует, получает значение, а не индекс или итератор в контейнер).

Answer 2

В C++ 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по порядку. Однако язык в документе явно не гарантирует этого. Это просто states:

Удаление осуществляется путем сдвига (путем уступки перемещения) элементов в диапазоне таким образом, что элементы, которые не должны быть удалены появляются в начале диапазона. Относительный порядок оставшихся элементов сохраняется и физические размеры контейнера не изменяются. Итераторы, указывающие на элемент между новым логическим концом и физическим концом диапазона, все еще разыскиваются, но сами элементы имеют неуказанные значения (в соответствии с пост-условием MoveAssignable). Обычно вызов для удаления сопровождается вызовом метода стирания контейнера, который стирает неуказанные значения и уменьшает физический размер контейнера в соответствии с его новым логическим размером.

Теперь, было бы трудно только с передним итератором к std::vector для обоего гарантийной стабильности результатов и не применять предикат в заказе. Но это, конечно, возможно для этого.

Answer 3

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 ,

Answer 4

Я действительно очень люблю то, как вы это делали, но я бы сделал пару изменений в ограничении области использования временного вектора, и я бы использовал std::vector::swap, чтобы избежать копирования в конце.Если у вас есть C++11 вы могли бы использовать std::move вместо 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 5

Различные версии, стирает элементы на месте, но не требует столько ходов алго Игоря требует и в случае небольшого количества элементов, которые нужно стереть может быть более эффективен:

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

но этот алго нестабилен.

Answer 6

Я слышал, что вы любите лямбды.

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(), затем возвращает лямбда типа ((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]; 
    } 
)); 

ограничение движений в удаление/удалить должны означает, что она вызывает лямбда на элемент в исходное положение.

---

Мы можем сделать это с помощью более элементарных шагов. Это становится сложным в середине ...

Во-первых, крошечная библиотека имени оператора:

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

solving your problem (live example).

Answer 7

Если вы используете list (или forward_list для C++ 11) вместо vector, вы можете сделать это на месте без перемещения/выделение/копирование служебных данных, необходимых для операций vector. Вполне возможно делать большинство связанных с хранилищем вещей с любым контейнером STL, но соответствующий выбор контейнеров часто дает значительные улучшения в производительности.