IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C++ Discussion :

réaliser un iterateur sur attributs


Sujet :

C++

  1. #1
    Membre éclairé Avatar de BioKore
    Homme Profil pro
    Dresseur d'Alpaga
    Inscrit en
    Septembre 2016
    Messages
    300
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Dresseur d'Alpaga

    Informations forums :
    Inscription : Septembre 2016
    Messages : 300
    Par défaut réaliser un iterateur sur attributs
    Bonjour à tous,

    Je me demande s'il est possible de réaliser des itérateurs directement sur des attributs plutôt que des objets. Par exemple, je sais comment réaliser ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    struct Position { float x; };
    customMap<int, Position> mMap;
    //[...]
     
    for(auto it{ mMap.begin() }; it != mMap.end(); ++it)
    {
    	std::cout << it->second.x << std::endl;
    }
    Pour info, la classe customMap, comme son nom l'indique est une classe perso reprenant globalement le fonctionnement de std::map, et est donc basé sur un tableau de std::pair.
    L’itérateur, dans mon cas actuel, est donc un simple pointeur sur une occurrence de ce tableau de std::pair.
    Cependant, je souhaite pouvoir faire abstraction de l'accès à l'objet, en me permettant de réaliser directement ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    struct Position { float x; };
    customMap<int, Position> mMap;
    //[...]
     
    for(auto it{ mMap.begin() }; it != mMap.end(); ++it)
    {
    	std::cout << it->x << std::endl;
    }
    Vous l'aurez compris, le but est de pouvoir faire quelque chose de plus convivial en évitant à l'utilisateur d'avoir à connaitre le format de la structure sous-jacente, sachant que la classe customMap gère les clés (cf it->first) de manière autonome.

    Après, je parle d'itérateur parce que c'est comme ça que j'imagine la chose à l'heure actuelle, mais peut-être avez-vous une idée plus simple, permettant à l'utilisateur de ne parcourir que les attributs désignés ?

    Merci d'avance.

  2. #2
    Membre Expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2011
    Messages
    760
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2011
    Messages : 760
    Par défaut
    Un itérateur n'est rien de plus qu'un objet qui respecte certaines conditions: la présence et le comportement de tel ou tel membre.

    Pour faire un itérateur custom, il suffit de faire une classe qui respecte une des 5 interfaces du standard et spécialiser std::iterator_traits: https://en.cppreference.com/w/cpp/it.../iterator_tags

  3. #3
    Membre éclairé Avatar de BioKore
    Homme Profil pro
    Dresseur d'Alpaga
    Inscrit en
    Septembre 2016
    Messages
    300
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Dresseur d'Alpaga

    Informations forums :
    Inscription : Septembre 2016
    Messages : 300
    Par défaut
    Merci pour ta réactivité.

    Malheureusement, cela confirme ma crainte ; je vais devoir réaliser une classe tierce...
    Qui plus est, cela semble dépasser mes compétences actuelles...

    Je vais tout de même me renseigner sur ce sujet mais il me semble que je vais devoir trouver une autre solution. Merci pour ce retour.

  4. #4
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    Salut,

    Excuses moi, mais j'ai les yeux qui piquent un peu, et je suis donc pas vraiment tout à fait réactif...

    Mais tu nous explique que tu voudrait créer une classe template customMap. Soit... Mais, peux tu m'expliquer en quoi elle différerait de ... std::map ou de std::unordered_map

    Car, dans bien des cas, il pourrait très facilement te suffire d'utiliser "une collection quelconque" (la mieux adaptée possible à ton besoin, quand même) en interne, en veillant à n'exposer que les services qui te sont réellement utiles, et en les déléguant à une donnée membre

    Je vais essayer de m'expliquer sur ce coup, et pour cela, je vais prendre un exemple tout bête : mettons que j'aie envie d'une map "en lecture seule": on peut ajouter et supprimer des éléments, on ne peut pas modifier la valeur d'une clé.

    Hé bien, ca, aussi surprenant que cela puisse paraître, ca ressemble quand même vachement à un std::set !!

    Nous pourrions donc "nous contenter" d'un code proche de
    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
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    template <typename Key, typename Value>
    class ReadOnlyMap{
         /* pour la facilité, quelque alias de type  privés,*/
         using data_type = std::pair<Key, Value>;
         using collection_type = std::set<data_type, decltype([](data_type const & a, data_type const & b){return a.first <b.first;})>;
    public:
         /* un alias de type public  pour l'itérateur */
         using const_iterator = typename collection_type::const_iterator;
         /* les fonctions constantes qui vont bien */
         const_iterator begin() const{
            return datas_.begin();
        }
        const_iterator end() const{
            return datas_.end();
        }
        size_t size() const{
            return datas_.size();
        }
        bool empty() const{
            return datas_.empty();
        }
        /* les fonctions modifiantes */
        void clear(){
            datas_.clear();
         }
        void insert(Key key, Value value){
            datas_.insert(std::make_pair(key,value));
        }
        void erase(Key key){
            auto it=datas_.find(key);
            assert(it!= datas_.end() && "inexistant key");
            datas_.erase(it);
        }
    private:
        collection_type datas_;
    }
    Et le tour sera joué
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  5. #5
    Membre éclairé Avatar de BioKore
    Homme Profil pro
    Dresseur d'Alpaga
    Inscrit en
    Septembre 2016
    Messages
    300
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Dresseur d'Alpaga

    Informations forums :
    Inscription : Septembre 2016
    Messages : 300
    Par défaut
    Bonsoir, et merci pour cette explication très intéressante.
    Tu mets le doigt sur quelque-chose d'important : je dois apprendre à mieux connaitre les container existant dans la STL et apprendre à les utiliser pleinement avant de tenter de faire les miens.

    J'explique tout de même un peu plus profondément ma situation actuelle. Récemment, je me suis intéressé aux ECS pour la flexibilité qu'un tel système apporte, flexibilité qui me sera bien utile pour mes projets futurs. Étant encore en cours d'apprentissage du C++ (et je pourrais même dire de la programmation / algorithmie de manière générale), et étant libre du temps que je prends à réaliser mes petits projets, je pense qu'il est intéressant, dans ce sens d'apprendre en "imitant" un peu les fonctions proposées par la STL.

    Dans le cas cité précédemment, je pourrais très bien utiliser un std::map, mais je me suis laissé dire que, dans le cadre d'un ECS, si je souhaite traiter/modifier beaucoup d'éléments, il est préférable d'utiliser d'autres types de container plus rapides dans ce cas (par exemple, la fonction de triage m'est absolument inutile, et de mémoire, il n'y a pas de manière "directe" de supprimer un composant de std::map). Même si les gains en terme de performance de mon code sont minimes, voire contraire à ce que je peux attendre, au moins, j'apprends.

    J'ai déjà réalisé un petit ECS sur la base de std::vector ; mais le gain en terme de "convivialité" de la classe est relativement faible par rapport à la réalisation, finalement, d'un container STL-like au complet. Cela a alors été un bon exercice de développement pour moi que de refaire un "CustomMap", collant à la nécessité future que j'en aurais (pas de tri, une fonction remove(), un operator[](), on joue avec les allocator() etc...). J'ai pris beaucoup de plaisir finalement à développer cette classe autour d'un std::pair. Cependant, comme cité ci-dessus, hier encore, il m'a fallu trouver une solution pour éviter les it->second.name_ par exemple, dans le cas où l'on stock une structure.

    Me pencher dès maintenant sur les iterator me semblant plutôt prématuré vis-à-vis de mes compétences actuelle, je me suis fait alors une structure comme ci-dessous pour remplacer le std::pair :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    template<typename Kt>
    struct Entity
    {
    	Kt key_;
    };
     
    template<typename Kt, typename Ct>
    struct cell: public Entity<Kt>, public Ct
    {
    	cell(): cell{0} {}
    	template<typename ...TArgs>
    	cell(Kt const & key, TArgs&&... args): Entity<Kt>{key}, Ct{args...} {}
    };

    Et j'ai enfin le résultat désiré, ou presque, dans le sens où je ne peux stocker que des structures ou des classes et non des types du genre double. Mais au final, je n'en ai pas trop l'utilité d'une part, et d'autre part, je pense qu'il peut être assez facile d'encapsuler automatiquement un double dans une struct avant de le stocker... Je vais réfléchir à ce point d'ailleurs.

    Au final, voici le code complet de mon container Field, qui ne demande qu'à être amélioré au fil du temps et en fonction de mes compétences :

    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
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
     
     
    #pragma once
     
    #include <utility>
    #include <memory>
     
     
    template<typename Kt>
    struct Entity
    {
    	Kt key_;
    };
     
    template<typename Kt, typename Ct>
    struct cell: public Entity<Kt>, public Ct
    {
    	cell(): cell{0} {}
    	template<typename ...TArgs>
    	cell(Kt const & key, TArgs&&... args): Entity<Kt>{key}, Ct{args...} {}
    };
     
    template<typename Kt, typename Ct>
    class Field
    {
    	using field_t 	= Field<Kt, Ct>;
     
    	using data_t 	= cell<Kt, Ct>;
    	using data_p 	= data_t*;
     
    	using cdata_t 	= const data_t;
    	using cdata_p 	= const data_t*;
     
    	using iterator	= data_t*;
    	using const_iterator = const data_t*;
     
    	using component_t 	= Ct;
    	using key_t 	= Kt;
     
    	using Alloc_t	= std::allocator<cell<Kt, Ct> >;
     
     
    private:
    	data_p data_;
    	std::size_t size_;
    	std::size_t capacity_;
     
    public:
    	Field(): data_{Alloc_t().allocate(20)}, size_{0}, capacity_{20}
    	{
     
    	}
     
    	Field(field_t const & cpy): size_{cpy.size_}, capacity_{cpy.capacity_}
    	{
    		std::size_t cpt {0};
    		for(const_iterator it { cpy.cbegin() }; it != cpy.cend(); ++it, ++cpt)
    		{
    			Alloc_t().construct(&data_[cpt], *it);
    		}
    	}
     
    	~Field()
    	{
    		if(!is_empty())
    		{
    			for(iterator it { &data_[0] }; it != &data_[size_]; ++it)
    			{
    				Alloc_t().destroy(it);
    			}
    		}
     
    		Alloc_t().deallocate(data_, capacity_);
    	}
     
    	inline iterator begin()
    	{
    		return &data_[0];
    	}
     
    	inline iterator end()
    	{
    		return &data_[size_];
    	}
     
    	inline const_iterator cbegin() const
    	{
    		return &data_[0];
    	}
     
    	inline const_iterator cend() const
    	{
    		return &data_[size_];
    	}
     
    	inline bool is_empty() const
    	{
    		return (size_ == 0);
    	}
     
    	inline std::size_t const & size()
    	{
    		return size_;
    	}
     
    	bool exist(key_t const & key) const
    	{
    		if(!is_empty())
    		{
    			for(const_iterator it {cbegin()}; it != cend(); ++it)
    			{
    				if(it->key_ == key)
    				{
    					return true;
    				}
    			}
    		}
    		return false;
    	}
     
    	std::size_t offsetOf(key_t const & key) const
    	{
    		if(!is_empty())
    		{
    			std::size_t cpt{0};
    			for(const_iterator it {cbegin()}; it != cend(); ++it, ++cpt)
    			{
    				if(it->key_ == key)
    				{
    					return cpt;
    				}
    			}
    		}
     
    		return -1;
    	}
     
    	field_t & reserve(std::size_t const & cap)
    	{
    		if(cap < capacity_)
    		{
    			return *this;
    		}
     
    		std::size_t cpt{0};
    		data_p buf_{ Alloc_t().allocate(cap) };
    		for(const_iterator it { cbegin() }; it != cend(); ++it, ++cpt)
    		{
    			Alloc_t().construct(&buf_[cpt], *it);
    		}
     
    		std::swap(data_, buf_);
    		for(iterator it { begin() }; it != end(); ++it)
    		{
    			Alloc_t().destroy(it);
    		}
     
    		Alloc_t().deallocate(buf_, capacity_);
    		capacity_ = cap;
     
    		return *this;
    	}
     
    	field_t & resize(std::size_t const & nSize)
    	{
    		if(nSize < size_)
    		{
    			for(iterator it {begin() + (nSize-1)} ; it != end(); ++it)
    			{
    				Alloc_t().destroy(it);
    			}
    			size_ = nSize;
    		}
     
    		return *this;
    	}
     
    	void remove(key_t const & key)
    	{
    		if(exist(key))
    		{
    			iterator itb { begin()+key };
    			iterator ite { end()-1 };
    			Alloc_t().destroy(itb);
    			Alloc_t().construct(itb, *ite);
    			Alloc_t().destroy(ite);
    			--size_;
    		}
    	}
     
    	field_t & push(data_t const & data)
    	{
    		if(!exist(data.key_))
    		{
    			if(++size_ >= capacity_)
    			{
    				reserve(capacity_ * 1.5f);
    			}
     
    			Alloc_t().construct(&data_[size_-1], data);
                            return *this;
    		}
     
    		data_[offsetOf(data.key_)] = data;
     
    		return *this;
    	}
     
    	template<typename ...TArgs>
    	inline field_t & push(key_t const & key, TArgs&&... args)
    	{
    		return push(data_t{key, args...});
    	}
     
    	inline data_t & get(std::size_t const & id)
    	{
    		return data_[id];
    	}
     
    	data_t const & operator[](key_t const & key)
    	{
    		for(iterator it { begin() }; it != end(); ++it)
    		{
    			if(it->key_ == key)
    			{
    				return *it;
    			}
    		}
     
    		if(++size_ >= capacity_)
    		{
    			reserve(capacity_ * 1.5f);
    		}
     
    		Alloc_t().construct(&data_[size_-1], data_t{key});
    		return data_[size_-1];
     
    	}
     
    };
    Pour le moment, à l'utilisation, cette classe est très simple, et se plie plutôt bien à l'utilisation que j'en ai. Il est certain que des personnes plus expérimentés que moi y trouveront des erreurs phénoménales ou des optimisations "magiques" à y apporter, mais bon, j'apprendrais comme ça.

    Enfin, je terminerais sur ce retour d'expérience : j'ai beaucoup appris en réalisant une telle classe, et son fonctionnement m'apporte beaucoup de satisfaction. Avant cela, je n'aurais pas imaginé qu'il puisse être aussi intéressant que de réaliser de telles fonctions (même si cette dernière en contiens rien de transcendant). Cela m'a tellement plu que je compte passer un peu plus de temps à apprendre à implémenter des container de toute sorte. Pourquoi pas, à long terme, au lieu de me brider aux ECS, en parallèle, me faire des container adaptés à des utilisations de type "base de donnée" (avec des fonctions de tri primaire, secondaire, klés multiples etc...).

    Mais on en reviens là à la première phase de ce post : avant de commencer à réinventer la roue, savoir utiliser les roues actuelles correctement, et apprendre toutes les fonctionnalités propres à chaque type de container proposés par la STL.

    Au passage, n'hésitez pas à me faire par de vos remarques concernant le code pondu ci-dessus, j'aimerais bien comprendre comment optimiser ce code.


    Merci !

  6. #6
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    Quelques remarques au passages :

    D'abord, quitte à permettre à la notion d'entité de varier, je la briderait quand même aux seuls types qui vont réellement m'intéresser en termes d'entités, à savoir : les types entiers non signés.

    Cela pourrait se faire somes toutes très facilement avec un static_assert proche de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    template<typename Kt>
    struct Entity
    {
        Entity(Kt key):key_{key}{
     
        }
    	Kt key_;
    };
    Cette restriction étant placée, je choisirais par défaut un type "qui va le mieux" permettant de représenter des indices pour la clé, parce que je compte travailler sur des tableaux indicés.

    Ce type est bien connu, car il s'agit de size_t, qui n'est qu'un alias sur le type entier non signé adapté pour l'architecteur à la représentation des indices .

    Pour pouvoir utiliser une valeur par défaut, il faudra donc que je déclare le paramètre template relatif à la clé en dernier lieu, ce qui me donnera une structure cell proche de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    ttemplate<typename Ct, typename Kt = size_t>
    struct cell: public Entity<Kt>, public Ct
    {
    	cell(): cell{0} {}
    	template<typename ...TArgs>
    	cell(Kt const & key, TArgs&&... args): Entity<Kt>{key}, Ct{args...} {}
    };
    L'étape suivante consistera à créer une table de cell, sans s'inquiéter de la recherche d'un élément particulier.

    Quand les performances priment, la meilleure solution sera sans doute celle qui est le plus amicale avec le système de mise en cache du processeur. Quoi que l'on en dise, le maintien des différentes cells devrait donc se faire de maniière à ce qu'elles soient contigues en mémoire.

    Nous pourrions donc créer une structure table proche de
    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
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    template <typename CT, typename TK = size_t>
    struct table{
     
        /* j'ai besoin de savoir quel est le type de "cell" */
        using cell_t = cell<CT, TK>;
    private:
        /* je vais maintenir en interne un tablea de cell_t */
        using tab_t = std::vector<cell_t>;
    public:
        /* je veux pouvoir utiliser les itérateurs de tab_t */
        using iterator = typename tab_t::iterator;
        using const_iterator = typename tab_t::const_iterator;
        /* je veux pouvoir accéder aux itérateurs constants et non constants sur begin et sur end */
        iterator begin(){
            return items_.begin();
        } 
        iterator end(){
            return items_.end();
        }
        const_iterator begin() const{
            return items_.begin();
        } 
        const_iterator end() const{
            return items_.end();
        }
        /* je veux pouvoir accéder aux cells par leur indice */
        cell_t & operator[](size_t index){
            /* parce que l'utilisateur est un imbécile distrait */
            assert(index < items_.size() && "index out of bound");
            return items_[index];
        }
        /* pour ne pas devoir me répéter */
        cell_t const & operator[](size_t index) const{
            return const_cast<table &>(*this)[index];
        }
        /* je veux pouvoir ajouter un élément */
        void add(TK key, CT value){
            maybeEnlarge();
            items_.emplace_back(cell_t{key, value});
        }
        /* je veux pouvoir retirer un élément à partir de son indice dans le tableau */
        void remove(size_t index){
            /* parce que l'utilisateur est un imbécile distrait */
            assert(index < items_.size() && "index out of bound");
            if(index < items_.size()-1)
                std::swap(items_[index], items_[items_.size()-1]);
            items_.erase(items_.begin()+items_.size()-1);
        }
        /* je veux pouvoir connaitre la taille de mon tabeau */
        size_t size() const{
            return items_.size();
        }
        /* je veux pouvoir connaitre la capacité de mon tableau */
        size_t capacity() const{
            return items_.capacity();
        }
        /* je veux pouvoir savoir si mon tableau est vide */
        bool empty() const{
            return items_.empty();
        }
        /* Lors de la construction, je prévois un "nombre suffisant" d'éléments, que l'on peut définir pour chaque table */
        table(size_t defaultSize = 1000){
            enlarge(defaultSize);
        }
        /* mes tables ne peuvent pas être copiées ni assignées */
        table(table const &) = delete;
        table & operator=(table const &) = delete;
    private:
        /* pour éviter qu'il n'y ait des allocation dynamiques trop fréquentes, je vais
         * je prévois doubler la capacité à chaque fois que la taille est identique à la capacité
         */
        void maybeEnlarge(){
            if(items_.size() == items_.capacity())
                enlarge(items_.size() * 2);
        }
        /* pour pouvoir définir une capacité bien particulière (par exemple, lors de la construction  de la table )*/
        void enlarge(size_t newCapacity){
             /* parce que l'utilisateur est un imbécile distrait */
             assert(newCapacity < items_.capacity() && "You can only enlarge capacity");
             items_.reserve(newCapacity);
        }
        tab_t items_;
    };
    NOTA : Tu n'utilisera sans doute jamais cette table non indexée. Pour être tout à fait honnête, il faudrait faire des benchmarks pour s'assurer qu'elle ne nous fait pas perdre quelques précieux cycles lorsqu'elle sera utilisée comme base d'une table indexée

    Si je l'ai créé ici, c'est surtout pour séparer clairement la notion de table indexée de celle de table non indexée

    Une fois que nous aurons cette table non indexée, nous pourrons l'utiliser pour créer une table indexée. L'idée est que, comme la clé est forcément une valeur entière non signée, nous pouvons créer un tableau qui contient l'ensemble des indices auxquels nous trouverons l'élément de type cell dans table.

    Cela pourrait prendre la forme de
    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
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
     
    /* toujours pareil : la clé est, par défaut, de type size_t */
    template <typename CT, typename KT = size_t>
    class indexed_table{
        /* en interne, nous aurons besoin d'un tableau de clés */
        using key_tab_t = std::vector<KT>;
        /* ainsi qu'une table non indexée */
        using data_table_t = table<CT, KT>;
    public:
        /* en public, nous aurons besoin des itérateurs, constants et non constants */
        using iterator = typename data_table_t::iterator;
        using const_iterator = typename data_table_t::const_iterator;
        /* ainsi que le type de "cell" */
        using cell_t = cell<CT, KT>;
        /* l'interface publique de cette classe est très proche de celle de table
         * une bonne partie de celle-ci ne fait que... lui déléguer le travail
         */
        iterator begin(){
            return datas_.begin();
        } 
        iterator end(){
            return datas_.end();
        }
        const_iterator begin() const{
            return datas_.begin();
        } 
        const_iterator end() const{
            return datas_.end();
        }
        cell_t & operator[](size_t index){
            return datas_[index];
        }
        cell_t const & operator[](size_t index) const{
            return datas_[index];
        }
        size_t size() const{
            return datas_.size();
        }
        /* une autre partie de l'interface doit adapter un tout petit peu son comportement
         */
        void add(KT key, CT && value){
           /* pour être sur de pouvoir maintenir l'index correspondant à key */
           maybeEnlarge(key); 
           /* parce que l'utilisateur est un imbécile distrait */
            assert(!exists(key) && "item already exists");
           datas_.add(key, value);
           indexes_[key]= datas_.size()-1;
        }
        void remove(KT key){
            /* parce que l'utilisateur est un imbécile distrait */
           assert(exists(key) && "inexistant item");
           /* Correction de la logique:
            * 1- récupérer la clé du dernier élément valide
            * 2- récupérer l'indice de l'élément à supprimer
            * 3- intervertir les données de l'élément à supprimer et celle du dernier élément valide
            * 4- intervertir les indices de l'élément à supprimer et de la dernière clé récupérée
            * 5- supprimer le dernier élément valide (qui maintenant celui qu'il faut supprimer
            * 6- invalider l'index de la clé supprimée
            */
           auto toRem = indexOf(key);
           auto lastValidKey = datas_[datas_.size()-1].key;
           std::swap(datas_[toRem], datas_[datas_.size()-1]);
           std::swap(indexes_[key], indexes_[lastValidKey]);
           datas_.erase(datas_.begin()+datas_.size()-1);
           indexes_[key]=invalidIndex();
        }
        /* Enfin, une dernière partie est spécifique à l'utilisation d'une table indexée */
        static constexpr size_t invalidIndex(){
            return std::numeric_limits<KT>::max();
        }
        bool exists(KT key) const{
            if(key >= indexes_.size())
                return false;
             return indexes_[key]!= invalidIndex();
        }
        /* la recherche, dans une forme non constante et dans une forme constante */
        iterator find(KT key){
           auto index = indexOf(key);
           if(index==invalidIndex())
               return datas_.end();
           return datas_.begin()+index;
        }
        const_iterator find(KT key) const{
           auto index = indexOf(key);
           if(index==invalidIndex())
               return datas_.end();
           return datas_.begin()+index;
        }
    private:
        /* on doit s'assurer que indexes_[key] sera toujours un élément valide  */
        void maybeEnlarge(KT key){
            while(key > indexes_.size())
                enlarge(indexes_.size() * 2);
        }
        /* et que tous les indices sont invalides par défaut */
        void enlarge(size_t newSize){
            /* parce que l'utilisateur est un imbécile distrait */
            assert(newSize > indexes_.size() && "you can only enlarge indexes tab");
            indexes_.resize(newSize, invalidIndex());
        }
        /* parce que l'on veut pouvoir retrouver l'indice à partir d'une clé */
        size_t indexOf(KT key) const{
            /* parce que l'utilisateur est un imbécile distrait */
            assert(key < indexes_.size() && "index invalid");
            return indexes_[key];
        }
        data_table_t datas_;
        key_tab_t indexes_;
    };
    Une telle classe va -- très certainement -- utiliser "beaucoup plus de mémoire que nécessaire", ne serait-ce que pour maintenir les indexes d'un nombre de d'entité qui risque d'être bien supérieur à ce que l'on utilise effectivement.

    Mais, son implémentation présente l'énorme avantage de toujours travailler d'une manière "amicale pour le cache", car il n'y a vraiment que lorsque l'on "déborde" de la capacité de indexes_ qu'une réallocation de mémoire est rendue nécessaire .

    C'est, malheureusement, l'un des choix auxquels il est impossible de couper, car il est très difficile de concilier une utilisation de la mémoire la plus faible possible avec un besoin de réallocation "aussi réduit que possible" tout en maintenant une structure amicale pour le cache

    Je pourrais, éventuellement, envisager l'utilisation de std::deque à la place d'utiliser std::vector pour indexes_. Mais je n'ai aucune idée du gain éventuel que cela produirait, ni même s'il y en aurait effectivement un
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  7. #7
    Membre éclairé Avatar de BioKore
    Homme Profil pro
    Dresseur d'Alpaga
    Inscrit en
    Septembre 2016
    Messages
    300
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Dresseur d'Alpaga

    Informations forums :
    Inscription : Septembre 2016
    Messages : 300
    Par défaut
    Bonsoir, et merci pour le retour.

    En fait, j'avais créé un truc du genre grâce à tes conseils sur un précédent post, mais de fil en aiguille je me suis plus intéressé sur le comportement en "interne" des containers (comme std::vector par exemple) et je me suis dit, pourquoi ajouter un niveau d'abstraction avec des vector quand ça ne mange pas beaucoup plus de pain à gérer l'allocation nous-même (dans une certaine mesure).

    Je relèverais tout de même deux points qui m'interpellent dans ton précédent code :
    * Dans mon cas, la clé peut être de n'importe quel type. Par exemple, ce pourrait très bien être un std::string ou tout autre type. Alors certes, dans l'utilisation la plus courante d'un tel système, le besoin sera probablement principalement des entiers non signés, mais j'aime me permettre de pouvoir utiliser un autre type. Mais ok. Si l'on recherche la performance brute, les comparaisons d'entier non signés sont certainement plus rapide que pour des std::string ou tout autre structures / classes.
    * En suite, tu me diras si je me trompe, mais je dirais que la fonction maybeEnlarge() me semblent inutile, dans le sens où std::vector élargit lui-même sa capacité de la même manière.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    if(size >= capacity)
    {
        allocate(size * 2);
    }

    Enfin, même si je serais d'accord avec le fait que le gain est minime ( ou pas ), mais le fait de gérer nous même les allocations en se passant des throw et autres joyeusetés dont je ne me sers jamais (shame on me ?) n'est il pas, de manière absolu, plus performant ?
    De même, ne vaut-il pas mieux limiter le nombre d'appel de fonctions ? Par exemple, de manière absolu, si je me passe des optimisations réalisées par le compilateur, selon ma logique :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    type fonction(type a, type b) { return a + b; }
    //est plus rapide que :
    type add(type a, type b) { return a + b };
    type fonction(type a, type b) { return add(a, b); }
    Car c'est clairement c'est ce qu'il se passe quand on utilise des std::vector plutôt que des pointeurs directement non (attention, je mets ici entièrement de côté l'aspect sécurité / maintenabilité / convivialité etc... et je ne dis pas que c'est ce qu'il faut faire) ? Cela ne ferait-il pas gagner justement, comme tu le dis, quelques précieux cycles si on a 3.000.000 de cellules ?

    En tout cas, merci pour cette présentation intéressante.


    PS: cela n'a rien à voir mais y a t'il une raison à ce que les attributs privés soient déclarés en fin de classe ? J'ai pris l'habitude de le faire en début de classe, mais le plus souvent, je le voit à la fin...

  8. #8
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    Juin 2010
    Messages
    7 147
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : Juin 2010
    Messages : 7 147
    Billets dans le blog
    4
    Par défaut
    Citation Envoyé par BioKore Voir le message
    pourquoi ajouter un niveau d'abstraction avec des vector quand ça ne mange pas beaucoup plus de pain à gérer l'allocation nous-même (dans une certaine mesure).
    Soit la taille est connue à la compilation et tu utilises std::array, soit elle est connue à l'exécution et tu utilises std::vector.
    Dans le premier cas, tu ne gagnes absolument rien à utiliser un tableau C [], dans le second, tu ne gagnes rien à faire un new[] toi-même. L'overhead est négligeable voire carrément nul en utilisant les flags de compile release correct (-o3 etc), et ils t'apportent des checks supplémentaires en debug pour contrer les étourderies.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  9. #9
    Membre éclairé Avatar de BioKore
    Homme Profil pro
    Dresseur d'Alpaga
    Inscrit en
    Septembre 2016
    Messages
    300
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Dresseur d'Alpaga

    Informations forums :
    Inscription : Septembre 2016
    Messages : 300
    Par défaut
    Ok ! merci pour ces précisions.

  10. #10
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    Citation Envoyé par BioKore Voir le message
    Je relèverais tout de même deux points qui m'interpellent dans ton précédent code :
    * Dans mon cas, la clé peut être de n'importe quel type. Par exemple, ce pourrait très bien être un std::string ou tout autre type. Alors certes, dans l'utilisation la plus courante d'un tel système, le besoin sera probablement principalement des entiers non signés, mais j'aime me permettre de pouvoir utiliser un autre type. Mais ok. Si l'on recherche la performance brute, les comparaisons d'entier non signés sont certainement plus rapide que pour des std::string ou tout autre structures / classes.
    Il est tout aussi mauvais de laisser trop de libertés à l'utilisateur de ton code que de ne pas lui en laisser assez.

    En gros, tout ce qui est comparable par égalité et comparable par "plus petit que" pourrait, effectivement, servir de clé, mais...

    Si tu cherches les performances brutes, tu sera forcément obligé de réduire les possibilités de clés, à cause de ce qu'un nombre trop grand de possibilités implique.

    Prenons l'exemple d'une clé sous forme de chaine de caractères:
    • la comparaison en elle-même se fait en temps proportionnel : plus les chaines de caractères sont longues et identiques, plus la comparaison prend du temps
    • Le maintien trié des chaines de caractères nous obligerait presque à utiliser le concept d'arbre binaire (de type RB -tree, ou arbre Rouge Noir), comme std::map (std::set étant disqualifié d'office à cause des restrictions d'accès sur ses éléments) pour lequel
      • la recherche se fait en O(log(N)
      • l'allocation dynamique de chaque noeud n'est vraiment pas des plus sympa pour le cache du processeur
    • Au delà d'une certaine taille (dans certaines implémentations, uniquement), le contenu de la chaine de caractère nécessite une allocation dynamique de la mémoire, ce qui n'est pas très sympa pour le cache du processeur
    • Il sertait possible d'utiliser une "hashmap" (std::unordered_map), mais cela nous oblige alors à calculer une somme de hachage qui sera selon toute vraisemblance ... une valeur entière non signée

    Chacune de ces raisons pourrait se suffire à elle-même pour éviter les types de données "complexes". Le fait d'en avoir trouvé quatre presque sans réfléchir est sans doute significatif
    * En suite, tu me diras si je me trompe, mais je dirais que la fonction maybeEnlarge() me semblent inutile, dans le sens où std::vector élargit lui-même sa capacité de la même manière.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    if(size >= capacity)
    {
        allocate(size * 2);
    }
    Je vais juste te dire que ... c'est à voir...

    Le problème, c'est que la politique d'augmentation de la capacité de std::vector est laissée à l'appréciation de la personne qui en fournit l'implémentation.

    A l'heure actuelle, il **semblerait** que la plupart des implémentations actuelles utilisent une politique d'augmentation de la capacité qui consiste à la doubler à chaque fois que l'on essaye d'ajouter un élément en plus que ce que std::vector peut contenir dans l'espace mémoire qui lui a été alloué.

    Si bien que tu as en partie raison sur ce point : la fonction maybeEnlarge (du moins, au niveau de table) ne fait que rendre explicite un processus qui est de toutes manières pris en charge de manière implicite par le mode de fonctionnement de std::vector.

    Seulement, voilà, j'ai appris "à la dure" à me méfier des certitudes et des a priori pour les choses sur lesquelles je dépend du bon vouloir de quelqu'un d'autre.

    Car, dans le cas présent, chaque personne qui implémente la bibliothèque standard est absolument libre de faire ce qu'il veut, si bien que ce qui est vrai aujourd'hui pourrait très bien devenir faux demain. Et comme c'est "implementation defined", le type qui déciderait de choisir une politique différente n'est même pas obligé de nous dire qu'il a changé cette politique, et encore moins de justifier sa décision.

    Le risque d'une telle décision a beau être très faible, c'est un risque que je ne veux pas prendre. Cette fonction maybeEnlarge a donc pour but de forcer toutes les implémentations possibles et imaginables de la classe std::vector à respecter des règles concernant la politique d'augmentation de la capacité que j'ai fixée moi-même.

    Si ces règles correspondent à la politique actuelle, tant mieux. Si ce n'est pas le cas, c'est quand même toujours tout aussi bien, parce que ce sont mes règles qui prévaudront

    Enfin, même si je serais d'accord avec le fait que le gain est minime ( ou pas ), mais le fait de gérer nous même les allocations en se passant des throw et autres joyeusetés dont je ne me sers jamais (shame on me ?) n'est il pas, de manière absolu, plus performant ?
    Il y a très peu de chances que tu gagnes réellement en performances.

    Par exemple, je viens de parler de la politique d'augmentation de la capacité. qui, à l'heure actuelle, consiste généralement à doubler la capacité à chaque fois que size() > capacity(). Il faut te dire que cette politique n'a pas été choisie sans raison : c'est parce que l'allocation dynamique de la mémoire (et les copies nécessaires lorsque cette réallocation a lieu) est un processus qui prend énormément de temps.

    Et bien sur, la copie (qui est rendue nécessaire du fait de la réallocation de mémoire) est un processus proportionnel, si bien que tu mettra sans doute deux fois plus de temps à copier les donnée si elles sont deux fois plus nombreuses.

    Il fallait donc trouver un "certain équilibre" entre le risque d'utiliser ne serait-ce que pendant un certain temps "beaucoup plus de mémoire que nécessaire" et le besoin de réallouer un espace mémoire de taille supérieure "trop souvent".

    Voilà typiquement le genre de "problème" qui aurait pu te rester totalement inconnu (poses sincèrement la question: y aurais tu pensé si je n'avais pas mis le doigt dessus ), mais auquel tu peux faire confiance à ceux qui implémentent la bibliothèque standard pour qu'ils y aient pensé.

    Et puis, le fait de vouloir gérer les allocation de mémoire "à la main", sans avoir une capsule RAII qui s'assure de la libération correcte de la mémoire lorsqu'elle est rendue nécessaire représente une complexité crasse.

    Le simple fait de décider que ton tableau doit être copiable (et assignable) te donnera des cheveux blancs pour éviter les risques de pointeurs invalides . J'ai expliqué suffisamment souvent sur ce forum (et sur d'autres) les règles à respecter pour éviter les problème que pour pouvoir te le garantir

    De même, ne vaut-il pas mieux limiter le nombre d'appel de fonctions ? Par exemple, de manière absolu, si je me passe des optimisations réalisées par le compilateur, selon ma logique :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    type fonction(type a, type b) { return a + b; }
    //est plus rapide que :
    type add(type a, type b) { return a + b };
    type fonction(type a, type b) { return add(a, b); }
    Car c'est clairement c'est ce qu'il se passe quand on utilise des std::vector plutôt que des pointeurs directement non (attention, je mets ici entièrement de côté l'aspect sécurité / maintenabilité / convivialité etc... et je ne dis pas que c'est ce qu'il faut faire) ? Cela ne ferait-il pas gagner justement, comme tu le dis, quelques précieux cycles si on a 3.000.000 de cellules ?
    Tu peux me croire sur parole, il y a bien d'autres choses que tu peux faire avant de t'inquiéter de ce genre de choses ...

    • La première est de revoir ta logique. Car "tous les chemins mènent au rhum" et que tu peux donc trouver trois, quatre, dix manières différentes (et correctes) d'obtenir un résultat particulier. Mais parmi toutes ces manière de faire, il y en a seulement une qui sera vraiment plus efficace que les autres.
    • La deuxième est d'éviter les copies inutiles de tout ce qui est "plus grand qu'un entier", surtout si cette copie implique l'allocation dynamique de la mémoire
    • la troisième est de revoir ta logique,
    • la quatrième est d'être amical avec le système de cache du processeur dans le maintien des données en mémoire
    • la cinquième est de revoir ta logique
    • la sixième est d'éviter autant que possible les appels systèmes
    • la septième est de revoir ta logique
    • la huitième est d'éviter autant que possible les accès disques et / ou réseau
    • la neuvième est de revoir ta logique

    car, tu as raison sur un point : le processus d'appel d'une fonction est un processus qui prend "un certain temps" au niveau du processeur. D'autant plus que, une fois que la fonction est terminée, il faut retrouver la première instruction qui suit l'appel de la fonction pour pouvoir l'exécuter.

    Mais, pour te donner une vague idée "du temps nécessaire", ces deux étapes correspondent à aux instruction call et ret en assembleur. Et, ensemble, ces deux instructions nécessitaient, selon le cas, soit 17 soit...28 cycles d'horloges sur un 386DX2 (voilà que nous remontons presque trente ans en arrière ).

    Je n'ai trouvé aucune information pertinente sur le nombre de cycles que ces instructions nécessitent sur les processeurs actuels. Mais, comme cela fait plus de dix ans que le moindre processeur tourne au moins à 1,7 Ghz, c'est à dire à 1 7000 000 000 cycles par secondes, tu te rends bien compte qu'il faudrait déjà faire appel à beaucoup de fonctions pour en arriver à ne perdre qu'une seule petite seconde à cause de ce processus

    De plus, c'est un processus qui est -- sous certaines conditions -- évité lorsque l'on fait appel à des fonctions inlines. Or, toutes les fonctions génériques (ou les fonctions membres de classes et de structures génériques) sont... forcément inline.

    Je ne vais pas te dire que tu ne devra jamais prendre ce problème en compte. Mais je peux te garantir que le gain obtenu en évitant un appel de fonction est absolument minimal par rapport à toutes les autres possibilités de gains


    PS: cela n'a rien à voir mais y a t'il une raison à ce que les attributs privés soient déclarés en fin de classe ? J'ai pris l'habitude de le faire en début de classe, mais le plus souvent, je le voit à la fin...
    Oui, il y en a une, qui vaut ce qu'elle vaut ... :

    Comme tout le monde, je présumes que tu lis un texte "de haut en bas". Les premières informations auxquelles tu auras accès sont donc celles qui se trouve "en haut" dans le code.

    Il semble donc "logique" de mettre "en haut dans le code" les informations qui sont les plus pertinentes pour le lecteur de ton code.

    Or, les informations les plus pertinentes pour le lecteur de ton code, ce sont ... les données et les fonctions publiques. Car les données et les fonction privées ne sont que "des détails d'implémentations" que le lecteur de ton code n'a -- à l'extrême limite -- même pas besoin de savoir.

    En plaçant les données et les fonctions publiques en premier, tu permet au lecteur de ton code d'arrêter "plus tôt" sa lecture, tout en ayant malgré tout reçu toutes les informations qui pouvaient l'intéresser

    C'est la raison pour laquelle, en dehors des besoins spécifiques du compilateur (car on ne peut pas utiliser un code comme using iterator = typename table::iterator; si on n'a pas déjà indiqué avant au compilateur que table est un type de donnée ) on va privilégier les données et les fonctions publiques, avant de donner la préférence aux éventuelles fonctions protégées, s'il y en a, et que l'on va terminer par les fonctions et les données privées.
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  11. #11
    Membre éclairé Avatar de BioKore
    Homme Profil pro
    Dresseur d'Alpaga
    Inscrit en
    Septembre 2016
    Messages
    300
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Dresseur d'Alpaga

    Informations forums :
    Inscription : Septembre 2016
    Messages : 300
    Par défaut
    Merci pour ces explications.

    Par contre, je me trouve confronté à deux problématiques. Pour éviter d'avoir à créer des constructeurs (parfois à rallonge) dans les structures que l'on passe en argument, j'utilise des variadic templates (voir méthode add() du code ci-dessous). Comme ça, les structures sont initialisées lors de l'appel. Par contre, je me retrouve du coup avec tout un tas de warning à cause du "narrowing". Par exemple, si je fais add(2, "str", 36) où "str" et 36 sont passés par variadic template, j'ai les warnings... Comme quoi, par exemple, le "str" est un const char (&) [4] alors que l'on attends un string dans la structure, et le 36 est considéré comme un int alors que l'on attends un short unsigned int dans la structure.
    Existe-t-il un moyen de rendre un peu plus propre ces initialisations ?

    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
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
     
     
    template<typename Kt = std::size_t>
    struct Entity
    {
    	Entity(Kt const & id): key_{id} {}
    	Kt key_;
    };
     
    template<typename Ct, typename Kt = std::size_t>
    struct Cell : public Entity<Kt>, public Ct
    {
    	Cell(): Cell{0} {}
     
    	template<typename ...TArgs>
    	Cell(Kt const & id, TArgs&&... args): Entity<Kt>{id}, Ct{args...} {}
    };
     
    template<typename Ct, typename Kt = std::size_t>
    class Field
    {
    	using cell_t = Cell<Ct, Kt>;
     
    private:
     
    	std::vector<Kt> indexes_;
    	std::vector<cell_t> cells_;
     
    	static constexpr std::size_t invalidIndex()
    	{
    		return std::numeric_limits<Kt>::max();
    	}
     
    	void checkCapacity()
    	{
    		if(size()+1 >= capacity())
    		{
    			reserve((size()+1) * 2);
    		}
    	}
     
    	std::size_t indexOf(Kt const & key) const
    	{
    		assert(key < invalidIndex() && "out ranged key !");
    		return indexes_[key];
    	}
     
    public:
     
    	using iterator = typename std::vector<cell_t>::iterator;
    	using const_iterator = typename std::vector<cell_t>::const_iterator;
     
    	inline iterator begin()
    	{
    		return cells_.begin();
    	}
     
    	inline iterator end()
    	{
    		return cells_.end();
    	}
     
    	inline const_iterator cbegin() const
    	{
    		return cells_.cbegin();
    	}
     
    	inline const_iterator cend() const
    	{
    		return cells_.cend();
    	}
     
    	inline std::size_t size() const
    	{
    		return cells_.size();
    	}
     
    	inline std::size_t capacity() const
    	{
    		return cells_.capacity();
    	}
     
    	bool exist(Kt const & key)
    	{
    		return indexes_[key] != invalidIndex();
    	}
     
    	void reserve(std::size_t const & cap)
    	{
    		cells_.reserve(cap);
    	}
     
    	void remove(Kt const & key)
    	{
    		assert(exist(key) && "this key do not exists");
    		auto rid { indexOf(key) };
    		Kt lid { cells_[size()-1].key_ };
    		std::swap(cells_[rid], cells_[size()-1]);
    		std::swap(indexes_[key], indexes_[lid]);
    		cells_.erase(begin() + size()-1);
    		indexes_[key] = invalidIndex();
    	}
     
    	template<typename ...TArgs>
    	void add(Kt const & key, TArgs&&... args)
    	{
    		assert(!exist(key) && "already existing key");
    		checkCapacity();
    		cells_.push_back(cell_t{key, args...});
    		indexes_[key] = size()-1;
    	}
     
    	void add(cell_t const & obj)
    	{
    		assert(!exist(obj.key_) && "already existing key");
    		checkCapacity();
    		cells_.push_back(obj);
    		indexes_[obj.key_] = size()-1;
     
    	}
     
    	cell_t & operator[](Kt const & key)
    	{
    		assert(exist(key) && "this key do not exists");
    		return cells_[indexOf(key)];
    	}
     
    	cell_t const & operator[](Kt const & key) const
    	{
    		assert(exist(key) && "this key do not exists");
    		return cells_[indexOf(key)];
    	}
     
    	Field(std::size_t const & cap=128)
    	{
    		reserve(cap);
    		indexes_.resize(0xFFFF, invalidIndex());
    	}
     
    	~Field()
    	{
    		cells_.clear();
    		indexes_.clear();
    	}
     
    };
    Autre problématique avec les templates, lié avec la première question, les template<typename T = size_t>. Compte tenu du "narrowing" vu ci-dessus, j'ai peur que, finalement, pour un même type, a priori, passé àa la classe / fonction, on se retrouve avec deux instances différentes (une en int, et l'autre en unsigned int par exemple).
    Si je demande ça, c'est parce que j'ai essayé de généralisé le code ci-dessus pour en faire un container multi types, mais j'ai l'impression que, du coup, je suis obligé de toujours spécifier explicitement le type de clé alors que le typename T = size_t me semblais être utile pour éviter ça justement. Une petite idée ?

    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
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
     
    #pragma once
     
    #include "Field.hpp"
     
     
     
    class Table
    {
    private:
     
    	template<typename Ct>
    	static Field<Ct> & getField()
    	{
    		static Field<Ct> field_;
    		return field_;
    	}
     
     
    public:
     
    	template<typename Ct>
    	using iterator = typename Field<Ct>::iterator;
     
    	template<typename Ct>
    	using const_iterator = typename Field<Ct>::const_iterator;
     
    	template<typename Ct>
    	inline iterator<Ct> begin()
    	{
    		return getField<Ct>().begin();
    	}
     
    	template<typename Ct>
    	inline iterator<Ct> end()
    	{
    		return getField<Ct>().end();
    	}
     
    	template<typename Ct>
    	inline const_iterator<Ct> cbegin() const
    	{
    		return getField<Ct>().cbegin();
    	}
     
    	template<typename Ct>
    	inline const_iterator<Ct> cend() const
    	{
    		return getField<Ct>().cend();
    	}
     
     
    	template<typename Ct, typename ...TArgs>
    	void add(std::size_t const key, TArgs&&... args)
    	{
    		getField<Ct>().add(key, args...);
    	}
     
    	template<typename Ct>
    	void add(Cell<Ct> const & obj)
    	{
    		getField<Ct>().add(obj);
    	}
     
    	template<typename Ct>
    	Ct const & get(std::size_t const & key) const
    	{
    		return getField<Ct>()[key];
    	}
    };
    Pour info, le code ci-dessus est pour le moment uniquement à titre d'essai pour les fonctionalités. Je tâcherais de faire un code plus précis par la suite, mais j'ai les deux détails précédents à fignoler...


    Merci d'avance.


    EDIT :
    Pour le second point...... C'est un problème d'esperluette qui m'a induit en erreur !!! Ce genre de galère m'arrivera de moins en moins je pense.... Par contre, pour le coup des narrowing, je suis toujours preneur. Je dois encore trouver une solution !

  12. #12
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    Juin 2010
    Messages
    7 147
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : Juin 2010
    Messages : 7 147
    Billets dans le blog
    4
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  13. #13
    Membre éclairé Avatar de BioKore
    Homme Profil pro
    Dresseur d'Alpaga
    Inscrit en
    Septembre 2016
    Messages
    300
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Dresseur d'Alpaga

    Informations forums :
    Inscription : Septembre 2016
    Messages : 300
    Par défaut
    Ah, merci bousk pour ces liens ! Voilà quelque chose de vraiment nouveau pour moi (en tout cas le fait que l'on puisse en créer, même si l'utilisation semble limitée).

    Les "narrowing" sont corrigés !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [HOOK] Problème(s) pour réaliser le tutoriel sur les HOOKS
    Par Rodrigue dans le forum C++Builder
    Réponses: 13
    Dernier message: 27/07/2016, 18h22
  2. Iterateur sur pointeur de vector
    Par Pragmateek dans le forum SL & STL
    Réponses: 9
    Dernier message: 13/05/2006, 13h50
  3. [ADO.NET]Comment réaliser une relation sur plusieurs champs?
    Par kleomas dans le forum Accès aux données
    Réponses: 3
    Dernier message: 13/03/2006, 12h40
  4. [MySQL] Réaliser une pagination sur un forum
    Par maroweb dans le forum PHP & Base de données
    Réponses: 3
    Dernier message: 25/02/2006, 12h39
  5. [JDOM] Filtre sur attribut
    Par Shiryu44 dans le forum Format d'échange (XML, JSON...)
    Réponses: 6
    Dernier message: 18/04/2005, 15h35

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo