Discussion :

[mazertys17]

Bonjour.

J'ai du mal a bien comprendre comment fonctionne la fonction find_if avec un std::vector. Le but, dans mon cas, étant de trouver un objet contenue dans un vector grâce à un de ses attributs ( un id ) au lieu de l'objet lui même.
En fait, je voudrais simplement faire la même chose qu'avec un std::map/unordered_map etc...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
 
auto it = m_myContainer.find ( id ) ;
 
it -> second.doSomething() ;

Connaissez vous une methode simple et optimisé pour ce faire ? La surcharge d'opérateur est-elle la solution ?

Merci si vous pouvez m'aider

[prgasp77]

Bonjour, tu as un très bon exemple d'usage sur cppreference :

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
// find_if example
#include <iostream>     // std::cout
#include <algorithm>    // std::find_if
#include <vector>       // std::vector
 
bool IsOdd (int i) {
  return ((i%2)==1);
}
 
int main () {
  std::vector<int> myvector;
 
  myvector.push_back(10);
  myvector.push_back(25);
  myvector.push_back(40);
  myvector.push_back(55);
 
  std::vector<int>::iterator it = std::find_if (myvector.begin(), myvector.end(), IsOdd);
  std::cout << "The first odd value is " << *it << '\n';
 
  return 0;
}

Source : http://www.cplusplus.com/reference/algorithm/find_if/

[mazertys17]

Merci pour ta réponse, prgasp77

Dsl, c'est peut être moi, mais je comprends toujours pas. Mon objet contenu dans le vector n'est pas un int, mais un objet, ex :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
 
struct Object 
{
     size_t id ;
     float x , y ;
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
 
    std::vector < Object > model ;
 
    Object m1 ;
    m1.id = 1 ;
    m1.x = 17 ;
    model.push_back( m1 ) ;
    Object m2 ;
    m2.id = 2 ;
    m2.x = 112 ;
    model.push_back( m2 ) ;
    Object m3 ;
    m3.id = 3 ;
    m3.x = 45 ;
    model.push_back( m3 ) ;
 
    std::vector < Object > :: iterator it = std::find_if ( model.begin(), model.end() , ..?? ) ;

[prgasp77]

Prends le temps d'étudier et de comprendre l'exemple, ne cherche pas une solution clé en main. Regarde la fonction IsOdd et comment celle-ci est passée à find_if. Lis la documentation que je t'ai référencée. Toutes les réponses sont là .

Une variante serait effectivement d'utiliser une std::map si tu fais de nombreuses recherches.

[mazertys17]

J'ai beau relire, j'ai toujours du mal

Une variante serait effectivement d'utiliser une std::map si tu fais de nombreuses recherches.

Nombreux son ceux qui m'ont dit que le std::map/unordered_map etc...étaient moins performants et de loin qu'un std::vector, voila pourquoi je tends vers le vector, mais encore un fois je ne parviens pas bien à saisir le concept de find_if, prédicat et foncteur, pourtant indispensable pour mon programme.
Dans mon cas, par ex, devrais-en en arriver à utiliser un std::bind1st, par ex ?
Ou, comme tu sembles le dire, tous les ingrédients son là ?

Merci si vous pouvez m'aider

[prgasp77]

find_if(begin, end, pred) te retourne un itérateur vers le premier élément de la plage [begin, end[ qui vérifie pred. C'est exactement ce que tu veux ; il te reste à écrire le prédicat. Procédons par étape si tu le veux. Écris une fonction libre (ie pas membre d'une classe) qui prenne une référence constante vers un Objet et qui retourne true si et seulement si son id est 42 (en dur pour l'instant). Pousse donc quelques Objets dans v (dont un avec id=42) et vois ce que donne auto it = std::find_if(v.begin(), v.end(), pred42);.


Concernant cette histoire d'optimisation, tu as des questions à te poser :

• As tu des contraintes de performances avérées ?
• Sais-tu dans quel(s) cas la performance des std::vector était supérieure à std::map ?
• Sais-tu dans quelle mesure ?
• As-tu identifié des problèmes de performance sur une première version de ton logiciel ?
• As-tu profilé ton code et identifié l'usage de std::map comme étant la cause de ces ralentissements ?

Si la réponse à une de ces questions est non (juste une), utilise la structure la plus "pratique", quitte à changer ensuite. Je te propose de terminer l'usage de find_if avec des vector comme exercice, mais il est probable que tu ais besoin d'une map-like.

[mazertys17]

Oui, effectivement, cela fonctionne avec une valeur en dure. ( en fait j'avais essayé, mais il me manquait bêtement l'include <algorithm> ).

As tu des contraintes de performances avérées ?

Je pense que oui : mon but est de faire un STR ( stratégie en temps réel ) , en utilisant le concept du ECS ( Entity Component System ).

Sais-tu dans quel(s) cas la performance des std::vector était supérieure à std::map ?
Sais-tu dans quelle mesure ?

Absolument pas...Mes compétences/connaissances ne vont pas jusque là. Je me suis juste fié à ce qu'ont dit des programmeurs plus expérimentés.

As-tu identifié des problèmes de performance sur une première version de ton logiciel ?
As-tu profilé ton code et identifié l'usage de std::map comme étant la cause de ces ralentissements ?

non...
Cependant, étant dans la phase d'élaboration de mon programme, celui ci étant un STR ( donc qui demande tout de même des bonnes performances ), et étant donné qu'il est basé sur le concept ECS, ce qui implique qu'il y aura un grand nombre de composants, donc de find/find_if, je me dis qu'il est bon de prendre partie dès le début de la meilleurs perf à venir.
Mais oui, pour l'instant, std::unordered_map me convient très bien...( mais si j'en viens à changer plus tard pour un vector, ce sera beaucoup de recodage pénible )

[prgasp77]

pour l'instant, std::unordered_map me convient très bien...( mais si j'en viens à changer plus tard pour un vector, ce sera beaucoup de recodage pénible )

Ça ne le devrait pas, les containers de std:: sont cohérents entre eux, avec un brin d'abstraction et une conception réfléchie tu devrais pouvoir passer de l'un à l'autre avec peu de modifications.

Quant à cette histoire de perf vector/map, renseigne toi on trouve beaucoup d'information sur le net. Chacun des deux est un choix qui privilégie la vitesse d'exécution en fonction de l'usage des données que tu as. Typiquement, pour de l'accès non séquentiel et peu d'insertion, la map met une claque au vecteur.

[mazertys17]

Ça ne le devrait pas, les containers de std:: sont cohérents entre eux, avec un brin d'abstraction et une conception réfléchie tu devrais pouvoir passer de l'un à l'autre avec peu de modifications.

Oui, bien sur. Mais mon code est voué à être assez complet, donc ca risque d'être long. Surtout que j'ai pris le parti d'envoyer en références chaque container de composants ( donc des std::unordered_map pour la plupart ) dans mes systems, donc parfois je peu avoir des constructeur comme ca, par ex :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
class Builder
{
public :
 
