La liste est-elle meilleure que le vecteur lorsque nous devons stocker "les n derniers éléments" ?

Question

De nombreuses questions suggèrent qu'il faut toujours utiliser un vecteur, mais il me semble qu'une liste serait plus adaptée au scénario dans lequel nous devons stocker "les n derniers éléments".

Par exemple, disons que nous devons stocker les 5 derniers éléments vus : Itération 0 :

3,24,51,62,37,

Ensuite, à chaque itération, l'élément à l'indice 0 est supprimé, et le nouvel élément est ajouté à la fin :

Itération 1 :

24,51,62,37,8

Itération 2 :

51,62,37,8,12

Il semble que pour ce cas d'utilisation, pour un vecteur, la complexité sera O(n), puisque nous devrions copier n éléments, mais dans une liste, elle devrait être O(1), puisque nous ne faisons que couper la tête, et ajouter à la queue à chaque itération.

Ma compréhension est-elle correcte ? Est-ce le comportement réel d'une std::list ?

Answer 1

Ni l'un ni l'autre. Votre collection a une taille fixe et std::array est suffisante.

La structure de données que vous mettez en œuvre s'appelle un tampon circulaire. Pour l'implémenter, vous créez un tableau et gardez la trace de l'offset du premier élément actuel.

Lorsque vous ajoutez un élément qui pousserait un élément hors du tampon - c'est-à-dire lorsque vous retirez le premier élément - vous incrémentez le décalage.

Pour récupérer des éléments dans le tampon, il faut additionner l'index et le décalage et prendre le modulo de cette somme et de la longueur du tampon.

Answer 2

std::deque est une bien meilleure option. Ou si vous avez évalué std::deque et trouvé ses performances inadéquates pour votre utilisation spécifique, vous pouvez implémenter un tampon circulaire dans un tableau de taille fixe, en stockant l'index du début du tampon. Lors du remplacement d'un élément dans le tampon, vous écraseriez l'élément à l'index de début, et ensuite vous mettriez l'index de début à sa valeur précédente plus un modulo la taille du tampon.

La traversée de liste est très lente, car les éléments de la liste peuvent être dispersés dans la mémoire, et le déplacement de vecteur est en fait étonnamment rapide, car les mouvements de mémoire sur un seul bloc de mémoire sont assez rapides, même s'il s'agit d'un grand bloc.

Le discours Apprivoiser la bête de performance de la conférence Meeting C++ 2015 pourraient vous intéresser.

Answer 3

Si vous pouvez utiliser Boost, essayez boost::tampon circulaire :

C'est une sorte de séquence similaire à std::list o std::deque . Il prend en charge les itérateurs à accès aléatoire, les opérations d'insertion et d'effacement en temps constant au début ou à la fin du tampon et l'interopérabilité avec les algorithmes std.

Il fournit un stockage à capacité fixe : lorsque le tampon est rempli, les nouvelles données sont écrites en commençant par le début du tampon et en écrasant les anciennes données.

// Create a circular buffer with a capacity for 5 integers.
boost::circular_buffer<int> cb(5);

// Insert elements into the buffer.
cb.push_back(3);
cb.push_back(24);
cb.push_back(51);
cb.push_back(62);
cb.push_back(37);

int a = cb[0];  // a == 3
int b = cb[1];  // b == 24
int c = cb[2];  // c == 51

// The buffer is full now, so pushing subsequent
// elements will overwrite the front-most elements.
cb.push_back(8);   // overwrite 3 with 8
cb.push_back(12);  // overwrite 24 with 12

// The buffer now contains 51, 62, 37, 8, 12.

// Elements can be popped from either the front or the back.
cb.pop_back();  // 12 is removed
cb.pop_front(); // 51 is removed

El circular_buffer stocke ses éléments dans une région contiguë de la mémoire, ce qui permet d'accélérer le processus. à temps constant l'insertion, le retrait et l'accès aléatoire des éléments.

---

PS ... ou mettre en œuvre le buffer circulaire directement comme suggéré par Taemyr .

Le Journal de la surcharge #50 - Août 2002 a une belle introduction (par Pete Goodliffe) pour écrire un tampon circulaire robuste de type STL.

Answer 4

Le problème est que O(n) ne parle que du comportement asymptotique lorsque n tend vers l'infini. Si n est petit, les facteurs constants impliqués deviennent significatifs. Le résultat est que pour "les 5 derniers éléments entiers", je serais stupéfait si vector ne battait pas list. Je m'attendrais même à ce que std::vector à battre std::deque .

Pour "les 500 derniers éléments entiers", je m'attendrais toujours à ce que std::vector pour être plus rapide que std::list - mais std::deque gagnerait probablement maintenant. Pour "les 5 derniers millions d'articles lents à copier", std:vector serait le plus lent de tous.

Un tampon en anneau basé sur std::array o std::vector serait probablement être encore plus rapide.

Comme (presque) toujours avec les problèmes de performance :

• encapsuler avec une interface fixe
• écrire le code le plus simple qui puisse implémenter cette interface
• si le profilage montre que vous avez un problème, optimisez (ce qui rendra le code plus compliqué).

En pratique, il suffit d'utiliser un std::deque ou un tampon circulaire préfabriqué si vous en avez un, sera suffisant. (Mais cela ne vaut pas la peine de se donner la peine d'écrire un tampon circulaire, sauf si le profilage indique que vous en avez besoin).

Answer 5

Si vous avez besoin de stocker le dernier N -alors logiquement vous faites une sorte de file d'attente ou un tampon circulaire, std::pile y std::deque sont des implémentations de LIFO y FIFO les files d'attente.

Vous pouvez utiliser boost::tampon circulaire ou implémenter manuellement un simple tampon circulaire :

template<int Capcity>
class cbuffer
{
public:
    cbuffer() : sz(0), p(0){}
    void push_back(int n)
    {
        buf[p++] = n;
        if (sz < Capcity)
            sz++;
        if (p >= Capcity)
            p = 0;
    }
    int size() const
    {
        return sz;
    }
    int operator[](int n) const
    {
        assert(n < sz);
        n = p - sz + n;
        if (n < 0)
            n += Capcity;
        return buf[n];
    }
    int buf[Capcity];
    int sz, p;
};

Utilisation de l'échantillon pour un tampon circulaire de 5 éléments int :

int main()
{
    cbuffer<5> buf;

    // insert random 100 numbers
    for (int i = 0; i < 100; ++i)
        buf.push_back(rand());

    // output to cout contents of the circular buffer
    for (int i = 0; i < buf.size(); ++i)
        cout << buf[i] << ' ';
}

À titre d'information, n'oubliez pas que lorsque vous ne disposez que de 5 éléments, la meilleure solution est celle qui est rapide à mettre en œuvre et qui fonctionne correctement.