C++ und Liste mit "Sieb"-Feature

[mekakic]

Hallo,

Ich hab eine Liste mit Elementen und möchte dort iterativ Elemente heraussieben bzw. filtern. Und wenn möglich relativ performant (Bzw. ich möchte negativ sieben aber das ist ja egal) und ohne viel Kopiererei... momentan kopiere ich viel; die listen sind riesig und die Performance schrecklich. Ich überlege schon das selber zu machen aber etwas derartiges muß doch auch existieren (STL, boost, ...)? Ich kenne das zumindest als klassische Listenoperation in einigen funktionalen Programmiersprachen.

Die genaue Implementierung des Filters, wäre eine Sache des Compare Operators... mir geht es darum irgendwie Elemente in einer sehr großen Liste nichtdestruktiv zu taggen (gehört das Element zur aktuellen Menge oder nicht)... und weitere Operationen beruhen dann bis zu einem reset immer auf der gefilterten Liste.

In etwa so:

list<linedb_t> mylist;
size_t sz=mylist.size(); //20000 elemente
mylist.filter("identifier_str1");
sz=mylist.size(); //500 elemente
mylist.filter("identifier_str2");
sz=mylist.size(); //50
mylist.filter("identifier_str3");
sz=mylist.size(); //3 Elemente
for(auto it=mylist.begin();it!=mylist.end();++it) {
/// 1,2,3
}

mylist.clear_filter();
sz=mylist.size(); //20000 Elemente
Am Ende hab ich dann noch drei Elemente übrig, auf die alle Kritierien zutreffen "identifier_str1", "identifier_str2" und "identifier_str3" und zu diesem Punkt ist man iterativ gekommen... eine Filterung aller Ausdrücke zu einem Zeitpunkt geht nicht. Und auch die Anzahl der Ausdrücke ist variabel... irgendwann weiß man eben dass man fertig ist. Geht sowas bzw. gibt es da "schlüsselfertige" Datenstrukturen für C++ für?


Danke!!

[Gast_samm]

Top of my head, korrekte Syntax müsstest du forschen ;) Du könntest dir folgendes Basteln:

std::list<std::function<bool (object)>> filterList;

Die füllen mit deinen Filtern à la

static std::function<bool (object)> someFilter = { x, equals("identifier_str1") };

Darüber iterieren und folgendermassen filtern:

mylist.remove_if (http://en.cppreference.com/w/cpp/container/list/remove)(mylist->front, mylist->back, [this](linedb_t currentLine)
{
for(function<bool (object)> currentFilter : filterList)
if(!currentFilter(currentLine))
return true;
});

Arbeite momentan mit C#, wo es das bequemere LINQ gibt, insofern keine Garantie auf das obige Geschreibe, aber vielleicht gibt es dir einen Anhaltspunkt :)

[mekakic]

Danke... ich habe es getestet und mittles remove_if ist es ein Stück flotter als meine jetzige Implementierung aber immernoch viel zu langsam. Ein richtiges Remove brauch (und will) ich ja eigentlich auch nicht. Es ist ja mehr eine Filterung.

Ich überlege ob ich da einfach eine std::list überschreibe, mit ein bitfeld dazuhole für die Elementanzahl, die Fitleroperationen als Vergleich bzw. Bitfeldoperationen hinzufüge und den iterator müßte ich noch den ++operator überschreiben, dass er bei einem increment nicht gesetzt Felder überspringt (bis zum nächsten oder bis zum Ende).

EDIT: mir fällt gerade ein... man soll IIRC doch nicht von STL Containern erben. Naja... ein Komposition würde ja auch gehen... mach aber mehr Arbeit.

[mekakic]

Das könnte sein was ich suche:
http://www.boost.org/doc/libs/1_39_0/libs/iterator/doc/filter_iterator.html