Löschen von Elementen aus vector durch vector mit Indices

Toasti

Hallo,

in Matlab habe ich häufiger häufiger mal die Funktion gebraucht, Elemente aus einem Vektor zu löschen, deren Indices in einem anderen Vektor spezifiziert sind. Beispiel:

a = [1, 2, 3, 4, 5, 6]
b = [3, 1, 5]

zum Löschen des 3., 1. und 5. Elements aus a:
a(b) = []

hat zur Folge:
a = [2, 4, 6]

Jetzt möchte ich diese Funktion gerne in C++ implementieren. Aber meine bisherige Lösung scheint mir nicht effizient:

void erase_by_indices(vector<int>& datavec, vector<size_t>& indices) {
	sort(indices.begin(), indices.end(), bigger);
	for(vector<size_t>::const_iterator iter = indices.begin(); iter != indices.end(); ++iter)
		datavec.erase(datavec.begin() + *iter);
}

bool bigger(int a, int b) {return a > b;}

Was mich stört ist der notwendige Aufruf der sort()-Funktion, wenn die Indices nicht schon von vornherein der Reihenfolge nach sortiert sind.

Die Containerklasse des Datenvektors ist im Prizip als vector vorgegeben, es sei denn, eine andere Containerklasse wäre viel effizienter. Die Containerklasse des Indexvektors wäre egal, könnte also auch list sein.

Ich habe wirklich lange im Internet geschaut, ob es irgendwelche anderen Lösungen zu diesem Problem gibt. I.d.R. geht es aber dann darum, Elemente bestimmter Werte zu löschen, nicht Elemente an bestimmten Positionen.

Gruß, Thorsten

Dravere

Darf die Reihenfolge in datavec verändert werden? Und in indices gibt es keine doppelten Indizes? Wenn zweimal ja:

#include <algorithm>

// ...

void eraseByIndices(vector<int>& datavec, vector<size_t> const& indices)
{
    vector<int>::reverse_iterator riter = datavec.rbegin();

    vector<size_t>::const_iterator indexIter = indices.begin();
    vector<size_t>::const_iterator indexEnd = indices.end();

    for(; indexIter != indexEnd; ++IndexIter, ++riter)
    {
        std::iter_swap(datavec.begin() + *indexIter, riter);
    }

    datavec.erase(riter.base(), datavec.end());
}

Wieso dieses ganze herumgeschubse? Weil man nur am Ende eines std::vector effizient löschen kann. Wenn Elemente nach dem Element kommem, welches gelöscht wurde, dann müssen diese alle umkopiert werden. Durch die swap Aufrufe wird dafür gesorgt, dass die Elemente, welche gelöscht werden müssen, am Ende liegen.

Ansonsten fällt mir keine performante Art ein, wie man Elemente in der Mitte eines std::vector herauslöschen kann. Dafür ist std::vector einfach nicht gedacht.

std::list ist dafür da, um in der Mitte auch effizient Elemente rauslöschen zu können. Nur ist std::list nicht dafür da, einen performanten Indexzugriff zu geben.

Vielleicht wäre es aber auch an der Zeit dein Design zu überdenken. Matlab und C++ sind nunmal zwei ziemlich unterschiedliche Sprachen, da geht man Dinge auch unterschiedlich an.

Grüssli

camper

Wenn wenigstens ein Wert in a nicht vorkommt, können wir das eine Problem auf das andere zurückführen

void erase_by_indices(vector<int>& datavec, const vector<size_t>& indices) {
    const int erasure_token = -1;
    for(vector<size_t>::const_iterator iter = indices.begin(); iter != indices.end(); ++iter)
        datavec[*iter] = erasure_token;
    datavec.erase(remove(datavec.begin(),datavec.end(),erasure_token),datavec.end());
}

