Effacement de plusieurs objets d'un fichier std :: vector?

Question

Voici mon problème, disons que j'ai un fichier std :: vector avec ints. Disons qu'il a 50,90,40,90,80,60,80.Je sais que j'ai besoin d'enlever les deuxième, cinquième et troisième éléments. Je ne connais pas forcément toujours l'ordre des éléments à enlever, ni combien. Le problème est en effaçant un élément, cela change l'index des autres éléments. Par conséquent, comment pourrais-je les effacer et compenser le changement d'index. (Tri, puis l'effacement linéaire avec un décalage est pas une option)

Merci

Answer 1

J'offre plusieurs méthodes:

1. Une méthode rapide qui ne retient pas l'ordre initial des éléments:

Affectez le dernier élément actuel du vecteur à l'élément à effacer, puis effacez le dernier élément. Cela évitera les gros mouvements et tous les index sauf le dernier resteront constants. Si vous commencez à effacer à l'arrière, tous les index précalculés seront corrects.

void quickDelete(int idx) 
{ 
    vec[idx] = vec.back(); 
    vec.pop_back(); 
} 

Je vois essentiellement une version est codée à la main de l'idiome d'effacement remove a par Klaim ...

2. Une méthode plus lente qui conserve l'ordre initial des éléments: Etape 1: Marquez tous les éléments vectoriels à supprimer, c'est-à-dire avec une valeur spéciale. Cela a O (| indexes pour supprimer |).

Étape 2: Effacer tous les éléments marqués en utilisant v.erase(remove (v.begin(), v.end(), special_value), v.end());. Cela a O (| vecteur v |).

La durée totale d'exécution est donc O (| vector v |), en supposant que la liste d'index est plus courte que le vecteur.

3. Une autre méthode plus lente qui maintient l'ordre initial des éléments:

Utilisation d'un prédicat et enlever si comme décrit dans https://stackoverflow.com/a/3487742/280314. Pour rendre cela efficace et respecter l'exigence de de ne pas "trier puis effacer linéairement avec un décalage", mon idée est d'implémenter le prédicat en utilisant une table de hachage et d'ajuster les index stockés dans la table de hachage Klaim a suggéré.

Answer 2

L'utilisation d'un prédicat et l'algorithme remove_if vous pouvez obtenir ce que vous voulez: voir http://www.cplusplus.com/reference/algorithm/remove_if/

Ne pas oublier d'effacer l'élément (voir remove-erase idiom).

Votre prédicat maintiendra simplement le idx de chaque valeur à supprimer et diminuera tous les index qu'il conserve chaque fois qu'il retourne vrai. Cela dit, si vous pouvez vous permettre simplement de supprimer chaque objet à l'aide de l'idiome remove-erase, simplifiez-vous la vie en le faisant.

Answer 3

Je déplacerais les éléments que vous ne voulez pas voulez effacer à un vecteur temporaire, puis remplacer le vecteur d'origine avec cela.

Answer 4

Effacer les éléments vers l'arrière. En d'autres termes, effacez l'index le plus élevé en premier, puis le plus proche, etc. Vous n'invaliderez pas les itérateurs ou les index précédents, vous pouvez donc simplement utiliser l'approche évidente de plusieurs appels d'effacement.

Answer 5

Est-ce que ce travail:

void DeleteAll(vector<int>& data, const vector<int>& deleteIndices) 
{ 
    vector<bool> markedElements(data.size(), false); 
    vector<int> tempBuffer; 
    tempBuffer.reserve(data.size()-deleteIndices.size()); 

    for (vector<int>::const_iterator itDel = deleteIndices.begin(); itDel != deleteIndices.end(); itDel++) 
     markedElements[*itDel] = true; 

    for (size_t i=0; i<data.size(); i++) 
    { 
     if (!markedElements[i]) 
      tempBuffer.push_back(data[i]); 
    } 
    data = tempBuffer; 
} 

Il est un O (n) opération, peu importe le nombre d'éléments que vous supprimez. Vous pourriez gagner en efficacité en réorganisant le vecteur en ligne (mais je pense que c'est plus lisible).