C++

[C++] Priority_queue/Vector

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [C++] Priority_queue/Vector

deather2

Bonjour,
J'ai besoin d'utiliser une priority_queue afin de classer une serie de classe (Ce qui fonctionne sans probleme).
Le sous-container (Ca s'appel comme ca?) utilise est un vector.
Mon probleme est le suivant:
Je souheterai lire le contenu du vector, mais sans le modifier, c'est-a-dire que je ne peux pas utiliser top() puis pop(), qui viderait le vector. Or il ne doit pas etre modifie.
Je dois aussi pouvoir supprimer une entree de mon choix, quelque soit sa position dans le vector.
Il n'existe pas d'iterator ni d'operator[] pour la priority_queue et ca m'embete franchement, de plus je ne suis pas encore tres a l'aise avec les STL.

Est-ce que quelqu'un aurait une idee ?

Merci

Publicité

deather2

Up :cry:

Taz

bisounours-codeur

ben utilise vector, vu que c'est que les opérations dont tu as besoin ne sont pas applicables à un vector. Si c'est l'ordre qui t'intéresse, un set peut t'aider. Voir aussi make_heap et ses amis

deather2

Taz a écrit :

ben utilise vector, vu que c'est que les opérations dont tu as besoin ne sont pas applicables à une priority_queue. Si c'est l'ordre qui t'intéresse, un set peut t'aider. Voir aussi make_heap et ses amis

Petite faute je suppose

Merci pour cette reponse,
En effet l'ordre m'interesse, il s'agit ici de classer une serie de calques (A la maniere photoshop/gimp) qui seront ensuite lu en partant du premier jusqu'au dernier.
L'ordre est donc d'importance cruciale.
J'avais entendu parler de make_heap, je vais me renseigner un peu plus la dessus

Merci !

deather2

Re,
J'ai finalement decide d'implementer ma propre classe base sur les vector.
J'ai cependant un soucis assez etrange a la declaration d'un iterator de vector dans la fonction suivante:

Code :

template <class T>
void CPriorityVector<T>::push(T Obj)
{
std::vector<T>::iterator itData;
for (itData = m_Vec.begin(); itData < m_Vec.end(); itData++)
{
if (Obj < *itData)
{
m_Vec.insert(itData, Obj);
return;
}
}
m_Vec.insert(m_Vec.end(), Obj);
}

Voici l'erreur de G++:

barney% make PriorityVector.o
g++ -Wall -W -ansi -pedantic -g -c -o PriorityVector.o PriorityVector.cpp
PriorityVector.cpp: In member function `void CPriorityVector<T>::push(T)':
PriorityVector.cpp:4: error: syntax error before `;' token
make: *** [PriorityVector.o] Error 1

Sans les options -ansi et -pedantic:

barney% g++ -c PriorityVector.cpp
PriorityVector.cpp: In member function `void CPriorityVector<T>::push(T)':
PriorityVector.cpp:4: warning: `std::vector<T, std::allocator<_CharT>
>::iterator' is implicitly a typename
PriorityVector.cpp:4: warning: implicit typename is deprecated, please see the
documentation for details

P.S: J'ai adapte les numeros de lignes, car tout le .cpp n'est pas copie ici.

Ca compile correctement avec le compilateur C++ de Hewlett-packard.

Ai-je fait quelque chose qui ne soit pas a la norme ?

Merci d'avance!

Message édité par deather2 le 20-06-2005 à 17:11:28

Taz

bisounours-codeur

t'as qu'à lire le topic sur typename. Moi je te conseille d'utiliser les fonctions make_heap et tout ça, et de cacher ça dans une classe si tu veux. Mais évite de réinventer la roue à tout recoder

deather2

Merci pour l'indication typename, ca compile maintenant.
En ce qui concerne la reinvention de la roue, je comprend tout a fait, mais mon code me suffit et je comprend mieux comment ca marche...
Merci a toi en tout cas!

Taz

bisounours-codeur

oui il te suffit mais il est peu efficace. ça te demande très peu de travail !

Code :

template <typename T>
void CPriorityVector<T>::push(const T& Obj)
{
this->m_Vec.push_back(Obj);
std::push_heap(this->m_Vec.begin(), this->m_Vec.end());
}

simple non ?

deather2

Effectivement, vu comme ca !
Je vais essayer d'utiliser ca alors, merci encore pour ton aide c'est sympa

Taz

bisounours-codeur

list bien la documentation, le pop est aussi simple que le push.

Publicité

deather2

Re,
J'ai tout refait en utilisant les heap.
Je me retrouve neamoins confronte au meme probleme que je rencontrais avec ma methode, a savoir les erreures suivantes au link:

Test.o(.text+0x76): In function `main':
: undefined reference to `CPriorityVector<CTest>::push(CTest const& )'
Test.o(.text+0x88): In function `main':
: undefined reference to `CPriorityVector<CTest>::push(CTest const& )'
Test.o(.text+0x9a): In function `main':
: undefined reference to `CPriorityVector<CTest>::push(CTest const& )'
Test.o(.text+0xb4): In function `main':
: undefined reference to `CPriorityVector<CTest>::pop()'

Voici le code source des 3 fichiers:

PriorityVector.hpp:

Code :

#include <vector>
#include <algorithm>
template <typename T>
class CPriorityVector
{
protected:
std::vector<T> m_Vec;
public:
void push(const T& Obj);
T& pop(void);
};

PriorityVector.cpp:

Code :

#include "PriorityVector.hpp"
template <typename T>
void CPriorityVector<T>::push(const T& Obj)
{
this->m_Vec.push_back(Obj);
std::push_heap(this->m_Vec.begin(), this->m_Vec.end());
}
template <typename T>
T& CPriorityVector<T>::pop(void)
{
return std::pop_heap(this->m_Vec.begin(), this->m_Vec.end());
}

Test.cpp:

Code :

#include "PriorityVector.hpp"
#include <iostream>
using namespace std;
class CTest
{
public:
int prio;
CTest(int _prio){prio=_prio;};
~CTest(){};
int operator<(const CTest& x)
{
return x.prio < this->prio;
}
};
int main(void)
{
CPriorityVector<CTest> PrVec;
CTest Test1(1);
CTest Test2(10);
CTest Test3(5);
CTest Result(0);
PrVec.push(Test1);
PrVec.push(Test2);
PrVec.push(Test3);
int i;
for (i = 0; i < 3; i++)
{
Result = PrVec.pop();
cout << Result.prio << endl;
}
}

Quelque chose ne va pas?

Encore merci !!

Message édité par deather2 le 20-06-2005 à 20:31:21

el muchacho

Comfortably Numb

Et ça, ça ne convient pas ?
http://www.sgi.com/tech/stl/priority_queue.html

deather2

Lol tu as lu le premier post ?
Justement j'utilisais ca au debut, mais ca ne me convient pas tout a fait non

Merci quand meme

el muchacho

Comfortably Numb

Oups, désolé.

Pour ton pb, il faut mettre le code de la classe template dans le .hpp, autrement dire coller le code de ton PriorityVector.cpp dans ton .hpp. C'est une restriction des compilos pour les templates (ou plus exactement du linker puisque celui-ci a besoin de classes "réelles", ce que ne sont pas les templates).

Bon, si je dis une connerie, Taz ne manquera pas de la relever...

Message édité par el muchacho le 20-06-2005 à 21:32:23

deather2

Arrfff !! C'etait juste ca
Merci a toi ca roule

Taz

bisounours-codeur

pop(void); n'a aucun sens. Rien, ça s'écrit ()

ensuite ton pop qui renvoie une &, j'y crois pas trop

# template <typename T>
# T& CPriorityVector<T>::pop(void)
# {
# return std::pop_heap(this->m_Vec.begin(), this->m_Vec.end());
# }

surtout que pop_heap renvoie void ...

# int operator<(const CTest& x)
# {
# return x.prio < this->prio;
# }

foutage de gueule

# bool operator<(const CTest& x) const
# {
# return x.prio < this->prio;
# }

# ~CTest(){};

s'il est vide ben l'écris pas !

# CTest(int _prio){prio=_prio;};

beurl

# CTest(int _prio) : prio(_prio) { };

sinon elle est nulle ta notation de foutre des C partout, ça rime à rien.

slash33

Taz a écrit :

sinon elle est nulle ta notation de foutre des C partout, ça rime à rien.

Heu c'est la notation officielle MFC :whistle:

Taz

bisounours-codeur

ça rime à rien quoi. T'as qu'à foutre des v devant toutes les variables, des f devant les fonctions, des n devant les namespace, etc.

slash33

Pourquoi tu n'utilises pas la notation hongroise (je crois que c'est comme ça qu'elle s'appelle) avec des préfixes d'attributs m_sz, m_b, m_n et j'en passe?

Taz

bisounours-codeur

ce qui y a de bien avec la notation hongroise, c'est les gens qui comprennes meme pas ce qu'ils écrivent. genre

string m_csz;

manque de bol, une string n'est pas terminée par un 0 ...

slash33

string m_strString ou CString m_strString
Génial même notation pour C++ et MFC!!

Taz

bisounours-codeur

je comprends rien. Je chie sur MFC.

slash33

Ben heu bon on va en rester là alors

Publicité

FORUM HardWare.fr

Programmation

C++

[C++] Priority_queue/Vector

Sujets relatifs
Récupérer l'heure du système avec un std::vector<int>	Débutant: vector non reconnu
[JAVA]Afficher un vector dans un Jtable	STL - map pair vector - documentation ?
Probleme avec un Vector (élément écrasé lors du .add() )	Différence entre string et vector<char>
trie tableau vector... (very debutant) help me please	[C++] classe Vector pas puissante ?
Classe Vector sou super Waba (pour PDA)	Ajouter des éléments dans un vector.
Plus de sujets relatifs à : [C++] Priority_queue/Vector

Page générée en 0.091 secondes