Andernfalls käme noch die Verwendung eines zusätzlichen Containers (vector<bool> o.ä.) in Betracht, der zunächst mal nur speichert, welche Positionen zu löschen sind. Auf diese Weise erreichen wir sicher lineare Komplexität.
Der sort-Ansatz ist furchtbar schlimm wahrscheinlich auch nicht, äußerst ineffizient ist allerdings die erase-Methode, hier wird künstlich quadratische Komplexität eingeführt, obwohl es linear sein sollte.

struct is_indexed : unary_function<int,bool> {
    std::vector<size_t>::const_iterator index_first,index_last;
    int* data_begin;
    is_indexed(vector<int>& data, const vector<size_t>& indices)
      : index_first(indices.begin()),index_last(indices.end()),data_begin(&*data.begin())
    {}
    bool operator()(int& i) const {
        if ( index_first == index_last || &i - data_begin != *index_first )
            return false;
        ++index_first;
        return true;
    }
};
void erase_by_indices(vector<int>& datavec, vector<size_t>& indices) {
    sort(indices.begin(), indices.end());
    datavec.erase(remove_if(datavec.begin(),datavec.end(),is_indexed(datavec,indices)),datavec.end())    
}

Badestrand

Es könnte unter bestimmten Umständen für die CPU-Zeit performanter sein, die nicht zu löschenden Elemente in einen neuen vector zu kopieren anstatt in dem eigentlichen herumzulöschen. Kommt wahrscheinlich auf das Verhältnis datavec.size/indices.size und die Art der Objekte an.
Also dann

void erase_by_indices(vector<int>& datavec, vector<size_t>& indices) {
    vector<int> new_one;
    new_one.reserve( datavec.size() - indices.size() );
    sort(indices.begin(), indices.end());
    // TODO: Alle nicht zu löschenden Elemente rüberkopieren
    datavec.swap( new_one );
}

edit: Lässt sich eventuell auch gut mit "I.d.R. geht es aber dann darum, Elemente bestimmter Werte zu löschen, nicht Elemente an bestimmten Positionen." kombinieren.

camper

@Dravere: auch bei dir muss indices (umgekehrt) sortiert sein, andernfalls kann es vorkommen, dass nur 2 zu löschende Elemete vertauscht werden.
data={1,2,3,4}
indices={2,4};
führt sonst zu {1,4) statt (1,3)

Dravere

@camper,
Hast recht. Hmmm, eindeutig zu spät und nun ist es sogar bald 3 Uhr. Ich sollte ins Nest

Ich bleibe aber bei der Aussage, dass es vielleicht lohnenswert wäre, das Design zu überdenken.

Grüssli

Toasti schrieb:

in Matlab habe ich häufiger häufiger mal die Funktion gebraucht, Elemente aus einem Vektor zu löschen, deren Indices in einem anderen Vektor spezifiziert sind. Beispiel:

a = [1, 2, 3, 4, 5, 6]
b = [3, 1, 5]

zum Löschen des 3., 1. und 5. Elements aus a:
a(b) = []

hat zur Folge:
a = [2, 4, 6]

Ich programmiere auch nebenbei in Matlab. Das ist allerdings eine ganz andere Denke. Um performante Matlab programme zu schreiben, muss man auf eingebaute Funktionen setzen, die auf Vektoren und Matritzen arbeiten. Ich kann mir vorstellen, dass Du hier das Index-Array über find(...) bekommst. Statt

% Matlab für alle ungeraden Elemente rausschmeißen  
  idx = find(mod(a,2)==1); a(idx) = [];

würde ich in C++ etwas völlig anderes machen

// Bestimmte Elemente aus vector a entfernen
  a.erase(
    remove_if(a.begin(), a.end(), is_odd()),
    a.end());

wobei is_odd dann so etwas wie das hier ist

struct is_odd : std::unary_function<int,bool> {
    bool operator()(int x) {return x & 1;}
  };

