Hello,

J'ai hésité à poster ici ou dans algo, j'espère avoir fait le bon choix ^^"

J'ai une méthode qui à une complexité en O(1), mais son temps d'exécution augmente avec la taille des données
La méthode
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
// unsigned int m_size: nombre d'éléments dans le tableau
// T *m_data: tableau de m_sizeMax éléments (m_sizeMax >= m_size)
// unsigned int m_poped: nombres d'éléments sortis et début du tableau (==0 dans mes tests)
 
template <class T>
bool Foo<T>::pop(T& val) {
   if(!m_size) {
      return false;
   }
   val = m_data[m_poped++];
   --m_size;
   return true;
}
Elle est appelée comme ça
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
const unsigned int TEST_REPEAT = 100U;
Foo<int> **foos; //je vous passes l'initialisation ^^
int val;
QueryPerformanceCounter(&start); // vui je bosse sous Windows.
for(unsigned int nbRepeat=0; nbRepeat<TEST_REPEAT; ++nbRepeat) {
   foos[nbRepeat]->pop(val);
}
QueryPerformanceCounter(&end);
Et malgré le fait qu'ici rien ne dépende de la taille du tableau m_data, le temps d'exécution de cette méthode est plus ou moins proportionnel à la taille du tableau.

Si quelqu'un à une explication ou une idée, je prend.