Effacer efficacement des éléments d'un vecteur standard

En C++, le conteneur standard le plus utilisé et, pour la majorité des opérations, le plus rapide est std::vector. Ce conteneur est extrêmement performant pour le parcours des éléments qu'il contient et les opérations d'ajout et de retrait en fin de conteneur.

Les opérations d'ajout ou de retrait ailleurs qu'en fin de conteneur sont toutefois beaucoup moins rapides, du fait que le substrat de std::vector est un tableau alloué dynamiquement, et du fait que std::vector conserve l'ordre relatif des éléments par ses opérations d'effacement ou d'insertion d'éléments.

Ceci signifie qu'éliminer le premier élément d'un vecteur, dans un cas comme celui ci-dessous, est une opération fort coûteuse (ça ne paraîtra pas ici dû à la petite taille du conteneur mais en pratique, sur de gros vecteurs, ça paraît beaucoup).

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
int main()
{
   using namespace std;
   vector<int> v = { 2, 3, 5, 7, 11 };
   v.erase(begin(v)); // O(n) car décale les éléments restants vers la gauche
   copy(begin(v), end(v), ostream_iterator<int>{cout, " "}); // 3 5 7 11
}

Si le souci du programmeur n'est pas de conserver l'ordre relatif des éléments d'un vecteur, il est par contre possible d'être beaucoup plus performant.

En effet, plutôt que d'effacer un élément puis de décaler tous ceux qui se trouvent à sa droite, opération de complexité $O(n)$, il est possible de permuter l'élément à effacer avec le dernier élément du conteneur puis de faire un pop_back(), donc une opération en fin de conteneur et de complexité $O(1)$. Parfois, procéder ainsi (quitte à trier le vecteur par la suite) peut apporter des gains considérables.

Cette opération, que nous nommerons erase_with_last_swap(), m'a été suggérée par un de mes anciens étudiants (Colin Towle) et se présente comme suit :

template <class C, class It>
   It erase_with_last_swap(C &cont, It it)
   {
      using namespace std;
      // PATCH (DÉBUT)
      if (&(*it) == &(cont.back()))
      {
         cont.pop_back();
         return end(cont);
      }
      // PATCH (FIN)
      swap(*it, cont.back());
      cont.pop_back();
      return it;
   }

Notez la section délimitée par PATCH (DÉBUT) et PATCH (FIN) : elle n'est pas très jolie, et je cherche une manière de m'en débarrasser avec élégance, mais malgré cette petite tare esthétique, cette fonction est nettement plus performante que erase() en général de par leur différence d'ordre de grandeur du point de vue de la complexité algorithmique.

À titre d'illustration, voici un programme de tests comparatifs pour montrer comment résoudre un même problème avec les deux approches. Retenez que, pour un vecteur v et un itérateur itt donnés, v.erase(itt) est de complexité linéaire mais préserve l'ordre relatif des éléments restants du conteneur, alors que erase_with_last_swap(v,itt) est de complexité constante mais ne préserve pas l'ordre des éléments dans la séquence (itt..v.end()(.

Le code de test suit. Il utilise des conteneurs remplis d'une alternance de nombres pairs et impairs, dont il retire les éléments pairs. L'algorithme est précisément le même dans chaque cas, au code de suppression d'un élément près.

#include <vector>
#include <algorithm>
#include <iostream>
#include <chrono>
#include <numeric>
template <class C, class It>
   It erase_with_last_swap(C &cont, It it)
   {
      using namespace std;
      // PR+ PATCH
      if (&(*it) == &(cont.back()))
      {
         cont.pop_back();
         return end(cont);
      }
      // PR- PATCH
      swap(*it, cont.back());
      cont.pop_back();
      return it;
   }

