webentwicklung-frage-antwort-db.com.de

Wählen Sie bestimmte Elemente aus einem Vektor aus

Ich habe einen Vektor v1 und einen booleschen Vektor v2 der gleichen Größe. Ich möchte alle Werte aus v1 löschen, sodass das Parallelelement von v2false ist:

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;

Gibt es einen besseren Weg, dies zu tun?

  • in C++ 03
  • in C++ 11
19
user31264
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());

Im Wesentlichen das gleiche wie bei Ihnen, nur dass es vor Ort funktioniert und keinen zusätzlichen Speicherplatz erfordert. Dies ist im Wesentlichen eine Neuimplementierung von std::remove_if (was direkt direkt zu verwenden wäre, da das von ihm verwendete Funktionsobjekt einen Wert und keinen Index oder Iterator im Container erhält).

20
Igor Tandetnik

In C++ 11 können Sie std::remove_if Und std::erase Mit einem Lambda verwenden. Dies ist das "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())

Und hier ist ein Link dazu, der wie beabsichtigt funktioniert: cpp.sh/57jpc

Wie aus den Kommentaren hervorgeht, gibt es einige Diskussionen darüber, wie sicher es ist, dies auf diese Weise zu tun. Die zugrunde liegende Annahme hier ist, dass std::remove_if das Prädikat auf die Elemente von v1 in der Reihenfolge. anwendet. Dies wird ausdrücklich garantiert. Es ist einfach Staaten :

Das Entfernen erfolgt durch Verschieben (durch Verschieben) der Elemente im Bereich, so dass die Elemente, die nicht entfernt werden sollen, am Anfang des Bereichs erscheinen. Die relative Reihenfolge der verbleibenden Elemente bleibt erhalten und die physische Größe des Containers bleibt unverändert. Iteratoren, die auf ein Element zwischen dem neuen logischen Ende und dem physischen Ende des Bereichs verweisen, sind noch dereferenzierbar, aber die Elemente selbst haben nicht angegebene Werte (gemäß MoveAssignable-Nachbedingung). Auf einen zu entfernenden Aufruf folgt normalerweise ein Aufruf der Löschmethode eines Containers, mit der die nicht angegebenen Werte gelöscht und die physische Größe des Containers an die neue logische Größe angepasst werden.

Jetzt wäre es schwierig, wenn nur ein Forward-Iterator zu einem std::vector Führen würde, um sowohl die Stabilität der Ergebnisse zu gewährleisten als auch das Prädikat nicht in der richtigen Reihenfolge anzuwenden. Aber es ist sicherlich möglich , dies zu tun.

17
aruisdante

Eine remove_if-basierte Alternative ist:

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

Wenn Sie nur eine Ansicht von v1 benötigen, in der einige Elemente übersprungen werden, können Sie vermeiden, v1 zu ändern und etwas wie boost::filter_iterator zu verwenden.

7
manlio

Ich höre dich wie 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 );
    };
  };
};

Das kann nützlich sein. Es benötigt einen .data()-Suporting-Container und gibt dann ein Lambda vom Typ ((Index,E&)->X)->(E&->X) zurück. Das zurückgegebene Lambda konvertiert einen indizierten Elementbesucher in einen Elementbesucher. Art von 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;
}

weil ich hasse die entfernungslöschung idiom im client code.

Nun ist der Code hübsch:

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

Die Einschränkung der Verschiebungen beim Entfernen/Löschen sollte bedeuten, dass das Lambda des Elements an seiner ursprünglichen Position aufgerufen wird.


Wir können dies mit mehr elementaren Schritten tun. Es wird kompliziert in der Mitte ...

Zunächst eine kleine benannte Operator-Bibliothek:

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

Jetzt definieren wir 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;

definiert ein Token then, sodass lambda1 ->*then* lambda2 ein Funktionsobjekt zurückgibt, das seine Argumente an lambda1 übergibt und den Rückgabewert dann an lambda2 übergibt.

Als Nächstes definieren wir to_index(container):

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

wir behalten auch den obigen erase_if.

Das führt zu:

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

Lösen Sie Ihr Problem (Live-Beispiel).

Ich mag die Art und Weise, wie Sie es gemacht haben, aber ich würde ein paar Änderungen vornehmen, um den Gültigkeitsbereich des temporären Vektors zu beschränken, und ich würde std :: vector :: swap verwenden, um eine Kopie am Ende zu vermeiden. Wenn Sie C++11 haben, können Sie std :: move anstelle von std :: vector :: swap verwenden:

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

Eine andere Version, die Elemente an Ort und Stelle löscht, jedoch nicht so viele Schritte erfordert, wie Igor Algo es erfordert, und im Falle einer geringen Anzahl von Elementen, die gelöscht werden sollen, könnte dies effizienter sein:

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

aber dieser algo ist instabil.

2
Slava

Wenn Sie eine list (oder forward_list für C++ 11) anstelle einer vector verwenden, können Sie dies vor Ort tun, ohne den für vector-Vorgänge erforderlichen Verschiebungs-/Zuweisungs-/Kopieraufwand zu verursachen. Es ist durchaus möglich, die meisten Speicherungsaufgaben mit jedem STL-Container zu erledigen. Die Auswahl der Container führt jedoch häufig zu erheblichen Verbesserungen der Leistung.

1
Graham