buffer tourant

Fabien LE LEZ

30/10/2003 à 10:11

On 30 Oct 2003 00:11:45 -0800, (mourad)
wrote:

il faut utiliser quoi comme container dans la stl pour remplacer mon
tableau et faire la même chose

Ça dépend comment tu mets/retires tes données.
Si tu as le choix des armes, le conteneur de la STL le plus adapté est
deque, puisqu'il est explicitement prévu pour pouvoir ajouter/enlever
des trucs aux deux bouts.
Si pour une raison ou une autre (par exemple, tu remplis ton tableau
via une fonction prévue pour le C), tu as besoin que les éléments
soient contigus, seul vector convient, mais bien sûr il est pas génial
pour enlever les données au début.

--
;-)

Philippe Guglielmetti

30/10/2003 à 10:53

pour aller vite, il faut éviter les allocations/déallocations de mémoire.
Le moyen habituel d'implanter les tampons circulaires est d'utiliser un
vecteur de taille fixe
et deux itérateurs (pointeurs...) qui indiquent le début et la fin des
données.
Voici ma proposition:

class CircBuffer:std::vector<T>
typedef std::vector<T> _Parent;
iterator b,e;
size_t n;
public:
CircBuffer(const size_t res):_Parent(res) {b¾gin(); e¾gin(); n=0;}

size_t size() const {return n;}

reference front() {return *b;}
const_reference front() const {return *b;}
reference back() {return *e;}
const_reference back() const {return *e;}

void push_back(const T& x)
{
++e;
if (e==end()) e¾gin();
if (e==b) throw std::exception("CirBuffer full");
(*e)=x; ++n;
}

T pop_front()
{
if (b==e) throw std::exception("read on empty CirBuffer");
T res(front());
++b; --n;
if (b==end()) b¾gin();
return res;
}
};

--
Philippe Guglielmetti - www.dynabits.com

Philippe Guglielmetti

30/10/2003 à 11:00

class CircBuffer:std::vector<T>
typedef std::vector<T> _Parent;

oups, il maneque évidemment
template <typename T>
au début
--
Philippe Guglielmetti - www.dynabits.com

Patrick Mézard

30/10/2003 à 20:02

Quelques remarques en vrac :

"Philippe Guglielmetti" a écrit dans le message de
news:3fa0df82$0$3659$

pour aller vite, il faut éviter les allocations/déallocations de mémoire.
Le moyen habituel d'implanter les tampons circulaires est d'utiliser un
vecteur de taille fixe
et deux itérateurs (pointeurs...) qui indiquent le début et la fin des
données.
Voici ma proposition:

class CircBuffer:std::vector<T>

Par curiosité, qu'est-ce qui te fait choisir de l'héritage privé plutôt que
de la composition ? Et quitte à faire du template autant faire un adaptateur
de séquence, non ? Il n'y a quasiment aucune contrainte sur le conteneur
sous-jacent.

typedef std::vector<T> _Parent;
iterator b,e;
size_t n;
public:
CircBuffer(const size_t res):_Parent(res) {b¾gin(); e¾gin(); n=0;}

size_t size() const {return n;}

reference front() {return *b;}
const_reference front() const {return *b;}
reference back() {return *e;}
const_reference back() const {return *e;}

void push_back(const T& x)
{
++e;
if (e==end()) e¾gin();
if (e==b) throw std::exception("CirBuffer full");

Si tu lances une exception ici c'est dommage, tu laisses le std::vector dans
un état indéfini (e pointe sur quelquechose qui peut être initialisé ou
pas). Travailler avec une variable temporaire et l'assigner après la copie
de x règle le problème (et offre une "basic guarantee" si le constructeur de
copie/assignation de T peut lancer des exceptions, et une "strong guarantee"
dans le cas contraire).

(*e)=x; ++n;

C'est un peu bizarre comme manière de faire : tu assignes x à *e avoir
l'avoir avancé. Mais si on fait :

CircBuffer<int> buffer(2);
buffer.push_back(1);
assert(buffer.front()==1); //passera pas, b pointe sur un int(0) si ma
mémoire est bonne
assert(buffer.back()==1); //ok

Il faudrait sans doute que b pointe sur le premier élément de la séquence,
et e pointe après le dernier.

}

T pop_front()

C'est peut-être mieux de s'en tenir au prototype STL habituel :

void pop_front()

qui permet dans ce cas là d'avoir une "strong guarantee" indépendamment des
caractéristiques du constructeur de copie de T.