void tests(std::vector<int>::size_type n)
{
   using namespace std;
   using namespace std::chrono;
   auto est_pair = [](int n) { return n % 2 == 0; };
   {
      vector<int> v(n);
      iota(begin(v), end(v), 0);
      auto avant = system_clock::now();
      for (auto it = find_if(begin(v), end(v), est_pair);
           it != end(v);
           it = find_if(itt, end(v), est_pair))
         it = v.erase(it); // O(n), et invalide tous les itérateurs
      auto apres = system_clock::now();
      cout << "Temps requis pour enlever tous les entiers pairs entre 0 et "
           << n << " d'un vector<int>: "
           << duration_cast<milliseconds>(apres-avant) << " ms. ("
           "avec vector<int>::erase"
           ")" << endl;
   }
   {
      vector<int> v(n);
      iota(begin(v), end(v), 0);
      auto avant = system_clock::now();
      for (auto it = find_if(begin(v), end(v), est_pair);
           it != end(v);
           it = find_if(itt, end(v), est_pair))
         it = erase_with_last_swap(v, it); // O(1), n'invalide rien
      auto apres = system_clock::now();
      cout << "Temps requis pour enlever tous les entiers pairs entre 0 et "
           << n << " d'un vector<int>: "
           << duration_cast<milliseconds>(apres-avant) << " ms. ("
           "avec erase_with_last_swap()"
           ")" << endl;
   }
}

int main()
{
   enum { N = 1000000 };
   for (int i = 1; i <= N; i *= 10)
      tests(i);
}

Les résultats à l'exécution sur mon petit ordinateur portable vont comme suit. Ce qui importe n'est pas tant les chiffres eux-mêmes que l'ordre de grandeur de la différence entre les chiffres dans chaque cas.

Temps requis pour enlever tous les entiers pairs entre 0 et 1 d'un vector<int>: 0 ms. (avec vector<int>::erase)
Temps requis pour enlever tous les entiers pairs entre 0 et 1 d'un vector<int>: 0 ms. (avec erase_with_last_swap())
Temps requis pour enlever tous les entiers pairs entre 0 et 10 d'un vector<int>: 0 ms. (avec vector<int>::erase)
Temps requis pour enlever tous les entiers pairs entre 0 et 10 d'un vector<int>: 0 ms. (avec erase_with_last_swap())
Temps requis pour enlever tous les entiers pairs entre 0 et 100 d'un vector<int> : 0 ms. (avec vector<int>::erase)
Temps requis pour enlever tous les entiers pairs entre 0 et 100 d'un vector<int> : 0 ms. (avec erase_with_last_swap())
Temps requis pour enlever tous les entiers pairs entre 0 et 1000 d'un vector<int>: 1 ms. (avec vector<int>::erase)
Temps requis pour enlever tous les entiers pairs entre 0 et 1000 d'un vector<int>: 0 ms. (avec erase_with_last_swap())
Temps requis pour enlever tous les entiers pairs entre 0 et 10000 d'un vector<int>: 17 ms. (avec vector<int>::erase)
Temps requis pour enlever tous les entiers pairs entre 0 et 10000 d'un vector<int>: 0 ms. (avec erase_with_last_swap())
Temps requis pour enlever tous les entiers pairs entre 0 et 100000 d'un vector<int>: 2362 ms. (avec vector<int>::erase)
Temps requis pour enlever tous les entiers pairs entre 0 et 100000 d'un vector<int>: 1 ms. (avec erase_with_last_swap())
Temps requis pour enlever tous les entiers pairs entre 0 et 1000000 d'un vector<int>: 480236 ms. (avec vector<int>::erase)
Temps requis pour enlever tous les entiers pairs entre 0 et 1000000 d'un vector<int>: 11 ms. (avec erase_with_last_swap())

On ne peut que constater l'ordre de grandeur. Quand la perte d'ordre relatif entre les éléments ne pose pas de problème, l'avantage d'erase_with_last_swap() sur erase() est considérable.

Variante plus simple

En 2015, dans un courriel, Aymeric Pelle a proposé ce qui suit, et qui a essentiellement le même comportement que la fonction erase_with_last_swap(), mais en plus simple encore (et toujours de complexité $O(1)$) :

//
// précondition: !v.empty()
//
template <class C, class It>
   auto unstable_erase(C &v, It it) -> typename C::iterator 
   {
      *it = std::move(v.back());
      v.pop_back();
      return it;
   }

Charmant!

Quelques exercices

Pour vous amuser, je vous invite à faire quelques expériences :

• Ajoutez un test semblable sur une std::list<int>. Où se situent les performances de ce conteneur si on applique les mêmes tests que sur un std::vector<int>?
• Est-ce que les types dans le conteneur influencent les résultats des tests? Essayez avec des conteneurs de std::string par exemple, et comparez les résultats obtenus;
• Qu'en est-il d'un std::deque<int>?