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++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  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

+ 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