{
if (b==e) throw std::exception("read on empty CirBuffer");
T res(front());
++b; --n;
if (b==end()) b¾gin();
return res;
}
};

Patrick Mézard

Quelques remarques en vrac :

"Philippe Guglielmetti" <news@dynabits.com> a écrit dans le message de
news:3fa0df82$0$3659$5402220f@news.sunrise.ch...

pour aller vite, il faut éviter les allocations/déallocations de mémoire.
Le moyen habituel d'implanter les tampons circulaires est d'utiliser un
vecteur de taille fixe
et deux itérateurs (pointeurs...) qui indiquent le début et la fin des
données.
Voici ma proposition:

class CircBuffer:std::vector<T>

Par curiosité, qu'est-ce qui te fait choisir de l'héritage privé plutôt que
de la composition ? Et quitte à faire du template autant faire un adaptateur
de séquence, non ? Il n'y a quasiment aucune contrainte sur le conteneur
sous-jacent.

typedef std::vector<T> _Parent;
iterator b,e;
size_t n;
public:
CircBuffer(const size_t res):_Parent(res) {b¾gin(); e¾gin(); n=0;}

size_t size() const {return n;}

reference front() {return *b;}
const_reference front() const {return *b;}
reference back() {return *e;}
const_reference back() const {return *e;}

void push_back(const T& x)
{
++e;
if (e==end()) e¾gin();
if (e==b) throw std::exception("CirBuffer full");

Si tu lances une exception ici c'est dommage, tu laisses le std::vector dans
un état indéfini (e pointe sur quelquechose qui peut être initialisé ou
pas). Travailler avec une variable temporaire et l'assigner après la copie
de x règle le problème (et offre une "basic guarantee" si le constructeur de
copie/assignation de T peut lancer des exceptions, et une "strong guarantee"
dans le cas contraire).

(*e)=x; ++n;

C'est un peu bizarre comme manière de faire : tu assignes x à *e avoir
l'avoir avancé. Mais si on fait :

CircBuffer<int> buffer(2);
buffer.push_back(1);
assert(buffer.front()==1); //passera pas, b pointe sur un int(0) si ma
mémoire est bonne
assert(buffer.back()==1); //ok

Il faudrait sans doute que b pointe sur le premier élément de la séquence,
et e pointe après le dernier.

}

T pop_front()

C'est peut-être mieux de s'en tenir au prototype STL habituel :

void pop_front()

qui permet dans ce cas là d'avoir une "strong guarantee" indépendamment des
caractéristiques du constructeur de copie de T.

{
if (b==e) throw std::exception("read on empty CirBuffer");
T res(front());
++b; --n;
if (b==end()) b¾gin();
return res;
}
};

Patrick Mézard

Vous avez filtré cet utilisateur ! Consultez son message

Quelques remarques en vrac :

"Philippe Guglielmetti" a écrit dans le message de
news:3fa0df82$0$3659$

pour aller vite, il faut éviter les allocations/déallocations de mémoire.
Le moyen habituel d'implanter les tampons circulaires est d'utiliser un
vecteur de taille fixe
et deux itérateurs (pointeurs...) qui indiquent le début et la fin des
données.
Voici ma proposition:

class CircBuffer:std::vector<T>

Par curiosité, qu'est-ce qui te fait choisir de l'héritage privé plutôt que
de la composition ? Et quitte à faire du template autant faire un adaptateur
de séquence, non ? Il n'y a quasiment aucune contrainte sur le conteneur
sous-jacent.

typedef std::vector<T> _Parent;
iterator b,e;
size_t n;
public:
CircBuffer(const size_t res):_Parent(res) {b¾gin(); e¾gin(); n=0;}

size_t size() const {return n;}

reference front() {return *b;}
const_reference front() const {return *b;}
reference back() {return *e;}
const_reference back() const {return *e;}

void push_back(const T& x)
{
++e;
if (e==end()) e¾gin();
if (e==b) throw std::exception("CirBuffer full");

Si tu lances une exception ici c'est dommage, tu laisses le std::vector dans
un état indéfini (e pointe sur quelquechose qui peut être initialisé ou
pas). Travailler avec une variable temporaire et l'assigner après la copie
de x règle le problème (et offre une "basic guarantee" si le constructeur de
copie/assignation de T peut lancer des exceptions, et une "strong guarantee"
dans le cas contraire).

(*e)=x; ++n;

C'est un peu bizarre comme manière de faire : tu assignes x à *e avoir
l'avoir avancé. Mais si on fait :

CircBuffer<int> buffer(2);
buffer.push_back(1);
assert(buffer.front()==1); //passera pas, b pointe sur un int(0) si ma
mémoire est bonne
assert(buffer.back()==1); //ok

Il faudrait sans doute que b pointe sur le premier élément de la séquence,
et e pointe après le dernier.

}

