3. Liste durchgehen und Elemente löschen

Liste durchgehen und Elemente löschen

  • ?

    guck mal hier:
    http://www.cplusplus.com/reference/algorithm/remove_if/
    http://www.cplusplus.com/reference/stl/vector/erase/

    vecA.erase(std::remove_if(vecA.begin(),vecA.end(),pred),vecA.end());

    (wobei pred ein Funktor ist, welcher für die Elemente in A true liefert genau dann wenn die Elemente gelöscht werden sollen)

    oder hier:
    http://www.cplusplus.com/reference/algorithm/sort/
    http://www.cplusplus.com/reference/algorithm/set_difference/
    http://www.cplusplus.com/reference/std/iterator/back_inserter/

    Es lohnt sich allgemein, die "Mengen" zu sortieren. Wenn Du zB den 2. Vektor sortiert hast kann der Funktor für remove_if eine binäre Suche durchführen statt jedes Element von vecB anzufassen.

    0
  • S

    Führt remove_if automatisch eine Binäre Suche durch, wenn der Vector sortiert ist?
    Ich versuche gerade remove_if zum laufen zu bringen, aber verstehe dieses pred noch nicht.
    Ich habe eine Methdoe IterB->CompareBit(IterA) (Ich kann sie aber beliebig überladen, ich weiß nur nicht wie ich Pred genau schreiben muss)
    Wie kann ich nun diese Methode anstatt Pred nutzen? Oder wie genau hat Pred auszusehen?

    vecA.erase(std::remove_if(vecA.begin(),vecA.end(),pred),vecA.end());

    Tut mir leid für diese elementaren Fragen 😞
    Würde mich trotzdem sehr freuen, wenn mir jemand helfen könnte.

    Viele Grüße,
    Samuirai

    0
  • ?

    Samuirai schrieb:

    Führt remove_if automatisch eine Binäre Suche durch, wenn der Vector sortiert ist?

    remove_if kopiert einfach ein paar Elemente im Vektor um und liefert Dir einen Iterator, der hinter das letzte noch übrig gebliebene Element zeigt. Dahinter steht Datenmüll, welcher mit vector::erase beseitigt werden kann.

    #include <vector>
#include <algorithm>

struct IstUngerade {
  bool operator()(int x) const {
    unsigned y = static_cast<unsigned>(x);
    return (y & 1);
  }
};

int main() {
  std::vector<int> foo;
  foo.push_back(1);
  foo.push_back(2);
  foo.push_back(3);
  foo.push_back(4);
  std::vector<int>::iterator xxx =
    std::remove_if(foo.begin(),foo.end(),IstUngerade());

  //
  //   +---+---+---+---+
  //   | 2 | 4 | 3 | 4 |
  //   +---+---+---+---+
  //   A       A       A
  //   |       |       |
  // begin    xxx     end

  foo.erase(xxx,foo.end());

  //
  //   +---+---+
  //   | 2 | 4 |
  //   +---+---+
  //   A       A
  //   |       | 
  // begin    end
}

    Und das kann man auch gleich in eins machen -- also remove_if und erase schachteln. IstUngerade ist ein sogenannter "Funktor" -- ein Objekt, welches die Funktionsaufruf-Syntax unterstützt -- siehe operator(). Mit IstUngerade() wird ein anonymes Objekt der Klasse erzeugt, welches remove_if übergeben werden kann.

    Die binäre Suche müsstest Du selbst in deinem Funktor erledigen. Dazu bräuchtest Du einen, der sich merken kann, in welchem vector gesucht werden muss. Das ist auch der Vorteil von Funktoren. Sie können sich Dinge merken, die remove_if überhaupt nicht interessiert. ZB so:

    template<typename Iterator>
struct is_in_set {
   Iterator beg, end;

   is_in_set(Iterator b, Iterator e) : beg(b), end(e) {}

