Pourquoi std::list::reverse a-t-il une complexité O(n) ?

Question

Pourquoi la fonction inverse pour le std::list de la bibliothèque standard C++ ont un temps d'exécution linéaire ? Je pense que pour les listes doublement liées, la fonction inverse aurait dû être O(1).

Pour inverser une liste doublement liée, il suffit de permuter les pointeurs de tête et de queue.

Answer 1

Hypothétiquement, reverse aurait pu être O(1) . Il aurait pu y avoir (encore une fois hypothétiquement) un membre booléen de la liste indiquant si la direction de la liste liée est actuellement la même ou opposée à celle d'origine où la liste a été créée.

Malheureusement, cela réduirait les performances de pratiquement toutes les autres opérations (sans toutefois modifier le temps d'exécution asymptotique). Dans chaque opération, un booléen devrait être consulté pour déterminer s'il faut suivre le pointeur "next" ou "prev" d'un lien.

Comme cette opération était vraisemblablement considérée comme relativement peu fréquente, la norme (qui ne dicte pas les implémentations, mais seulement la complexité), spécifiait que la complexité pouvait être linéaire. Cela permet aux pointeurs "next" de toujours signifier la même direction sans ambiguïté, ce qui accélère les opérations courantes.

Answer 2

Il pourrait être O (1) si la liste contient un indicateur qui permet d'intervertir le sens de l'expression " prev " et " next Chaque nœud a des pointeurs ". Si l'inversion de la liste est une opération fréquente, un tel ajout pourrait être en fait utile et je ne vois aucune raison pour laquelle l'implémenter serait une erreur. interdit par la norme actuelle. Cependant, l'existence d'un tel indicateur rendrait les traversée de la liste plus cher (ne serait-ce que par un facteur constant) parce qu'au lieu de

current = current->next;

dans le operator++ de l'itérateur de liste, on obtiendrait

if (reversed)
  current = current->prev;
else
  current = current->next;

ce qui n'est pas quelque chose que l'on décide d'ajouter facilement. Étant donné que les listes sont généralement parcourues beaucoup plus souvent qu'elles ne sont inversées, il serait très imprudent que la norme prévoie de mandat cette technique. Par conséquent, l'opération inverse peut avoir une complexité linéaire. Notez cependant que t ∈ O (1) ⇒ t ∈ O ( n ) donc, comme mentionné précédemment, la mise en œuvre de votre "optimisation" serait techniquement autorisée.

Si vous venez d'un environnement Java ou similaire, vous pouvez vous demander pourquoi l'itérateur doit vérifier le drapeau à chaque fois. Ne pourrait-on pas plutôt avoir deux types d'itérateurs distincts, tous deux dérivés d'un type de base commun, et avoir std::list::begin et std::list::rbegin retourner polymorphiquement l'itérateur approprié ? Bien que cela soit possible, cela rendrait l'ensemble encore pire parce que l'avancement de l'itérateur serait maintenant un appel de fonction indirect (difficile à mettre en ligne). En Java, vous payez ce prix régulièrement, mais c'est l'une des raisons pour lesquelles de nombreuses personnes choisissent le C++ lorsque les performances sont critiques.

Comme l'a souligné Benjamin Lindley dans les commentaires, puisque reverse n'est pas autorisé à invalider les itérateurs, la seule approche autorisée par la norme semble être de stocker un pointeur vers la liste à l'intérieur de l'itérateur, ce qui entraîne un accès doublement indirect à la mémoire.

Answer 3

Étant donné que tous les conteneurs qui supportent les itérateurs bidirectionnels ont le concept de rbegin() et rend(), cette question est sans objet ?

Il est trivial de construire un proxy qui inverse les itérateurs et d'accéder au conteneur par ce biais.

Cette non-opération est en effet O(1).

comme :

#include <iostream>
#include <list>
#include <string>
#include <iterator>

template<class Container>
struct reverse_proxy
{
    reverse_proxy(Container& c)
    : _c(c)
    {}

    auto begin() { return std::make_reverse_iterator(std::end(_c)); }
    auto end() { return std::make_reverse_iterator(std::begin(_c)); }

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); }

    Container& _c;
};

template<class Container>
auto reversed(Container& c)
{
    return reverse_proxy<Container>(c);
}

int main()
{
    using namespace std;
    list<string> l { "the", "cat", "sat", "on", "the", "mat" };

    auto r = reversed(l);
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));

    return 0;
}

résultat attendu :

mat
the
on
sat
cat
the

Dans ces conditions, il me semble que le comité de normalisation n'a pas pris le temps d'imposer l'ordre inverse O(1) du conteneur parce que ce n'est pas nécessaire, et la bibliothèque standard est largement construite sur le principe de n'imposer que ce qui est strictement nécessaire tout en évitant la duplication.

C'est juste mon avis.

Answer 4

Parce qu'il doit traverser chaque nœud ( n total) et mettent à jour leurs données (l'étape de mise à jour est en effet O(1) ). Cela rend l'ensemble de l'opération O(n*1) = O(n) .

Answer 5

Seulement une explication de l'algorithme. Imaginez que vous avez un tableau avec des éléments, puis vous avez besoin de l'inverser. L'idée de base est d'itérer sur chaque élément en changeant l'élément sur la première position à la dernière position, l'élément sur la deuxième position à l'avant-dernière position, et ainsi de suite. Lorsque vous arrivez au milieu du tableau, vous aurez changé tous les éléments, donc en (n/2) itérations, ce qui est considéré comme O(n).