T pop_front()

C'est peut-être mieux de s'en tenir au prototype STL habituel :

void pop_front()

qui permet dans ce cas là d'avoir une "strong guarantee" indépendamment des
caractéristiques du constructeur de copie de T.

{
if (b==e) throw std::exception("read on empty CirBuffer");
T res(front());
++b; --n;
if (b==end()) b¾gin();
return res;
}
};

Patrick Mézard

Luc Hermitte

30/10/2003 à 20:38

N'y avait-il pas rope, dans certaines implémentations non standard de la
STL, qui remplissait ce rôle ?

--
Luc Hermitte <hermitte at free.fr>
FAQ de <news:fr.comp.lang.c++> :
<http://www.cmla.ens-cachan.fr/Utilisateurs/dosreis/C++/FAQ/>
Dejanews : <http://groups.google.com/advanced_group_search>

Loïc Joly

30/10/2003 à 21:48

mourad wrote:

Bojnour à tous,
Voilà jusqu'à maintenant j'utilise dans mon application un tableau de
taille connu qui me sert de buffers tourant qui reçoit les données en
temps réel, une fois qu'il est plein à chaque fois qu'on rajoute un
point "ou nombre de points "à la fin, on enlève un point "ou nombre"
au début.
ma question :
il faut utiliser quoi comme container dans la stl pour remplacer mon
tableau et faire la même chose et biensur le plus rapide et
éfficace.

Si tu veux vraiment un buffer tournant (c'est à dire de taille fixe), un
std::vector, voire même un tableau à la C est plutôt approprié (en fait,
dans ce cas, l'idéal et peut-être d'utiliser un truc comme boost::array).

Si maintenant, tu veux gérer une vraie file d'attente, pourquoi ne pas
utiliser directement std::queue ?

Selon ton profil d'utilisation, tu peux baser ta queue sur un deque ou
autre chose (d'ailleur, question : Y a-t-il intérêt à baser un
std::queue sur autre chose qu'un deque ?).

--
Loïc

Christophe de VIENNE

31/10/2003 à 09:21

Loïc Joly wrote:

Selon ton profil d'utilisation, tu peux baser ta queue sur un deque ou
autre chose (d'ailleur, question : Y a-t-il intérêt à baser un
std::queue sur autre chose qu'un deque ?).

Il me semble que c'est plus efficace avec un vector, à cause de
l'algorithme utilisé (monceau si je me souviens bien). J'avais posé la
question il y a quelque temps, ça doit être dans les archives...

A+

Christophe

Christophe de VIENNE

31/10/2003 à 11:42

Christophe de VIENNE wrote:

Loïc Joly wrote:

Selon ton profil d'utilisation, tu peux baser ta queue sur un deque ou
autre chose (d'ailleur, question : Y a-t-il intérêt à baser un
std::queue sur autre chose qu'un deque ?).

Il me semble que c'est plus efficace avec un vector, à cause de
l'algorithme utilisé (monceau si je me souviens bien). J'avais posé la
question il y a quelque temps, ça doit être dans les archives...

Petite correction de mon propos : Ce sont les priority_queue, et non les
queue, qui utilisent monceau/heap. Ma mémoire me joue des tours, je
devrais consulter les archives _avant_ de poster :-/

Voir:
http://groups.google.fr/groups?q=priority_queue+vector+monceau+group:fr.comp.lang.c%2B%2B++group:fr.comp.lang.c%2B%2B+group:fr.comp.lang.c%2B%2B&hl=fr&lr=&ie=UTF-8&group=fr.comp.lang.c%2B%2B&selm=4VZha.3406%249I.231769%40news20.bellglobal.com&rnum=1

A+

Christophe

kanze

03/11/2003 à 16:15

Luc Hermitte wrote in message
news:...

N'y avait-il pas rope, dans certaines implémentations non standard de
la STL, qui remplissait ce rôle ?

Rope, c'est plutôt une variante de std::string. Pas 100% compatible, je
crois, mais fortement optimisé pour des choses comme les insertions à un
endroit arbitraire.

--
James Kanze GABI Software mailto:
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16

buffer tourant

9 réponses

Veuillez sélectionner un problème