   template<typename T>
   bool operator()(T const& value) {
      return std::binary_search(beg,end,value);
   }
};

    Den könnte man das so benutzen:

    void hau_wech_die_scheisse(vector<int> & io, vector<int> const& wech)
{
   is_in_set<vector<int>::const_iterator> pred ( wech.begin(), wech.end() );
   io.erase(
     std::remove_if(io.begin(), io.end(), pred),
     io.end()
   );
}

    (alles ungetestet und eventuell fehlerhaft)

    Wenn Du aber sowieso die Vektoren sortieren darfst, ist es wahrscheinlich am einfachsten, beide zu sortieren und dann einfach std::set_difference zu benutzen. Dafür sind die Algorithmen in <algorithm> ja da ... dass man sie benutzt.

    0
  • S

    Was ist denn die schnellste Methode?
    Ich habe zwei Vectoren, einer mit über über 50 und einer mit über 1000 Elemente.
    Ist set_difference oder remove_if schneller?

    Ich habe das hier versucht, aber wieso geht das nicht?

    // set_difference example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  vector<int> v;  

  vector<int> a; 
  a.push_back(5);
  a.push_back(10);
  a.push_back(15);
  a.push_back(20);
  a.push_back(25);

  vector<int> b; 
  b.push_back(50);
  b.push_back(40);
  b.push_back(30);
  b.push_back(20);
  b.push_back(10);

  sort (a.begin(), a.end()); 
  sort (b.begin(), b.end()); 

  set_difference (a.begin(), a.end(), b.begin(), b.end(), v.begin());

  for(int i=0; i<v.size();++i)
	  cout << v.at(i) << ",";
	cin.get();
	cin.get();
  return 0;
}

    Es kommt kein Compiler Fehler, erst wenn das Programm läuft:
    Debug Assertion Failed! Expression: ...

    0
  • N

    Weil v zu klein ist.

    Wenn Du aus vector<int> v; ein vector<int> v(10); machst, sollte es laufen. In Wirklichkeit natürlich checken, wie groß die anderen Vektoren sind, bevor Du sowas machst.

    0
  • N

    Oder du verwendest als Output-Iterator nicht

    v.begin()

    sondern

    std::back_inserter(v)

    Ebenfalls auf www.cplusplus.com nachzuschlagen.

    0
  • S

    Oh ich dachte das benötigt Vector nicht.
    Ich benutze statt int eine eigene Klasse vector<myClass> und nun kommt der Fehler:

    Fehler 1 error C2512: 'myClass::myClass': Kein geeigneter Standardkonstruktor verfügbar

    Ist denn set_difference schneller als das remove_if?

    Viele Grüße

    Edit:
    Oh, hab den Post über mir übersehen.
    Vielen vielen Dank für eure Mühe. Ich habe jetzt wieder einiges gelernt 😉

    aber noch eine letzte Frage.
    set_difference vs. remove_if bei vectoren mit ca. 1000-5000 Elementen

    0
  • T

    aber noch eine letzte Frage.
    set_difference vs. remove_if bei vectoren mit ca. 1000-5000 Elementen

    Warum nicht einfach testen?

    0
  • S

    Ich hab remove_if noch nicht zum laufen gebracht, und wollte dann einfach schnell nachfragen.

    vector<CBitList> vecA;
vector<CBitList> vecB;
vector<CBitList>::iterator iterA;
vector<CBitList>::iterator iterB;

//[...]

for(iterB = vecB.begin(); iterB != vecB.end(); ++iterB) {
    vecA.erase(std::remove_if(vecA.begin(),vecA.end(),compareBit()),vecA.end());
}

//[...]

struct compareBit() {
  bool operator()(CBitList x) const {
    // Irgendwie x mit vecB, bzw iterB vergleichen
  }
};

    Ich habe versucht compareBit(CBitList) zu machen, aber das scheint nicht zu funktionieren.

    Viele Grüße

    0
  • ?

    Samuirai schrieb:

    Ich hab remove_if noch nicht zum laufen gebracht

    Dann guck Dir nochmal genau meine Antwort von 19:46 Uhr durch. Ich hatte die Lösung mit remove_if skizziert.

    0
Anmelden zum Antworten