Ich schätze die Motivation C++ zu benutzen ist die, dass es schneller läuft. Dann solltest Du auch so einige Matlab-Angewohnheiten ablegen. In Matlab legt man häufig unnötige Vektoren, Matritzen an (wie "idx"). In Matlab ist das noch sinnvoll, da ein manuelles durchlaufen des Vektors viel zu langsam ist.

Toasti schrieb:

Jetzt möchte ich diese Funktion gerne in C++ implementieren. Aber meine bisherige Lösung scheint mir nicht effizient:

Wie gesagt. Versuch Dich von der Matlab-Denke zu entfernen. Wenn Du die Matlab-Funktionen nachbaust, kannst Du gleich Matlab benutzen.

Toasti schrieb:

void erase_by_indices(vector<int>& datavec, vector<size_t>& indices) {
	sort(indices.begin(), indices.end(), bigger);
	for(vector<size_t>::const_iterator iter = indices.begin(); iter != indices.end(); ++iter)
		datavec.erase(datavec.begin() + *iter);
}

bool bigger(int a, int b) {return a > b;}

Ok, das geht viel eleganter mit so etwas wie das hier

// alles über 23 löäschen
  data.erase(
    std::remove_if(
      data.begin(),data.end(),
      std::bind2nd(std::greater<double>(),23)
    ),
    data.end()
  );

Siehe <algorithm> und <functional>

Gruß,
SP

Toasti

Danke für die vielen hilfreichen Hinweise/Antworten!

@Camper: An so etwas wie einen Wert zu "reservieren", der dann als Markierung zur Löschung gebraucht werden kann, habe ich auch schon gedacht. Nur selbst wenn ich davon ausgehe, dass ich nicht alle Werte des Typen (int) brauche, scheint es mir irgendwie unsauber. Die andere Lösung ist wohl besser.

Auf jeden Fall werde ich künftig den Tipp beachten, zu löschende Element erst mal ans Ende zu kopieren.

@Dravere, @SP: Ja mit dem Design... Bin tatsächlich ziemlich Matlab gewöhnt

Was ich einfach ausgedrückt damit bezwecken will ist: Ich schreibe ein GUI das einen eindimensionalen Datenvektor anzeigt. Die Elemente werden nebeneinander angezeigt. Der User soll dann entscheiden dürfen, dass ihm z. B. das 4. 9. 18. usw. Element "nicht gefällt", sodass sie dann gelöscht werden. Der User gibt dafür die Positionen der Elemente die ihm nicht gefallen in Ziffern ein und drückt dann auf einen Button zum Löschen. Da es um max. ca. 100 zu löschende Elemente geht, ist das Sortieren wohl kein Problem.

Im Moment ist es nicht vorgesehen, dass man mit den angzeigten Datenelementen interagieren kann, sie also graphisch zur Löschung markieren. Dann würde ich wohl einfach einen mit dem Datenvektor gleichlangen vector<bool> is_indexed haben, der den Datenvektor filtern kann.

Es ist also nicht ein Problem des Entfernen bestimmter Werte, sondern bestimmter Positionen.

camper

Die remove_if-Variante ohne komplexes Prädikat ist wahrscheinlich verständlicher:

void erase_by_indices(vector<int>& data, vector<size_t>& indices) {
    if (indices.empty())
        return;
    sort(indices.begin(), indices.end());
    std::size_t i = 0;
    for ( ; i + 1 < indices.size(); ++i )
        copy( datavec.begin() + indices[i] + 1, datavec.begin() + indices[i+1], datavec.begin() + indices[i] - i );
    copy( datavec.begin() + indices[i] + 1, datavec.end(), datavec.begin() + indices[i] - i );
    datavec.erase(datavec.end()-i,datavec.end());
}

Auch Draveres Version lässt sich noch verfeinern:

// statt
//         std::iter_swap(datavec.begin() + *indexIter, riter);
datavec[*indexIter]=/*std::move(*/*riter/*)*/;

schließlich wird der Rest am Ende sowieso gelöscht werden. Kein Grund also, swap einzusetzen.