    Builder( Resources& resources, Data& data ,
             std::unordered_map < size_t , EntityHolder >& entityHolder ,
             std::map < size_t , Graphics >& graphicWord ,
             std::map < size_t , Graphics >& graphicsHud ,
             std::map < size_t , sf::Vector2f >&  position ,
             std::map < size_t , sf::IntRect >& selectionZone ,
             std::unordered_map < size_t , std::vector < sf::Vector2f > >& C_destination ,
             std::unordered_map < size_t , double >&  speed ,
             std::unordered_map < size_t , std::vector <  std::string > >& associateID_Hud );

( Là dessus, je ne sais pas vraiment si c'est le bon concept, personne ne m'a répondu ni favorablement, in négativement, mais c'est encore autre chose ).

Typiquement, pour de l'accès non séquentiel et peu d'insertion, la map met une claque au vecteur.

pour un str, "peu d’insertion", est probablement valable, vu que les objets devront être crées, détruits, probablement de l'ordre d'un par seconde en moyenne, par ex...
En revanche, pour "l'accès non séquentiel", je supose que non : un système doit parcourir en boucle tous le composants tt le temps pour les updates, par ex. ( si j'ai bien saisi le sens de l'accès non séquentiel ? ), ce qui signifierait qu'un vector est du coup plus adapté...

[mazertys17]

Typiquement, pour de l'accès non séquentiel et peu d'insertion, la map met une claque au vecteur.

L'accès non séquentiel, c'est l'utilisation de find, par ex ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
       auto& it = C_myComponent.find( 45 ) ;

[prgasp77]

Surtout que j'ai pris le parti d'envoyer en références chaque container de composants ( donc des std::unordered_map pour la plupart ) dans mes systems

Passe des itérateurs Si tu es libre d'utiliser le compilateur de ton choix, utilise le nouveau GCC 5.1 qui intègre les fonctionnalités C++11/14 et les concepts d'itérateurs .

L'accès non séquentiel, c'est l'utilisation de find, par ex ?

Oui. Si c'est l'opération en lecture que tu fais le plus souvent, autant utiliser une [unordered_]map qui le fera pour toi, en mieux et plus clair. Mais s'il ne s'agit que de 10% des accès en lecture que tu fais, autant effectivement partir sur un autre container. Le mieux étant de mesurer la performance dans ton cas particulier pour prendre le meilleur choix, et pour cela pas d'autre choix que de concevoir son architecture pour qu'elle soit indépendante du container. Voir remarque ci-avant.

[mazertys17]

Merci pour tes conseils

Passe des itérateurs Si tu es libre d'utiliser le compilateur de ton choix, utilise le nouveau GCC 5.1 qui intègre les fonctionnalités C++11/14 et les concepts d'itérateurs .

J'utilise code::block 13.12, avec c++11, donc ca devrait être bon pour les itérateurs, mais je vais tenter d'en savoir plus. Après je reconnais que pour l'instant les refs me conviennent plutôt bien...( c un peut astreignant pour les constructeurs de Systems, mais au final plus sécurisé je crois ).

Oui. Si c'est l'opération en lecture que tu fais le plus souvent, autant utiliser une [unordered_]map qui le fera pour toi, en mieux et plus clair. Mais s'il ne s'agit que de 10% des accès en lecture que tu fais, autant effectivement partir sur un autre container. Le mieux étant de mesurer la performance dans ton cas particulier pour prendre le meilleur choix, et pour cela pas d'autre choix que de concevoir son architecture pour qu'elle soit indépendante du container. Voir remarque ci-avant.

J'en conclu que je peux très bien alterner : utiliser des unordered_map pour certaines choses comme les données qui doivent être accessibles que par certains id et à certains moment, type, life, energie etc...et utiliser des vector pour, par ex, la position, ou d'autres composants qui doivent être utiliser continuellement.

[prgasp77]

J'en conclu que je peux très bien alterner : utiliser des unordered_map pour certaines choses comme les données qui doivent être accessibles que par certains id et à certains moment, type, life, energie etc...et utiliser des vector pour, par ex, la position, ou d'autres composants qui doivent être utiliser continuellement.

Ça a du sens, mais dans la vie de dev de ton produit, puisqu'il n'a pas été précédé par une conception très poussée, tu sera amené à modifier tes containers. Garde ça en tête.