# Aiuto per Tieni aggiornato il catalogo (catalogo)

**URL:** <https://forum.olinfo.it/t/aiuto-per-tieni-aggiornato-il-catalogo-catalogo/9388>\
**Category:** Aiuto\
**Created:** [20 Gennaio 2025, 9:05pm UTC](https://forum.olinfo.it/t/aiuto-per-tieni-aggiornato-il-catalogo-catalogo/9388 "2025-01-20T21:05:52Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Kiograh](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/b9e5f3/32.png) [@Kiograh](https://forum.olinfo.it/u/Kiograh)\
**Post date:** [20 Gennaio 2025, 9:05pm UTC](https://forum.olinfo.it/t/aiuto-per-tieni-aggiornato-il-catalogo-catalogo/9388/1 "2025-01-20T21:05:53Z")

</div>

Ciao a tutti, ho bisogno di aiuto per risolvere il problema [Tieni aggiornato il catalogo](https://training.olinfo.it/task/catalogo).

Ciao, il codice penso funzioni, ma è lento (va fuori tempo, Time limit exceeded)  
C’è qualche modo per farlo più efficente? Penso ad un vettore o ad un array dinamico, ma non sono pratico in c++

Ecco il mio codice:

```cpp

#include <list>
std::list<int> libri;

void aggiungi(long long int id) {
    libri.push_front(id);
}

void togli(long long int id) {
    for (auto it = libri.begin(); it != libri.end(); ++it){
        if(*it == id){
            libri.erase(it);
            break;
        }
    }
}

int conta(long long int id) {
    int count = 0;
    for (auto it = libri.begin(); it != libri.end(); ++it){
        if(*it == id){
            count++;
        }
    }
    return count;
}

```

Grazie mille in anticipo!

---

<div class="post-metadata">

**Author:** ![LeoJ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/leoj/32/2737_2.png) [@LeoJ](https://forum.olinfo.it/u/LeoJ)\
**Post date:** [21 Gennaio 2025, 2:43pm UTC](https://forum.olinfo.it/t/aiuto-per-tieni-aggiornato-il-catalogo-catalogo/9388/2 "2025-01-21T14:43:14Z")

</div>

Ciao, la tua soluzione fa TLE perchè utilizzi funzioni come push\_front() e erase() che sono temporalmente molto dispendiose:  
Il push\_front di un elemento davanti a una lista è un’operazione che non crea una nuova posizione 0, ma ti aggiunge una posizione alla fine della lista e shifta tutti gli elementi a destra di uno (lasciando così la prima posizione libera per poter ospitare l’elemento); ha quindi complessità temporale O(N).

L’erase funziona in modo simile, shiftando tutti gli elementi a destra di quello scelto di una posizione verso sinistra (sovrascrivendo quello scelto) e eliminando l’ultima posizione della lista (rimasta vuota).

> **soluzione**
>
> Per questo ti consiglio di ripensare la tua soluzione utilizzando le mappe al posto delle liste (questa soluzione consiste in pochissime righe di codice, se la provi cerca di non complicare troppo la logica).  
> Ti consiglio di associare il numero del libro con il numero di copie (map\<int, int\> mp).

---

<div class="post-metadata">

**Author:** ![Kiograh](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/b9e5f3/32.png) [@Kiograh](https://forum.olinfo.it/u/Kiograh)\
**Post date:** [21 Gennaio 2025, 3:13pm UTC](https://forum.olinfo.it/t/aiuto-per-tieni-aggiornato-il-catalogo-catalogo/9388/3 "2025-01-21T15:13:26Z")

</div>

Grazie mille, effettivamente facendo questo ho sistemato il codice!

Mando il codice se qualcuno volesse una mano:

```cpp
#include <map>
std::map<long long int, int> libri;

void aggiungi(long long int id) {
    libri[id]++;
}

void togli(long long int id) {
    if(libri[id] > 0){
        libri[id]--;
        if(libri[id] == 0){
            libri.erase(id);
        }
    }
}

int conta(long long int id) {
    return libri[id];
}
```

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [21 Gennaio 2025, 3:38pm UTC](https://forum.olinfo.it/t/aiuto-per-tieni-aggiornato-il-catalogo-catalogo/9388/4 "2025-01-21T15:38:29Z")

</div>

Ti segnalo che su una lista concatenata erase e push\_front hanno complessità costante.  
Ovviamente a essere lenta resta la ricerca lineare.

---

<div class="post-metadata">

**Author:** ![LeoJ](https://forum.olinfo.it/user_avatar/forum.olinfo.it/leoj/32/2737_2.png) [@LeoJ](https://forum.olinfo.it/u/LeoJ)\
**Post date:** [21 Gennaio 2025, 4:11pm UTC](https://forum.olinfo.it/t/aiuto-per-tieni-aggiornato-il-catalogo-catalogo/9388/5 "2025-01-21T16:11:21Z")

</div>

Ok, grazie mille, lo terrò a mente, scusate tanto per il mio errore… 😔