Pile rapide en C++

Pile rapide en C++ - C++ - Programmation

Marsh Posté le 04-05-2008 à 13:11:20    

Bonjour a tous, j'ai surement une poutre dans l'oeil ce matin, je ne trouve pas le bug :-/
J'essaye d'implémenter une pile rapide (pour remplacer std::stack<T, std::vector<T> > ) ; la taille est fixe, et voila mon code :
 

Code :
  1. template <class T, unsigned int SIZE>
  2. class FastStack
  3. {
  4. public:
  5. FastStack() {  index=data; }
  6. FastStack(const FastStack& s) { *this=s; }
  7. FastStack& operator=(const FastStack& s)
  8. {
  9.  //TODO inutile de copier tout jusqu'a SIZE  
  10.  for(unsigned int i=0;i<SIZE;i++)
  11.   data[i]=s.data[i];
  12.  index=data+(s.index-s.data);
  13.  return *this;
  14. }
  15. inline T& top() const { return *index; }
  16. inline void push(const T& element)
  17. {
  18.  BOOST_ASSERT((index-data)<(SIZE+1));
  19.  *index=element;
  20.  index++;
  21. }
  22. inline void pop()
  23. {
  24.  index--;
  25.  BOOST_ASSERT(index>=data);
  26. }
  27. inline bool empty() const { return(index==data); }
  28. private:
  29. T data[SIZE],*index;
  30. };


 
Vous vous en doutez, je ne posterai pas ici si ca fonctionnait :-) J'utilise ca dans un programme complexe, et des que je remplace std::tack par mon machin, je suis au pays des mauvais resultats...donc, avant de renter plus profondément dans le débuggage, je me demande si j'ai raté quelque chose de vraiment évident ?
 
Merci d'avance

Reply

Marsh Posté le 04-05-2008 à 13:11:20   

Reply

Marsh Posté le 04-05-2008 à 13:23:51    

quitte à utiliser boost, essaye std::stack<T, boost::array<T,N> >

Reply

Marsh Posté le 04-05-2008 à 13:48:15    

Joel F a écrit :

quitte à utiliser boost, essaye std::stack<T, boost::array<T,N> >


 
Merci Joel, je me dis aussi que ce que je fais doit exister quelque part, mais visiblement je ne peux pas utiliser boost::array comme conteneur :/  :

Code :
  1. error:
  2. class "boost::array<gaia::Position::State, 1024Ui64>" has no member "push_back"
  3.                 c.push_back(_Val);
  4.                   ^
  5.           detected during instantiation of "void std::stack<_Ty, _Container>::pu
  6. sh(const _Container::value_type & ) [with _Ty=gaia::Position::State, _Container=b
  7. oost::array<gaia::Position::State, 1024Ui64>]" at line 35 of "./src\makemove.cpp
  8. "


 
D'après la doc de Boost::array : "It doesn't fulfill the requirements of a "sequence" (see Section 23.1.1, [lib.sequence.reqmts] of the C++ Standard)"
 
Donc je reformule mes questions :
1 - Est ce qu'il y a manière de faire ca sans réinventer la roue ?
2 - Ou est le bug s'il y en a un ? (j'aimerai qd meme comprendre ce que je rate)

Reply

Marsh Posté le 04-05-2008 à 14:17:16    

ah mince vrai :/
pour ton bug, tu peut donner qqs exemples simple où ça plante. parce que là à vue d'oeil c'est pas facile :E

Reply

Marsh Posté le 04-05-2008 à 16:58:03    

Bon, j'aurai du regarder du coté des choses simples en premier...  :pfff:  
 

Code :
  1. inline T& top() const { return *index; }


 
a remplacer par
 

Code :
  1. inline T& top() const { return *(index-1); }


 
et c'est réglé..! Mais merci pour la piste boost  :) Je trouve ca étrange q'un conteneur de taille fixe ne soit proposé ni dans la STL ni dans Boost.

Reply

Marsh Posté le 04-05-2008 à 17:36:21    

bah, c'est le role de array. Je pense que c'est par design qu'il n'est pas sequence-compliant.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed